Video Game AI: Shooters vs. RTS

Factual Questions
1

I waste a huge chunk of time better spent elsewhere on playing first person shooters and real time strategy games. I’m always amazed when I hear the accolades about the AI in FPS games like Half-Life and Halo. Such accolades often include:

  1. The enemy will attempt to flush you out with grenades!

  2. The enemy will actually use cover!

  3. The enemy will attempt to flank you!

While I’m not a programmer, I don’t see how these feats are particularly impressive and I don’t find their execution to be particularly impressive either. Isn’t this just a basic pathfinding algorithm?
Then I play a game like C&C:Generals or Rise of Nations and wonder how the hell they come up with making an AI for these games. Not only is the concept complex, but the execution is often surprisingly good. Pathfinding seems like the least of the feats the AI can accomplish in an RTS.
I find the gap in AI between FPS and RTS games particularly perplexing because from chess I know that computers are generally better at tactical vs. strategic algorithms.
I know that the heart and soul of an RTS is the AI so that’s where a significant percentage of resources would go, but it still seems like there is an odd disparity. A Turing test of an RTS ten years ago would seem to equal that of the best FPS AI today. Why?

2

I think one problem is that you’re comparing virtual humans (FPSs) to virtual machinery/vehicles (C&C). We deal with humans on a day-to-day basis, and thus are aware of their intricacies, if something even slightly seems off, we’ll catch it (whether it be AI based or graphics based). On the other hand, we have simulated machinery which I believe we’re a lot more willing to forgive, as opposed to simulated humans. For instance, if a tank collided with a wall, I strongly doubt you’d bat an eye, however, if a human did the same it would look utterly ridiculous. It’s all about the perception.

3

I’ll give it a try, now I’m not a games programmer, but I am a gamer and a programmer, so I’ll make my guesses.

You mention 3 types of games, FPS, RTS, and chess-type. Each type of game AI will need to consider different factors.

A chess-type game is interesting to study because it’s possible to play chess, checkers, or tic-tac-toe “perfectly”. All players know everything about the game state, therefore these games are possible to model perfectly using game theory (game trees and minimax tree analysis). The human opponent in these games also has perfect knowledge of game state so there’s no real question of “cheating”.

An RTS game has a couple of interesting features:

  1. It’s easy for the AI to “cheat” regarding game knoledge. The game knows what resources and units the human player has, so the AI could use this information to play better (I don’t know if the game developers exploit this knowledge, but I suspect that they do).
  2. An RTS game is won throughout the game, it’s tough to make a comeback, since it’s much quicker to destroy an army or base than to build one. The AI really only needs to be good at gathering resources, building units, and occasionally making attacks. It’s also easy to evaluate an army’s chance of defeating another army (based on number of units and unit type).
  3. The human player is using the AI too. You don’t command individual units to attack specific units (usually), the game manages that. Most often you build an army and send it out to attack his army or base, though you can micromanage some units, in general the game uses some crude algorithm to decide what your units attack.
  4. The AI doesn’t have the same mouse and screen limits as the human player. You need to scroll, hotkey, or mapclick to select and command a unit, and you’re limited to doing one thing at a time, the AI isn’t, it could simultaneously be building a base, building units, and commanding an army. Build queueing works to the human player’s advantage, but the AI can still do the mechanical tasks of play better than a human can.

In comparison to the other two, the AI doesn’t have many advantages in an FPS.

  1. The AI can know only a little about the human player, such as your position, health, armor, and weapons. The game doesn’t (and can’t) know what you are planning.
  2. An FPS game can turn around in a matter of seconds (it’s easy to kill any one opponent) and preparation doesn’t help very much.
  3. Cheating (using info that a human wouldn’t have) is much more obvious. You’d be annoyed if the AI could track you perfectly, even if you hid behind an object or if the AI always chose the corridor that you aren’t guarding.
  4. The human players perform all of their actions manually, including aiming and movement. You could give the AI perfect aim but human players would quickly get sick of that.
  5. FPS game state ideas are more difficult to recognize and it’s difficult to change meaningfully. Consider the concept of hiding, it’s difficult to detect that a player is hiding (you need to consider the player’s position relative to objects in the room) and it’s even more difficult to carry out the action of hiding. I daresay that these types of problems are np complete (in the size of the room data) (it’s certainly a difficult computational problem).

The short story is that the AI can “cheat” more effectively, more easily, and less noticably in RTS games than in FPS games. One other factor to consider is 3d vs 2d. The game map in an RTS game is essentially 2d (though some games have several 2d planes) where every recent FPS is 3d. Pathfinding is much simpler in 2d than in 3d, and even moreso when you can’t fly in the 3d case.

4

My two cents: I think with FPSs (I’m not a big RTS fan) there’s a danger of making the AI too good. I mean, it’s conceivable that a bot could hit you with ever single shot it shoots while simultaneously moving at the last second in exactly the right way to dodge most of the shots you shoot (depending on the weapon you have, naturally).

Also, bots could team up on you by, say, having two bots throw a grenade to your left and right while shooting you as you wait in the middle.

So, I think that maybe one reason FPS bots aren’t just fantastically good is that they would be too good and then it wouldn’t be any fun.

5

What exactly is the difference between a tactical and a strategic algorithm?

Putting that aside for a second, don’t be fooled by chess computers. They are not good at tactical play or positional play. They are good at calculating all of the possibilities for N moves deep and then selecting which line gives them the highest evaluation. Computers don’t see forks, they see that no matter what, 2 moves from now, they will be up a piece. This leads to the classic short comming of computer chess… their inability to properly evaluate sacrifices. For example, if a chess computer is programmed to search for the next 10 moves in every line, then you can beat it every time, by finding a line that contains a sacrifice and wins on the 11th move.

In so far as AI for RTS or FPS is concerned, it’s quite an easy thing to say, “I want my AI to flank the player”. It’s an entirely different matter to make it a reality. It isn’t the action of flanking per se that is difficult, it’s the evaluation of when it is a good idea to flank vs when not to flank. In chess, this is simplified. The computer can calculate the next moves and decide whether any given move is a good move or a bad move. In a FPS it’s much harder, because there is no way of telling where the Human player is going to go or what they are going to do. It would probably involve a mammoth effort on the programmer’s part to input all of the various map locations including terrain options and to write routines to determine which areas of which maps are good for flanking, which are good for sniping, which are good for ambush, etc, etc.

RTS by contrast are far easier to program AI for, because the rules of the game are much more clearly defined. It’s a relatively simple matter to determine whether it’s more economical to produce another citizen to collect the necessary resources for a given project, or just save the resources you have.

For example,

A citizen costs 50 food and requires 4 turns to build and can collect 5 food per turn.

You want to build a structure that requires 250 food.

You have 100 food in the bank and are accruing food at the rate of 25 food per turn.

It’s a simple calculation based on how long it takes to build a citizen as to whether you can build that structure faster by making another citizen to farm resources, or saving your resources for the 6 turns until you have enough to build. (in this example, you are better served waiting to build the structure and making the citizen afterwards)

So, in a nutshell, the more clearly defined the rules of the game are, the easier it is to write an AI. That being said, there are still some excellent FPS AIs out there, but Half-life and Halo aren’t among them. Check out Call of Duty or Medal of Honor.

6

Pathfinding is actually a lot more complex than people realize, especially in a 3D environment. Modern Bots have to navigate over and around stairs, lifts, swim underwater. Games like the Unreal series actually have an entire Pathnode system that lets the bot get from one area of the map to another without bumping into things and good pathnoding can make a big difference in the quality of the level. First-person shooters are much more demanding on a computers CPU than turn-based games because the bots have to react in real time to an environment that changes from second-to-second. The Bots have a lot to think about: “Where is the Player now? How can I get to him? How much damage have I taken? What kind of weapon do I have and how much ammo does it have left? Should I grab that powerup that just respawned a second ago or just stay where I am?”

>The enemy will attempt to flush you out with grenades!

It’s not as easy as it sounds. The bots have to pick the best direction to lob the grenade and then anticipate which direction you are likely to run when they throw it. They also have to force you go in a direction that will expose you the most and benefit them, so they can’t force you into an area that’s more difficult to reach.

The enemy will actually use cover!

If the bots can avoid taking damage, they avoid dying and can engage you for longer periods of time. We’ve come a long way since the “suicide bots” of Quake II. Half-Life came out in 1998(?) so this isn’t as impressive as it used to be. :slight_smile:

The enemy will attempt to flank you!

3D Bots used variations of the “run straight at you and die” AI for a long long time. Now that graphics cards are bearing a greater part of the CPU load, programmers have more resources available to spend on Bots to make them think more strategically. (Plus it’s harder to defend yourself against fire coming from more than one direction at once and very difficult to get bots to coordinate their efforts (like not get in each other’s way, for instance) ) It’s still possible to beat 3D bots by memorizing combo moves but they are a lot smarter now than they used to be.

7
8

I was the lead design on Rainbow Six and Ghost Recon … so I might know a little about FPS AI … .

One advantage that RTS AI programmers have is that the typical RTS level is geometrically simpler than the typical FPS level.

RTS levels are mostly 2-D and when there are 3-D elements they usually are usually limited to a fixed set of elevations. Elements that block line of sight can be easily approximated insernally with boxes instead of having to be represented in their full polygonal glory. And movement is often quantized to a grid, limiting the number of possible positions and facings that units can assume.

In an FPS you don’t have the luxury of these simplifications. Bots have to handle all three dimensions. They have to take into account fuzzy ideas like partial cover. And they have to deal with totally arbitrary positions and facings.

These means that a lot of things that can handled in an RTS by a simple general rule (“a grunt on level 3 can see enemies up to 4 grid squares away”) have to be handled in an FTS on a case-by-case basis with computationally expensive line-of-sight checks.

“Taking cover” is easy if it means moving a unit into a woods square. “Taking cover” is hard if it means crouching behind a tree and updating your position second by second to avoid a circle-strafing enemy.

9

I was the lead design on Rainbow Six and Ghost Recon … so I might know a little about FPS AI … .

One advantage that RTS AI programmers have is that the typical RTS level is geometrically simpler than the typical FPS level.

RTS levels are mostly 2-D and when there are 3-D elements they usually are usually limited to a fixed set of elevations. Elements that block line of sight can be easily approximated insernally with boxes instead of having to be represented in their full polygonal glory. And movement is often quantized to a grid, limiting the number of possible positions and facings that units can assume.

In an FPS you don’t have the luxury of these simplifications. Bots have to handle all three dimensions. They have to take into account fuzzy ideas like partial cover. And they have to deal with totally arbitrary positions and facings.

These means that a lot of things that can handled in an RTS by a simple general rule (“a grunt on level 3 can see enemies up to 4 grid squares away”) have to be handled in an FTS on a case-by-case basis with computationally expensive line-of-sight checks.

“Taking cover” is easy if it means moving a unit into a woods square. “Taking cover” is hard if it means crouching behind a tree and updating your position second by second to avoid a circle-strafing enemy.

10

Pochacco, how much do the bots know in the games you’ve worked on? I expect that they know every game fact that a human opponent would know (position if you’re in view, current weapon, and armor (if armor is visible)).

Do the bots know your current health?
Can they see you if you’re behind them?

I know that it would require more computation calculate what the bots can actually “see”, but do they know anything about the human players when they’re not visible?

Do you know anything about how this works in RTS games? RTS games have much more confined rules than FPS games, but I’ve often wondered how much the AI players know.

11
  1. This makes sense
  2. You’re my fricking hero. I cut my FPS teeth on R6 and Rogue Spear. More hours spent on RS than any other game. The advent of the lean feature is the single greatest addition to the fps genre.
12

I meant to address this before. I know for sure that the AI in Rise of Nations has the same fog of war that you do. The only difference is that at the highest difficulty, the ai gets a resource collection bonus. I believe the same thing is true re: the fog of war in Generals. Of course the AI has perfect execution speed but that’s assumed.

13

I can’t speak for every FPS, only for the one’s I was involved with.

Yeah … our bots cheated all over the place. Basically we’d give them whatever data would make our jobs easier … .

That said … our job wasn’t to kill the player. Our job was to give him a fun fight. The bots were mostly trying to move realistically and present interesting targets to the player … and sometimes to kill him.

So every bot knew exactly where the player and his squad were at all times. But they wouldn’t do anything about it unless they had a successful line of sight check on one of them. This would flip them over from a passive “patrol” state into an active “search and destroy” state. (And a bunch of factors went into this detection model … range, illumination, player movement)

Once the AI had detected the player he would immediately pass the detection flag over to the other members of his unit so they would all be in the same state and act together. The AIs would then try to engage the player.

Sometimes they’d just stand and fire and sometimes they’d run for cover. The modellers embedded cover points in the maps so the AI’s knew good places to hide. The AI’s would test the nearby cover points to see if they actually provided cover given the locations of the player and his squad. If they found a good cover point they would path-find to it. The AIs all shared info about what they were doing so two of them wouldn’t run for the same cover point.

Once they were under cover the AIs would pop out periodically and attack. Once an AI knew where you were they would continue to track you even if you were out of sight, so you couldn’t really fake them out by hiding. But if you remained hidden long enough they would stop trying to engage you and would wait for you to reappear.

We experimented with big strategic movements (flanking, tactical retreats, etc.) in Ghost Recon but we wound up deciding that that level of AI was largely a waste for us. A secret flanking maneuver didn’t feel like a secret flanking maneuver to the player – it felt like a random ambush by a new force from an unexpected direction. We basically had a rule of thumb that if the player couldn’t watch the AI while he did it, there was no point in coding it.

I imagine things are a little different for one-on-one deathmatch bots … .

The bots could “see” you even when you were behind them if you got close enough. They all had an automatic detection radius and if you crossed it you were detected no matter what. This was so you couldn’t creep up behind a bot and stand undetected a few inched from his back.

I don’t think we ever tracked player weapon or health state. It wouldn’t have added anything to the player’s experience.

I can’t comment on how RTS games handle things.

14

Ah, thank you. But I can’t take credit for inventing “lean”. That would go to Carl Schnurr (or maybe another member of the Rogue Spear team). Carl was my co-designer on R6. After we shipped R6 I moved over to another Red Storm project that was in trouble, while Carl continued on with Rogue Spear. Then Carl left to do XBox games while I led the Ghost Recon team.

My contribution to RS was tangential only – some story stuff, some mission suggestions. I wrote all the briefing dialog.

(Interesting Rogue Spear fact: The first draft of the story was much more tied in with real world events than the version we shipped with. The original bad guy was modelled very closely on, believe it or not, Osama Bin Laden … who was still relatively unknown in 1998. Ultimately we changed it because we wanted a more secular bad guy.)

15

WOW Pochacco, this thread kicks ass since you showed up. Thanks!

I know I’d appreciate any other little tidbits that you’d care to post.

16

Pochacco, one of the things that has always bothered me about all the incarnations of the R6 series, including the latest RavenShield, is that the terrorists can kill you before the animation of their gun being raised is complete. So I’ll often take an extra second to aim, seeing that the tango’s gun isn’t raised, and get sniped from some hidden barrel in the middle of his forehead. Anyway, kudos to making the most interesting games in the genre.

17

Hmmm … ask me a specific question and I’ll see what I can do.

18

Interesting indeed. R6 completely blew my mind and caused me MANY nights of lost sleep. By far one of the most enjoyable game series that I have ever played.