Route-finding between known checkpoints?
I'm trying to create a sort of "crane" that moves from a starting checkpoint to a known ending point. However, it shouldn't follow a straight line there; it should be bound within what are best described as roads.
So the crane can only move along the roads, and needs to find a series of checkpoints between the starting point and the ending point. I need a good method of finding this series. Here's a picture of what I mean:
https://gyazo.com/3c76ff069715ceffe721cc3c6b7a2f9a
The black block on the right is the crane, and the gray transparent blocks on the "roads" are checkpoints. The red transparent blocks are known ending points. If I input the ending point I want the crane to travel to as the ending point on the left, what method can I use to find the a series of checkpoints between the start point and the ending point specified?
2 answers
To find the quickest route between paths, you can use a number of different methods.
Dijkstra is the most common method followed by A*. Dijkstra works by calculating all the possible routes at once and storing the shortest path for each, the advantage of using this is that you run it once and everything is done. A* works by calculating the quickest route by using heuristics.
Both algorithms are extremely complex and so I'm not going to be posting them here. If you want to learn more about the different methods of finding the quickest path, there are lots of tutorials online.
Hope this helped :)
0
You COULD make a script generate a table for each checkpoint and then in that table have a list of the checkpoints that's one "move" away, then have when the crane gets told where to go, it looks at that part's table, and then i find all the possible routes and chooses the fastest one(basicly A*. Dijkstra), I do NOT have a script for this since it would take quite a long time, but hopes this helped anyway