RTS AI

www.gamasutra.com has a number of articles on different topics. I remember the AI of an RTS from a few years ago (Age of Mythology?) being described in detail by its author, for example.

In general, game AI is more of an "agent" problem and less of a "search" problem. You can also google for "planning," which is an interesting research area that's starting to become relevant to game AI.

Typically, you'll need a database of all facts the AI has discovered about the map; a database of rules of the game; and a database of strategies to accomplish various tasks. Agents then query and update this database as the game progresses.

An agent, typically, has some desires ("kill enemy" "stay protected by friends" etc), some beliefs ("enemy is there" "friends are here" "my ground weapons won't work on enemys air units") and from those, formulate a goal ("stay behind friends"). There's lots more to it than that, of course, but that ought to set you looking in the right direction (I hope :-)

gamasutra doesn't seem to have any kind of index, just a huge list of every article in a big list?

Check out AI Wisdom.com

Hope this helps

Eric

So I've revised the A* algorithm now. But there's an issue with this - to plan a route using A* don't you need the whole map to be 'visible' to the search? If you have the concept of exploring the map then what happens when you attempt to send units to a far-off unexplored place?
I suppose my first thought is that A* can be used to find a route to the edge of explored space, and then a simpler approach of just trying to get to the destination by avoiding obstacles could be used. This is more realisitc, butdo players want realism or the ability of units to always find the best route between locations?

One idea I had was that instead of getting too concerned on making unit AI good enough to get around any obstacle (including groups of enemy units deliberately placed to block your path), units can report to you. In Total Annhilation they told you about being under attack; units could also report if they get stuck or lost - this way you could quickly sort them out rather than find out 10min later that your strike force never made to the enemy base. As long as the individual units aren't really dumb I think this could make a big difference.

About the parts of the map you can't see, you just assume they are all crossable, and have all the same level os difficulty to cross.

Then you can either check whenever a unit is moving to a different tile if that tile is crossable, or, you check at regular time intervals if the next n tiles of the path for a given unit are all still crossable. I preffer this last one, because as the unit uncovers more terrain, it will decide to take a different route before actually hiting is face against a rock.

I don't think it is a problem that units know their way around a map; it would be much too frustrating otherwise because units would take years to get where you told them to go. Unless, of course, your maps are generally open.


I have a question for you: How are you going to handle splitting the pathfinding over several frames? I was thinking: if you give the pathfinding routine a set amount of time per frame, people with slower computers would see their units taking longer to find a path.

I haven't done any RTS AI (or any for that matter...), so I don't speak from experience. :P

One idea I've had, that I still haven't really tested, is keeping "pheremone" levels for the different areas of the map. Every ten seconds of so, you'd go through and multiply the pheremone levels by, say, .9 ( so they decay ). For example, a "base" pheremone would be generated periodically by your resource structures, so positive "base" would be your area, negative would be the opponent's. Then perhaps a "damage given" and a "gamage taken" pheremone, which would be adjusted at the obvious time. Then, for example, defensive units would want to be in areas of slightly-positive base pheremone, and more concentrated in "damage given" and "damage taken" areas.

Quote:

Original post by me22 One idea I've had, that I still haven't really tested, is keeping "pheremone" levels for the different areas of the map. Every ten seconds of so, you'd go through and multiply the pheremone levels by, say, .9 ( so they decay ). For example, a "base" pheremone would be generated periodically by your resource structures, so positive "base" would be your area, negative would be the opponent's. Then perhaps a "damage given" and a "gamage taken" pheremone, which would be adjusted at the obvious time. Then, for example, defensive units would want to be in areas of slightly-positive base pheremone, and more concentrated in "damage given" and "damage taken" areas.

This is good in a per-unit basis. (it also comes in handy for deciding where to attack in battles, just pick the weakest spot in there defences to charget through.

Also, the pheremone should be proportional to the strength of the unit. (so your little guys won't go running towards the giganto-people-killer 9000)

You would also need a segmented ai.

What does that mean?

It means that you have one ai for each soldier (really really simple)
One ai for a group.
Then one for a squadran. (so you would have one squadran ordered to protect building X or defend space Y, or attack space/building Z, which then takes all of its groups and decides who will go where, ect.)

You would also have one high level ai, which will figure out the orders for its squadrans.

As well as another one which decides what shal be built. (it. a logistics ai).

From,
Nice coder

Nice Coder: I call that "Heirarchical" AI :P But regardless of name, it'd be a good additional layer. Somewhat logical too, since it's how modern armies work.

( Commander-in-Chief says "take over Europe". Generals say "move into Poland". Lieutenants say "ok, we're going in from these two flanks in 3 days". Sergeants say "ok, use these hills for cover". Privates say "yes, sir!". Same thing works the other way too, just getting abstracted instead of specified. Private says "Taking mortar fire!". Sergeant says "need covering fire". Lieutenant tells different Sergeant to help out, perhaps. )

Disclaimer: I know that's not how responsabilities work in a real army, but it's a reasonable separation for a computer model in an RTS AI. Also, I probably got the ranks in the wrong order or spelling :|

A* for RTS games:
the map should be completely visable to the A* pathfinder. Otherwise you get bizarro behavior that frustrates the user. Typically in an RTS game you can see land features through the shroud, it's only the locations of enemy troops that is shrouded. Either way, you always want the A* to be completely knowledgable of the terrain. The amount of knowledge that you give the computer opponent is a lot more debatable and depends on implementation.

Most RTS AI cheats blatently and gives the AI complete knowledge of the board state (essentially the AI always plays without a shroud). You can trick the user into thinking the AI has a shroud by dumbing down it's moves or just simply by introducing random selection into the process.


AI:
I seperate the AI into 2 basic parts:

1) Unit level AI. things like targeting, defending themselves when attacked, firing weapons, playing animations, guard states, move execution, etc.

2) tactical level AI. things like planning where to attack, where to move troops, how many troops to move to tactical targets, when to attack, when to defend, etc.

To make things easier on you in the programming, it's much easier to have the tactical level AI control troops by essentially simulating user input. That way the unit level AI doesn't need any changing to work on both player and computer controlled sides. By simulation i don't necessarily mean simulating mouse-clicks, etc, but rather just hooking into whatever code gets executed by user input.

If you are starting from scratch tackle the unit level AI long before the tactical level AI. The game should be completely playable by a human before you even start to work on the tactical AI.

-me

Thanks very much for your advice - I like the sound of it. I'm not sure if I'll actually have a shroud - I suppose most players will expect it but I never liked playing that way! One older game let you see the last state of the map under the shroud, including buildings but not units. Letting the AI see that would help it to know where your base is/was while hiding your exact troop strength etc.

I'm still not sure about A* though. If units only know about the explored map they will uncover more of it looking for a path which would make exploring the map early on both easier and more profitable. But as you say, providing a map of the terrain to start with would remove this problem. I remember WarcraftII frequently got units stuck up against obstacles when they got lost, but it seems such behaviour is just not acceptable anymore.

Thanks again.

This thread owns! This is how AI gets implemented in game programming, for real.

[Edited by - Pipo DeClown on July 9, 2005 2:53:32 AM]

Worse comes to worse, you can always backtrack...

Also, remember to weight squares based on the amount of enemies there... (so our scout party isn't going to run straight through the enemy camp before getting killed).

From,
Nice coder

Quote:

Original post by Pipo DeClown This thread owns! This is how AI gets implemented in game programming, for real.

I don't get it. It sounds like sarcasm but about what? Your rating suggests much knowledge, sir - do you have anything less cryptic for this thread?

[smile]

But seriously is RTS game AI still generally poor, relying on perfect knowledge and additional resources? I'd got the impression modern games didn't do that.
What are the recent games which follow the style of warcraft2 and C&C, and how is the AI different in terms of unit AI and tactics?

It sounds from that like the latest game is no different than the original C&C from the days of the 486, but with better graphics then?

Quote:

Original post by Anonymous Poster I'll make a comment on the C&C Generals AI though.

So the C&C generals AI is 100% scripted. That's why the opening attack is always the same. It's almost completely deterministic and thus really crappy. You can actually look at the AI if you open up the Libraries/ folder and open one of the .map files in the Worldbuilder tool. You have to remember though that it's ~5yrs old so hardly represents the pinnacle of RTS AI. (Incedentally the AI for generals was completely new for that iteration of the franchise. It had really good reviews when it was released, it just looks crappy now b/c our expectations are higher.)

At any rate, more modern RTS AIs are a lot less deterministic and the best don't actually cheat at all. The way they are challenging is by exploiting the things that a computer can do better than a player. More or less that is soley micro-management. A human is always going to be better at tactical planning and long-range thinking so you can't win by just making an amazing tactical planner.

Humans however are serial thinkers. We can only think directly about one thing at a time and to multi-task we have to keep switching our attention to different parts of the map. Even the best players can typically manage no more than 3 or so parts of the map. Any more than that and the effectiveness of the forces at those locations is lowered because the player cannot micro-manage them effectively.

IMHO the key then to making a challenging AI opponent then is to keep the player frantic by waging a war on many fronts. Whereas the player has to move the camera around all the time (thus losing focus on local battles) the AI does not and can operate everything simultaneously.

I think that a potentially great strategy for RTS AI is to attack on at least 3 fronts at all times so that the player is forced to keep switching attention between the attacks. I find that it works really well in terms of distracting the player. Basically if you can constantly maintain 2-3 attacks, the player is either going to lose one battle due to lack of attention or they will forget to queue up units at their base and the AI will get a step ahead in production. Essentially you are exploiting the ability of the AI to never lose focus on what it is doing. You also exploit the general lack of low-level unit AI. In most RTS games units that are near other units that are being attacked will not move over to help their buddies out. It's done for game mechanic reasons (you don't want the player's units to run around aggroing on everything b/c it might destroyed some kind of bait tactic and annoy the player). If you can keep the player frantic then you can win.

I think it's also vital that the AI plays clearly towards the win conditions of that map. In most RTS games the win condition is "all enemy buildings destroyed". Thus the AI should only consider buildings to be targets. If the player takes his entire army to the side of the map, the AI should completely ignore them and just rush the base.

Anyway, whatever road you choose to go down the single most important thing for developing a challenging RTS AI is to watch as many replays of RTS battles between people who are the best in the world at the particular game. The most effective winning strategies actually have little to no actual strategy to them. Typically it boils down to rushing and attacking multiple fronts of the enemy. I think the danger in developing an RTS AI is to make up theories of how military battles actually unfold and to make your AI really good at military theory. It's certainly a more appealing and complicated problem to solve but actually has little to do with how people win at RTS games.

-me

C&C:G is from 2003, so unless someone has changed how the math works, thats not 5 years :P

But as for the AI going on multiple fronts and that, it should be limited to mimic what a human can do. Whats the fun in playing against a computer that can keep pumping out troops, and slowly carve your army to bits from every side, when you have no chance to use such an attack style.

Also the part about "How people actually win an RTS", thats just how they win that style. Take a look at Lords of the RealmII (Actually mixed time, turn based empire manament, realtime army battles) The gameplay styles are fairly different, because the game is simply played differently. So if the game play is set up differently for a different and better AI, the players will adapt.

http://www.neoseeker.com/Companies/profiles/Westwood_Studios/ Maybe he meant the original C&C?

The best way to defeat an AI who just sends units at you is probably to do the same. An AI using tactics would require tactics to beat. I don't like the idea of an AI who can fight 8 battles at once - frantically switching camera is not fun to me. Being able to have decent group AI for your units would let them fight multiple fronts by themselves though, leaving you to coordinate which divisions fight where.