2

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!

Improve this question
3
  • The first three images with A*/Dijkstra paths are strange: the first one seems to only have considered diagonal steps. The second one has flooding in one direction but not the other. That can't be right. I'm quite sure you have an error in your code, but without seeing it we cannot help you further on that. Commented Mar 16, 2024 at 20:49
  • Hi trincot. Thanks for your response. I've been playing with some heuristics and algorithms. I think the predominance of diagonal steps comes after that diagonal steps cost the same (1) as orthogonal ones, but I use the Euclidean distance (Ed) to choose the next node. w.r.t flooding only in one direction, again, if you consider only the Ed you can see that the selection of nodes to visit points straight to the target. Commented Mar 16, 2024 at 22:53
  • But even then, A* would visit also the horizontal and vertical neighbors. I don't see that in your images. I'm convinced you have a bug in your A* implementation. You say "the selection of nodes to visit points straight to the target", but that is not true. In this image there is a lot going on in the section below the starting point, and there is no good reason why there (going up!!) and not in other directions (going down at every possible point). I really believe you should not (yet) look into the simplifications you suggest, but fix your A* search. Commented Mar 18, 2024 at 9:28

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.