Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

Jumper - ( An Extremely Fast) 2D Pathfinder For grid-based games
Started by roland.yonaba Aug 27 2012 08:02 PM

* * * * * 1 votes
38 replies to this topic
[TOPIC CONTROLS]
Page 1 of 2 1 2
This topic has been archived. This means that you cannot reply to this topic.
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#1

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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 :

package.path = package.path .. ';.\\?\\init.lua'
local Jumper = require('Jumper')
-- A collision map : 0 for walkable tiles, 
-- non-zero for unwalkable tiles
local map = {
   {0,0,0},
   {0,2,0},
   {0,0,1},
}

local walkable = 0 -- specify walkable tiles
local allowDiagonal = true -- allow diagonal moves
-- Inits our pathfinder instance
local pather = Jumper(map,walkable,allowDiagonal,Jumper.HEURISTIC.MANHATTAN)
local startX, startY = 1,1 -- starting point
local endX,endY = 3,3 -- ending point
-- Gets our path, t
local path, cost = pather:searchPath(startX,startY,endX,endY)

Find it on Github, with Documentation, usage examples, and visual demos!
Page: Jumper
Github: Jumper
uid: 142361 topic_id: 30317 reply_id: 330317


[TOPIC: post.html]
#2

Danny

[GLOBAL: userInfoPane.html]
Danny
  • Corona Geek

  • 2,597 posts
  • Corona Staff

Excellent work, thanks for sharing.

PS: Are you the same Yonaba who made "The age of nations" homebrew RTS game for the PSP?
uid: 84637 topic_id: 30317 reply_id: 121483


[TOPIC: post.html]
#3

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Yep, totally. That's me.
uid: 142361 topic_id: 30317 reply_id: 121541


[TOPIC: post.html]
#4

Danny

[GLOBAL: userInfoPane.html]
Danny
  • Corona Geek

  • 2,597 posts
  • Corona Staff

Nice to see you here! I knew you back then, you would have known me as "zack" in those days.

You may recall the wolfenstein 3d port and luaplayer euphoria i made for the psp back then under the alias of "zack"

uid: 84637 topic_id: 30317 reply_id: 121543


[TOPIC: post.html]
#5

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Yep, I do remember. Back in the old days....
Actually, I recognized the avatar, but I wasn't that sure about where I saw it. There's been a long time!
Good to see you're still active. I've been quite busy the past days, but actually i'm back to coding, and sharing my good snippets. :P
uid: 142361 topic_id: 30317 reply_id: 121551


[TOPIC: post.html]
#6

dingo

[GLOBAL: userInfoPane.html]
dingo
  • Contributor

  • 700 posts
  • Corona SDK

thanks for the share, i am sure i can use it the sooner or latter!
uid: 90610 topic_id: 30317 reply_id: 121554


[TOPIC: post.html]
#7

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Hi folks,

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 Corona. As i'm working with some other frameworks, I don't know much of Corona'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 Corona. Would be greatly apreciated.
uid: 142361 topic_id: 30317 reply_id: 125262


[TOPIC: post.html]
#8

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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!
uid: 142361 topic_id: 30317 reply_id: 125403


[TOPIC: post.html]
#9

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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!

uid: 142361 topic_id: 30317 reply_id: 126388


[TOPIC: post.html]
#10

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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.
uid: 142361 topic_id: 30317 reply_id: 126651


[TOPIC: post.html]
#11

EHO

[GLOBAL: userInfoPane.html]
EHO
  • Contributor

  • 259 posts
  • Corona SDK

Jumper is insane! Very helpful. Thanks for sharing your work :)
uid: 105707 topic_id: 30317 reply_id: 126696


[TOPIC: post.html]
#12

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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!
uid: 142361 topic_id: 30317 reply_id: 126926


[TOPIC: post.html]
#13

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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 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.
uid: 142361 topic_id: 30317 reply_id: 127615


[TOPIC: post.html]
#14

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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.
uid: 142361 topic_id: 30317 reply_id: 128703


[TOPIC: post.html]
#15

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Hi all,

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

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


[TOPIC: post.html]
#16

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

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

uid: 142361 topic_id: 30317 reply_id: 129882


[TOPIC: post.html]
#17

evonalien

[GLOBAL: userInfoPane.html]
evonalien
  • Observer

  • 1 posts
  • Corona SDK

This is really amazing, I have been following this for a few weeks now hoping someone would make a more in-depth tutorial for this because I'm still a beginner and have tried several times to get it to work but don't understand it very well. How do you specify the size of each box, how do you even see the map, I can't even get it to work with your example =(

Anyway love you for doing something like this, it's the only diagonal pathfinding module I could find. Hope someone releases a tutorial in the near future!
uid: 194360 topic_id: 30317 reply_id: 130505


[TOPIC: post.html]
#18

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Hi Evonalien,

Would be please be a little bit more explicit on the problem ?
Is it all about using Jumper (setting the collision map, make pathfinding requests and so on) ?
You can take the time to review this thread,there might be some useful hints for you.
You can also open a ticket on the issue tracker, and submit the exact problem, on Github.

If you are looking for a full example with Corona, you can always look at this demo made by Mario Roberti. Find the source code here.

I'll be working on some examples for Corona by myself, when I have the time, hopefully.
uid: 142361 topic_id: 30317 reply_id: 130533


[TOPIC: post.html]
#19

Dotnaught

[GLOBAL: userInfoPane.html]
Dotnaught
  • Contributor

  • 370 posts
  • Corona SDK

Very cool, thanks for sharing!
uid: 1560 topic_id: 30317 reply_id: 132109


[TOPIC: post.html]
#20

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Hi community,

Jumper reached v1.6.2. See the detailed changelog.

First of all, I've removed all links to third-party libs previously included. I chose to rewrite a lighter version of binary-heaps, featuring only the operations I needed (push, pop, heapify). Jumper no longer uses any extra dependancy, which makes less files to cope with.
I also made a full code review, bringing some slight internal changes.

I have also included a new type of distance heuristic, which is cardinal/intercadinal distance. I also included support for custom distance heuristics.

The initialization pattern have also been changed, to provide a way to init the pathfinder with a limited number of args. So, from now on, Jumper receives only three args upon initialization. See here for more details.

Last point, setDiagonalMoves and getDiagonalMoves methods were removed, as I didn't find them explicit enough. Instead, you can now use setMode and getMode. setMode requires a string argument stating how the search should be processed: in diagonal mode (8-directions) or straight-mode only (4-directions).

Docs & Readme have been updated with the latest changes.
The benchmark program have also been updated to the latest version of Jumper.

Thanks reading.
uid: 142361 topic_id: 30317 reply_id: 133247


[TOPIC: post.html]
#21

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Hi all,

Jumper reaches version 1.6.3.
Basically, they were not much changes, but just some new features added, as some people have requested.
First, Jumper now supports string maps. The collision map passed upon initialization of the library no longer have to be a 2D table. Instead, you can pass a string, that Jumper will parse in rows (using line-break chars - '\n' and '\r' as delimiters).

Nodes walkability rules were also enhanced, for convenience. You might want to have multiples values for walkable tiles on a collision map, for instance. As of v1.6.3, you can pass a function that Jumper will call to evaluate whether or not a tile is walkable.

local stringMap = [[
xxxxx#xxxxx
xxxx#*#xxxx
xxx# . #xxx
### . . ###
#  . . .  #
#*. .$. .*#
#  . . .  #
### . . ###
xxx# . #xxx
xxxx#*#xxxx
xxxxx#xxxxx
]]

-- We want chars '#', '.' and '*' to be walkable tiles.
local function isWalkable(value)
  return value:match('[#.*]')
end
local Jumper = require ("Jumper")
local pathfinder = Jumper(stringMap, isWalkable)

A path iterator function have been added, too:

local path, len = pathfinder:getPath(startx, starty, goalx, goaly)
if path then
  for x,y in path:iter() do
    print('Cell: '..x..' - '..y)
  end 
end

The Grid object API, adding some functions, mostly iterators too:

Grid:iter()
Grid:each(f,...)
Grid:eachRange(lx,ly,ex,ey,f,...)
Grid:imap(f,...)
Grid:imapRange(lx,ly,ex,ey,f,...)

Some little code improvements were made, too.
There also a complete HTML documentation, available on the git repository. It fully describes the API, and gives a brief description of the purpose of each of Jumper's modules. This documentation was generated using the excellent LDoc.

See the changelog for more details. The benchmark for Jumper was also updated with the latest version of the library, feel free to try!
uid: 142361 topic_id: 30317 reply_id: 139587


[TOPIC: post.html]
#22

horacebury

[GLOBAL: userInfoPane.html]
horacebury
  • Corona Geek

  • 3,070 posts
  • Corona SDK

Awesome
uid: 8271 topic_id: 30317 reply_id: 139588


[TOPIC: post.html]
#23

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Hi all,

I am releasing the version 1.7.0 of Jumper.
Documentation is available online.

In this new version, I have been focusing on ameliorating the internal code: split the search algorithms from the pathfinder class, and then provide a common API for each of these search algorithms.
The new version have some new features, and runs even faster, thanks to a little optimization made in the binary heaps module.

So far, Jumper offers you Finders, which are just different search algorithms. Astar and Jump Point Search are implemented, so far, but this is likely to grow next.
When a pathfinder object is created, it uses by default Jump Point Search algorithm. As of this version, you can switch to pure A-star if desired.

With both finders (JPS and A-star), a search can be made in "ORTHOGONAL" mode (that is, only 4-directions allowed) or in "DIAGONAL" mode (8-directions allowed). You can also use any of the built-in distance heuristics (Manhattan, Euclidian, Diagonal and Card-Intercardinal distance), or even cook your own custom heuristic and pass it to the finder.

New methods have been added to the pathfinder class, mostly for a convenient usage of the new fatures.
Pathfinder:setFinder
Pathfinder:getFinder
Pathfinder:getFinders
Pathfinder:getHeuristics
Pathfinder:getModes

The autoFill feature has been removed. So for now on, to interpolate a path returned by Pathfinder:getPath, you will need to call explictely Pathfinder:fill.

Another new feature is the Pathfinder:filter. This utility function does the opposite of Pathfinder:fill. Being given a path, it detects all nodes that can be deducted (interpolated) from a straight move, and prunes them. It leaves a "compressed" or "filtered" path. See handling paths for more details about this feature.

For a detailed list of changes, see the changelog.
Feel free to check this out on Github!

Thanks for reading.
uid: 142361 topic_id: 30317 reply_id: 140098


[TOPIC: post.html]
#24

StarCrunch

[GLOBAL: userInfoPane.html]
StarCrunch
  • Contributor

  • 824 posts
  • Corona SDK

Hi!

I was last playing with A* a couple years back or so (and remember a few of the snags you mention above...), and I ran across

Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments

while I was at it.* Have you looked into anything like that? I ended up distracted by other shiny things and never implementing it, but it seemed interesting.

* - The author has a few papers; I don't recall if this was his most recent.
uid: 27791 topic_id: 30317 reply_id: 140104


[TOPIC: post.html]
#25

roland.yonaba

[GLOBAL: userInfoPane.html]
roland.yonaba
  • Enthusiast

  • 60 posts
  • Corona SDK

Funny you mention it. I already came across that paper, and I'll be looking at it, soon, hopefully.
Anyway, thanks.
uid: 142361 topic_id: 30317 reply_id: 140215



[topic_controls]
Page 1 of 2 1 2
 
[/topic_controls]