Gideros Forum

Roland_Y

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

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

techdojo

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

Roland_Y

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

@techdojo: Oh, thanks!

MikeHart

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

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

Good for you then :))

ndoss

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

Roland_Y

You're welcome!

GregBUG

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

ciao ciao
Gianluca.

Magnusviri

@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

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

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

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

Roland_Y

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

@Roland_Y great! thank you :)
@Magnusviri Currently if nobody creates a Gideros example project, I'm willing to create one.

Roland_Y

atilim said:
@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

@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

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

atilim said:
@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

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

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

Any progress so far? :)

Roland_Y

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

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

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

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

@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

@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

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

Roland_Y

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

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


from file1	file1
from folder1.file1	folder1.file1

Roland_Y

Okay, That was what I was expecting.
Then would you please try this (sorry, I'm bothering):
Replace the code inside "init.lua" with this:


print('From init.lua, path received from main.lua', ...)
local _path = (...):gsub("%.init", "")
return require (_path..'.jumper')

And let me know what the output is.
Thanks for the help.

ar2rsawseen

I've excluded everything except init.lua from code execution and applied your changes, here is an output:


Uploading finished.
From init.lua, path received from main.lua
init.lua:25: attempt to index a nil value
stack traceback:
	init.lua:25: in main chunk

Roland_Y

Okay, thanks for the help.
It seems that init.lua doesn't receive the expected args from main.lua.
Would you please help with one last thing.
Can you try both of these, and provide some feedback ?

PS: I'm downloading the latest Gideros,
I'll try to see what's going on with that issue as soon as possible.

ar2rsawseen

Still getting


Uploading finished.
init.lua:24: attempt to index a nil value
stack traceback:
	init.lua:24: in main chunk

for the first one, and second one outputs:


Uploading finished.
.\?.lua;C:\Program Files\Gideros\lua\?.lua;C:\Program Files\Gideros\lua\?\init.lua;C:\Program Files\Gideros\?.lua;C:\Program Files\Gideros\?\init.lua

Roland_Y

@ar2rsawseen:
I think i solved the issue, with the latest 1.3.2 version.
See the relevant commit.
The problem was due to the way Gideros run the project folder. I've managed to deal with that, while keeping Jumper compatible with some other frameworks.

I've updated the original post with and provided a sample project.
Some feedback would be greatly appreciated.
Thanks for your support.

ar2rsawseen

Yep, everything works now. Thanks ;)

Roland_Y

Thanks for tipping about that.
Well, should I expect a sweet little demo test from you ?

ar2rsawseen

Yes @Roland_Y that was the idea ;)

Roland_Y

Awesome.
As I said earlier, I'm looking forward people self-explanatory demos that will be shared as examples of use for those who can't get their hands with it.
Looking forward your work, though.

Roland_Y

Hi all,
Jumper now reaches v1.4.1.
Some changes were brought internally, but they won't affect the public interface.
Hope you like it!

Roland_Y

Hi folks,

I've been working on some changes in Jumper (now at v1.5.0)
Some people were complaining about issues with loading collision maps built with external tools and exported to Lua. Such maps were non-compatible with Jumper, as they were starting indexing at location different than (1,1).
This is now fixed. For now on, collision maps passed to init Jumper can start indexing at any integer. The only obligation is the cells must be indexed with consecutive integers.
Also, the heuristic name 'CHEBYSHEV' was removed, as it was just an alias.Now use 'DIAGONAL' instead.

I have also created a new repository (Jumper-Examples) where i'll be pushing examples of use for this library. If someone come up with a clean demo, i'll be happy to know about that.

Thanks.

Roland_Y

Hi all, fresh update.

Since the start, I had some odds with non-diagonal moves. Fact is, the original algorithm was designed to prefer diagonal search instead of horizontal/vertical search.
So I basically hijacked it, to be able to deal with diagonals and orthogonal moves. It worked, but I wasn't that much satisfied with the results. Fact is, they were too much "zigzags" at each step when a path with no diagonal moves was requested.
I took a fresh look at that recently, and I made some changes...
And the results were ashtonishing:

Until 1.5.0:

Now (1.5.1)

There's still some things I could come back on, such as find a way to reduce the expanded nodes when diagonal moves are forbidden. Anyway, that's way better than before.

Github: Jumper

Hope you like it!

Roland_Y

Hi everyone.

First of all, Jumper was updated to 1.5.1.2, bringing typos fixes and other tiny bugfixes.

Appart from that, I've been working on a seperated version to support tiles that can be crossed on specific directions, like one-ways tiles (doors, ladders, etc)...
Just want to give heads up about the current progresses on this.
Considering these conditions:

- Tiles can either be fully walkable/fully unwalkable.
- Tiles can be partially walkable, meaning that they can be crossed in specific directions.
- The overall should remain simple to use

At this point, I needed a way to represent all tiles and their "passability" (i.e how each node can be traversed). Thanks to some help with some the geniuses at @StackOverflow, I could hopefully overcome this issue.

As Lua (5.1) do not have a native bitwise operations library (and I didn't want to rely on an external C lib), I used David Manura's bit.numerlua module, from which I ripped some functions i needed (bit.band, bit.bor).

I made lots of changes internally. Well the algorithm remains the same (A* + Jump Point Search), but on the top of that, some rules to discard expanding the search process on nodes that cannot be crossed in the actual heading direction of search.

The results are clearly awesome. See the relevant screenshots below.

On this first series of screenshots, you can see the pathfinder in action, with diagonal moves allowed. Note that on the second screenshot, one tile was found passable following the north-south direction, then the pathfinder chooses it.

Here is the same situation, with only straight moves allowed.

Side note, I haven't released this modified version yet, as i'm actually trying to design a simple public interface that will let the user alter easily tiles passability rules, without having to mess with bitwise ops... Once I get this done, i'll be pushing it on a separated branch on the Github repository.

Thanks reading.

Roland_Y

Hi folks,

Little update. Indeed, that was a bugfix.
The problem occuring was a sort of "tunneling" issue, so that when the goal node was neighbouring the start node,
the pathfinder would always return the straight line, even if this would have implied going through walls, as shown in the following picture:

With the latest bugfix, I had to add an extra function that acts as a validator routine between the online jump node search process and the regular a-star evaluation. When a jump point is found, and happened to be the goal node, this routine evaluate if the pathfinder can actually enter the goal node heading straight, through this function. If not, it will choose for another possible way. All this extra-process is called internally only for diagonal mode, and on the first jump point expanded. As a result, you might no longer encounter such an issue:

Feel free to try it (Github repo).
Note that i have only updated the default branch, not the experimental version (as this might require a bit more thinking).

Thanks reading.

bernard

@Roland_y
Just went to the repository at https://github.com/Yonaba/Jumper-Examples

and there are no examples there. Just a Readme.MD file

So where are the examples?

Roland_Y

Hi Bernard,
Thanks checking this out.
The master branch just links to other branches where you may find these examples.
If you look at the Readme.md file,

Find here some example of use and demos for Jumper made with differents Lua-based game engines and frameworks. Each of the following framework will have their relevant demos in a dedicated branch of this repository.

Love2d - Go to Love2D Branch
Corona - Go to Corona Branch
Gideros - Go to Gideros branch

So you'll have to follow the link to the branch dedicated to gideros, corona or love2d to find demos for these frameworks. But I have to say that Gideros branch is actually empty, as I didn't write a gideros demo yet (maybe you could do somethng about that ?).

Roland_Y

Hi all,

Some bugs which was causing the pathfinder to fail between successive paths call were e recently fixed. Pixk up the latest version on Github (now 1.5.2.2).

Appart from that, I've been working on a benchmark program from Jumper, with maps taken from the 2012 Grid-Based Path Planning Competition (GPPC).
The whole program can be found here : Jumper-Benchmark.

Roland_Y

Hi all,

Jumper reaches v1.6.0, with some new tuning options.

Now, when initializing Jumper, passing it a 2D map (2-dimensional array), Jumper keeps track of the map and perform node passability checks according to this map values. So that you can easily update your map cells (lock/unlock cells) changing directly the map values) and Jumper will perform accordingly.


local map = {
 {0,0,0},
 {0,0,0},
 {0,0,0},
}

local Jumper = require 'Jumper.init'
local walkable = 0
local pather = Jumper(map,walkable)
-- etc etc
map[2][1] = 1 -- Cell[1,2] becomes unpassable

Second, I have managed to add specialized grids, and a tuning parameter, called grid processing. Therefore, you can [b]either[/b] choose to init Jumper in pre-processing mode (by default) or post-processing mode.

In pre-processing mode (which is the default mode), Jumper caches all map cells in an internal grid and create some internal data needed for pathfinding operations. This will faster a little further all pathfinding requests, but will have a drawback in terms of memory consumed. As an example, a 500 x 650 sized map will consume around 55 Mb of memory right after initializing Jumper, in pre-preprocesed mode.

You can optionally choose to post-process the grid, setting the relevant argument to true when initializing Jumper.

local Jumper = require 'Jumper.init'
local walkable = 0
local allowDiagonal = false
local heuristicName = 'MANHATTAN'
local autoFill = false
local postProcess = true
local pather = Jumper(map,walkable,allowDiagonal,heuristicName,autoFill,postProcess)

In this case, the internal grid will consume 0 kB (no memory) at initialization. But later on, this is likely to grow, as Jumper will create and keep caching new nodes and relevant data on demand. This might be a better approach if you are working with huge maps and running out of memory resources. But it also has a little inconvenience : pathfinding requests will take a bit longer being anwsered (about 10-30 extra-milliseconds on huge maps).

Extra - informations, documentation can be found at Github.
Any feedback would be appreciated.
Thanks for your interest in this.

john26

Wow, thanks so much for doing all this work. It looks very impressive! I intend to write a game based on this functionality. I wonder, would it be possible to have one-way sections on the map (you can only cross the square in one direction?). That way it would be possible to account for gravity by having "holes" you can traverse downward (fall) but not upward?

I was thinking about this, in an actual maze game where you are pursued by monsters, would the player get a different impression if jumper is used rather than just random movement? For instance in Pac Man, the ghosts just seem to change direction randomly when they hit a wall. But still they often get Pac Man. With jumper, they could hunt Pac Man directly, calculating the route. I'm just wondering would the player notice this for example in a scrolling game when only part of the maze is visible at any time? Just speculating...

Roland_Y

Hi John,

Thanks so much for your interest.
Well, this library was originally designed for 2D grid maps. The first idea was to deal with either fully passable or unpassable tiles.

But I have recently started working on an parallel version of this lib to support specific tiles like one-way tiles, for instance. This version works, yet it is still experimental and does not include all the features of the official one.

Find it here: Jumper-Experimental
Find also a demo here (you will have to install Löve2D framework to run it though).

Now about the chase-game you are thinking of, using Jumper or not will all depends on the behaviour of your game entities. Jumper would be perfect for that, but you will have (IMHO) to add a bit of randomness, otherwise the chasing entities will hunt down the player with a perfect efficiency. Would be quite frustrating.
This could be accomplished in a dozen of manners with Jumper, though: target a tile near the player instead of targetting the player itself, simulate a wandering behaviour and start chasing at the player when he stays near a hunter, etc...). There's a game using Jumper (HideAndSneek) in a similar manner that you may find somewhat inspiring.

Pacman uses a different type of AI logic, that we can refer as a "short-sighted pathfinding".You can visit this very comprehensive article for more details, which also provides links to other complementary resources too.

Sorry for being that long, and hope this helps!

Gideros Forum

Howdy, Stranger!

Categories

In this Discussion

Top Posters