Path-Finding, AI Plans

Like I said in my last post, the AI doesn't path-find very well.  It will head directly towards the player's location without creating a path around obstacles.  Well, it will eventually go around them, but it will go as far as it can before it has to start moving around it.  This works well enough on a map with little or no obstacles, but every other map gives the AI quite a bit of trouble.  Like I said, it eventually makes it around, but it's messy and not very intelligent.  Also, it's not very fun to play against because its offense is slow and it fills up the area around its home base with loads and loads of routes that you have to tediously make your way through.  Better path-finding would mean the AI would build its routes with more purpose and strategy rather than trial and error.

I've been brainstorming what would be the fastest way to do it.  I've known for a while now the the AI will calculate where it thinks its enemy is and send all of its routes in that direction.  The trick is doing the path-finding for each route quickly and efficiently.  I originally thought I'd just do an A* path search from each node one after another, but I figured that would quickly slow things down when the AI's routes get bigger.  Then I had an idea.  I could use Dijkstra's algorithm, starting at the end point and run it until it finds all of the nodes.  I can save alot of time and resources that way, sharing the processing time between all of the nodes at the same time.

The one issue with this method that I can see is that if there's a node that cannot reach the destination, the algorithm will keep running until it has tested every point on the map, which really really slows things down.  My solution is to run it until it finds one of the nodes, and then set a time limit for the next one.  For example, after one is found, it will only test 100 more before it ends unless it finds another in that time, in which case the time limit will reset back to 100 again.  That way, it will stop when it thinks that it has found all of the nodes that are actually reachable.

I'm excited to get this working.  It will really open up alot more possibilities with maps.  After that, I want to give the AI a state machine.  At the moment, it is always in attack mode.  Eventually, I want it to have modes like "Scouting", "Offensive", "Defensive", etc.  I want there to be routes that only attack you when they are attacked first, or routes that attack on sight, or routes that only attack if you're close, but stop when you back off.

I was hoping that at this point I could really take off with designing levels, but with a messy AI, it's just not very fun yet.  I like to think that once the AI starts acting more intelligently and is more flexible, the levels will start popping out of their own accord.  However, after the AI is beefed up a bit, I'll probably pull all of my time into integrating scripting into the engine.  It's something I've never done before, so I don't know the best practices.  I'll have to do some research.

Anyway, it's moving forward slowly but surely.  I can't wait for all of this "under the hood" stuff to be behind me so I can really start experimenting with the actual game.

Thanks for reading!
clevceo