Jumper - ( An Extremely Fast) 2D Pathfinder For grid-based games

EHO · October 6, 2012, 11:29pm

Jumper is insane! Very helpful. Thanks for sharing your work [import]uid: 105707 topic_id: 30317 reply_id: 126696[/import]

roland.yonaba · October 9, 2012, 2:12pm

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

roland.yonaba · October 9, 2012, 2:12pm

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

roland.yonaba · October 16, 2012, 1:58pm

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

roland.yonaba · October 16, 2012, 1:58pm

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

roland.yonaba · October 25, 2012, 4:22pm

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

roland.yonaba · October 25, 2012, 4:22pm

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

roland.yonaba · November 2, 2012, 2:43pm

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.
[import]uid: 142361 topic_id: 30317 reply_id: 129720[/import]

roland.yonaba · November 2, 2012, 2:43pm

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.
[import]uid: 142361 topic_id: 30317 reply_id: 129720[/import]

roland.yonaba · November 5, 2012, 4:29am

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.

[code]
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[/code]

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.

[import]uid: 142361 topic_id: 30317 reply_id: 129882[/import]

roland.yonaba · November 5, 2012, 4:29am