In Alden Ridge, I developed a sophisticated multi-layer, multi-agent pathfinding algorithm (so that 300 zombies could solve their path to each human player at once, for example -- though most levels only have 5-20 zombies) that is sort of a simplified-but-more-powerful version of A*. It handles diagonals better, and such, as well. I attached some technical notes about Alden Ridge, that talks about some of the pathfinding at least a bit.
For AI War, I'm basically using a slimmed-down version of that, but one that is tree-based instead of grid-based. Really that's not a whole lot different, I'm using the same methods of valuing and range-checking and such. But with my custom algorithm, it lets me put in weights for things like friendly planets, etc. And it's actually even more complex than that, because it tries to find friendly planets that are nearby, and then move through them, and so forth. It's not a perfect algorithm, particularly when you are in enemy territory trying to get out, but the fundamentals are rock solid. Some of the higher-level decisions it makes needs some tweaking at some point, for those specific cases.
