Whats the theory behind a 2d game AI that runs away? How do they choose where to go? It is easy to choose where to go when chasing but not when running. This is for my game where noninfected NPCs run away from zombies

I'm no programmer but couldn't you compare co-ordinates between the uninfected NPC and a Zombie then have some algorithm to make the uninfected NPC keep maximum safe distance between Zombies? Is it a top down view? I dunno I'm just guessing =P

Going on the assumption that your NPCs do not have a safezone (like one person has already posted) or are mainly reactionary, it still isn't too hard.

If your game is tile based, you could do something like this:

//NPC has seen a zombie and will now move//find the difference between the x and y positions of the NPC and the ZombiedifX = zombie.x - NPC.x;difY = zombie.y - NPC.y;//if the value isn't zero (to avoid divide by zero and it would be useless//anyways), add the value diveded by itself (to get either 1 or -1) to the NPC's//position.if(difX != 0){NPC.x += difX/difX;}if(difY != 0){NPC.y += difY/difY;}

This 'zombie' could either be the closest to the NPC or the average position of all the zombies within the NPC's view.

If your game doesn't use tiles, you could just get the angle between the NPC and the zombie. You would then add 180 or PI to it and have the NPC move in that direction.

The simplest answer would be to use a potential function approach: Compute a "threat" function (perhaps you could use "distance to nearest zombie" (computed using the brushfire algorithm) for this) and have your NPCs always move down the threat function in the steepest direction. This would give reasonably good behavior, but NPCs could still get stuck in local minima (e.g., zombies could push an NPC into a corner; the NPC would never run closer to a zombie even though it might mean being able to escape to a larger area).

If you wanted more clever behavior than this you'd need to do some planning.

For instance, you could, for each NPC, find the path which maximizes the distance at the final time to the nearest zombie (where by 'distance' I mean "length of shortest path between points taking obstacles into account"), subject to the constraint that at step k the path be at least k steps away from the nearest zombie (change this accordingly if zombies and players move at different speeds). This would keep your NPCs alive the longest in the worst case scenario. This could be found without too much difficulty by any standard graph search algorithm like BFS or A*.

If your player can predict the behavior of zombies, then the optimal strategy will be different, but it could still be found by graph search in an appropriate state space.

I might be able to elaborate on this more later.

Quote:Original post by Emergent
The simplest answer would be to use a potential function approach: Compute a "threat" function (perhaps you could use "distance to nearest zombie" (computed using the brushfire algorithm) for this) and have your NPCs always move down the threat function in the steepest direction. This would give reasonably good behavior, but NPCs could still get stuck in local minima (e.g., zombies could push an NPC into a corner; the NPC would never run closer to a zombie even though it might mean being able to escape to a larger area).

Then again, it could be desirable that NPCs can get stuck. Humans don't always think rationally when panicked. And why won't anyone think of the zombies?!?! They have to eat too!

I've used influence maps for this.
Make a gradient circle around all threats. An agent standing on an area with a high threat rating will try to escape the threats. Use BFS to find a safe spot for him.

[EDIT: Several incorrect versions removed. This I think is right.]

Ok, here goes.

For some NPC, consider any tile that a zombie can reach before the NPC can an obstacle. You can figure this out by using the brushfire algorithm to compute the distance of each cell from the NPC and from the nearest zombie, and ensuring that the zombie distance is greater; such cells are passable.

Now, find the cell in the reachable set (which can be determined with a simple floodfill algorithm) for which the distance to the nearest zombie is maximal. You want to find the shortest path to this cell which stays in the reachable set (other paths may also be optimal, but computing them is harder).

Note that by running the zombie and NPC brushfire algorithms simultaneously you get the reachable set for free, so you don't actually need to run a separate floodfill to find it.

I'm pretty sure this is the right answer, which maximizes the time you'll stay alive in the worst case scenario.

And by "worst case scenario," I mean, "zombies that can see the future." :-)

[Edited by - Emergent on September 19, 2009 3:15:05 PM]