Help me optimise my pathfinding
Author
I''ve got A* path finding working but I''ve run into a specific case that can really hurt performance. If a creature I want to attack is completely surrounded by other creatures A* will search until it maxes out. At first I though you could reverse the way A* searches from dest to source. But you encounter the same problem if a creature is surrounded by enemies and wants to go to another place.
I have heard of a search method (can''t remember the name) that searhes from both ends at the same time and when the two meet in the middle you have a path. But I don''t know how expensive it is. I was going to use a cheap version of this as a quick test before I used an A* search. Does anyone know the name of this search and if there are any sample implementations out there?
Also has anyone got any other ideas I can try to solve the creature surrounded problem?
If you are truly using A* from the destination as well as the source, then wouldn''t the (surrounded) destination search get to a point where it could no longer explore options without retracing its steps? And at that point, wouldn''t it know that it isn''t getting anywhere and decide to quit?
Dave Mark
Intrinsic Algorithm Development
"Reducing the world to mathematical equations!"
Dave Mark
Intrinsic Algorithm Development
"Reducing the world to mathematical equations!"
As it''s been said, bidirectional A* will solve your answer.
Two more points:
- you might want to do your pathfinding without taking into
account any characters. Indeed, chances are that once the
character arrives at the desired point, characters will
have moved anyway. More, when you''re blocked by a character,
it''s often easier to deal with this directly through some
"push" action than to try to A* around a moving obstacle.
- Hierarchical pathfinding will help there also. First compute
a rough path, then compute a precise path for every rough
large tile you step on. This way, the path is computed as
the character moves, which has two main effects: the load
is balanced over the whole travel time, and the delay between
path computation and actual move is lowered, meaning paths
will less likely be obsoleted by moving obstales (be they
characters or moving fixtures).
--
Lyrian
Check out my RPG, <a href="http://lyrian.obnix.com/valkin2/en/">Valkin2</a>
Two more points:
- you might want to do your pathfinding without taking into
account any characters. Indeed, chances are that once the
character arrives at the desired point, characters will
have moved anyway. More, when you''re blocked by a character,
it''s often easier to deal with this directly through some
"push" action than to try to A* around a moving obstacle.
- Hierarchical pathfinding will help there also. First compute
a rough path, then compute a precise path for every rough
large tile you step on. This way, the path is computed as
the character moves, which has two main effects: the load
is balanced over the whole travel time, and the delay between
path computation and actual move is lowered, meaning paths
will less likely be obsoleted by moving obstales (be they
characters or moving fixtures).
--
Lyrian
Check out my RPG, <a href="http://lyrian.obnix.com/valkin2/en/">Valkin2</a>
If you can easily discretise your world into cells, use the distance transform method for determining a rough path. You can then use either a reactive behaviour model or a steering behaviour to move from one cell to the next, depending on how cluttered cells are with obstacles (including other agents).
Cheers,
Timkin
Cheers,
Timkin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
