I'm currently searching for details regarding what sort of algorithms certain RTS games have in dealing with certain aspects of their program. For example, with the RTS game Starcraft, what kind of pathfinding algorithm is used? What of its AI component? These things aren't really disclosed normally in the games' websites, so I'm having a hard time. This may be something too hard to ask, but should anyone be able to share these, I would very much appreciate it. By the way, no need for code snippets and what not, just the names of the algorithms and where it's used. For those who are wondering, me and three/six others are working on a game for a thesis, and were needing comparisons of other games for the submission of a requirement.

Quote:

Original post by Starchaser For example, with the RTS game Starcraft, what kind of pathfinding algorithm is used? What of its AI component?

Pathfinding is nearly always some version of the A* algorithm. The 'AI component' (which includes pathfinding, by the way) is not so clean-cut and will be a mix of ideas, in pretty much every game. You are probably looking at several of the following: finite state machines, scripts, fuzzy logic, hierarchical command structures, influence maps. rules-based systems, etc etc. I believe Starcraft was heavily based around scripts and rules, but I don't know for certain.

I think you should learn about the different pathfinding algorithms.
A* would be the most relevant (and also the most widely used), but it can be improved in some games by mixing it with another like Dijestra or Depth-First (I know the first is spelled wrong, please correct me). A* will always do the task (in a tilebased enviroment), but it might not be the best nor the fastet algorithm for your game. I know that Age of Empires I and II used a modified version (that's quite normal) of the A* together with another algoritm. If you've ever played AoE 2 you'll know that the pathfinding is quite good in some cases and stinks in other (especially when the units has to travel long distances).

The really good thing about the AoE AI is that it doesn't cheat, like the ones in StarCraft. That, on the other hand, means that it's not nearly as "intelligent" as you would expect it to be in some situations, simply because it requires to many clock ticks (with that times hardware of course).

You should also read the postmortems of the games on gamasutra.com, you'll learn alot, I know I did. There's also one for the AoE 2 expansion.

A* star 'works' .. its slow but it damn works. The problem is just in RTS is that you have many units going going to use it an alot of times the units close to the first unit is going to go almost same path. If you want scalability you need implement levels in you pathfinding, call it caching or 'strategy' pathfinder or whatever, the point is, you have alot of units and a-star cause low performance if used brute force on all units, but small tricks can optimize it alot (eg. by assign almost same both when you move groups of units). Mark terrano (Aoe2) from ensemble studio wrote somewhere they used 30% of cpu cycles on AI and pathfinding (excluding running the simulation) .. and thats a very optimized game.

But even when you have found yoru algorithm, dont ever forget whom your users are and how they play. they often dont move very long in rts and they dont really need defacto 'correct' pathfinding, but its all upto how you make you features .. is there rivers or other than can make blind ends or is it like tiberian sun where there is almost only

Pathfinding usually ends up with A* being quoted, but I don't know about the practice. There are some graph traversal algorithms, but if you're poking at a thesis, you know the names.

Carmack's Reverse?

Vector math for aim leading for bots, guided weapons, and interface reticles?

Threat assessment in strategy games?

Chess move algorithms?