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

Roland_Y · September 2012

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 · September 2012

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 · September 2012

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 · September 2012

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 · September 2012

@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 · September 2012

Yep, everything works now. Thanks

Roland_Y · September 2012

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

ar2rsawseen · September 2012

Yes @Roland_Y that was the idea

Roland_Y · September 2012

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 · October 2012

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 · October 2012

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 · October 2012

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 · October 2012

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 · October 2012

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 · October 2012

@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 · October 2012

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 · November 2012

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 · November 2012

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 · November 2012

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 · November 2012

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!

Coolis · November 2012

Hello Roland_Y,
I've noticed that Jumper expands each neighbor node in non-diagonal mode. I had expected it to jump first; however I must confess that after reading the article you link to inside jumper.lua, I think that in order to jump, we must include a diagonal search too, where we add both the final jump point and, if necessary, a 'corner point' which provides a link between the jump point and the original node. I will try to implement this and post here any results.

Roland_Y · November 2012

Hi Coolis,
Thanks for your interest.
Well, that was intented. As you read the technical papers, you might have noticed that Jump Point Search was designed to prefer "heading diagonally" first. So to have this "straight-mode" working, I had to "hack" into the original algorithm, and I came up with this. I tried to include "jumping" in this mode, but I didn't succeed, then I switched to this step-by-step alternative.

But any help is welcomed, if you come up with something (or anything interesting), let me know. Feel free to send a pull request on Github.

Thanks!

john26 · November 2012

@Roland_Y, thanks for your comments. I will try jumper and the experimental version. Also what happens if there is no path to the destination (entirely surrounded by walls). Does jumper return a failure result in this case? (hopefully it doesn't go into an endless loop!)

Roland_Y · November 2012

Hi John,
When there no possible path, Jumper:getPath(...) returns nil (in like no time).
And no, I won't propagate any error, that would be fairly unkind

So you don't have worry about endless loops. ^^

Coolis · November 2012

I think that a temporary way to allow jumps in straight only is to allow diagonal moves, and process diagonal jumps so that we walk in a zig-zag way between nodes. I believe this will imply separating the recursion for straight moves from the one for diagonal moves. Getting the minimum turns path (avoiding zig-zags) from such diagonal jump, or in general between points seems to be another subject; I just made a google search with these terms - minimum turns path - and apparently it's a topic of research on itself. I'll keep searching!

EDIT: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=625782
This seems to be a starting point.
EDIT: Apparently not. The article seems to use a form of rectangular symmetry that has been proven to be less effective than jump points (at least, according to the article on which jump points are based).
What I've thought until now: for minimizing turns, we should use the Manhattan heuristic and add the number of turns needed to perform a jump to the g-factor. Also, maybe the Euclidean heuristic in the g-factor can be replaced with the Manhattan heuristic?
Besides that, the main problem is transforming a diagonal jump into a sequence of turn-wise optimal moves (that number then would add to the jump node g-score).
Eg, a simple case where we try to move from S to E:
(bear in mind that no other jump point was found in the diagonal search until we found E)
1 0 1 1 1 E
1 0 1 0 0 0
1 0 0 0 0 0
1 0 0 0 0 1
0 0 0 0 0 0
S 1 1 0 1 1
There is already several paths made available by the fact that it is a diagonal jump point (marked with 2's):
1 0 1 1 1 E
1 0 1 2 2 2
1 0 2 2 2 0
1 2 2 2 0 1
2 2 2 0 0 0
S 1 1 1 1 1
Under these conditions, what is the best, turn-wise, straight moves only path ?(because the distance covered will be the same under the Manhattan metric) (having in account an initial orientation).
We can ignore holes in the map (filled with 3's):
1 3 1 1 1 E
1 3 1 0 0 0
1 0 0 0 0 0
1 0 0 0 0 1
0 0 0 0 0 3
S 1 1 3 1 1
This case is simple, and a perfect solution with 3 turns + a possible start turn would be the following path (marked P):
1 3 1 1 1 E
1 3 1 0 0 P
1 P P P P P
1 P 0 0 0 1
P P 0 0 0 3
S 1 1 3 1 1
From there on, I have no idea, although it would be fantastic to find some way of improving the state of affairs in this problem with jump points.
PS: I think I will repost this in the article page.

Roland_Y · December 2012

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.

Roland_Y · January 2013

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!

Roland_Y · January 2013

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.

Roland_Y · January 2013

I've been actively working on this project the past hours, and i came up with a new iteration of Jumper.
Here's the 1.8.0 release. The detailed changelog can be found here.

Some little changes were brought to the interface. Mostly because I wasn't satisfied with the relationship that was existing between the Grid class and the Pathfinder class, that is, encapsulating the Grid object within the Pathfinder. That was a bad design choice, just because it was preventing a user from handling efficiently a map with multiple terrain types.
So, as of this new release, Jumper offers to its user two main modules, at the top level : a Grid class, and a Pathfinder class.

local Grid = require('jumper.grid')
local Pathfinder = require('jumper.pathfinder')

To create the grid, it is still fairly simple, just pass a collision map to the Grid class. Then, pass the grid object to the Pathfinder.
The Pathfinder class takes three args upon instantiation: the finder name, referring to the search algorithm to be used, the grid and the value/function for walkable tiles.

local map = {
  {1,1,1,1,1},
  {1,0,0,0,1},
  {1,0,0,0,1},
  {1,1,1,1,1},
}
local grid = Grid(map)
local myFinder = Pathfinder('JPS', grid, 0)

What makes that layout very interesting is that you can stick to a unique grid object, and then easily simulate multiple terrain types. In the example above, let's consider '1' represents a specific terrain type, like 'land', and 0 stands for 'water'. That way, one can design a finder that will look for path on 'lands', and another that will search for paths on 'water'. We can even have a pathfinder for both (land and water, as walkable can also be a function).

local finderLand = Pathfinder('ASTAR', grid, 1)
local finderWater = Pathfinder('ASTAR', grid, 0)
local finderAmphibia = Pathfinder('ASTAR', grid, function(v) return v == 0 or v==1 end)

Added to that, I have included some new search algorithms. Well, they may all not be fast, by essence, but the duty of a library is to offer choices, not to limit. So far, Jumper implements five well-know search algorithms: A-star, Dijkstra, Breadth first Search, Depth first search and Jump Point Search (the fastest one actually).

The Pathfinder class and the Grid class have also been extended with some new methods, mostly for their convenient use. You can check out the online documentation for more details.

Last point, some methods such as Pathfinder:filter() and Pathfinder:fill() were removed from the Pathfinder class. For now on, using Pathfinder:getPath returns a path, which would be an instance or an internal class named Path. To alter the returned path (interpolate, or compress it), you will just have to call these methods from the returned object:

local path = myFinder:getPath(startX, startY, endX, endY)
if path then
  path:fill() -- or path:filter()
 
  -- iterating along the path
  for node, count in path:iter() do
    -- etc
  end
end

Documentation is available online, and source. Check out the Readme, as it provides all informations you need to easily get started.
Source: Github
Documentation: Jumper

Thanks reading.

bowerandy · January 2013

@Roland_Y, I've been following your messages about Jumper for some time but have never actually jumped (heh heh) in and tried it. I'm currently developing a game where I have to find a route around a drawn maze. I currently use some AI that I developed in ObjectiveC to do this (my pure Lua solution was too slow). I wonder if you could advise me whether Jumper might be a suitable replacement.

The main difference that I see between what I have and your examples is that the game is not really grid-based. Well it is, but the grid size is effectively one pixel and and the map size is that of the screen. Therefore in a brute force approach I would have to give Jumper a grid of 1024x768 pixels, which would be rather memory intensive to describe and probably too slow to trace (do you think)?

The edges of the path are actually described by two poly-lines so can you see any obvious way to use these as an input to Jumper? I guess I might be able to reduce the overall map area by 2 or 4. Do you think Jumper would be fast enough to trace around a grid of 256x192 slots? Or do you have any other suggestions?

best regards

Howdy, Stranger!

Categories

In this Discussion

Top Posters

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

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

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

Comments