Sign in to follow this  
d000hg

RTS AI

Recommended Posts

d000hg    1199
For the 4E4 contest, I'm going to do an RTS entry. While the graphics and general game stuff shouldn't raise any suprises, I've got the problem that I've never really done any AI programming before. I've a little knowledge from some courses at university about different searches like depth/breadth - first, A* etc but I'm looking for some articles/tutorials specific to a RTS world. I had a look at GD's article lists but can anyone recommend the best resources they have used? I've got as far as realising that there are at least 2 distinct AI 'levels' for an RTS game. In a broad sense there's the game logic AI - equivalent to me deciding what to build and where, when and who to attack with what etc - and the unit AI to do with avoiding obstacles, responding to attacks and so forth. Is this the kind of architecture others have/would use, or would there be many separate levels of AI behaviour? Thanks.

Share this post


Link to post
Share on other sites
hplus0603    11347
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 :-)

Share this post


Link to post
Share on other sites
d000hg    1199
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.

Share this post


Link to post
Share on other sites
xor    516
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.

Share this post


Link to post
Share on other sites
Daniel Miller    218
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

Share this post


Link to post
Share on other sites
me22    212
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.

Share this post


Link to post
Share on other sites
Nice Coder    366
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

Share this post


Link to post
Share on other sites
me22    212
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 :|

Share this post


Link to post
Share on other sites
Palidine    1315
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

Share this post


Link to post
Share on other sites
d000hg    1199
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.

Share this post


Link to post
Share on other sites
Nice Coder    366
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

Share this post


Link to post
Share on other sites
d000hg    1199
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?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
RTS AI?

Well this is pretty much how the 'professionals' do it:


void rts_game_ai()
{
cheat_a_bit_before_game_starts(resources += 10000000, hugebase++);
send_multiple_weak_and_pointless_attacks();
act_like_youre_actually_gathering_resources_not_cheating_to_get_them();
cheat_some_more();
lose_building_to_enemy(OH_NOES);
cheat_more(CHEAT_INFINITE_RESOURCES | CHEAT_FAST_BUILD);

while(still_alive() == true)
{
send_multiple_weak_units_to_defend();
}

die();
}

Share this post


Link to post
Share on other sites
d000hg    1199
[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?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Hmm, C&C Generals and Age of Mythology are the newest RTS games I own. Can't say a lot about AoM because I didn't play it a lot.


I'll make a comment on the C&C Generals AI though. This is just roughly what I can remember from playing recently.

I have heard that the Generals AI does cheat for resources and such but I can't say I've really took any notice, you generally don't when simply playing a game. I might fire up a quick skirmish and take control of all resource gathering methods to see how it goes though. I'll let you know if I actually do do this.

I haven't played any skirmishes against the AI yet, I've been playing through the campaigns on the hardest difficulty (though with 2 missions left on the 3rd campaign I'm finding it quite easy). The AI does seem to be constantly sending the same types of units in the same sized groups constantly over and over. Every now and again it might just send in a couple different units but again these are the same every time (usually "artillery" style units, long range units meant for taking out structures).

So lets take a look at an example scenario. I'm settled in with a base and defences.
1) AI sends it's first attack consisting of 10 machine gunners, 2 tanks and 1 humvee. I destroy it quite easily.
2) AI repeats first attack and I win again.
3) After roughly the same amount of time between attacks, the AI repeats the first attack yet again and I win again.
4) AI sends another attack this time consisting of 10 machine gunners, 2 tanks, 1 humvee and 1 cruise missile launcher. I have to send my army forward to take out the cruise missile launcher and I suffer a few losses but I still win.
5) Repeat until AI wins or AI loses.

So yeah, it seems C&C Generals does stick to the general cheat and execute weak attacks method of RTS AI.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
^^Note 1: Someone else who has played C&C Generals may be able to comment further.

^^Note 2: It would be quite interesting to start a very simple RTS project just to attempt making a decent AI that doesn't cheat (ie ~3 building types, ~3 unit types, barebones minimalist RTS. Surely the AI could then be scaled up to a more realistic situation in a full blown RTS?). But then is a single unprofessional person could make a decent RTS AI then why don't the professionals do it? Maybe it's just a hell of a lot easier to make cheating AIs. I might just make this my next project :)

Share this post


Link to post
Share on other sites
Palidine    1315
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

Share this post


Link to post
Share on other sites
Talroth    3247
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.

Share this post


Link to post
Share on other sites
d000hg    1199
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.

Share this post


Link to post
Share on other sites
spencerholmes    157
Hello. Trust me there are alot of resources out there for anyone who wants to learn about Game AI. My main university project was on Game AI and i had quite a interesting time researching.

I will tell you what i know...

RTS game usually use AI techniques such as:

1. A* Pathfinding for movement of units and other game entities.
2. Scripting.
3. Influence maps to determine how popular a certain region is on the map,
attack points, choke points, item location and weak spots.
4. Heirarchical finite-state machines which are you to apply behvaiour to npc'

Here are a couple of links i used:

www.gamasutra.com //very useful
www.gameAI.com
www.generation5.org
www.AIwisdom.com

or you could use a torrent search and look for game AI ebooks!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this