Hi, I was hoping to get some tips about FPS 'combat' AI. When having a brawl you don't want your opponents just to stand there waiting to get shot. They should move around, but... where to? I don't know how other games exactly work, but maybe its an idea to move from cover-to-cover. I think in real life you would stay at a covered position until it gets too hot for comfort. But in games you might want somewhat faster/dynamic/Rambo III action. The guys in Halflife2 or F.E.A.R. didn't stand still for a second, yet they seem to have a certain strategy or pattern of howto walk. But I never figured out what... In my editor I can help the AI a little bit by placing nodes. For example, "sniper", "ambush", "cover" or "defense position" nodes. So when someone has to reload, he could search for a nearby "cover" point. But the "quality" of these nodes often depends on the player position. I mean, a cover position is worthless if the player is already standing there. Or covering behind a wall depends on which side the player is. In my game I could approach the area from different directions in many cases. Could you guys give some hints on how this kind of stuff is done? Greetings, Rick

Hi Rick,

this paper/presentation probably answers some of your questions (and raises a few new ones).

Killzone's AI : Dynamic Procedural Combat Tactics, Beij, Straatman, Van der Sterren (Game Developer Conference 2005)
- slides
- paper

Have fun,

William

Dank u, dank u, exactly what I was looking for!


You actually helped developing the AI for Killzone? Saw your name on the paper... Hollandse glorie :)

Thanks,
Rick

Reading through the papers right now. I like the way complex things are presented in clear and clean way. Two questions though.

If I understand right, to test visibility, each waypoint stores the maximum potentional "threat distance" for 8 global directions and 2 poses (stand / crouch). And then it comes, only 64k needed for 4.000 weaypoints. If I store 2 sets of 8 bytes(2 poses, 8 directions, each holding a byte for the maximum distance), I would need 500 kb for 4000 waypoints. It's not much, but a whole lot more than 64K! 64K = 2 bytes per waypoint. How can you store 16 directions into that? Probably I understood something wrong there...


When A* generates a path, I assume it will calculate its costs depending on coverage. If 1 or more enemies can see you at a certain waypoint, it means no bonus points for that piece of path. The Lookup table can speed up this test greatly, but still... I mean, you must then check for each potentional enemy from which global direction he comes, calculate its distance towards the player, and then compare it with the Lookup table. On itself quite easy tasks, but when doing it for hundreds of points (on longer routes) it still might be much, right? Or do you guys split long paths into smaller ones? Or is the way of testing I wrote incorrect?

Greetings,
Rick

Quote: Original post by spek
If I understand right, to test visibility, each waypoint stores the maximum potentional "threat distance" for 8 global directions and 2 poses (stand / crouch). And then it comes, only 64k needed for 4.000 weaypoints. If I store 2 sets of 8 bytes(2 poses, 8 directions, each holding a byte for the maximum distance), I would need 500 kb for 4000 waypoints. It's not much, but a whole lot more than 64K! 64K = 2 bytes per waypoint. How can you store 16 directions into that? Probably I understood something wrong there...

64KB / 4,000 waypoints is 16 bytes p waypoint.

Quote: When A* generates a path, I assume it will calculate its costs depending on coverage. If 1 or more enemies can see you at a certain waypoint, it means no bonus points for that piece of path. The Lookup table can speed up this test greatly, but still... I mean, you must then check for each potentional enemy from which global direction he comes, calculate its distance towards the player, and then compare it with the Lookup table. On itself quite easy tasks, but when doing it for hundreds of points (on longer routes) it still might be much, right? Or do you guys split long paths into smaller ones? Or is the way of testing I wrote incorrect?

It (obviously) turned out not to be a problem: in the presence of threats, the individual AI on average performs short moves (to a next nearby cover/attack) position. Longer routes are rare but may happen for squad maneuvers. I don't remember all the details, but cutting off all LoF checks once you're more than 15s distance into finding a potential path would be a viable performance improvement (assumptions about the current enemy positions will not be valid 15s into the future against smart opponents).

Hello,

just read through the slides and working on the paper now the question arises:

How expensive is this in comparison to usual approaches?

I mean the way search part. The positioning should eventually go in there as well as you aim for a good position, move there and when you realize your target moved on you have to switch position as well.
And which part is the really expensive stuff. You mentioned the small size of additional information but I feel that doesn't matter at all since I have several GB of RAM on most computer anyway...

Anyway, would it be easier to leave out units that are far away or that haven't been seen for some time ? Though the later would require to check and remember where you have seen your oponents the last time.

I am just asking myself if something like this is viable in a RTS because you have many more units but you can make lots of stuff much simpler. Like store a threat zone for a whole army (like an overlay on the whole map) adjusting it whenever you get new information but you can leave out all the LoF calculations for Individuals.

Quote: Original post by Leartes
How expensive is this in comparison to usual approaches?

As the paper indicates, performance was good enough to run the game with 14 autonomously operating bots on a Playstation 2. That's due to the AI design and due to Guerrilla Games' game engine, which left a good amount of CPU for the AI.

I'm not sure there is a 'usual' approach. Wrt to path-finding in FPS combat situations, you can:
- use shortest-paths (which is what most games used to do at that time);
- fake tactical movement by preferring paths next to walls and cover, which looks OK most of the time but may result in some weird choices. I suspect Company of Heroes does this. 'Nearby wall/covers' checks are cheap.
- do tactical movement based on approximated pre-computed LoF, which is what Killzone does in response to land-based threats. Not cheap but doable on a PS2.
- do tactical movement based on real-time ray casts, which is what some games do, and what Killzone did in response to (rare) flying threats. Typically too expensive to use them for everything all the time (LoF checks are generally more expensive than path-finding).

The paper mentions an additional advantage of approximated pre-computed LoF: the error from approximating the LoF was chosen to coincide with possible movement by the threat.
The look-up table size of 64kB was key to use it on a PS2 (32MB RAM). Small tables still are relevant for today's processors, since they fit easily within the cache, and don't kick too much other relevant data out of the cache.

Quote:
Anyway, would it be easier to leave out units that are far away or that haven't been seen for some time ? Though the later would require to check and remember where you have seen your oponents the last time.

Something along that lines was done, and primarily for reasons other than LoF checks: we humans don't base our decisions on more than a few threats (even when playing something less lethal such as soccer or football, we don't track all 11 opponents in detail).

Quote:
I am just asking myself if something like this is viable in a RTS because you have many more units but you can make lots of stuff much simpler. Like store a threat zone for a whole army (like an overlay on the whole map) adjusting it whenever you get new information but you can leave out all the LoF calculations for Individuals.

Check Chris Jurney & Shelby Hubick's GDC2007 presentation 'Dealing with Destruction: AI From the Trenches of Company of Heroes' where he describes how they tackled path-finding, LoF and cover in Company of Heroes, a WWII RTS with destructible terrain/buildings (great game!). My interpretation is that they don't do too many LoF checks but simply put soldiers in positions that offer generally good cover.

Battlefront's Combat Mission: Shock Force is newer PC game (2007) which uses a somewhat similar approach for a real-time tactical modern combat wargame, featuring hundreds of individuals and vehicles on a 12km^2 piece of open terrain. It uses pre-computed LoF check (at different height levels) for the 8x8m tiles occupied by the attacker and target, and only performs real LoF ray-cast if the LoF check passes. My understanding (from Steve Grammont's explanations at their forum) is that LoF checks dominate the AI performance. The game's AI is done by Charles Moylan.
(Btw, I recommend the game - it's way better than now (v1.10) than originally released and reviewed).

Hi again,

I've been playing around with the "distance radials" that are stored for each waypoint. So each point calculates the maximum "threat distance" for 8 radials. It works ok for wider/outdoor area's, but in my (indoor) test scene there are quite much situations that the radials also overlap other sectors. Also height differences can bring problems. I hope this ASCII art can clarify:

                      C            _______            |  A         |  B  -----------------    side view

When calculating node A, it can also see C. But then it also overlaps the closed sector B that lies beneath C. So when targetX is standing in sector B, Bots could choose position A.


I can think of 2 things to improve it. First is to use more than 8 radials, 16 for example. It makes stuff slower and eat more memory, but I don't have to make it run on a PS2 :L Second is to exclude sector B from A somehow. If its really closed in, sector B could tell that to A in other to scrap it from the options. However, this doesn't work anymore if there is somewhere a door between A and B. That was the biggest problem in my test scene, lot's of chambers and doors, and therefore in many cases too big threat distances for the nodes. Reducing and averaging helps, but you also risk to make some positions completely invisible.

How did Killzone handle indoor complex situations like these?

Rick

Quote: Original post by spek
Hi again,

I've been playing around with the "distance radials" that are stored for each waypoint. So each point calculates the maximum "threat distance" for 8 radials. It works ok for wider/outdoor area's, but in my (indoor) test scene there are quite much situations that the radials also overlap other sectors. Also height differences can bring problems.

[... snip ...]

How did Killzone handle indoor complex situations like these?

Rick

Great to see you experiment with these ideas!
Wrt effectiveness of this approach in Killzone, there's a subtle detail in the paper (bottom of page 9) that's tough to explain but quite essential. With an attacker at position A and target at position C, there can only be a LoF in the game world if the table indicates a potential LoF from A to C AND a potential LoF from C to A. And there is guaranteed to be NO LoF if there's no LoF from A to C OR no LoF from C to A. (The actual system takes postures into account as well).

This addressed the problem you sketched in your post (and many other situations as well):
- the table would indicate a potential LoF from B to A, since there is a true LoF from C to A and B and C are at a similar distance from A
- the table would indicate no potential LoF from A to B, since no position near A will have a true LoF through the cover separating A and B.

Nevertheless, the approximation of LoF in table may yield consistently hit false positives (LoF where there isn't a true LoF). For Killzone, these were rare and typically involved balconies. One way to avoid them is to add more resolution in the look-up table (and increase its size). Arjen Beij at Guerrilla Games took another approach for Killzone 2, but I can't tell you about it...

Ah, quite logical to do a check in both ways. That would indeed discard quite some situations, though walls with windows and doors can still deliver problems sometimes. Increasing the radial count (only for upper stance, cover at lower stance doesn't have to be that accurate I think) might help... Well, back to the test-scene. I'm having too much fun with my bots, whom have still much to learn :)

Thanks again!
Rick