CODEWITHSUNDEEP
algorithmsortingpath-findingheuristics
Alex
Alex

Reputation: 1337

Finding path is a mostly empty weighted grid

I need to find a path from A to B in a 8-connected grid (up/down left/right and diagonals). The problem is, this grid is mosty (25-60%) empty, but there are certain spots with high weighted values (~20 times the empty tiles' weight) that may have to be passed through. I have looked at things like A* with RSR and JPS, but those seems to be for only unweighted grids. Right now I have rolled an A* implementation, but it is slower than I would like. I don't even need a fully optimal algorithm, just something that is close.

Upvotes: 0

Views: 635

Answers (2)

Gene
Gene

Reputation: 47020

If speed is a concern, consider using graphics hardware (e.g. CUDA or OpenCL). This paper discusses a "brushfire" algorithm on a 3d grid to find a path for a 2d robot with rotation. It's almost exactly the same as your problem, although you're in 2d.

Upvotes: 0

dan3
dan3

Reputation: 2559

JPS was formulated and analyzed for uniform grids with obstacles. I think that if you treat any "unusual" tiles as you would treat obstacles, JPS will work (i.e. will let you go fast through uniform regions). JPS' author even speculated as much in the comments to his JPS blog post (and it seems fairly obvious):

simply treat any neighbour which is of a different terrain type to the current node, as forced. This will allow you to quickly search across a uniform-cost region, stop to expand a node when crossing into a different region, and continue jumping on the other side

However you seem to imply that your grid is not just non-uniform, but also has bonus tiles in addition to penalty tiles. You will need to deal with those as well (e.g. bias all grid weights up to avoid negative weights).

Upvotes: 1

Related Questions