People always talk about building influence maps and doing pathfinding on them; that seems to be a popular approach, but it only really solves a subset of your problems, so I'm also interested to hear answers (e.g., how is resource allocation managed? Timing? etc.)

heh. The AI in Supreme Commander isn't actually good at all. (Neither in Supreme Commander 2 if you've played it). Units will sit around and die if they can't attack a target instead of trying to dodge the incoming bullets.

The pathfinding isn't that advanced either. Planes for instance use something resembling boids and so do ground units. There's also an optimized pathfinding system. It's funny though if you play it. Large units literally push other smaller units out of the way as they move. (Maybe just implement a rigid body circle to circle system to perfectly enforce unit boundaries? Boids already has a rule to try to preserve spacing but often units can drift into one another in compact groups).

The main thing you want to look up is concepts relating to boids. With only a few lines of code you can do stuff like naive boids implementation.

Finding how to do pathfinding for groups of units should be interesting. I know there are many queue problems people try to solve. (100 units 3 doors type stuff so that units "flow" evenly through given paths).

Start simple. Like stupid-simple. Add complexity later only after you have that working.

So start with forgetting about attempting a skirmish opponent AI. (i.e. the AI that models an opposing player). I've written one, it's super fun but above your head if you're trying to get unit level AI to work. And also pointless working on until you have unit level AI working correctly.

Unit level AI is very straight forward, but there is enough complexity here to keep you busy for a long time.

1) Unit State machine:
Read some tutorials. Foundationally you need onEnter, onUpdate and onExit methods for each state. And you need a state machine to drive the states.

For a basically functional RTS you only need 3 states: Attacking, Idle, Moving
When you get that solid add: Guard (radius tethered, will fight inside that radius), Attack-Move (moving but will break off move to fight and then resume moving)
More advanced will depend on your game but: SpecialPowers, Leaping, Repairing, MoraleBroken, Pinned, etc...

Idle: piece of cake, do nothing. this is your default state
Attacking: relies on other sub-systems - target chooser, weapon system. Most simply: Fire weapon at target.
Moving: relies on other sub-systems - pathfinder. pretty simple, just keep following the current path

2) Target Chooser: this can be either per unit or global. Global is more efficient but probably harder to conceptualize. At it's simplest level this is a simple range check and choose closest enemy; more advanced will tweak the target choosing heuristic to include things like health, effectiveness of weapon, etc. This is not part of the state machine but is a system which the states must be able to query: if (targetChooser->hasTarget()) gotoAttackState()

3) Weapon System: you don't want the AI to drive the weapon system. You want the AI to set a flag on the weapon like bCanFire=true. The weapon runs it's own state machine: reloading, ready, firing. Again not part of the AI state machine but the state machine must be able to control it: mWeapon->startFiring(), mWeapon->stopFiring()

4) Pathfinder: simple A* pathfinding to start. This will quickly become a performance problem so you'll eventually want to move to hierarchical A* (most likely...there are other options but this is relatively standard). Again, outside the state machine but state machine must access it: mPathfinder->getPath(). Instigation of path planning will happen when a unit receives an order; keep the order system abstracted from input so that later on a high level AI can give units orders.

5) Command system. A simple message queue per unit, probably; also maybe not a queue but just an interface for setNetCommand(). You simply add commands to the queue or call the interface, and the state machine controller or states themselves process the commands. Example Commands: MOVE_TO, ATTACK. Each command should have a payload (additional data): ex. in the case of MOVE_TO the payload is a destination, in the case of ATTACK the payload is a target. It's important that you have this so that commands can be abstracted from player input; this will allow you to write higher level AI later

Otherwise I would recommend either a safe-pointer for targets or an id. Units die all the time and you don't want to have to directly manage making sure that no one is holding a bad pointer.

After that stuff get very complicated very quickly. For instance you'll eventually want a group-level AI which will coordinate unit positioning so you get nice spreading out of units like you see in the new SC2 videos. It can also coordinate units for focus-firing and generally help to micro-mananage units if you want to move in that direction. There are tons of other things like allowing certain units to path over certain terrain that other units cannot. Differences between large and small unit pathfinding can also add fun.

This should keep you busy for a year or so. Come back when you want to start tackling player-level AI [smile]

-me

[Edited by - Palidine on February 25, 2010 5:40:44 PM]

Quote:Original post by Palidine
2) Target Chooser: this can be either per unit or global. Global is more efficient but probably harder to conceptualize. At it's simplest level this is a simple range check and choose closest enemy; more advanced will tweak the target choosing heuristic to include things like health, effectiveness of weapon, etc. This is not part of the state machine but is a system which the states must be able to query: if (targetChooser->hasTarget()) gotoAttackState()

Although I don't want to detract from Paladine's very important message of "start simple," and I also haven't implemented a target chooser myself, reading this does make me think immediately of an optimal assignment algorithm called the Hungarian algorithm. At first glance, it doesn't quite solve the problem at hand, but I think that on closer inspection it does, so long as for the purposes of the algorithm you (1) create multiple copies of tasks (so that multiple units can contribute to the same task (e.g., killing a particular unit)), and (2) add "null units" so that the number of workers equals the number of tasks.

That said, this kind of optimality may be more than is necessary. And by "may be," I think I mean, "almost certainly is, if you're honest." But it's still at least academically interesting, and perhaps something to consider eventually as "icing on the cake" for said subsystem.

Quote:
4) Pathfinder: simple A* pathfinding to start. This will quickly become a performance problem so you'll eventually want to move to hierarchical A* (most likely...there are other options but this is relatively standard). Again, outside the state machine but state machine must access it: mPathfinder->getPath(). Instigation of path planning will happen when a unit receives an order; keep the order system abstracted from input so that later on a high level AI can give units orders.

On this subject, an alternative to grid-based hierarchical A* which is becoming increasingly appealing to me is Voronoi roadmap-based approaches. What's nice about the Voronoi graph is that it (1) is small (and so, quickly searched), and (2) feels like a much more natural representation for the connectivity of your level. And although it's often presented as applying to polygonal worlds, there are in fact some very simple algorithms for computing Voronoi diagrams on grids.

Quote:Original post by xx:
The main thing you want to look up is concepts relating to boids. With only a few lines of code you can do stuff like naive boids implementation.

Boids are great, but if you want reliable behavior with guarantees you may want to use an inter-agent-potential-based approach rather than Reynold's original, which is more ad-hoc. It's still more-or-less the same idea, but a little more principled: You define a potential function over the inter-agent "distances" (which may actually include things like orientation), differentiate it, and then have the agents do whatever moves down the gradient.

[Edited by - Emergent on February 26, 2010 1:37:25 AM]

Quote:Original post by MONSTROZZITY
Orignally I wanted to try to make an RTS game kind of like supreme commander but I reallized that I have no real idea as to go about the AI creation proccess.

Im using Python because Im using Blender 3d which Im very comfortable modeling with and because it has a built in game engine. It seems that most of the posts on this site are about C, C++, and C#. Blender 3d doesn't support them though. Even if you don't know how to go about it in Python then any tips for my consideration would be way more than appreciated.

I imagine that you would get more help with algorithms, here, than with Python specifically. Even a quick search on Bing reveals several resources for game programming in Python, such as:

Python Game Programming Challenge
"Game Programming With Python"
Pygame


-Will Dwinnell
Data Mining in MATLAB