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

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

Roland_YRoland_Y Member
edited December 2012 in Game & application design
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
+1 -1 (+3 / -0 )Share on Facebook
«13

Comments

  • If it is pure LUA, then on mobile devices it will not be fast enough.
  • 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
  • @MikeHart : I don't really understand....
    "Not fast enough because it features Lua ?" What's the point ?

    @techdojo: Oh, thanks!
  • 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.
  • 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
  • MikeHartMikeHart Guru
    edited June 2012
    Good for you then :))

    Dislikes: MoKaLux

    +1 -1 (+0 / -1 )Share on Facebook
  • Neat library, I plan to give it a spin. Thanks!
  • You're welcome!
  • @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
  • @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?
  • 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.
  • 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
  • Having a Gideros example project would help a lot in evaluating if this project can do what a developer needs.
  • 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
  • atilimatilim Maintainer
    @Roland_Y great! thank you :)
    @Magnusviri Currently if nobody creates a Gideros example project, I'm willing to create one.
  • @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!

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

  • 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!
  • jack0088jack0088 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!
  • 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.


  • 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~
    http://www.nightspade.com
  • 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.
  • 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!
  • @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
  • @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.
    rar
    rar
    Require_Test.rar
    312B
  • Output is:
    from file1
    from folder1.file1
    from file1 file1
    from folder1.file1 folder1.file1
  • That's odd. Did you run only the file main.lua ?

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

    image

    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 ?
  • ok it seems you're right I'v excluded all files except main.lua from execution
    from file1	file1
    from folder1.file1	folder1.file1
Sign In or Register to comment.