-2

I'm interested in attempting to (quickly) the shortest paths for a given grid. The grid is n by m where each node corresponds to a position of x,y. Each node can be traveled to by all adjacent nodes with with either a cost of 1 or infinity from adjacent nodes (meaning that's its an unweighted graph where some nodes are impassible). I haven't chosen constraints on n or m yet but I'd like to be able to pathfind a 100 by 100 graph. I've already tried a couple of options but none have been fast enough. However, the constraints on the problem (unweighted, easy heuristic), make me think that someone might have a better solution to the problem.

One option that occurred to me (and I would like to do if possible) was pre-generating all of the paths for all options of n and m between 0 and 100. Obviously, that takes a significant amount of time but I was wondering if maybe there was some sort of online resource where I could find paths. Alternatively, if anyone has a method of computing all of the paths for all of the graphs reasonably quickly that would be great to.

Sam H
  • 91
  • 1
  • 9
  • pathing is a very well worked on topic for an kind of autonomous, self-steering vehcle/robot. googeling "algorythm for finding path" should give you 1 or 2 to try out... start with https://de.wikipedia.org/wiki/Dijkstra-Algorithmus , then google A* and read this https://stackoverflow.com/questions/10995699/how-do-you-use-a-bidirectional-bfs-to-find-the-shortest-path – Patrick Artner Jan 06 '18 at 23:32
  • I've tried the simple ones (A* and BFS. Dijkstra is simply worse than A* since I have a heuristic) and I've written code to make a lot of it more efficient (like remembering previously completed results). My problem is that A* still is too slow for what I would like. I can probably come up with a way around the issue but ideally I would precompute paths. My question was whether anyone had a particularly good solution for an unweighted grid with cartesian coordinates (which is something I can't find) – Sam H Jan 06 '18 at 23:35

1 Answers1

-1

No one seems to be commenting on this question with anything very useful but I'd like to note that the comments given above are not entirely correct on the point that A* is the best solution. This isn't exactly an answer but I thought I would answer my question with some of the information I have found.

JPS, a jump point search: https://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm--gamedev-5818 can be used for an 8 way grid (a logical way of doing any cartesian grids) and is certainly one way of improving A* (though there may be others that people more informed on the topic could provide)

In addition, localizing the graph problem to smaller areas may help solve the problem for a general graph pathfinding algorithm

Sam H
  • 91
  • 1
  • 9