Sign up ×

I have been looking at different path-finding algorithms for my game. I have almost settled upon D* Lite, but have a question. (perhaps I missed it in the documentation) - Are there any algorithms, D* included, that allow for squares that are less desirable to pass over, but still possible, should there be no other way? I believe that I saw this in A* but I believe that I need it dynamic, as I will be having objects placed and removed from the map.

UPDATE: Is it possible to have levels of undesirable squares? Eg. Some still arent desirable, but are better than really undesirable ones

share|improve this question
Most of these algorithms have a cost for a node. Increase the cost of the less desirable nodes. The algorithm will choose the least expensive path. The cost can be something like an integer or float value, which will allow as many levels of undesirable-ness as you want. –  Byte56 Dec 30 '12 at 16:30
Do note that a dynamic algorithm assumes changes while the algorithm is running. If you're just adding and removing objects from your world, you could probably use regular A* if you're not going to be adding objects while the algorithm is running. –  Byte56 Dec 30 '12 at 18:10

2 Answers 2

up vote 2 down vote accepted

See Collaborative Diffusion. This approach is computationally cost-effective and implictly addresses the issue of dynamic obstruction.

share|improve this answer

I do not know the algorithm but wikipedia writes:

The original D* was introduced by Anthony Stentz in 1994. The name D* comes from the term "Dynamic A*", because the algorithm behaves like A* except that the arc costs can change as the algorithm runs.

Isn't it enough to put a high cost on the squares that are less desirable to pass over ? This way if there are no cheap squares the expensive one are chosen.

Answer to your "Update": This is just a question of cost, the higher the cost of a square is the less desirable the square is.

disclaimer: my answers are based on my knowledge of A*.

share|improve this answer

Your Answer


