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

Roland_Y · June 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

MikeHart · June 2012

If it is pure LUA, then on mobile devices it will not be fast enough.

techdojo · June 2012

That would actually be a good candidate for a native plugin - pass the map in and get your response back

Roland_Y · June 2012

@MikeHart : I don't really understand....
"Not fast enough because it features Lua ?" What's the point ?

@techdojo: Oh, thanks!

MikeHart · June 2012

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.

Roland_Y · June 2012

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!

MikeHart · June 2012

Good for you then

)

ndoss · June 2012

Neat library, I plan to give it a spin. Thanks!

Roland_Y · June 2012

You're welcome!

GregBUG · June 2012

@Roland_Y
thanks for your library. i'll try.

ciao ciao
Gianluca.

Magnusviri · June 2012

@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?

Roland_Y · June 2012

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.

Roland_Y · June 2012

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...

Magnusviri · June 2012

Having a Gideros example project would help a lot in evaluating if this project can do what a developer needs.

Roland_Y · June 2012

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!

atilim · June 2012

@Roland_Y great! thank you

@Magnusviri Currently if nobody creates a Gideros example project, I'm willing to create one.

Roland_Y · June 2012

@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.
Please, go ahead!

atilim · June 2012

@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.

Roland_Y · June 2012

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.

Roland_Y · June 2012

@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.

Roland_Y · August 2012

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.

Find the latest version on Github.
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!

jack0088 · September 2012

@Magnusviri Currently if nobody creates a Gideros example project, I'm willing to create one.

Any progress so far?

Roland_Y · September 2012

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.

Nascode · September 2012

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?

Roland_Y · September 2012

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.

Roland_Y · September 2012

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!

ar2rsawseen · September 2012

@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

Roland_Y · September 2012

@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.

ar2rsawseen · September 2012

Output is:
from file1
from folder1.file1
from file1 file1
from folder1.file1 folder1.file1

Roland_Y · September 2012

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 ?

ar2rsawseen · September 2012

ok it seems you're right I'v excluded all files except main.lua from execution

from file1	file1
from folder1.file1	folder1.file1

Howdy, Stranger!

Categories

In this Discussion

Top Posters

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

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

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

Comments