Jumper : Lightweight, fast and easy to use pathfinding library

Code Sharing
21

@Jmv38

Hi,
Thanks for the comment. I took a quick peek at @reefwing source. Actually, I already came accross the Astar implementation he used in FindPath.lua. It was originally written in Lua by a coder named Altair (see reference).

As for comparison, well Jumper wins here, and that is fairly normal. The fact is, Jumper’s Astar implementation uses binary heaps to maintain internally a list of expanded nodes, which results in a huge speedup for the overall process. It also has to do with the way I implemented it, trying to keep it short, clean and reusable (you can see that the astar module is used by the dijkstra module).

Well, indeed, I made a test. ‘Altair’ refers to the star implementation used by @reefwing. See for yourself the output, seems like every single algorithm Jumper implements is faster:

lua -e "io.stdout:setvbuf 'no'" "bench.lua"

Generating a grid of : 10 cells x 10 cells…

Memory used to store the grid (10 x 10): 23 kiB

DFS - path length: 33.31 - Time: 0.00 ms

JPS - path length: 32.49 - Time: 0.00 ms

DIJKSTRA - path length: 32.49 - Time: 1.00 ms

BFS - path length: 32.49 - Time: 1.00 ms

ALTAIR - path length: 37.00 - Time: 1.00 ms

ASTAR - path length: 32.49 - Time: 1.00 ms

THETASTAR - path length: 32.31 - Time: 1.00 ms



Generating a grid of : 25 cells x 25 cells…

Memory used to store the grid (25 x 25): 133 kiB

JPS - path length: 275.11 - Time: 2.00 ms

DFS - path length: 275.11 - Time: 3.00 ms

DIJKSTRA - path length: 275.11 - Time: 5.00 ms

BFS - path length: 275.11 - Time: 5.00 ms

ASTAR - path length: 275.11 - Time: 5.00 ms

THETASTAR - path length: 274.93 - Time: 7.00 ms

ALTAIR - path length: 289.00 - Time: 23.00 ms



Generating a grid of : 50 cells x 50 cells…

Memory used to store the grid (50 x 50): 525 kiB

JPS - path length: 1149.05 - Time: 8.00 ms

DFS - path length: 1149.88 - Time: 25.00 ms

BFS - path length: 1149.05 - Time: 27.00 ms

ASTAR - path length: 1149.05 - Time: 30.00 ms

DIJKSTRA - path length: 1149.05 - Time: 33.00 ms

THETASTAR - path length: 1148.88 - Time: 37.00 ms

ALTAIR - path length: 1177.00 - Time: 337.00 ms



Generating a grid of : 100 cells x 100 cells…

Memory used to store the grid (100 x 100): 2080 kiB

JPS - path length: 4892.59 - Time: 33.00 ms

THETASTAR - path length: 4892.19 - Time: 241.00 ms

BFS - path length: 4892.59 - Time: 290.00 ms

DFS - path length: 4932.36 - Time: 290.00 ms

DIJKSTRA - path length: 4892.59 - Time: 309.00 ms

ASTAR - path length: 4892.59 - Time: 317.00 ms

ALTAIR - path length: 4951.00 - Time: 5513.00 ms



Generating a grid of : 128 cells x 128 cells…

Memory used to store the grid (128 x 128): 3342 kiB

JPS - path length: 8054.19 - Time: 53.00 ms

THETASTAR - path length: 8053.79 - Time: 453.00 ms

DFS - path length: 8105.55 - Time: 705.00 ms

BFS - path length: 8054.19 - Time: 726.00 ms

DIJKSTRA - path length: 8054.19 - Time: 731.00 ms

ASTAR - path length: 8054.19 - Time: 735.00 ms

ALTAIR - path length: 8129.00 - Time: 14836.00 ms

Exit code: 0

@brookesi
I would also like to mention a few things.
Using Jumper, your tables do not have to start at 1, not necessarily. They can also start at 0, or -1, Jumper would accomodate with it.

`
– A 10x10 map, indices starting at zero.
local map = {}
for y = 0, 9 do
map[y] = {}
for x = 0, 9 do
map[y] = 0
end
end

local grid = Grid(map) – this is ok
`

Also, when trying to draw the map, you can also use the Grid module iterators. As is, it won’t be much of use, as it seems Corona’s display is kind of reverted, but in the next version of the library, I am planning to provide custom vectors for map iteration, so that one can define how he wants to loop through the map.

Ah oh, would you be interested in writing some Codea demos for Jumper, by the way ?

Thanks reading!

22

@RYonaba Correct me if I’m wrong, but I thought indexed Lua tables could only start at >= 1?

23

Thanks @brookesi.
@RYonaba thanks for the detailed analysis, that is quite interesting. About writing a demo, well yes, i was wondering if i would do one or not, starting from @brookesi example, cause it should be rather easy an fun. But since you are intersested i’ll definitely write and post one, unless sby is faster than me!

24

@SkyTheCoder lua can use anything for indexes, the question is in which order do you access the points? With ipairs() you will start at 1 and miss the 0. With pairs() you dont know where you start., nor the order. So he uses a trick, a for loop, that starts at 0. Then he will start at 0, and have the correct order.

25

@RYonaba i explored a little bit your doc. You did an awsome job at structuring and documenting your code. This is great!

26

@SkyTheCoder
Naturally, when you init a table, and start inserting things in it, indexes naturally start at 1. But nothing is stopping you to use any other values for indexes.
That is why I decided to take this into account in the way Jumper accepts maps arrays, to make it compatible with some other libraries exporting Lua arrays starting at zero (thus, without the need to defined custom offsets). AdvancedTiledLoader is an example.

@Jmv38 : Thanks for the kind words, yes, writing the documentation took a bit of time, but was very helpful in the end. The documentation itself is in written in the library source, and was generated in HTML thanks to the very nice LDoc.
As for the demo, I was technically addressing to @brookesi, but well, any contribution is welcomed and much appreciated.
Thanks!

27

Hi @RYonaba,

I am heavily using jumper in the game I am currently writing to draw realistic roads and rivers across a 2D tiled map with altitude values per tile… It is rather heavily embedded at present, but I’ll try and put something together that looks cool,

Brookesi

28

Hi all,

I have knocked up a quick demo:

https://github.com/brookesi/Codea/tree/master/src/Jumper

I’m off on holiday so wanted to get something down, hope it works…

Basically there is a colour map of 1024x768 resolution which has shading and what is called hypsometric tinting whereby you select a series of colours for different altitude ranges which blend together to give a ‘false colour’ image of e.g. green vegetation to brown rocks to snowy peaks…

Another version of the map is created which just uses a colour ramp from white to black for the lowest to highest elevation, this effectively generates a greyscale altitude map, where looking at e.g. the red component of image:get(x,y) gives you an altitude from 0 to 255…

I then bicubic reduce the size of this map to a 128x96 resolution, so one pixel of the greyscale map is equivalent to 8 pixels on the colour map and the altitude is automatically averaged out by the size reduction process.

We use this reduced ‘tile’ map to save processing power. Running the Jumper pathfinder on here is pretty quick.

Once we get the path we then draw at the ‘tile’ point onto the colour map, multiplying by 8 to scale up to the colour map resolution.

The custom heuristic function takes the elevation data into account by doing a tilemap:get(x,y) and multiplying the distance ‘cost’ by the altitude value, making high altitudes ‘expensive’ to traverse…

Hope that makes sense…

You’ll need the Lua files and the two images from the above repository, customise the image names as appropriate in the main Lua file when you import them…

Regards,
brookesi

PS The whole map generation thing is quite tricky, am happy to expand to anyone who is interested, basically its real world data with Igor shading and hypsometric tinting with pretty colour ramps!

29

How can i get the images from an ipad? I cant find a way to download them frm github…

30

@Jmv38 Hold down on the image, then select Copy, go into Codea, go to the left sidebar, go to Sprites, then Documents, then Paste from Clipboard.

I get an error for some reason when trying to load the project, though… error: [string "--[[..."]:757: attempt to index local 'startNode' (a nil value)

It draws the map if I press play afterwards, though.

Nothing happens after that… >_<

31

Hi guys,
Sorry, was done in a tremendous hurry, will check it, in throes of holiday packing… :wink:

Brookesi

32

The Jumper.lua up on Github may have been slightly out of date, have refreshed it so may be worth pulling that down again, although I’m not sure…

It certainly works for me…

Brookesi

33

Thanks for the tip @sky, but unfortunately each time i press paste from clipboard, it kills my codea… @simeon this might be a bug of last beta + ios5?

34

Try:

https://raw.github.com/brookesi/Codea/master/src/Jumper/Map1_Colour.png

https://raw.github.com/brookesi/Codea/master/src/Jumper/Map1_Elevation_Tile.png

in Safari, then press and hold and do Save Image which should drop it to your camera roll…

Brookesi

35

Output should look like:

https://raw.github.com/brookesi/Codea/master/src/Jumper/jumpertestoutput.png

Brookesi

36

That fixed it. I think part of my issue might have been I’m on a retina iPad. Importing automatically has “retina” checked, which assumes the image is retina, @2x. It resized it to be smaller. This time I unchecked retina.

37

Ah, I’m going to have to be careful of that, well, good that its working anyway, phew, can go on holiday happy… Although I will be forging ahead on Codea by the pool ;))

Brookesi

38

@brookesi ha, i hadnt tried the raw, thx. Still cant load the image, but it is not on your side.