AI for a small RTS

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]

This is more than I could have hoped for, I appreciate it alot. I won't have alot of free time to work on the project except on weekends, and even that time is limited(I live on a military base for college and my only escape is off base liberty), but Im itching to get to work.

Im getting the feeling that this may be too big a project for me to handle, but heck, I learned how to use blender 3d with youtube alone so I might as well bash through this too and learn along the way.

Im basically getting all of this done in python so I was also wondering if anyone new of any good books that dealt with programming of this nature. And of course youtube will no doubt be a valuable life line. When I get updates (you said this would take like a year so they will be few in between) I will post them up.

Any clue about resource management though?

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]

If he has no idea how to write AI, boids, the Hungarian algorithm, influence maps, etc. are SERIOUS overkill. As Paladine stated, just getting a single unit to move in the right direction and engage a target is a lot of work. Start there.

And yes, you are going to run into C[..] because it is what 90% of games are written in. And probably 99% of RTS games. You are really going to have a hard time writing a full RTS AI with Python. Remember, many scripting languages are merely a high level veneer that is laid over the C++ guts of an engine.

I would seriously recommend writing a tank battle game of some sort first. Write something where 2 enemies find, follow, attack, and kill each other. That will keep you busy for a while. After that, it's all variations on a theme.

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

Quote:

Original post by InnocuousFox If he has no idea how to write AI, boids, the Hungarian algorithm, influence maps, etc. are SERIOUS overkill. As Paladine stated, just getting a single unit to move in the right direction and engage a target is a lot of work. Start there.

Yea I think starting with movement and attack commands would be a good place to start for me, then I could probably incorporate the parts of coding dealing with attack into a turret type programming, then eventualy I could go on to group attack AI, like how to tell them to focus on a single enemy at a time as a group or to break up into individual skirmishes. I'll also look into Algorithms.

I appreciate all the tips from everyone, now I have a good idea were to start and what to look for/expect.

Actually Predictor, could you be a little more specific as to how Algorithms could help, or just refer me to another post on Algoritms that might explain a little more in-depth?

Quote:

Original post by MONSTROZZITY Any clue about resource management though?

Define resource management. That's not something the AI has to worry about unless you're writing a computer-opponent level AI. As I mentioned, I wouldn't even start to think about doing this until you have the entire game functional as player v. player. Or at least reasonable functional.

If you're curious, I believe I've made other posts before outlining the architecture I used for the computer-opponent. Just search the site.

And re:Emergent's point about target choosing: definitely forget about anything better than "closest target" until you have the basics stood up. However, after covering the basics you're definitely going to want to spend a lot of time on the target chooser. That's a really huge deal for player perception of the intelligence of the units. An anecdote of interest we spend a full 1.5 person man-month simply designing the algorithm for most intelligent target choosing; it involved tons of spreadsheet battle simulation to derive a the basic mathematical ruleset for our specific game. The result worked pretty wickedly, but was relatively non-intuitive: don't always focus fire, don't always hunt what you're best at killing, etc. Anyway, you need all the basics stood up before working on this anyway because you'll want to test many unit skirmishes of TargetChooserPolicyA versus TargetChooserPolicyB.

Another thing to be aware of is that the actual most correct choice is frequently not the one you want to go with because it may appear "dumber" to the typical user. What's important is user-perception of intelligence, not actual intelligence.

It's also fair to pawn off this micro-management on the user. i.e. units do basic stuff, we want to encourage micro-management by not providing the "best" solution (despite what you typically see on forums, our surveys found that a larger portion of the user base wanted more micro-management not less)

-me

Quote:

Original post by MONSTROZZITY Actually Predictor, could you be a little more specific as to how Algorithms could help, or just refer me to another post on Algoritms that might explain a little more in-depth?

An algorithm is a recipe for how to solve a computer program that can be applied in any language. So basically: these are the logical steps you take to implement so and so a solution. Knowing how to translate an algorithm to working code is an essential part of learning how to program.

Predictor is simply saying that it's probably going to be more productive for you to ask about how to program something in the sense of algorithm than how to program something in the sense of actually syntactically correct Python code. Basically, the type of answer I gave you was a very high-level algorithm of sorts; I didn't write the Python or whatever code, just told you how to logically approach the task. [smile]

-me

Quote:

Original post by Palidine It's also fair to pawn off this micro-management on the user. i.e. units do basic stuff, we want to encourage micro-management by not providing the "best" solution (despite what you typically see on forums, our surveys found that a larger portion of the user base wanted more micro-management not less)

I didn't really intend on making an micro management A.I. when I said that, I really should have asked how to make a resource management system for the player to use. Then again, that doesn't really belong in the A.I. section for the forums.

Thanks for the description of Algorithms Paladine, and I'll look through your other posts to see if you had put anything on resource management.

I was actually wondering whether or not I should buy that book called "Game Programming with Python". I got the book " Beginning Game Development with Python and Pygame: From Novice to Professional". Should I have gotten the book you suggested Predictor?

Quote:

Original post by MONSTROZZITY I didn't really intend on making an micro management A.I. when I said that, I really should have asked how to make a resource management system for the player to use. Then again, that doesn't really belong in the A.I. section for the forums.

Gottit. Yeah it's pretty simple. You just have a central counter for each type of resource, probably just an integer. Production units add to it either on a tick or when the harvester delivers it's payload (depending on what economy type you build). Anything built just subtracts from those same counters. You block actions probably at the UI level based on whether or not the item can be afforded.

It also depends on what type of construction economy you build. You can either go 100% cost up front: which is easy and i'd reccomend starting there. Or you can go pay as you go where each tick you subtract a percentage of the total build cost: this is the C&C model. That's a lot more complicated: basically each factory has a construction queue of items being built (need that anyway), each frame you iterate each factories queue and subtract the cost to build that frame's worth of construction. If the player is out of resources, you don't advance the percent done.

yeah... start with 100% cost up front. like I said you'll need construction queues anyway but then it's a simple timer. layering the pay as you go on top is something you can consider later and, though complicated, should be easy to plug in.

-me