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