Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

up vote 10 down vote accepted

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

share|improve this answer
    
I was hoping to find something delicious (for supper) when I clicked the link. :P I'd fix it myself but I need to make more than single character changes. –  Richard Marskell - Drackir Feb 3 '12 at 17:41
    
Good catch I fixed it :) –  ClassicThunder Feb 3 '12 at 17:53

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.

share|improve this answer
    
Because I don't have any points on here it wouldn't let me post multiple urls so I've added them in the comment section to get around this. webdocs.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf www-cs-students.stanford.edu/~amitp/gameprog.html forum.unity3d.com/threads/44229-Fringe-vs-A*/page2 –  vternal3 Feb 9 '12 at 21:03
    
Added them for you. :) Also, I just noticed you wrote "fridge" instead of "fringe". –  Richard Marskell - Drackir Feb 10 '12 at 18:14
    
Thanks for the edits XD –  vternal3 Feb 22 '12 at 19:14
    
No problem. :-) –  Richard Marskell - Drackir Feb 22 '12 at 19:16

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.