AI using cover?

What defines a node in this case? If we consider a node to be an object, I don''t think it works well as defined here. Since all your algorthim does is move the agent to object as far from players firing arc as possible. It would better to call this the run away in cover algorthim.

A cover algorthim would take the following things into consideration.
1)Distance from target
2)Agent''s Weapon range
3)percentage of Agent covered
4)percentage of target covered
5)Distance from Agent

So if the cover algorthim assigns a node to each visible object and caluclates those four values for each object, as well applies weights to each value. You could use A* to locate the best piece of cover.

-----------------------------------------------------
"Fate and Destiny only give you the opportunity the rest you have to do on your own."
Current Design project: Ambitions Slave

I meant node as in a piece of space :$ (at least thats what i use).

I was thinking of useing something like this formula:
WE = (AFD - PAD) / (DD^2)

PAD = Player distance
AFD = Players Firing range
DD = Difference of position (in radians), (from Player)

Maybe
WE = ((AGD - PAD) * DD) / ARC
AGD = Agent distance
ARC = Number of Ray casts from player to point (including those in the immediate area of the player)

But the first one isn''t that good a formula, because once your outside the players firing range, it would go negitive. so maybe try and minimize its value? what would be a better formula here?
(percantage of agent covered and percentage of target covered, can you explain these?)

The second formula would be OK, but still lacking...

Why not treat the problem of cover as one involving the view as seen by the player. Since you''re already processing this as a graphics action, use that information to determine regions of the visual space that are ''hidden'' from the players perspective. Then simply label these and set them as possible goals for the pathfinding. Select one based on some criteria (closest, largets region, close to escape route, etc). Use your pathfinding algorithm to get there... and you''re done.

Timkin

If a node is just a point in space how can that be cover? Cover requires some intervening object.

By percentage of agent covered I mean that you have say a crate 10 units high and agent is 20 units high there for .5 of the agent is covered, which would be considered more cover then say a pipe the covers .1 of the agent. The percentage of the target covered would require multiple calculations and might slow things down to much, but the idea is that from any point there are x objects between the agent and the target, the percentage of cover would be the amounts those objects cover the target from that point. So if the agent is behind the pipe the crate might be between the agent and target and due to the targets relative distance .9 of the agent is then covered.



-----------------------------------------------------
"Fate and Destiny only give you the opportunity the rest you have to do on your own."
Current Design project: Ambitions Slave

I think of nodes like hexagons in some 2D games, they represent a unit of space; but are linked to other objects (like crates).

Maybe a formula of:
WE = (((AGD - PAD) * DD) / ARC) * (AH / UH))

AH = Ai''s height
UH = Units height, (for empty space- no objects, this formula would generate an error... maybe set the height of empty space to 1?... or do a switch to ''switch in'' the extra part of the formula...

wouldn''t his make more sense
U= (AFR/DTT) * ((AH - UH)/AH))

DTT = Distance to target from node
AFR = agents Firing range


Then choose the the node with highest value.


I''m not really sure what you mean by these values since they rather ambiguious.
PAD = Player distance
AFD = Players Firing range
DD = Difference of position (in radians), (from Player)

AGD = Agent distance
ARC = Number of Ray casts from player to point (including those in the immediate area of the player)



-----------------------------------------------------
"Fate and Destiny only give you the opportunity the rest you have to do on your own."
Current Design project: Ambitions Slave

PAD = Player distance (in nodes, 2d distance - along floor)
AFD = Players Firing range (how far the players current weapon can fire)
DD = Difference of position (in radians), (from Player) (find the difference in the angles- ie. how far the player would have to move to face the node)

AGD = Agent distance (how far the agent is from the node - 2d distance, along floor)
ARC = Number of Ray casts from player to point (including those in the immediate area of the player)- For each node ''near'' (within 10 nodes of) the player, do a ray cast, then find out how many rays pass that node (is in line of sight to the other node))

Thanks technogoth for the new formula... now why didn''t i think of that...

Extracting information about the environment with ray traces can get expensive quickly. Most games have predefined ''cover locations'' to get around this problem; these locations are places a level designer deemed to be good cover from a particular direction.

These locations may be tagged with information such:

* valid if the enemy is within a designer specified distance (distance prevents AIs from moving too close or too far from the enemy)
* valid if the enemy is in side a designer specified FOV of the node (FOV simulates a screening object)
* valid if the time to get to it is less than X (because a close node in world space may not be close in path space)

Nice Coder, can you provide examples of failures of existing games when it comes to using cover? What specificly would you like to see in games that you don''t see right now?

If you''re interested in tactical pathfinding, you might want to look at William van der Sterren''s site CGF-AI. He has several papers and many links to information that would be usefull. You might also want to look at his articles in the AI Wisdom books.

We actually had a huge discussion on this at a GDC roundtable this year. The ideas that were floated were pre-calculated hot spots for cover (behind crates, tables, etc.) and dynamically calculated spaces (such as what Timkin wrote above).

The problem with using instantaneous LOS is that it can change significantly from frame to frame. Imagine a room with large boxes and tables scattered around and a person-width column in the middle of the room. The AI, upon examining LOS shadows would determine that standing either right next to the column on the far side from the player... or even ANYWHERE back from that column towards the far wall... would be suitable cover. You and I know that a simple step to the side by the player exposes that cone behind the column. OUR decision would be to find something that is not only currently in LOS shadow but likely to stay that way from a variety of places in the room.

The only way to determine that is to case a number of LOS checks. These can be done from scattered room locations or points selected by an algorithm based on the player''s current location and where he is likely to get to anytime soon. This now complicates the situation in that we are not just able to use the simple LOS checks done by the graphic engine. If we want 10 check points, we have to do 10 LOS checks. That doesn''t even include the algorithm(s) to determine the check points themselves.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Why use LOS tests though Dave, over say the polygons of the NPC that are clipped during the drawing of the scene. Since this drawing is done from the players perspective, it automatically tells you which parts of the NPC are not visible to the player.

As to the problem of short term cover - which you mention with the pillar example - why not use an approximate player trajectory and the bounding box of the covering object to update the cover, given the trajectory. I''ll explain what I mean in a little more detail.

Assume first that we know the visibility shadow cast by an object. We can define this by a polygon created by extending LOS rays from the player to each ''corner'' of the object created by projecting it into the camera plane (which you could actually pull out of the graphics engine for the previous frame). Let''s assume that we''re dealing with the visibility shadow cast by the bounding box of the object rather than the exact edge, since this is a good first approximation.

To extend this polygon to 4-D, computer the angular rate of change of the player relative to each corner and rotate that corners LOS rays according to the angular ROC.

This may be more efficient than multiple LOS checks, or it may not. I''m not really sure how efficient it could be made... but it''s an idea to consider.

Cheers,

Timkin

Unfortunately, modern graphic pipelines (on PCs at least) do much less on the CPU. I don''t think cliping information is generally available anymore; similarly, shadows in real time lighting systems are calculated entirely on the GPU, meaning that the AI systems have no idea what areas are lit or not.

Now, this work could be duplicated on the CPU for the AI, though I would have a hard time convicing people to accept this trade-off, as I would be arguing that we undo advantages gained in the last 3 years of GPU advancement.

I think it is still worth considering, though it may make sense to have a simplified version of as much of the geometry as possible to make this cheaper, as it does not need to be super accurate.

@BrianL
Currently (at least in the games i play) the Ai only attempts to destroy the player (tho most just are going on camacazi missions). In the NPC i am working on, i''m trying to make it ''live'' longer, eg. taking cover under fire, and only occasionally going out on camacazi missions.

It should only attack when possible (when the combined cost(possibility of injury) of getting to the safest spot to attack the player is low enough). And move to safe cover. (if the cost of getting there is lower then the cost of staying under current cover).

I also think that anywhere the Player can''t shoot it is a good place to hide... (these things are footsoldiers, there meant to be smart... not very smart (i only have so many clocks/frame!)

@Extrarius, thank you for the link... i am checking that now...
But these units are only footsoldiers... But still thanks (could be usefull for the bosses...).

quote:

---

Original post by BrianL
Unfortunately, modern graphic pipelines (on PCs at least) do much less on the CPU. I don''t think cliping information is generally available anymore;

---

Do you think then that this might be a case for either an AI board that computes this information for itself (along with other useful information that the AI could use pertaining to the physical layout of the environment... e.g., for pathfinding); or, the extension of the graphics card to include hardware for extraction of important domain information, possibly in a lower resolution, for use by game AI?

Timkin

quote:

---

Original post by Timkin
Do you think then that this might be a case for either an AI board that computes this information for itself (along with other useful information that the AI could use pertaining to the physical layout of the environment... e.g., for pathfinding); or, the extension of the graphics card to include hardware for extraction of important domain information, possibly in a lower resolution, for use by game AI?

---

The later of these options would result in a stall as the CPU waits for the information to be processed by the gfx card.

The former option of a separate AI board would definately be interesting, however I have my reservations as to just how useful it would be. IMHO AI in its current state is still too dependant upon the application to be able to develop a general purpose AI board, the best you could get would be a set of unconnected functionallity such as A* path-finding, neural net evaluation and backpropogation, dataset correlation, etc. I think that AI is better kept on the CPU where the most flexibility is possible and moving more well-defined functions such physics off the CPU.

Another approach would be to not calculate the entire shadow zone of all the objects in the room... but rather to just draw a line from the shooter through the center of the object. Fine tuning of a hiding place (e.g. peeking out) is only done once you get to the spot so we don''t need to know exactness. Here''s a list of tasks in order that I envision:

(for entire room)
* Ident all objects in room (place in list).
* Remove those not large enough for cover.
* Draw a line from shooter through center of each object.
* Check for avail room BEHIND object (opposite side from shooter). Remove those without avail room.

(for each agent - "GoToCover" state)
* Sort list by distance from their location
* Starting with nearest, test for usable quick path
* If path is usable, go there, else check next location in list

(once there - "ArrangeInCover" state)
* Determine more accurate "shadow zone" of object - can be used to either fine-tune cover (hide MORE) or to peek/fire around cover.
* Poll once in a while or when threatened for "better cover" (uses "GoToCover" state above)


Alternately, the algorithm that sorts the potential cover spots simply by distance could include a combined algorithm that rates both the distance and the "quality" of the cover. However, the quality is either going to be something subjective such as materials (metal drum beats wooden desk) or size (back to the shadow zone stuff again). The size calculation can be done a little quicker by just measuring the size of the bounding box of the item - but that doesn''t work for all possibilities. A large item with sparse coverage would trick that algorithm.

Anyway, its a starting point.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Not that this helps the conversation in any way, but if you''re looking for a bang up example of enemies using cover effectively, check out 007: Everything or Nothing.

The enemies will get behind something (create, wall, pillar, anything) and shoot around the object while exposing not much more than their head (makes the game''s targeting system actually be used effectively).

Joel Martinez
http://www.codecube.net/

Timkin, something like that seems like more of a ''super math processor'' than an AI specific CPU. I could see something being used for physics acceleration as well as AI acceleration. I would have to talk with my graphics programmer about shadows volumes and how the cost works out.

I haven''t kept up on the discussions about dedicated AI hardware; what allows the proposed hardware designs to function more efficiently than a general purpose CPU? Is it restricted to a particular set of operations (like GPUs are), or is it more of a general purpose CPU?

Side note:

Did anyone take a look at No One Lives Forever (either the original, or the sequel)? Both games used cover. I am curious what peoples impressions were.

@Nice Coder:
I''ve got a demo available of more or less the algorithm you describe, with several options to compare and tweak. It comes with a brief manual and source code. Have a look at http:\\www.cgf-ai.com.

@Timkin:
"Why not treat the problem of cover as one involving the view as seen by the player."
Would work for a lot of games but not for games where you also have friendly AI that is supposed to act tactically sound (just about any tactical FPS right now, thank goodness).

@InnocuousFox:
"[At the GDC roundtable] ... the ideas that were floated were pre-calculated hot spots for cover (behind crates, tables, etc.) and dynamically calculated spaces (such as what Timkin wrote above)."
You can use one (pre-calculated guaranteed cover) to reduce the costs of the other (dynamic ray casts). We do so in something similar to the algorithm you describe in your other post. Cannot tell more though