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

[Roland_Yonaba]

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)

The largest path possible ? For what purpose would you need this ? Could you please give more details about this ?
Drawings, if possible.

[Roland_Yonaba]

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.

Code: Select all

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.

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

The largest path possible ? For what purpose would you need this ? Could you please give more details about this ?
Drawings, if possible.

For example a game where the AI needs to go form A to B but he must step over all maximum possible cells without walking twice over the same cell.

[MarekkPie]

Longest path is actually a much harder problem than shortest path:

http://en.wikipedia.org/wiki/Longest_path_problem

[Roland_Yonaba]

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 map with multiple terrain types.
So, as of this new release, Jumper offers now to its users two main modules, at the top level : a Grid class, and a Pathfinder class.

Code: Select all

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

To create a 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.

Code: Select all

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

Code: Select all

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:

Code: Select all

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.

[Roland_Yonaba]

Hi all,
Here is a new iteration of Jumper: 1.8.1 release.
The detailed changelog can be found here.

This new release if totally backwards compatible with the latest one, except for only one minor change (for pure convience issues), related to the way one inits the pathfinder object.
See the related documentation: pathfinder
For now on, to init a new Pathfinder object, the grid object comes first. Then one specifies the finder algorithm to be used, and then the walkable value(s).

As a straightforward example:

Code: Select all

local Grid = require('jumper.grid')
local Pathfinder = require('jumper.pathfinder')
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(grid, 'JPS',0)

Added to that, some inner changes were brought to the code in order to fix some little odds that were causing the pathfinder to fail on specific situations.
Hopefully, all issues detected were solved, as of now.

A new feature have been added, that is the ability for the pathfinder to tunnel through walls.
That feature overrides the normal behaviour of the pathfinder, and would authorize it to tunnel through walls, heading diagonally towards them.
The screeshot below illustrates this feature:



See the dedicated section in the Readme, for more details.

Documentation and full source is freely available.
To easily get started with this library, please take a look at the readme.

Source: Github
Documentation: Jumper

Thanks reading.

[Roland_Yonaba]

Hi all,

Find here an unofficial version of Jumper with minor modifications for multi-agents pathfinding, that I wrote upon the request of a user.
It doesn't aims to speed, but to return intelligent and realistic looking paths when moving a group of units, avoiding the "stacking" issue when units pathing at the same time have the same destination.
The Readme provides interesting details on how to use it.
Grab it on Github: branch - Node-weight

[Karai17]

Ooooh~ Avoiding stacking is brilliant!

[qaisjp]

I was minding my own business on a forum and it looks like I found something that may or may not interest you.. http://forum.mtasa.com/viewtopic.php?t=58384

[rokit boy]

hey i have a problem
in main.lua

Code: Select all

grid = require ("jumper.grid")
pathfinder = require ("jumper.pathfinder")

in game.lua

Code: Select all

gr = grid(map)
finder = pathfinder('JPS', gr, 0) 

i get an error saying it needs a grid object when initializing finder. so "gr" isn't a grid object for some reason.
help?