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
• Example of Use
• API & Docs
• Usage
• The Grid
• Handling paths
• Chaining
• Specs
• Credits and Thanks
• License

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

###Bash

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

###Download (latest)

• Development release: zip | tar.gz
• Stable release (1.8.1): zip | tar.gz
• All releases: tags

###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(grid, 'JPS', 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 starting at 0 or 1.

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(grid, finderName, walkable)

The first arg is mandatory. The others are optional.

• grid refers to the grid object.
• finderName refers to the search algorithm to be used by the pathfinder. See finders for more details.
• 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(Grid(map), 'ASTAR', 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. Since v1.8.0, Jumper implements a wide range of search algorithms:

• A-star
• Dijkstra
• Breadth-First search
• Depth First search
• 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(Grid(map), 'JPS', 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(Grid(map),'ASTAR')
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(Grid(map), 'ASTAR')
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(grid, 'DFS', 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.

Tunnelling

Normally, the pathfinder should returns paths avoiding walls, obstacles. But, you can also authorize it to tunnel through walls, that is, to cross them deading diagonally.

Let's set an example:

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

0 refers to walkable tiles, and 1 for unwalkable tiles. Let's assume we want to move from location [x: 1, y:3] to [x: 3, y:1]. Calling getPath() would fail, because it can't normally cross from [x: 1, y:3] to [x: 2, y:2] (because tiles [x: 1, y:2] and [x: 2, y:3] are unwalkable), nor from [x: 2, y:2] to [x: 3, y:1] (because tiles [x: 2, y:1] and [x: 3, y:2] are unwalkable).

Passing a fifth argument tunnel will override this behaviour, and cause the pathfinder to tunnel though those walls.

local map = {
 {1,1,0},
 {1,0,1},
 {0,1,1},
}
local tunnel = true
local path = myFinder:getPath(1,3,3,1,tunnel)
print(path~=nil) --> true

A side note though, that feature works perfectly with all the available finders built-in Jumper, except Jump Point Search algorithm, as of now.

##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(grid, 'BFS', 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!				   

##Specs Specs tests have been included.
You can run them using Telescope with the following command from the root folder:

tsc -f specs/*

##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 awesome documentation generator tool LDoc.
• Srdjan Markovic, who reported various bugs and feedbacks.

##License## This work is under MIT-LICENSE
Copyright (c) 2012-2013 Roland Yonaba.

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.