0
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – House
    Commented Dec 30, 2012 at 16:30
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – House
    Commented Dec 30, 2012 at 18:10

2 Answers 2

Reset to default
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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*.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .