Simplify 2D map to optimize pathfinding

Question

I'm working on a personal project that requires solving the well-known shortest-path problem.

I have 256x256 tiles maps like the following:

Example map

I'm only interested in white (walkable) areas. The rest are either walls or voids on the map.

Running a simple Dijkstra or A-star algorithm produces a path like this one:

Shortest path on example map

However, it takes more time than expected. When I draw every visited tile I get these images, depending on the algorithm used:

Visited tiles while finding shortest path 1

Visited tiles while finding shortest path 2

I know there is almost infinite research on pathfinding, and that's great unless you don't know where to start. The problem is quite simple, I think. The cost of every arc is simply the Euclidean distance between them. These maps have portals that shorten the path length, but I didn't add them yet. The path doesn't have to be the shortest one, either, just a reasonable one is fine.

I noticed that I could break the problem into 3 simpler problems, but to do this I need this kind of modification on the map:

Simplyfied paths

Now, the walkable areas are the gray ones. Finding the shortest path between any pair of gray points is almost free, even with bare Dijkstra.

The partition of the problem would look like this, when trying to connect points A and B:

1. Find the closest gray point to A. Let's call this point Ag.
2. Find the closest gray point to B. Let's call this point Bg.
3. Find the shortest path for these pair of points: (A-Ag) (Ag-Bg) (Bg-B).
4. The concatenation of these 3 paths are the solution to my problem.

A and Ag should be (almost) linearly reachable to one another, the same with B and Bg. It's possible that the closest gray point to A is on the other side of a wall, so we should find the next closest Ag point. But this is just an idea.

The concrete question is: Is there an algorithm to make such simplification on the map? or what shortest path algorith would you suggest?

Thanks!

Answer 1

The direct answer to your question, whether there is such a simplification on the map, is yes. The approach you came up with to provide a predetermined graph, a roadmap if you will, to find viable paths in negligible amounts of time, is a good one. I am not sure how you managed to create the quite decent looking "simplified paths" shown in grey, but two formally well defined standard algorithms to find such graphs are the Visibility Graph and the Voronoi Graph. These are two geometric concepts that translate well into the grid world you are in. As long as your map remains unchanged, you can compute as many paths as you want with the approach you already lined out: connect the start and the target nodes with the Voronoi / Visibility / Your Custom Graph in the shortest possible way (or the optimal way, which is almost never the shortest) and use A* or Dijkstra to find the shortest path in the graph.

However, this only makes sense as long as your map remains constant. If your map changes, you would have to repair or recompute the graph structure. In such cases it is better to stick to one shot path finding algorithms. Plain vanilla A*, the one you are using right now, is one of the best one shot algorithms and it should be able to find paths in a 250x250 grid in well below 50 ms of time. I am referring to this paper where A* has been used to find paths in about 50 ms in a 1000x1000 times grid. A good implementation can make a big difference in runtime. If you require any angle paths, which are smoother and shorter than the vanilla ones consisting only of multitudes of 45°, you could use LazyTheta*. In conclusion, exploit the simplest A* approach first to its full potential and see if the runtime and quality suffices for your purpose. If not, then upgrade to a precomputed Graph approach.