Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

[qaisjp]

What does OPEN/CLOSE ways do?

Say you want to model a door on your 2D grip map (a one-way tile).
You want the corresponding tile to be entered only from left/right, for instance, and not from any other direction.
Select the "CLOSE WAYS" button, then select the tile you want to modify, then "close" the directions you do not want the pathfinder to enter on this tile typing the matching keys.

Hope this is explicit enough ?

Yup, now I understand; thanks.

[Roland_Yonaba]

Hi community!

First of all, I've brought some little changes to Jumper, which now goes to version 1.5.2.2

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

[Roland_Yonaba]

Hi all,

Version 1.6.0, with some 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.

Code: Select all

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.

Code: Select all

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.

[Roland_Yonaba]

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

Readme have been updated with the latest changes.
The benchmark program have also been updated to the latest version of Jumper.
Find the examples/demos with love2d and ATL here.

Thanks reading.

EDIT: Added on the wiki!

[Roland_Yonaba]

Hi all,

Jumper reaches version 1.6.3.
Basically, they were not much changes in the interface, 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.

Code: Select all

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:

Code: Select all

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!

[Ref]

Couldn't find where in the code you could specify that a figure could walk through trees.

[Roland_Yonaba]

Couldn't find where in the code you could specify that a figure could walk through trees.

Hem, I don't get this at all. Did you find an issue testing it ?

[Ref]

No issue.
Just referring to the image you posted showing the path going through the trees rather than behind them.
Nice library!

[Roland_Yonaba]

No issue.
Just referring to the image you posted showing the path going through the trees rather than behind them.
Nice library!

Oh, thanks.
Actually, you might want to give it a try by yourself, it's just an issue of display. The path doesn't go through the tree, just behind it

[Ubermann]

I have been using this for WitchavenRL. Good library IMO.

But what I miss is that the library allows to calculate the LARGEST path possible (without using map cells twice, of course)