Artificial Intelligence - when to update pathfind?

Question

Right now I have a pathfind algorithm A* so I'm already using it to move the player around. My problem comes to the NPC'S. They find the path to the player but if the player change the position they have to find a new path all the time? or there's something I can do to avoid so many calculations?

Example I have an enemy 5 units of distance from the player. He moves to 4 units of distance based in the path he already found and then search the path again? or does he make half of the path until he search for a new path?

I imagine making that for 5 or more enemies may make the game slow? (I never tested it before) Any toughs?

Answer 1

I imagine making that for 5 or more enemies may make the game slow? (I never tested it before) Any toughs?

Don't optimize until you run into performance problems. Get the stuff working first before you make things more complex than they need to be.

That being said if you do run into problems I see 2 simple ways to optimize this issue.

1. Add an event to your player that is triggered when the players character changes orientation. The AI can subscribe to this event and update only when needed.

2. Update the check at a slower rate than the default 60hz of the XNA update loop. The average human reaction time is about .2 seconds so nobody is going to notice (or care) that the AI isn't adjusting to their movements on the millisecond. Even running the loops as slow as 5 - 10hz should be hard for a player to notice and take a lot less time.

Super Official Research

Answer 2

Here are some reference materials on a similar A* search algorithm called Fridge search. This is a search which uses the last search path as a reference point to the new search path that needs updating. I believe this will help a bunch. My buddy in my CS class showed me this and it solve this same issue for me... that is if I understand your question correctly.

• http://en.wikipedia.org/wiki/Fringe_search
• http://webdocs.cs.ualberta.ca/~yngvi/pdf/BjornssonEHS05.pdf
• http://webdocs.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf
• http://www-cs-students.stanford.edu/~amitp/gameprog.html
• http://forum.unity3d.com/threads/44229-Fringe-vs-A*/page2

Answer 3

If your map is static (or mostly static), you might want to consider using Dijkstra's algorithm, instead of A*. Precalculate it for every node in every map and store them as game data. When loading a level, load every shortest path for each of its nodes, and you won't need to calculate anything at runtime.

If your map is dynamic, however, Dijkstra is not an option. I'd recommend recalculating things every so often, or once the main character has deviated a certain distance from the previous known destination. It might be a good idea to run this calculations in a secondary thread. Once the calculations are ended, update each enemie's path. This will probably make their reactions a bit slower, but that often looks more natural.

Answer 4

By accident I was playing Killing floor and I notice how their A.I. mostly works by look. They have a huge number of monsters running around in 3d (my game is 2d by the way). So it looks like the monsters walk to a point and after they reach that point they just rush to the player. I believe this can be optimized by detecting an area where the players are and make several paths to "surround" this area. Also I believe they might be using the same path (from previous monsters) to get to the players.

Another thing I notice is that most of the monsters might never recalculate the path since they die before getting to the player. This might also turn to be an "accidental" optimization.

Finally i remembered the days I use to level design for half life and I recall of having map nodes to define pre defined paths which the monsters would use as guides to turn around. These were only used when the characters went to a certain distance around the node. But i don't believe this would be a good solution.

Answer 5

There is no single answer, the exact frequency probably changes from game to game. You're right in that recalculating every frame is probably not all that necessary or optimal. Decouple the pathfinding update from the other updates, and tweak the frequency to your liking. Find the point that is just often enough to not look unresponsive.