AI Decisions

I've noticed a few issues with my current setup.  First off, path-finding with distance approximation creates a similar path to the Manhattan Distance Heuristic.  In other words, the fastest way from point A to point B is more like an L.  First you move at a 45 degree angle in the general direction of the target until you are parallel to it either horizontally or vertically, then head straight for it.  This works, and it works fast, but I really want my AI to move in straighter lines.  So, unless I change my mind, back to the original heuristic.

Next, taking a snapshot of all state info for the AI every few seconds takes alot of time and memory.  I knew this would come, but I wanted to focus on it later.  Unfortunately, it kills the performance already, when there are only 8 nodes on screen.  I've decided to merely keep track of changes to the world and sync them with the AI.  The data transferred to the AI will be things like 'segment id 2's length changed to 150' or 'node id 7 removed'.  Of course, it won't be passing text, but you get the idea.  It will pass minimal information and it will be up to the AI to do all the processing involved to update its current snapshot.  This means alot less processing on the main thread and alot less information passed to the AI.  The AI will have to do a little more thinking, but that's okay.  As long as the player's experience is smooth, I'm happy.

I've been thinking about how the AI will plan his routes as well.  I've been entertaining the idea of using genetic algorithms again.  I'm pretty sure they'll be too slow, but I want to give them a try.  I may as well try everything, you know?  What if I'm surprised or it leads me to a better idea?  I may even end up doing a hybrid of multiple different techniques.

Today, however, I focused on trying to get one path built from the enemy to the player.  I wanted to use actual pathing rather than a fixed route that only works on one map.  In other words, I want the AI to be just as effective as my last one on any map I create.  Now, remember that it's only building one line of nodes and segments, it doesn't defend itself, and it only tries to attack the segment connecting the player's parent nodes, nothing else.  It will still be stupid, but once I get it working, I'll be a step farther in route planning.

Ultimately, I want the AI to be able to make up its own mind about the map's layout.  I don't want there to be any map-specific scripting that aids the AI's strategy and tactics.  I want to be able to drop it into any map at all and have it still be just as effective as any other.  What attracts me to genetic algorithms is that I don't have to think up every strategy beforehand.  It can come up with them itself.  It still has its limits (besides inefficiency), but as long as I can tell it what's a good move and what's a bad one, it can come up with more creative strategies than I ever could.

I may create the genetic algorithm alongside any others I work on and see which turns out best.  Initially, I'm pretty sure the genetic algorithm will be the slowest, but that's because I've never actually built one and there are so many different ways to do it.  I'll have to experiment and try to optimize it until I either decide its fast enough or it will never be fast enough.  I'm crossing my fingers for the former.  I'd love to create an emergent AI.

Anyway, thanks for reading!

clevceo

Math Optimizations

I've been avoiding optimization for a while now.  I used to think optimization was the secret to life, but then I listened to a lecture by Jonathan Blow where he said that it's rarely necessary when we think it is, and it takes forever to do, so it's usually a waste of time.  However, after reading through Christopher Park's (developer behind AI War: Fleet Command) blog, I've decided to optimize just a bit before I move forward.  Because Sever's AI will work similarly to a standard RTS, speed is of the essence.  I need the AI to think fast and not lag too far behind the human player.  Also, these optimizations should keep things synced between clients in a multiplayer game.

First off, I changed the primary data type that I was using for all of the math.  I was using the float datatype because that's the default type used in MonoGame.  If I was more educated, I could probably tell you why.  But alas, I'm not.  Anyway, Christopher Park had an issue with syncing and created a truly fixed-point struct that apparently did the trick.  Rather than waiting until I have syncing issues, I decided I'd start early and do the same.  It took a bit to get it working correctly because I had to go through every single stinking class in the game and change Vector2s to my new VectorF struct and floats to the new FInt struct.  I also made some modifications to his version of FInt to make it do what I wanted it to do.

If you want to know more about fixed point math, look here.

I got it working, and I haven't noticed any performance improvements, mostly because as an early prototype, it rarely goes under 60fps anyway, which is actually probably too high.  I'll probably lower it for the sake of processing power.  60fps is more important for shooters and stuff like that.  RTSs can sacrifice a bit to make room for non-graphical processing.  Anyway, I trust that using fixed point math will help out in future versions, whether I notice it or not.

Also, he talked about distance approximations.  Square roots are slow, and finding the distance between two points requires a square root.  Finding the distance between a point and a line (a common operation in Sever) requires 4 square roots!  When drawing graphics, you need exact numbers, but when doing collision testing, you can first use an approximation, which is enough to tell if the points are close enough to do the real distance calculation.  In the end, that's more math, but 90% of the time it doesn't get past the approximation, so it really saves time when doing collision testing against a hundred objects, most of which are far away and don't need precise calculations to know that they don't collide.

If you want to learn more about distance approximation, look here.

While I'm not sure how much I'll notice a difference in performance as a result of the switch to fixed point math, I'm pretty sure that the distance approximation is going to make a big difference in both collision testing and path-finding.  In both, there's usually alot of wasted distance calculations, so this should soften the blow to performance quite a bit.

That's all that I've done since my last post, besides play against the AI over and over.  Hopefully my next post will be more interesting.  Thanks for reading!

clevceo

My First Gameplay Demo Ever

That's right, I have a gameplay demo for you.  Yes, that also means that it's somewhat playable.  The AI fights back.  It's really stupid, and it only works on the one map that I've made, but it does the trick.  It's actually about 4 lines of code.  However, it proves that my AI setup works, all except for the actual thinking part.  I'll probably make plenty of modifications in the future, but the foundation is done and tested.  This is a pretty big milestone for me.  I know I've said that before, but this takes the cake.  I've never had an AI to play against, and it happens to kill me almost every time I play.  He's easy to kill, but he takes me out before I can finish him off.  Here's the video:

It still looks like the screenshots, except the color of the opponent.  Sorry his routes are a bit hard to see.  I would change it, but I've already uploaded the video.  At least I made him a different color.  Otherwise, it would look really confusing.

Anyway, you'll notice that he keeps attacking even after I've split his parent nodes, which destroys the system in a chain reaction.  Watch it twice, the first time watch me take him out, and then watch him attack me.  I make the first strike (he doesn't defend himself, so it's not quite fair), and I keep trying to stop him from attacking me, but he gets me in the end.

This AI follows a decision tree with two branches, and it always builds from the last node created (starting with the bottom-left node).  If the AI controls 4 nodes, build 350 pixels to the left.  Otherwise, build up 200 pixels.  Like I said, it's stupid, but it works great for this video.  It really looks like it's trying to beat me.

Let me know what you think.  I'm really proud of this milestone.  Thanks for reading!

clevceo

AI Progress

This is a really short update.  I've done some good work, but it was all on one thing and it can be explained fairly quickly.

I've made a little progress on AI.  It doesn't work yet, but I've begun setting it up based on what I've read.  There's now a thread that runs for each AI player and does all of its thinking.  So that I don't have to worry about making things thread safe (which is both messy and inefficient), I take a snapshot of everything in play and send it to the AI to process.  This is also necessary because I can't have the world data change while the AI is looking at it.  The snapshot isn't 100% complete.  It's only what the AI will need to do its thing.  That way, I can save a little time and memory.

Before I did that part though, I made all player actions command-based.  This cleans up the player interaction quite a bit.  I'm liking the changes.

It's all a bit of a mess at the moment, but hopefully it will come together soon so I can build a simple AI to play against.

Thanks for reading!

clevceo

Articles

I'm at a point in Sever where I can't just keep building without stopping and making a plan.  I mean, there are a few things I could do, but I'd basically just be killing time before I move to the important stuff.  This is the wall I hit in projects that usually stops my progress short.  However, I imagine I'll hit this wall with every project I ever work on.  The difference between the successful projects and the failures will be whether I chose to climb over the wall or not.

It's a bit scary thinking about that.  I've done it too many times.  Anyway, rather than giving up just yet, I'm choosing to do a little research that will hopefully give me what I need to move forward.  In particular, I'm reading up on RTS networking and AI.  Sever isn't nearly your typical RTS, so I'll have to pick through the AI articles for anything that might apply, but the networking methods should be very relevant.

I didn't realize that networking for an RTS might work differently from any other multiplayer game.  However, it makes perfect sense once I think about it.  Basically, the game runs in steps, and each player gets to decide what moves to make, and all moves from all players are executed at once, and then on to the next step.  Many games communicate states of units back and forth, while RTS's typically communicate unit commands.

Because there are so many units, it would take up too much bandwidth to send the unit states back and forth for so many units.  Because they only communicate each players' commands to each other, each client computer has to run his own version of the simulation and each has to be in sync.  This is the only practical way to network a game with so much going on.

With that in mind, I'll have to rethink how I've been planning to run Sever.  I'll have to make some changes to make sure it runs in steps.  I'll also have to have all player input be sent to the engine in the form of commands.  I think I'd like that anyway.  It would simplify player interaction and how I build the AI.  Here's an article about this sort of thing from the developers of Age of Empires.

About AI, I read a few articles by the developer of AI War: Fleet Command.  I've never played the game myself, but I found the articles fascinating and I'm tempted to try the game out.  I don't know how much will really apply to Sever, but it's given me some ideas to try.  Basically, his intent with the AI was to avoid traditional decision trees.  Instead, he gives each individual unit a little bit of intelligence and has it make its decisions based on what the units around it are doing.  He did this in hopes that the AI would have "emergent" behavior, as he calls it.  In other words, he didn't want all tactics and tricks that the AI uses to be pre-programmed.  He wanted them to think for themselves and do things even the programmer hadn't thought of.

In order to do this, each unit needs to do some number crunching about what's going on around it.  This particular developer uses LINQ to run queries in order for each unit to make a decision.  I've never used LINQ, but I have been reading up on it a bit.  I write SQL every day, so it shouldn't be too bad.  Also, this method apparently requires less code to write than the typical humongous decision tree.

Again, I'm not sure if I'll use his method or not, but I think I might at least try.  I won't be able to make every node autonomous because of how crucial every move is in comparison to a typical RTS where a unit can simply turn-around and go the other way if he makes a mistake.  It will really have to be almost 100% hive-mind, but I think I can try out some of the principles he explains.

At the moment, networking might be the easier path to take.  I'll start by making the game run in steps with commands, and then I'll try to develop some simple networking code, at least enough to be able to connect by LAN.  I really think it will be important for me to actually play the game and see what strategies work and what doesn't before I can really build an AI.  I understand the mechanics of the game and I have some general ideas about what strategies might work, but when it comes down to it, I know even more strategies for typical RTS's that I'm terrible at.  So it's pretty important that I actually play the game (alot).  Once I get the networking working, maybe I'll recruit somebody to help me test it.

I'm hoping in the testing that I'll have more epiphanies.  I really need epiphanies right now.  I've also been listening to lectures by Jonathan Blow, the creator of Braid (one of the best games, highly recommended).  He says a good way to make a game is to build it around a good idea.  For example, Braid's good idea is time manipulation.  Throughout the game are time puzzles, which evolve as you progress.  A more famous example is Portal.  Portal has (or had, until Portal 2 added more) one cool mechanic that the entire game revolves around.  Rather than trying to come up with as many cool ideas as they possibly could, like most games, they just explored that one concept fully and cut out all the extra content that didn't contribute.  And the results were great.

I guess what I'm saying is that I think I have a good idea, but I haven't explored it.  I think there's so much more than networking and AI that will be put in this game.  However, I think they're the minimum.  Once I have at least enough of both to be able to play the game, I want to start experimenting.  I want to try everything out and see what sticks.  I want to try building puzzles in the game.  I want to build a typical RTS map and duke it out with another player.  I want to add different kinds of nodes with different properties and see how it affects gameplay.  I don't think it will turn out like Braid or Portal, but I want to at least use their method of building a pure game and see if I can do the same for mine.

I know that wasn't much of an update, but it's what's on my mind at the moment.  Thanks for reading!

clevceo

AI

Since I got the path-finding working, I've been thinking about how the AI will make decisions in the game.  I've thought about measuring each nearby path-node based on its offensive and defensive value, and then testing all the different possible moves it could make and picking the best one.  It could be done, but it wouldn't be very efficient.

Today, I had an idea that might work.  The AI will have different goals and each goal will be given a priority based on the current situation.  For example, If the enemy is close to the AI's base, defense is given priority.  If the enemy base is found, and the AI's base is safe, then offense is given priority.  If the enemy has not yet been found, then scouting is given priority.  The AI cycles through each goal in order of priority and determines if it wants to make another move toward that goal.

Scouting mode will look for nearby fog of war and build nodes near it to clear it out.  Offensive mode will do one of two things: if the enemy is close, attack it; if the enemy is far away, close in on it.  Lastly, defensive mode will either fortify the base or fend off attackers.

Whenever a goal is examined, it determines whether another move needs to be made or whether it should wait for something to be completed first (a segment to finish building, for example).  In order to determine what move to make, it needs to assess how good its current state is, and what can be done to improve it.

Today, I've been focusing on how the defense assessment could work.  For the most part, a decent defense just means that there are nodes on the outer edge of the base with segments to spare.  In order to see how the current defense is, I need to determine which nodes are on the outside of the base.  This is tricky, but I think I came up with a solution.  Here are a couple screenshots.  I'll explain them afterwards.

First off, I'll find the left-most node, draw a horizontal line to the left and rotate it counter-clockwise until it hits another node.  Then, I'll duplicate that line and rotate counter-clockwise again from the second node to the third node.  This will repeat until the entire system is outlined.  These are the nodes I'll test.  If I find too much space without a node that can attack, I'll try to fix that problem.

You'll notice that there's a big pink object in the middle of the base.  Obviously, I won't need to place defenses around it.  That would be a waste.  So I'll probably let the line hit these objects as well and rotate around them until I hit another node.  Of course, anywhere the line touches the object will be considered well-defended.

Also, this outline will envelope all scouting and offensive routes as well, so I'll have to find a way to section it off.  Sectioning off the scouting routes might be easy.  The segment length requited to build a scout node will be longer than the line, so the line will pass straight through the segment and hit the next node in line.  Offensive routes however, will need to be separated somehow.  I'll cross that bridge when I get there.

Thanks for reading!

clevceo

Path-finding

The last two days have been spent trying to get the path-finding to work.  It finally does, but it took longer than it should have.  First off, I worked off of examples from a book called Programming Game AI by Example by Mat Buckland.  Let me start by saying that it's a great book.  It has helped out a ton.  However, all the examples are in c++, and while he shows most of the code, some of it you have to get off of the included cd, which doesn't come with the kindle version.

Honestly, the hardest part was getting a working indexed priority queue to use in the algorithm.  The rest wasn't too bad.  I ended up using the A* algorithm, which he says is the best one if you have a specific destination in mind.  If you don't, it's easy enough to switch it to Dijkstra.

The problem with the indexed priority queue is that .NET doesn't have one built in for me to use, and all the code for it was on the cd.  I searched around the internet, but it was difficult to find one in C# that did what I needed.  I tried to translate one from Java, but I don't remember Java as well as I thought I did.  Finally, I found a good one, though it went a bit overkill and I had to simplify it a little bit so I could understand it.  I had to modify it a little and build a wrapper around it to get it to work with my path-finder, but it works now and that's all that matters.

I don't know if the algorithm is 100% optimized or not, but I'll figure that out later.  Right now, I'm just happy that it's working at all.

For testing purposes, I just had a path traced from the top-left corner of the map to the cursor.  That's why it looks like a pointless path.  Also, if you're not familiar with path-finding, you might be wondering why there are so many paths branching off into nowhere.  Because computers are computers and not humans, they can't instantly see paths from point A to point B like we can.  Consequently, it has to test tons of different paths until it runs into the destination.  In most path-finding algorithms, there would be many more paths going the wrong direction, but this algorithm eventually narrows the search at the end.  The only reason why it's not narrow at first is because of the big obstacle in the way.

Next, I'll probably build an extremely minimal AI that will just build a straight line toward the player's routes.  Even though it's so simple and should be so easy to beat, this is still particularly exciting because it will be the first AI I've ever built for Sever.  For the first time, there will be an opponent to play against.

Eventually, when the AI is more fleshed out, it probably won't have specific destinations it wants to find.  Instead, each node will have a score based on how safe a node would be if built there, how close it is to where the AI thinks the enemy base is, whether or not it will clear out fog of war, etc.  Also, I'll have to do this for all nodes with empty connections to spare, which will use more processing power, so I'll probably have to make it run over several update cycles rather than busting it all out at once and lowering the frame-rate.

Thanks for reading!

clevceo

Node Types, AI

There's not much new to show in a screenshot, unless you want to see a bunch of debugging graphics that will normally be hidden.  But I won't bother you with that.  This will be a short post anyway.  Just popping in to share a little progress update.

There are now a set of different types of nodes that you can build, and the way you choose which to build is by the distance you place between it and the node it leads from.  In other words, there isn't some menu that allows you to choose the node type.  You can't press a number key to select which node type you want to build.  If you want to build a certain kind of node, you have to drag a certain distance away from the node you're dragging from.

That might sound unusual, and it's very possible that I'll give this idea up for a different one later on.  However, I'm sticking with it for now.  Here's why:

Previously, you right-clicked to cycle through the different types of nodes.  This isn't terrible relative to the ways you traditionally choose weapons in an FPS.  In fact, I may have mapped number keys to different kinds as well later on.  Many gamers may have felt at home with that method.  However, I had some qualms with it.  First off, having to right-click three times or reach up and press a number key every time you wanted to build a certain node felt tedious and forced.  Also, while right-clicking is easy and the player wouldn't easily forget it, but nobody would ever know about it without first being told.  From day one, I've wanted this game to feel so intuitive that the player could just start playing without any tutorial.  Of course, this may have been wishful thinking and it may be impossible, but I don't think it's such a bad idea to get as close as I can.  All in all, it just didn't feel right.

For a long time, I thought I'd be stuck with that method because there really wasn't anything better that I could think of.  However, one day I thought about the selection by distance method, and it played around in my head for a bit before I really set on it.  At first, I only thought about how much more intuitive it would make things, but I also started to think about how it would affect the rest of the gameplay.  For one, it would limit the way the player builds his/her routes.  The minimum distance wouldn't change anything because there was already a minimum distance for different types of nodes, but the maximum distance was a new limit that would drastically change playing-style.

At first, this scared me, but after a while it grew on me.  One of the main reasons I grew to like it was because it made each node type more unique in its use.  The distance became the cost of building the node.  Honestly, it just felt natural.  It fit.  It also simplifies AI a bit (which I've been thinking about quite alot lately).

Anyway, that's my current choice for node selection.  On to path-finding.

I'm starting on the AI.  I hit a point point where I could go one of three ways: add more features, start on networking, or start on AI.  There are some features I want to add, but I can easily add them after networking and AI.  That way, networking and AI will initially be simpler to code and I can just build on top of them later.  Networking would be really cool to do, but AI's been on my mind and I really don't know anybody that could help me test the networking at the moment.  I can test the AI myself no problem.

At the moment, I'm developing a path-finding system.  I've never actually done path-finding before.  I've read up on it, but I never got around to trying it out.  As I've been reading up on it, however, I've been thinking through how I could use it in Sever.  Normally, path-finding gets an agent from one point on a map to another.  It doesn't build a route system.  Because there isn't really a precedent for this kind of game, I thought it was a lost cause, but now ideas are starting to pour into my head about how I could implement it.  I'm really excited to get it working and have an opponent to play against.

So far, a map of possible paths is created and it takes all geometric obstacles into account.  However, it isn't yet able to do anything with it.  I'm still reading up on all the different algorithms, trying to determine which one is best.

I'm also reading up on genetic algorithms and neural networks, seeing if there's any way to use them in Sever.  Don't worry, I'm not just trying to find excuses to use them, but I think it's a good idea to explore them just in case.  They may just turn out to be the best thing that ever happened to Sever, but I'll never know if I don't look.

I guess this turned out to be a bit longer than planned.  My bad.  Anyway, thanks for reading!

clevceo

Geometric Obstacles, Fog of War, Collision Detection, etc.

I've been working my tail off on Sever.  Here's a screenshot.  Beware the ugly placeholder graphics!

There are a couple things to notice in this screenshot.  First off, the big ugly pink thing in the middle.  That is a geometric obstacle (geo for short).  It's called that because I'm unsure what else to call it.  I had geos in previous iterations of sever, but they were only for collision detection.  You couldn't actually see them.  Because of that, you had to attach them to sprites.  I didn't know how to display the shape itself at the time.  This time, however, I bit the bullet and researched how to do it.  Of course, they're going to look better than that because that's just a thrown-together shape with placeholder tiles over it.  Also, I'll probably add nice borders to them so they don't have those hard edges.

The reason why I didn't know how to do it before is because you can't draw them the usual way that MonoGame and XNA draw 2D graphics.  You actually have to draw it the same way you would 3D graphics, which I had never done.  This means you have to draw them in triangles.  As you can see, it's not a triangle, so I had to write code to take the shape and split it up in triangles just so I could display it.  It was difficult and buggy at first, but I did it and you can see it working in the screenshot.  I must say I'm proud of myself.

Next is the fog of war.  You can see two different shades at the moment.  The darker one will be black in the future, but since it's in development, I want to be able to see what's going on behind it.  Anyway, only nodes can see.  The route segments are blind.  The lighter fog you see is what a node I built earlier saw before I destroyed it.  So far, the fog is just cosmetic.  The game will still try to draw everything that's behind it.  I'll write that code soon.

Next, you'll notice the red circle.  This was in the last screenshot, but I don't know if I explained it before, but that's the currently selected node.  The red line and white circle leading from it are where my cursor is dragging a new node.

Lastly, you'll notice the dark circles around each of the nodes in the upper-left corner.  This is the required spacing between each node and every other node owned by the same player.  This way, players can't build them so close to each other.  However they can build them as close as they want to enemy nodes as long as they don't touch.

Oh, if you haven't figured it out yet, collision detection actually works now.

Anyway, that's my progress, or at least the interesting part.  I'll keep posting as it progresses.

Thanks for reading!

clevceo

It's Happening Again

Wow, I can't believe I'm writing this post.  I haven't touched Sever in so long.  For a long time, any efforts on any of my projects were short-lived, but this year I've put alot of work into both Idea and Sever.  You can look at my Idea blog to see what's going on there.  I'm a bit stumped on a few things, so I thought I'd give Sever another shot.  It's looking a ton more promising than it did in the past.

I just wrote the collision testing math today.  I haven't applied it to everything quite yet, but the hard part is over.  So far, there are only nodes and segments, no geography of any kind.  However, I've set up a robust system for handling the route systems and the people inside them.  It's simpler and better than anything I've written in the past.

I'm reusing bits and pieces of my previous code, like certain formulas I used.  However, there is one hefty bit of code I took and polished up.  It was a grid system.  Rather than collision testing every single object on the map, the map is split up into a grid, and each object is stored in its respective square.  When collision testing, only the relevant squares are tested.  That way, alot of processing time is saved.  It's a complex system, and I'm so glad I already had most of it written.

Things are working pretty well so far.  There are still some basic things I need to code before I really start moving forward.  I want to start on the network code fairly early on.  I also want to code some basic AI just for testing and fun.  I figure the earlier I start on these things, the earlier I'll find out I need to rewrite something.  It should save trouble later.  I made that mistake in the past, and I won't again.

The graphics are terrible, but that's placeholder graphics for you.

In the past, I was using Microsoft XNA for the graphics, but Microsoft has dropped support for XNA.  I tried looking around for an alternative and found MonoGame.  So far, it's good.  It doesn't do "everything" that XNA did,but it hopefully it will with future updates.  Plus, it's cross-platform, unlike XNA.  All that matters to me, though, is that it's doing what I need it to right now.

Anyway, thought I'd write an update.  Thanks for reading!

clevceo