Jumper : Lightweight, fast and easy to use pathfinding library

Hi all,

I would like to share a library I am working on.
Jumper is a pathfinding library designed for 2D grid-based games. It aims to be fast and lightweight. It features a wide range of search algorithms, built within a clean interface with chaining features which makes it very friendly and easy to use.
Jumper is written in pure Lua. Thus, it is not framework-related and can be used in any project embedding Lua code.

Here is a simple usage example for Jumper:

-- Usage Example -- First, set a collision map local map = { {0,1,0,1,0}, {0,1,0,1,0}, {0,1,1,1,0}, {0,0,0,0,0}, } -- Value for walkable tiles local walkable = 0 -- Library setup local Grid = require ("jumper.grid") -- The grid class local Pathfinder = require ("jumper.pathfinder") -- The pathfinder lass -- Creates a grid object local grid = Grid(map) -- Creates a pathfinder object using Jump Point Search local myFinder = Pathfinder(grid, 'JPS', walkable) -- Define start and goal locations coordinates local startx, starty = 1,1 local endx, endy = 5,1 -- Calculates the path, and its length local path = myFinder:getPath(startx, starty, endx, endy) if path then print(('Path found! Length: %.2f'):format(path:getLength())) for node, count in path:nodes() do print(('Step: %d - x: %d - y: %d'):format(count, node.x, node.y)) end end

The output:

--> Path found! Length: 8.83 --> Step: 1 - x: 1 - y: 1 --> Step: 2 - x: 1 - y: 3 --> Step: 3 - x: 2 - y: 4 --> Step: 4 - x: 4 - y: 4 --> Step: 5 - x: 5 - y: 3 --> Step: 6 - x: 5 - y: 1


The latest stable release of Jumper (1.8.1) can be found on github. It goes along with a very comprenhensive README tutorial, to help get your hands ready with the library and a full HTML documentation.

Important Note for Codea Users:
As-is, Jumper cannot work with Codea because of its internal modularisation (the source code is splitted in different files, for clarity and easier maintenance). However, thanks to kind contribution of Codea users, there are two alternative variations of a single-file version of the library, for your perusal, as Github Gits:

Thanks reading!

@RYonaba: this looks really nice, thanks for sharing! I especially like that you’ve included several algorithms.

Looks like a very nice tool. Thanks for sharing!
What is the performance? (how many ms to find a path in a random 128x128 map?)

@toadkick: Thanks for the kind words. Yes, I tried to include several search algoritms. Depending on the situations, one might find an algorithm to be more appropriate than another.

@Jmv38: Well, I tried to design it in a way it would be fast and lightweight. Using a simple stress test, with different map sizes, I generated some worst-case scenarios where the only solution is really long. So far, here is the output:

Generating a grid of : 10 cells x 10 cells... Memory used to store the grid (10 x 10): 13 kiB DIJKSTRA - path length: 32.49 - Time: 2.00 ms BFS - path length: 32.49 - Time: 2.00 ms ASTAR - path length: 32.49 - Time: 2.00 ms JPS - path length: 32.49 - Time: 3.00 ms DFS - path length: 33.31 - Time: 3.00 ms
Generating a grid of : 25 cells x 25 cells... Memory used to store the grid (25 x 25): 74 kiB JPS - path length: 275.11 - Time: 9.00 ms DFS - path length: 275.11 - Time: 13.00 ms BFS - path length: 275.11 - Time: 15.00 ms ASTAR - path length: 275.11 - Time: 16.00 ms DIJKSTRA - path length: 275.11 - Time: 17.00 ms
Generating a grid of : 50 cells x 50 cells... Memory used to store the grid (50 x 50): 290 kiB JPS - path length: 1149.05 - Time: 23.00 ms DFS - path length: 1149.88 - Time: 85.00 ms BFS - path length: 1149.05 - Time: 85.00 ms DIJKSTRA - path length: 1149.05 - Time: 103.00 ms ASTAR - path length: 1149.05 - Time: 104.00 ms
Generating a grid of : 100 cells x 100 cells... Memory used to store the grid (100 x 100): 1142 kiB JPS - path length: 4892.59 - Time: 106.00 ms BFS - path length: 4892.59 - Time: 946.00 ms DFS - path length: 4932.36 - Time: 953.00 ms ASTAR - path length: 4892.59 - Time: 1011.00 ms DIJKSTRA - path length: 4892.59 - Time: 1037.00 ms
Generating a grid of : 128 cells x 128 cells... Memory used to store the grid (128 x 128): 1806 kiB JPS - path length: 8054.19 - Time: 159.00 ms BFS - path length: 8054.19 - Time: 2386.00 ms DFS - path length: 8105.55 - Time: 2443.00 ms ASTAR - path length: 8054.19 - Time: 2520.00 ms DIJKSTRA - path length: 8054.19 - Time: 2532.00 ms

I am sharing the code I used as gist, feel free to try it by yourself: Jumper-1.8.1-Stress-Test.
In case you want to witness how the generated maps look like, just uncomment line 39, maps will be printed out the console output (0 as walkable cells, 1 as obstacles).

Once again, thanks for your interest.

Looks pretty efficient indeed. JPS algo seems to be a really fast one. Why is it so, if you know?

Thanks for sharing. But having downloaded all the code, I can see it needs quite a lot of adjustment before it will run in Codea. For example, I don’t believe we have a require function.

Until someone does that, it’s not going to get any use here, unfortunately. And converting it is too technical for me.

@Ignatz : I haven’t fully tried Codea by myself, and I may have missed the fact that the “require” function isn’t supported. Actually, Codea just features a small subset of Lua’s native API. However, adjusting the code to make Jumper working with Codea won’t be that hard to do, as far as I can see. I’ll be working on that on a specific branch of the repository.

@Jmv38 : Well, JPS stands for Jump Point Search. It’s a recent algorithm designed for grid-based maps, that runs very fast on some situations because it takes advantages of path symmetry, and then wisely prunes some directions while expanding the search from a starting point to an endpoint. But, it was originally designed for 8-connected grids. My implementation is a direct translation of the original algorithm, plus a few enhancements to make it work on 4-connected grids.

In Codea, you instantiate a class with

c = MyClass(parameter list)

and the class is set up as

MyClass = class()

function MyClass:init(parameter list) --runs automatically when instantiated
–code
end

@Ignatz: It seems you made a confusion, I guess you wanted to answer to this thread. :slight_smile:

Hi all,

I have ported the Jumper library to a Codea-friendly single file using a namespace of Jumper.

The code is here: https://gist.github.com/brookesi/6593116

I’ve done a fair amount of testing, and it works in my project brilliantly. I am using a custom heuristic that takes altitude data into account so my paths track rivers/roads etc. which is a joy to behold!

Many thanks to Ronald Yonaba for an outstanding piece of work and kind permission to allow me to distribute this port.

I believe there may be some work in progress to produce a ‘native’ version of the code in Codea-friendly format, and my port will suffer from not being up to date/difficult to incorporate any subsequent changes, but it is stable and is a stop-gap for now,

Regards,
brookesi

Thanks for sharing. Would you post and exemple of usage project so we can more easily enter into the code?

Sure,

There is an example at the end of the Gist, but it is not clear, I will try and sort something out soon,

Brookesi

Thanks for updating this. I have an issue with Air code and the syntax hilighting. Not a show stopper, but a sea of grey words appear after line 715 and the code show fine in Codea editor. IE 10 to and Chrome latest version.

Anyone else with this issue

@Thwapp That’s a glitch with multi-line comment syntax highlighting. It thinks the comment goes on after the multi-line comment ended. Happens a lot for me, but it’s just a syntax highlighting bug. No problem. It is annoying, though…

@brookesi : Thanks for sharing this snippet, its an awesome contribution.
I have updated the initial post to officialize your implementations.

As already mentionned, these single-file scripts were manually generated, and will not support the future updates. But at least, they are working and are based on a stable release, so that’s all fine.

I am planning to create an official branch for a side version targetted at frameworkds such as Codea, when I will have some spare time to work on this. I will be using a custom script to generate a single-file version of the lib for each new stable so that it can be available to Codea coders.

Regards,
Roland.

Hi all,

Thanks @RYonaba

Simple example as requested:

-- JumperTest

-- Use this function to perform your initial setup
function setup()
    print("Hello World!")
    
    map = {
        {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
    }
    
    local walkable = 0 -- map value you can walk on
    local grid = Jumper.Grid(map, false) -- false means do not precompute grid

    local myFinder = Jumper.Pathfinder(grid, 'ASTAR', walkable)

    local p = myFinder:getPath(1, 1, 16, 12)

    route = {}
    for node, count in p:nodes() do
        print(('%d. Node(%d,%d)'):format(count, node:getX(), node:getY()))
        table.insert(route, vec2(node:getX(), node:getY()))
    end
    print(('Path length: %.2f'):format(p:getLength()))
   
end

-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness
    strokeWidth(5)

    -- Do your drawing here
    
    for y=12, 1, -1 do -- Iterate over first dimension which is y
        for x=1,16 do -- Iterate over second dimension which is x
            if(map[y][x] == 1) then -- a wall
                rect((x-1)*64, (y-1)*64, 64, 64)
            end
        end
    end
    spriteMode(CORNER)
    for k,v in ipairs(route) do
        sprite("Planet Cute:Character Boy", (v.x-1)*64, (v.y-1)*64, 64, 64)
    end      
end

```


Please note the following when using Jumper:

The map is declared as a table of tables, a two-dimensional array. The first dimension of the array is actually the y values, e.g. each row in the first dimension contains a table of x values...

So when you iterate over 'map', you are iterating down the map in the y-axis... This means that from a screen perspective you need to transpose 'y' as looking into the screen at the map table, map[1] is actually at the 'top' of the map, but the origin of the screen is bottom left, so to *draw* map[1][...] you need to flip the y... 

Be very aware of this when you come to display the results, you have to look up map[y][x] for example to find the walls...and to draw you flip the y. 

As tables start from index 1 you have to draw at x-1, y-1 as the screen origin starts from (0,0)...

I hope that makes sense...

Regards,
Brookesi

Thanks for he example @brookesi.
Could you change the way the code is posted to use the standard ‘blue format’? I cant even select it from my ipad the way it is formated… So i cant run it… Thanks!

Ah yeah, what a pain, I like the syntax highlighting of the

 tag

~~~

-- JumperTest

-- Use this function to perform your initial setup
function setup()
    print("Hello World!")
    
    map = {
        {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
    }
    
    local walkable = 0 -- map value you can walk on
    local grid = Jumper.Grid(map, false)

    local myFinder = Jumper.Pathfinder(grid, 'ASTAR', walkable)

    local p = myFinder:getPath(1, 1, 16, 12)

    route = {}
    for node, count in p:nodes() do
        print(('%d. Node(%d,%d)'):format(count, node:getX(), node:getY()))
        table.insert(route, vec2(node:getX(), node:getY()))
    end
    print(('Path length: %.2f'):format(p:getLength()))
   
end

-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness
    strokeWidth(5)

    -- Do your drawing here
    
    for y=12, 1, -1 do
        for x=1,16 do
            if(map[y][x] == 1) then
                rect((x-1)*64, (y-1)*64, 64, 64)
            end
        end
    end
    spriteMode(CORNER)
    for k,v in ipairs(route) do
        sprite("Documents:road", (v.x-1)*64, (v.y-1)*64, 64, 64)
    end      
end
~~~

Finally i could try it! Thanks!
It looks good. Did you compare with the A* algo published 1 year ago by @reefwing on the forum? How does this one differ?

The algorithm is much the same except that Jumper has ‘pluggable’ algorithms, you can choose from Astar, Djikstra. Jump Point Search etc., and it has the pluggable heuristics which allow you to manipulate the distance ‘cost’ based on some other factor, e.g. grid square height, or type of terrain or similar… Check the documentation for details…

Regards,
Brookesi