Jumper

Jumper is a pathfinding library designed for grid-based games. It aims to be fast and lightweight. It features a wide range of search algorithms, built within a clean interface with chaining features which makes it very friendly and easy to use.

Jumper is written in pure Lua. Thus, it is not framework-related and can be used in any project embedding Lua code.

###Contents

##Installation The current repository can be retrieved locally on your computer via:

###Bash

git clone git://github.com/Yonaba/Jumper.git

###Download (latest)

Archive: zip
Tarball: tarball

###LuaRocks

luarocks install jumper

###MoonRocks

luarocks install --server=http://rocks.moonscript.org/manifests/Yonaba jumper

##Example of Use Here is a simple example explaining how to use Jumper:

-- Usage Example
-- First, set a collision map
local map = {
	{0,1,0,1,0 },
	{0,1,0,1,0 },
	{0,1,1,1,0 },
	{0,0,0,0,0 },
}
-- Value for walkable tiles
local walkable = 0

-- Library setup
local Grid = require ("jumper.grid") -- The grid class
local Pathfinder = require ("jumper.pathfinder") -- The pathfinder lass

-- Creates a grid object
local grid = Grid(map) 
-- Creates a pathfinder object using Jump Point Search
local myFinder = Pathfinder('JPS', grid, walkable) 

-- Define start and goal locations coordinates
local startx, starty = 1,1
local endx, endy = 5,1

-- Calculates the path, and its length
local path, length = myFinder:getPath(startx, starty, endx, endy)
if path then
  print(('Path found! Length: %.2f'):format(length))
	for node, count in path:iter() do
	  print(('Step: %d - x: %d - y: %d'):format(count, node.x, node.y))
	end
end

--> Output:
--> Path found! Length: 8.83
--> Step: 1 - x: 1 - y: 1
--> Step: 2 - x: 1 - y: 3
--> Step: 3 - x: 2 - y: 4
--> Step: 4 - x: 4 - y: 4
--> Step: 5 - x: 5 - y: 3
--> Step: 6 - x: 5 - y: 1

Find some other examples of use for Jumper, made with various Lua-based frameworks and game engines in this separated repository: Jumper-Examples

##API & Docs## Find a complete documentation and API description online here: docs

##Usage## ###Adding Jumper to your project### Copy the contents of the folder named jumper and its contents and place it inside your projet. Use require function to import any module of the library.

###Setting your collision map The collision map is a regular Lua table where each cell holds a value, representing whether or not the corresponding tile in the 2D world is walkable or not.
Caution : All cells in your collision maps must be indexed with consecutive integers.

local map = {
  {0,0,0,0,0,0},
  {0,1,2,3,4,0},
  {0,0,0,0,5,0},
  {0,1,2,3,6,0},
  {0,0,0,0,0,0},
}

Note: Lua array lists starts indexing at 1, by default. Using some dedicated librairies/map designing tools to export your collisions maps to Lua, the resulting tables might start indexing at 0 or whatever else integer. This is fairly legit in Lua, but not common, though. Jumper will accomodate such maps without any problem.

Jumper also supports string maps. Therefore, you can also use a string to define your collision map. Line break characters ('\n' or '\r') will be used to delimit rows, as shown below:

local stringMap = "xxxxxxxxxxxxxx\n"..
				  "x  r         x\n"..
				  "x       .... x\n"..
				  "x            x\n"..
				  "x   J  $$$   x\n"..
				  "x            x\n"..
				  "xxxxxxxxxxxxxx\n"
]]

Optionally, you can also use square brackets :

local stringMap = [[
xxxxxxxxxxxxxx
x  r         x
x       .... x
x            x
x   J  $$$   x
x            x
xxxxxxxxxxxxxx
]]

###Initializing Jumper### Once your collision map is set, you have to init a grid object. This is fairly simple, you just have to require the grid module, and then pass it two arguments.

local Grid = require 'jumper.grid'
local grid = Grid(map,processOnDemand)

Only the first arg map is mandatory. It refers to the collision map previously defined. The second arg processOnDemand is optional. See here for more details.

Next, to init a pathfinder, you have specify what value in this collision map matches a walkable tile. If you choose for instance 0 for walkable tiles, and you happen to assign that value to the pathfinder, it will consider any other value as non walkable.
To initialize a pathfinder, you will have to require the pathfinder module, and then pass it three arguments.

local myFinder = Pathfinder(finderName, grid, walkable)

The first and second arguments are mandatory. The last one is optional.

finderName refers to the search algorithm to be used by the pathfinder. See finders for more details.
grid refers to the grid object.
walkable (optional) refers to the value representing walkable tiles. If not given, any tile will be considered fully walkable on the grid.

You might want to have multiple values designing a walkable tile. In this case, argument walkable can be a function, prototyped as f(value), returning a boolean.

local map = {
  {0,0,0,0,0,0},
  {0,1,2,3,4,0},
  {0,0,0,0,5,0},
  {0,1,2,3,6,0},
  {0,0,0,0,0,0},
}
-- We want all values greater than 0 to be walkable
local function walkable(value)
  if value > 0 then return true end
  return false
end

local Grid = require ('jumper.grid')
local Pathfinder = require('jumper.pathfinder')
local myFinder = Pathfinder('ASTAR', Grid(map), walkable)

###Finders Jumper uses search algorithm to perform a path search from one location to another. Actually, there are dozens of search algorithms, each one having its strengths and weaknesses, and this library implements some of these algorithms. As of version 1.8.0, Jumper implements A-star, Dijkstra, Breadth-First search, Depth First search and Jump Point Search (which is one of the fastest available for grid maps).

local Grid = require ('jumper.grid')
local Pathfinder = require ('jumper.pathfinder')
local myFinder = Pathfinder('JPS',Grid(map),0)
print(myFinder:getFinder()) --> 'JPS'

Use pathfinder:getFinders to get the list of all available finders, and pathfinder:setFinder to switch to another search algorithm. See the pathfinder class documentation for more details.

###Distance heuristics### Heuristics are functions used by the search algorithm to evaluate the optimal path while processing.

####Built-in heuristics Jumper features four (4) types of distance heuristics.

MANHATTAN distance : |dx| + |dy|
EUCLIDIAN distance : sqrt(dxdx + dydy)
DIAGONAL distance : max(|dx|, |dy|)
CARDINAL/INTERCARDINAL distance: *min(|dx|,|dy|)sqrt(2) + max(|dx|,|dy|) - min(|dx|,|dy|)

By default, when you init Jumper, MANHATTAN distance will be used.
If you want to use another heuristic, you just have to pass one of the following predefined strings to pathfinder:setHeuristic(Name):

"MANHATTAN" -- for MANHATTAN Distance
"EUCLIDIAN" -- for EUCLIDIAN Distance
"DIAGONAL" -- for DIAGONAL Distance
"CARDINTCARD" -- for CARDINAL/INTERCARDINAL Distance

As an example :

local Grid = require ('jumper.grid')
local Pathfinder = require('jumper.pathfinder')
local myFinder = Pathfinder('ASTAR',Grid(map))
myFinder:setHeuristic('CARDINTCARD')

See docs for more details on how to deal with distance heuristics.

####Custom heuristics You can also cook your own heuristic. This custom heuristic should be passed to Pathfinder:setHeuristic() as a function prototyped for two parameters, to be dx and dy (being respecitvely the distance in tile units from a target location to the current on x and y axis).
Note: When writing your own heuristic, take into account that values passed as dx and dy can be negative.

As an example:

-- A custom heuristic
local function myDistance(dx, dy)
  return (math.abs(dx) + 1.4 * math.abs(dy))
end
local Grid = require ('jumper.grid')
local Pathfinder = require('jumper.pathfinder')
local myFinder = Pathfinder('ASTAR',Grid(map))
myFinder:setHeuristic(myDistance)

##The Grid ###Map access When you init a grid object, passing it a 2D map (2-dimensional array), Jumper keeps track of this map.
Therefore, you can access it via (Grid()):getMap()

###The Grid Object When creating the grid object, the map passed as argument is pre-preprocessed by default. It just means that Jumper caches all nodes and create some internal data needed for pathfinding operations. This will make further pathfinding requests being answered faster, 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, when using the pre-preprocesed mode.

You can optionally choose to process nodes on-demand, setting the relevant argument to true when initializing Jumper.

local map = {
  {0,0,0},
  {0,0,0},
  {0,0,0},
}
local Grid = require 'jumper.grid'
local Pathfinder = require 'jumper.pathfinder'

local processOnDemand = true
local grid = Grid(map, processOnDemand)
local walkable = 0
local myFinder = Pathfinder('DFS', grid, walkable)

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 automatically create and keep caching new nodes on purpose. This might be a better approach if you are facing to tightening constraints in terms of available memory, working with huge maps. But it also has a little inconvenience : pathfinding requests will take a little tiny bit longer (about 10-30 extra-milliseconds on huge maps), because of the extra work, that is, creating the new required nodes.
Therefore, consider this a tuning parameter, and choose what suits the best to your needs.

##Handling paths## ###Using native Pathfinder:getPath()###

Calling Pathfinder:getPath() will return a path.
The path is always represented as follows :

path = {
	node1,
	node2,
	...
	nodeN
}

Each node has x and y attributes, corresponding to its location on the grid. That is, a set of nodes makes a complete path.

You can iterate on nodes along a path using path:iter

for node,step in path:iter() do
  -- ...
end

###Path filling### Depending on the search algorithm being used, the set of nodes composing a path may not be contiguous. For instance, in the path given below, you can notice node {x = 1,y = 3} was skipped.

local path = {{x = 1, y = 1},{x = 1,y = 2},{x = 1,y = 4}}

This is actually not a problem, as the way from {x = 1,y = 2} to {x = 1,y = 4} is straight. Anyway, Jumper provides a path filling feature that can be used to polish (interpolate) a path early computed, filling such holes.

-- Assuming: path = {{x = 1,y = 1},{x = 4,y = 4}}
path:fill() -- Returns {{x = 1,y = 1},{x = 2,y = 2},{x = 3,y = 3},{x = 4,y = 4}}

###Path filtering### This feature does the opposite work of Pathfinder:fill. Given a path, it removes some unecessary nodes to leave a path made of turning points. The path to follow would be the straight line between all those nodes.

-- Assuming: path = {{x = 1,y = 1},{x = 1,y = 2},{x = 1,y = 3},{x = 1,y = 4},{x = 1,y = 5}}
path:filter() -- Returns {{x = 1,y = 1},{x = 1,y = 5}}

See path class documentation for more details.

##Chaining## All setters can be chained.
This is convenient if you need to quickly reconfigure the pathfinder object.

local map = {
  {0,0,0},
  {0,0,0},
  {0,0,0},
}

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

local grid = Grid(map)
local myFinder = Pathfinder('BFS', grid, 0)
-- some code
-- calls the finder, reconfigures it and requests a new path
local path,length = myFinder:setFinder('ASTAR')
				   :setHeuristic('EUCLIDIAN')
				   :setMode('ORTHOGONAL')
				   :getPath(1,1,3,3)
-- That's it!

##Credits and Thanks##

Daniel Harabor, Alban Grastien : for the algorithm and the technical papers.
XueXiao Xu, Nathan Witmer: for their JavaScript port
Steve Donovan: for the documentation generator tool LDoc.

##License##

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

colinchen1984/Jumper

Jumper