Pathfinding Routine & Libraries for Slower Areas

[Hepth]

I'm looking for the name of a routine for pathfinding or some libraries, where it can have slow areas.

I know what A* is for binary paths, but what about paths that have regions where you might want to avoid, but only to a certain cost. Like, if there is mud that slows you by 1/2, then there are times its more efficient to cross that "mud".

I took an A* and modified it so I could put weights at each point, and it works, but I'm wondering if this has an official name? Maybe a programmer can help me.

I'm doing a hobby project where I need a 2D pathfinding over a 200x200 grid where some squares "cost" more than others, and if it can be parallelized it would be even better. It's going to be used for a Neural Net so I have to think about optimization too.

Thanks!

 

[jedishrfu]

What about using a genetic algorithm to find the best path?

Each solution would be a potential path that you score and keep if above some threshold value for your next generation. You iterate thru several generations and finally choose the one with the best score.

 

[newjerseyrunner]

I took an A* and modified it so I could put weights at each point, and it works, but I'm wondering if this has an official name? Maybe a programmer can help me.

Lightmapping, bitmapping...
I've never heard that given a name, but I know it's very common in games. I wrote a series of articles many years ago about using maps for cheap pseudo-intelligence. I always called it light mapping, because originally, that's what I figured out how to do it with, figuring out how to light a character as it moved through space.

You can have your blocks actually have multiple variables and a function that returns their weight.

 

[Hepth]

Yeah, its sort of like a greyscale bumpmap.
In a mathematical sense its like having a variable density grid, where some squares cost double to cross because they have a more dense spatial grid.
If it was in a video game (which it isnt) it'd be like having a bot cross water or jump a wall to find the minimum time path.

I could see how its lightmapping, its basically like ray tracing with different refraction indices. I'll look into that.

In the end I could just program it myself, as I have done. But I know A* isn't the fastest when there's symmetry, and I thought SURELY someone else has done this really well. Give it a greyscale bitmap and it finds the path of least resistance.

I'd rather not do it in a random way, but a path-finding way that builds from the diagonal out.

 

[JorisL]

About parallelising, it seems like it should be possible.
You're looking at a very symmetric graph. You assign a weight to each vertex (the cost to traverse the corresponding square).

How to parallelize this? I'd say divide your square map in patches (n x n or n x m doesn't really matter).
In each patch look for the optimal path.

Now comes the hard part, patching these paths together in such a way that you optimize your metric (whatever it is like time, fuel consumption, ...)
This is hard because of several reasons, some sections can be ignored but you'll need to lessen the efficiency almost always.

I drew a simple sketch here. Suppose each of the smaller grids containing a black path is such a section.
As you can see they don't align.

Suppose the best path possible is the grey one (there's a big swamp at the bottom :) ).
You'll want to go from the upperleft to it's right neighbour in this case.
However this isn't that easy since the data is quite possibly at different CPUs/cores and in different caches.
A communication step is necessary.

That's the very naive and quite possible much slower algorithm I just came up with.

Another thing you can do is create some sort of distance-function for comparing paths.
So say you have a path A that's terrible. You'll know that a path B that's "close to A" has a high probability of being a bad one as well. (close/far is dependent on the norm you create so to speak)
If another path C is very good (or good) you can restrict your search to it's surrounding. That way you'll always have a good solution(C) and might be able to improve by perturbing the path.

The latter is easier to parallelize with OpenMP. This is as far as I know the quickest way to try and parallelize some code.
If you want to go more into the computer science part where you estimate the cost of your algorithm and benchmark the code, I'm more inclined towards BSP.
Because it has a very simple cost model. And can be used as a gentle introduction to some parallel computing.

 

[pbuk]

Isn't this just a shortest route problem?

 

[jim mcnamara]

This is a well known problem that traffic flow analysis deals with - what is the fastest timewise route, not the shortest possible path. Most modern gps units with realtime access to WAZE data (or similar) use algorithms to facilitate route choice.

Maybe start with: generalized density and flow in time and space -> https://en.wikipedia.org/wiki/Traffic_flow#Generalized_density_and_flow_in_time-space_diagram

 

[pbuk]

All such problems are essentially shortest path problems with an appropriate metric applied to each route section e.g. transit time -> fastest route, transit cost -> cheapest route, length -> shortest route.

Dijkstra's method is the classic algorithm but it does not easily parallelise.