Quick Links: Download Gideros Studio | Gideros Documentation | Gideros Development Center | Gideros community chat | DONATE
Jumper : (Very) Fast Pathfinder for 2D Grid-Based games — Gideros Forum

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Jumper : (Very) Fast Pathfinder for 2D Grid-Based games

Member
edited December 2012
Jumper is a pathfinding library designed for uniform cost 2D grid-based games.
It is written in pure Lua and features a mix of A-star, Binary-Heaps and Jump Point Search algorithm.
Indeed, it is extremely simple to use, lightweight, and works really fast!
Jumper can fit in games where pathfinding is needed.

Example :
 ```local Jumper = require('Jumper.init') -- A collision map : 0 for walkable tiles, -- non-zero for unwalkable tiles local map = { {0,1,1,0}, {0,1,1,0}, {0,0,0,0}, }   local pather = Jumper(map,0) -- Inits our pathfinder pather:setAutoFill(true) -- Turns on autoFill feature local startX, startY = 1,1 -- starting node local endX, endY = 4,1 --end node local path, dist = pather:getPath(startX, startY, endX, endY) -- gets the path -- Output it! if path then print(('From [%d,%d] to [%d,%d] : Length: %.2f'):format(startX, startY, endX, endY, dist)) table.foreach(path, function(i,node) print(('Step %d: x = %d, y = %d'):format(i,node.x,node.y)) end) else print(('From [%d,%d] to [%d,%d] : No Path found!'):format(startX, startY, endX, endY)) end```
The output:
 ```main.lua is uploading. Uploading finished. From [1,1] to [4,1] : Length: 5.83 Step 1: x = 1, y = 1 Step 2: x = 1, y = 2 Step 3: x = 2, y = 3 Step 4: x = 3, y = 3 Step 5: x = 4, y = 2 Step 6: x = 4, y = 1```
Find it on Github, with Documentation, usage examples, and visual demos!
Find attached to this post a sample project with Gideros featuring the above snippet.
Hope you like it!

Page: Jumper
Github: Jumper
Tagged:
+1 -1 (+3 / -0 )Share on Facebook
«13

• Guru
If it is pure LUA, then on mobile devices it will not be fast enough.
• Guru
That would actually be a good candidate for a native plugin - pass the map in and get your response back
WhiteTree Games - Home, home on the web, where the bits and bytes they do play!
#MakeABetterGame! "Never give up, Never NEVER give up!" - Winston Churchill
• Member
@MikeHart : I don't really understand....
"Not fast enough because it features Lua ?" What's the point ?

@techdojo: Oh, thanks!
• Guru
I say pathfinding in lua (gideros, interpreted, not Luajit) on a decent sized map with a good amount of objects will take the frame rate down to much on a mobile device.
• Member
Well, I would have agreed if it was only a "simple" pathfinding (I meant A-star, DFS, BFS, etc...)

Actually I am using A-star, but with some optimisations. Jump Point Search speeds up a *lot*. Plus, internally, the library do not store nodes in a simple tables or lookup, but a proper implementation of binary heaps, which makes it faster.
On a regular map of 512x512 cells, pathing problems are solved in less than 10 ms for short paths, and less than 250 ms for more complex paths on a computer (DualCore @2Ghz, 2Go DDR2 Ram). But, making a game on a mobile, who will need a 512x512 sized map ? (unless making a Lord Of The Rings - like :P )

My point is, it's worth being tried!

Likes: phongtt, MoKaLux

+1 -1 (+2 / -0 )Share on Facebook
• Guru
edited June 2012
Good for you then )

Dislikes: MoKaLux

+1 -1 (+0 / -1 )Share on Facebook
• Guru
Neat library, I plan to give it a spin. Thanks!
• Member
You're welcome!
• Guru
@Roland_Y
thanks for your library. i'll try.

ciao ciao
Gianluca.
TNT ENGiNE for Gideors Studio - Particle Engine, Virtual Pad, Animator Studio, Collision Engine - DOWNLOAD NOW !!! IT'S FREE!!! -
www.tntengine.com
• Member
@Roland_Y, I looked at this and it requires the Love Framework. Since it is Lua I'm guessing it will work with Gideros? Are you planning on making a Gideros demo project?
• Member
Hi Magnus,
The library doesn't use Love by itself. Just the public demos featuring Jemper did.
Jumper is abstract, it uses pure Lua, then you won't have any trouble using it with Gideros, since Gideros features Lua.

Well, I think I can consider making demos for Gideros, for more clarity. But you can try it by yourself, using the base clode I have given.
• Member
Hi,
I am actually walking towards a new implementation. I am actually aiming on improving speed, getting rid of some tiny bugs in the first release, and make the whole thing a light-weight. I am thinking of bypassing the internal virtual grid, acting directly on the map table passed on initialization...This will make preprocessing step no more necessary, and will lessen memory usage.
Though the first release was really light-weight and fast...

Likes: atilim

+1 -1 (+1 / -0 )Share on Facebook
• Member
Having a Gideros example project would help a lot in evaluating if this project can do what a developer needs.
• Member
Hi all,

I've been working on updates to this library.
I've added a path smoother utility, and implemented a solution to handle 4-directions pathfinding (straight moves).

It runs fine, though there are some little optimizations to bring to this.
All issues are now fixed, and new demos are available for testing (Compatible Mac, Linux and Windows) in the download section.

See : https://github.com/Yonaba/Jumper

Hope you like it!

Likes: atilim

+1 -1 (+1 / -0 )Share on Facebook
• Maintainer
@Roland_Y great! thank you
@Magnusviri Currently if nobody creates a Gideros example project, I'm willing to create one.
• Member
@Roland_Y great! thank you
@Magnusviri Currently if nobody creates a Gideros example project, I'm willing to create one.
Thanks Atilim. Actually, I am very interested in your proposal.

• Maintainer
@Roland_Y Already started playing with it Your code contains some variables like _PACKAGE. I think they are related to Love2d, right? But there are only a few so it will be easy to adapt them.
• Member
Hi,
That's wonderful. I can't wait to see your results.
Where exactly did you catch that _PACKAGE variable, I mean, in what table.
Fact is, it is not related to Love2d, just Lua's module. It is just a variable holding internal path (as string) that each component of the library uses to be loaded properly.
• Member
@Roland_Y Already started playing with it Your code contains some variables like _PACKAGE. I think they are related to Love2d, right? But there are only a few so it will be easy to adapt them.
Did you have it working ?

I've been making some progress on this. Actually, there is some little issues with straight moves handling, yet all works fine. I'll be updating the repository soon, I guess.

• Member
Hi folks,

Jumper now moves to v1.2.
I've been working recently on some core improvements. Not exactly on the library itself, but on its third-parties libraries.

I published recently a 30-lines library for object orientation,30 Lines Of Goodness that Jumper now uses as a base for its pathfinder, grid and node classes, instead of my previous Lua-CLass-System.

Added to that, the other third-party module Binary_Heaps, internally used to optimize openlist/closedlist search have been updated.

There was a little problem that is now fixed. Previously, requiring Jumper would pollute the global environment with a table, giving full access to the pathfinder class. That was due to the way I was using the module system. It is now fixed.

All demos/tests downloads have also been updated, and are now fully Mac OS X and Linux compatible (hopefully).
Feel fry to try and provide feedbacks.
Thanks!
• Member
edited September 2012
@Magnusviri Currently if nobody creates a Gideros example project, I'm willing to create one.
Any progress so far?

Owltwins. Smart design and creative code.
»Gideros Illustrator« - [svg|xml] scene designer using Adobe Illustrator®™ Within one line of code!
• Member
Hi all,

I've been working on some updates.
Jumper nows works a little bit faster. I made some enhancements on return values (making profit of Lua's ability to yield multiple values instead of packing them into tables). As a result, internal processes runs faster and reduces the memory footprint overall.

I've also added an autosmoothing feature that can be turned on/off.

I've also added chaining feature that could be interesting when one feels the need to reconfigure a pather instance in a quick and elegant manner. All setters are supported.

Documentation, and demos have been updated.
Hope you like it!

See Jumper on Github

PS: Actually, I would love some demos with Gideros. As i'm working with some other frameworks, I don't know much of Gideros's API and I miss time to get my hands with it. So I am looking forwared some kind people that would gently propose a little demo, self explanatory, on how to make use of Jumper with Gideros. Would be greatly apreciated.

• Guru
Hi @Roland_Y
thank you for your update, haven't tried Jumper yet but it looks awesome.

What method do you choose to check memory footprint? And is LOVE the other framework you are working now?
have fun with our games~
• Member
Hi @Nascode,

I use profilers, and some benchmark map tests to ensure that any update made results in a faster search and what are the bottlenecks in the code to be optimized.
Actually, I essentially make my visual demos with Love2D, just because I'm used to it. But, Jumper's is pure Lua, it isn't related with Love2D, and then can be used with any framework featuring Lua.
• Member
Hi all,

Jumper now moves to v1.3.1.
I've changed the way differents files were called internally, to make Jumper independant from Lua's built-in module function. Some people were complaining about some errors when calling the library, that should be fixed now.
Added to that, Jumper's should be now compatible with Lua 5.2 (but not fully tested yet, though).
Some bugs about the global env pollution with globals generated by Jumper were also fixed.
Have fun with it!
• Maintainer
@Roland_Y
Gideros still does not like this statement:
 `local _path = (...):gsub("%.init", "")`
Error:
 ```init.lua:24: attempt to index a nil value stack traceback: init.lua:24: in main chunk```
Test project: http://appcodingeasy.com/Jumper.zip
• Member
@ar2rsawseen:
Weird... I can't debug right, as I don't have Gideros Studio on the computer I'm working on right now.
In the meantime, can you try this and tell me what's the output ?
PS: You may have t make some adjustements with Gideros to have it working.
• Maintainer
Output is:
from file1
from folder1.file1
from file1 file1
from folder1.file1 folder1.file1
• Member
That's odd. Did you run only the file main.lua ?

I was expecting just two lines in the output, something like this:

Fact is, when you call a file B from file A using require, it spawns a local string variable within the chunk of file B, that you can catch with the following assignment:
 ```-- In B.lua local path = ...```
Or maybe Gideros implements require function a different way ?
• Maintainer
ok it seems you're right I'v excluded all files except main.lua from execution
 ```from file1 file1 from folder1.file1 folder1.file1```