# Length of the Shortest Path

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.

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!

1 Like

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