Pathfinding in non tile-based 2d map (maybe potential field)

Question

I am developing a top-down 2d zombie shooter in AS3. I have implemented collisions against segments (line from point a to point b), polygons (array of points, convex) and round obstacles (center and radius) Player and enemies are basically moving round obstacles, with different radii.

Now, I'm having trouble with zombie AI's pathfinding. I have read about potential fields, and I found it fascinating, but I can't figure out how to adapt it to a non tile-based map. I can calculate the distance from a point to the closest obstacle, and get the obstacle repulsive potential in that point. I don't know how to get the player's attracting potential in that point though. In tile-based maps you use the A* algorithm, considering every walkable tile as a node. This is my first problem.

Once I have calculated the player's attracting potential in a point, what I get is a Number. In tile-based maps, I would test this number against the potential of the 8 adjacent tiles, and move the enemy to the tile with the lowest potential. In my non-tile based map instead I do not have a fixed set of tiles to test, so I can't understand how to get the moviment vector to apply to the enemy. This is my second problem.

If I, say, set a waypoint every x*y pixels, I could use it as the centre of a tile, but that sounds very unelegant, mainly because enemies would be forced to move along the 8 directions of adjacent nodes.

Should I forget PFs and try a different approach?

Answer 1

Use finite differences. The potential field method relies on computing a function which is at a minimum around your target, and increases going away from that point. This acts as an "attraction" for the zombies, in your case. Then, obstacles are given a repulsive force, by adding in a term for

P(x) = p_target(x) + sum(p_o(x) for o in obstacles)

Here p_target should be small around the target, and grow larger the further you are. Typically:

p_target(x) = |x - target|

i.e. the potential is just the distance to the target location (|*| is length). Similarly, a common :

p_obstacle(x) = 1 - sqrt(min(|x - closest(x,obstacle)| / delta, 1))

where closest(x,obstacle) is the closest point on the given obstacle to the point x, and delta is the distance at which the obstacle is ignored by the zombies. This defines our potential function.

Now we want the gradient of this function, which we can use finite differences to obtain. We evaluate the vector <P(x + <0.1,0>)-P(x), P(x + <0,0.1>)-P(x)>, and normalize it. This gives us a direction to go in. Note that the discrete version of this is exactly the "evaluate at all tiles and pick the lowest one" that you describe - this is the continuous version.

Potential fields do not require any sort of tiles or subdivision of space, such as quadtrees, etc., as they are defined continuously through space. However, in our formulation of the obstacle function, the influence falls to zero when you are further than delta from an obstacle: so such spatial division would be helpful in only considering the obstacles that actually have an effect. Otherwise the sum above is over all obstacles, which isn't very efficient. Also, by calculating this function on a grid first, each zombie does not need to re-evaluate the sum, which could get expensive if you aren't being clever about which obstacles you are summing over. The absence of grids is one of the benefits of this method.

On of the drawbacks is that zombies will not route around obstacles, the can get "stuck" inside of rooms if the door is on the other side from where the player is. Perhaps this is desirable for zombies, creatures of lower intelligence? If you want your enemies to intelligently route, then you could try a hybrid approach.

Answer 2

I did some research and checked and benchmarked some methods. I found this library which could be easily used with a navigation mesh to create a fluid motion.

http://gamma.cs.unc.edu/RVO2/downloads/