Length of the Shortest Path

Authoring Twine
,
1

For my work in progress I need a pathfinding algorithm, and I figured that I should ask here before reinventing the wheel.

More specifically, I need a function (or something similar) that will take two points as arguments and return the length of the shortest path. Has anyone written a library (or whatever the equivalent of that would be for Twine) that does this sort of thing? If anyone knows of JavaScript code that might be easily adapted to SugarCube, I would be interested in that as well.

2

Generally speaking the A* pathfinding algorithm is used for things like this, though there are a variety of other pathfinding algorithms out there.

You can find a JavaScript implementation of A* in the astar.js library. You can see an example of that library in use at this online demo.

To use that in Twine/SugarCube, just include the astar.js file in the same directory as your game’s HTML file, and then do something like what I show in my “Loading External Scripts” sample code. (Click “Jump to Start” in the UI bar to see other sample code there.)

Hope that helps! :slight_smile:

1 Like
3

A* might be overkill here, since the edges are unweighted. It still works, of course, and is very powerful and general, just like @HiEv says. Just set all weights to the same (positive) value.

But in this case, a breadth-first search is probably easier to wrap one’s head around. It works like this:

We compute the length of the shortest path from Node A to every other node, and store it in an array called shortest_distance. Once we have this array, the answer is of course shortest_distance[B].

First we set shortest_distance[A] = 0. Then we create a work queue, initially containing just A. Then, in pseudo-code:

While work queue is non-empty:
    Take the first element, E, out of the work queue.
    For every neighbour N of E:
        If shortest_distance[N] is undefined:
            Let shortest_distance[N] = shortest_distance[E] + 1
            Add N to end of work queue (if it's already there, you don't have to)

Actually, you can stop the algorithm as soon as you’ve stored a value in shortest_distance[B].

2 Likes