BrainBlitz.org

And here I thought I was doing good because I had basic pathfinding implemented. Pffft. Turns out, that is only half of the story. The other half is unit coordination.

A* works very nicely, as long as the walkable/unwalkable cell states are at least somewhat permanently so. But what happens when you have, say, two units, getting all up in each-other’s grill? With A*, you find the path, then set the units on their way. Along the way, one may invalidate the path of the other. You can, of course, be performing collision detection en-route, and repath a unit if it encounters another. This is what I did in the demo on this page. The problem is, this direct approach opens a huge can of complicated worms. The system as a whole is so dynamic, that trying to handle all of the possible “race conditions” and circular results inevitably produces quite the code quagmire.

Here’s the actual demo. Click to create a tower “character.” Control-click to reinitialize the whole thing.

It won’t take much playing with it to realize that it is very, very broken. Characters will freeze as their states become invalid. Characters will be retarded. Sometimes the whole darn thing will freeze. (No code this time… it’s simply a nightmare, what-with all of my experimenting.)

 Not that you can’t make an acceptable algorithm using the straight-forward approach that I have here for simple applications, but I’m aiming a little higher for my final “product,” and most likely will take a step backwards in progress and work on more elegant solutions.

Here’s a rough outline of what’s happening in my code:

• Unit starts in sleep mode, searching within its site range for entities from a different (“enemy”) group.
• If enemy unit is found, build a list of all open cells adjacent to enemy. 
• Pick closest enemy-adjacent cell that is open, and run A*.
• Check for collision with other units on frame.
• If collision, modify A* map with other character’s cell as unwalkable, recalc path, and revert A* map to prior state.

So, where do the issues come in?

One example is when the characters go into a collision state, and may respond in a way that keeps them in a collision state (i.e. they both move to the same cell to avoid the collision). This often results in “stuttering,” where the solution to the collision puts them into a collision for which the solution puts them back into the original collision. This could be handled in a couple of ways.

1. Have the first unit (#1) to detect the collision send a message to the other unit (#2) to ignore it (#1).
2. …sorry, I forgot what the other idea was while writing the first. I’m tired.

I’ll spend a little more time seeing if I can get an acceptable algorithm with the straight forward method. Otherwise…

I’ve got my reading cut out for me.
Amit’s Notes about Path-Finding – the pathfinding Bible? (Look at the rest of the site too)
Gamasutra: Coordinated Unit Movement - by Dave Pottinger (developed AI for Age Of Empires)
Gamasutra: Implementing Coordinated Movement - also by Dave

Also relevant:
AS3 data structures library (requires CS4, I believe) – at the moment I’m only using singly and doubly linked lists, but as I take a step back, I’ll probably end up using a lot more from it.
Cute lil’ character sprites by Karura