Ted Vessenes over at Brainworks posted an interesting little observation about his Quake 3 bot and FPS AI in general. Here's a quick quote:

bots use items as the primary motivating factors for deciding where to go. The pathing and routing code will tell you how to get from point A to point B, but all of that is meaningless if you don't know what point B is. The typical strategy is for the bot to pick up the items that help it the most and require the least amount of movement. If the bot can't find any enemies, it will head to the nearest generally useful item and hope a target wanders by. Item placement is the core component of goal selection in BrainWorks.

While I'm cool with all of that and can see the point he is trying to make, I don't necessarily agree with the following (emphasis mine).

When two human players are in a level that contains no items, however, they don't get confused at all. Instead they strategically run and hide around the map, using cover to create good shots on the opponent while dodging their return fire. What BrainWorks is missing (and all first person shooter AI bots for that matter) is this dynamic tactical movement. You just don't notice it's missing from BrainWorks because of the item pickup code.

It's very difficult to design AI that can recognize and avoid dangerous areas of terrain while simultaneously taking advantage of opponents in those spots. But it's not impossible.

If that is the design of the bot, certainly that is a problem. This used to be a problem in FPS games, but I don't believe it is as much any more. Most AI isn't built in the same purely functional framework as a bot. AI is also designed to 'do nothing' in a reasonably convincing fashion. Many games now have plenty of things for the AI to do when it is idle or lacking any obvious goals. Games such as STALKER (I refuse to put the periods in there), Far Cry, Crysis, Far Cry 2, and even Left 4 Dead, have many idle behaviors.

Specifically regarding tactical movement, however, many of the recent generation of FPS games have such features as seeking and using cover, finding adequate fire points, etc. Ted addresses this somewhat by suggesting potential algorithms to use:

Here's the basic algorithm I have in mind. The first objective is to create a "danger map" for the level. The danger map estimates how tactically risky it is to be in each area of the level. Note that "area" needs to be relatively small-- roughly one to two square meters on the ground. Too much larger and the algorithm will get muddied, mistaking good regions for bad. Too much larger and the computation will become prohibitive.

He is correct in his suggestion. Much of the tactical awareness of an AI agent is done with either subdividing the map or by using many pre-positioned cover points. Many variations of these techniques are already in use. AI Game Programming Wisdom 3, for instance, had a number of exceptional articles on FPS tactics. Damian Isla (Halo 2 and 3) wrote about Probabilistic Target Tracking and Search Using Occupancy Maps, Remco Straatman and William van der Sterren (CGF-AI) wrote a brutally cool article on pretty much what Ted defines above entitled Dynamic Tactical Position Evaluation, and Christian J. Darken and Gregory H. Paull wrote Finding Cover in Dynamic Environments which even included the height and visibility of terrain. And those three articles were back to back in that book!

That is why I wholeheartedly disagree with Ted's statement:

It's far too hard to analyze the geometry of a level to create a danger map, although some simple techniques could be used for a first pass analysis.
[snip]
This all sounds well and good on paper, but if it were actually that easy, it would have been done already. You might be wondering what the catch is.

That's simply not true. Sure, it helps to have some pre-processing done, but it can be done without as well.

Anyway, Ted is usually on his game over there at Brainworks. (I'm hoping to get his butt over to GDC so I can meet him!) However, on this one he might have been outside his comfort zone. After all, writing a bot isn't exactly the same as writing AI.

Labels: Brainworks, FPS, tactics, using cover

Got linked to this by Paul Tozour. Here are Damian Isla's (Bungie) slides from his 2005 AIIDE presentation on "spatial competence" entitled "Dude, where's my Warthog?" It includes info on a ton of the stuff he/they did in Halo 2. Included is information on pathfinding - especially with regard to how we (as people) process spatial information. It's nice to see someone else tapping into psychology as a source for potential solutions for game AI.

Fantastic stuff... and left me dying for the audio.

Labels: AIIDE, Bungie, Damian Isla, Halo, Halo 2, pathfinding, psychology, slides, using cover

Alex Champandard, at AIGameDev has posted a nice video analysis detailing some of the complicating issues surrounding the inclusion of destructible cover in an FPS game. He uses video from a recent trailer from the upcoming Brothers in Arms 2. As always, Alex details things rather well. He offers an off-the-cuff solution without getting terribly technical. I can understand why he can't "solve" the problem... it is usually something that is very game and engine specific. Regardless, it shows the issue itself very well.

This reminds me of a conversation that was had at the AI Game Programmers Dinner at the 2008 GDC. There was a brief exchange where we were talking about points of visibility in the games that were represented in the room. Many games tend to use around 6 points... a rectangle representing shoulders and perhaps thighs, one for the center of the body and one for the head. Others may add a few more here or there. I asked Christian Gyrling (Naughty Dog) how many they used in "Uncharted: Drake's Fortune"... his answer? 20. That's a LOT of ray casts. Admittedly, this was 20 points on the player's body to determine if the enemy AIs could see him. However, the result is the same... 20 potential raycasts for each active enemy NPC. Ouch. (Welcome to the PS3, I suppose.)

I would like to think that specialized graphics hardware and simply more processing power will make this approach more cost-effective in the near future.

Labels: AIGameDev, Alex Champandard, Brothers In Arms, using cover, video

I noticed this GamePro blurb about the upcoming sequel to F.E.A.R. Here's an excerpt...

"The most obvious difference that will hit the player right away is in the visual density of the world," said Mulkey. "F.E.A.R. looked really great, but where F.E.A.R. would have a dozen props in a room to convey the space, Project Origin will have five times that much detail.

"Of course, this will only serve to further ratchet up that 'chaos of combat' to all new levels with more breakables, more debris, more stuff to fly through the air in destructive slow motion beauty."

OK... I can dig that. One thing I noticed as I played through F.E.A.R. is that things were kinda sparse. (I really got tired of seeing the same potted cactus, too.)

The part that I am curious about, however is this:

... Mulkey says improved enemy behavior is at the top of the list.

"We are teaching the enemies more about the environment and new ways to leverage it, adding new enemy types with new combat tactics, ramping up the tactical impact of our weapons, introducing more open environments, and giving the player the ability to create cover in the environment the way the enemies do," he says.

Now that is the cool part. When the enemies in the original moved the couches, tables, bookshelves, etc. it was cool... but rather infrequent. I was always expecting them to do more with it. If they are both adding objects to the environment and then "teaching" the agents to actually use those objects, we may see a level of environment interactivity that we've never experienced before.

The cool thing about their planning AI structure is that there isn't a completely rediculous ramp-up in the complexity of the design. All one needs do is tag an object that it can be used in a certain way and it gets included into the mix. On the other hand, having more objects to use and hide behind does increase the potential decision space quite a bit. It's like how the decision tree in chess is far greater than that of Tic-tac-toe because there are so many more options. The good news is that the emergent behavior level will go through the roof. The bad news is that it will hit your processor pretty hard. Expect the game to be a beast to run on a PC.

I certainly am looking forward to mucking about with this game!

Labels: agent based AI, emergence, F.E.A.R., FPS, Monolith, planning, smart objects, using cover

OK... I'm liking where these guys are going with this. This is a description of some of the natural behaviors that are being used in the upcoming game, "Warhound". I admit I haven't heard about this game until now, but I'm definitely impressed with what I see here. They don't talk about the AI design/programming techniques that they use (and I don't blame them), but they mention some of the resultant behaviors.

Make sure you click on the video link. It will show you how the AI uses the cover of a large crate to attack the player in a variety of ways.

Thanks to Alex Champandard at AIGameDev for the link.

Labels: AIGameDev, FPS, using cover, Warhound