Pathfinding
From GiderosMobile
Jumper by Roland Yonaba
The Jumper pathfinding library, written by Roland Yonaba, is optimized for Lua and has 6 pathfinding algorithms: "ASTAR", "DIJKSTRA", "THETASTAR", "BFS", "DFS", "JPS".
- GH: https://github.com/Yonaba/Jumper
- GF: http://forum.giderosmobile.com/discussion/1081/jumper-very-fast-pathfinder-for-2d-grid-based-games
"Jumper, very fast pathfinder for 2d grid based games"
The Gideros version of Jumper has:
- pull requests (PRs) present on Jumper GH but not merged by the original author
- specific Gideros Luau Enhancements
The library has been tested quite thoroughly but I am no Pathfinding expert.
You can download the Library and extract it as is in your assets folder:
Demos
-- https://github.com/Yonaba/Jumper/tree/master/examples
local Grid = require "Jumper/grid"
local Pathfinder = require "Jumper/pathfinder"
-- bg
application:setBackgroundColor(0x555555)
-- pathfinding map (must be rectangle/square shaped)
local mapping = {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,},
{1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,1,},
{1,0,5,0,0,0,0,0,0,0,0,0,0,0,0,1,},
{1,0,0,3,3,0,0,0,0,0,0,0,0,0,0,1,},
{1,0,2,2,2,2,0,0,0,2,0,0,0,0,0,1,},
{1,0,0,0,0,0,2,2,2,0,0,0,0,0,0,1,},
{1,0,0,0,0,0,2,2,2,0,0,0,0,0,0,1,},
{1,0,0,0,0,0,2,2,2,0,0,0,0,0,0,1,},
{1,0,0,2,2,2,2,0,0,0,0,0,0,0,0,1,},
{1,0,0,0,2,0,0,0,0,0,0,0,0,0,0,1,},
{1,0,0,3,3,0,0,0,0,0,0,0,0,0,0,1,},
{1,0,3,3,0,0,0,0,0,0,0,0,0,0,0,1,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,},
}
-- map settings
local CELL_W, CELL_H = 32, 32
-- a player1
local player1 = Pixel.new(0x550000, 1, 8*2, 8*2)
local p1w, p1h = player1:getDimensions()
player1:setAnchorPosition(-(CELL_W-p1w)/2, -(CELL_H-p1h)/2)
local p1col, p1row -- we set the player1 position when we draw the map
local mc = MovieClip.new({{0,0,player1}}, true) -- movieclip to simulate player1 movement
-- pathfinding walkable
--local walkable = 0 -- for a single value
local function walkable(value) -- for multiple values
-- return value:match("[#.*]") -- for special characters
return value == 0 or value == 3 -- values 0 and 3 are walkable
end
-- drawing the map
local map = Sprite.new()
for row = 1, #mapping do
for col = 1, #mapping[1] do
local pix = Pixel.new(0xaaff00, 1, CELL_W, CELL_H)
if mapping[row][col] == 0 then pix:setColor(0xaaff00) -- ground
elseif mapping[row][col] == 1 then pix:setColor(0xff5500) -- walls
elseif mapping[row][col] == 2 then pix:setColor(0xffaa00) -- sand
elseif mapping[row][col] == 3 then pix:setColor(0x00aaff) -- water
elseif mapping[row][col] == 5 then p1col = col; p1row = row -- 5 = player1 starting position
else pix:setColor(math.random(0xff0000)) -- unknown cell
end
pix:setPosition(col*CELL_W, row*CELL_H)
map:addChild(pix)
end
end
local grid = Grid(mapping)
local myFinder = Pathfinder(grid, "ASTAR", walkable) -- steps
--local myFinder = Pathfinder(grid, "DIJKSTRA", walkable) -- steps
--local myFinder = Pathfinder(grid, "THETASTAR", walkable) -- straight
--local myFinder = Pathfinder(grid, "BFS", walkable) -- steps
--local myFinder = Pathfinder(grid, "DFS", walkable) -- the longest steps path!!!
--local myFinder = Pathfinder(grid, "JPS", walkable) -- straight, the fastest
-- finder params
--myFinder:setTunnelling(true)
-- position
player1:setPosition(p1col*CELL_W, p1row*CELL_H)
mapping[p1row][p1col] = 0 -- make player1 starting position walkable (row, col)
-- order
stage:addChild(map)
stage:addChild(player1)
stage:addChild(mc)
-- listeners
local anims = {} -- for the movieclip
local timing = 8*1.5 -- for the movieclip
local completed = true -- allows movement only when previous completed
local function pathmove(path)
-- print(('Step: %d -> x: %d -> y: %d'):format(count, node:getX(), node:getY()))
completed = false -- processing movements
for node, count in path:nodes() do
p1col, p1row = node:getX(), node:getY() -- set new player1 position
anims[count] = {
(count-1)*timing+1, count*timing, player1,
{
x = p1col*CELL_W,
y = p1row*CELL_H,
}
}
end
mc = MovieClip.new(anims)
mc:play() -- play only once
mc:addEventListener(Event.COMPLETE, function()
completed = true -- movements complete
anims = {}
end)
end
local walls = {} -- create a list of walls we can add/remove
map:addEventListener(Event.MOUSE_UP, function(e)
if map:hitTestPoint(e.x, e.y) then
local x, y = map:globalToLocal(e.x, e.y) -- mouse coords on the map
local button, _modifier = e.button, e.modifiers
local mapcol, maprow = x//CELL_W, y//CELL_H -- convert mouse coords to map coords
if button == 2 then -- RMB add/remove walls
-- if mapping[maprow][mapcol] == 0 then -- one walkable
if walkable(mapping[maprow][mapcol]) then -- multiple walkable
if not walls[maprow..mapcol] then -- create only one wall per cell
walls[maprow..mapcol] = {
index=mapping[maprow][mapcol],
pixel=Pixel.new(0x000000, 0.5, CELL_W, CELL_H),
}
end
walls[maprow..mapcol].pixel:setPosition(mapcol*CELL_W, maprow*CELL_H)
map:addChild(walls[maprow..mapcol].pixel)
mapping[maprow][mapcol] = 1 -- set the cell as being a wall
else -- wall already exist hide it
if walls[maprow..mapcol] then
walls[maprow..mapcol].pixel:setVisible(false)
mapping[maprow][mapcol] = walls[maprow..mapcol].index -- reset original index
end
end
else -- LMB
if walkable(mapping[maprow][mapcol]) and completed then -- cell is walkable and player1 has finished moving
local path = myFinder:getPath(p1col, p1row, mapcol, maprow) -- pathfinding
if path then pathmove(path) end
else
print("UNREACHABLE DESTINATION!")
end
end
e:stopPropagation()
end
end)
Left click somewhere on the grass to move the player, right click to add/remove walls
Demo 2: clearance
-- Tests sample for clearance metrics calculation
-- See Figure 10 at http://aigamedev.com/open/tutorial/clearance-based-pathfinding/
-- https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
local Grid = require "Jumper/grid"
local PF = require "Jumper/pathfinder"
local map = {
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,2,0},
{0,0,1,1,1,0,0,2,0,0},
{0,0,0,1,1,0,2,0,0,2},
{0,0,0,0,1,0,0,0,0,2},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
}
local grid = Grid(map)
local walkable = function(v) return v~=2 end
local finder = PF(grid, "ASTAR", walkable)
finder:annotateGrid()
for y = 1, #map do
local s = ""
for x = 1, #map[y] do
local node = grid:getNodeAt(x, y)
s = (s .. " " .. node:getClearance(walkable))
end
print(s)
end
--[[
-- Expected output
-- 6 6 5 5 4 4 4 3 2 1
-- 6 5 5 4 4 3 3 3 2 1
-- 6 5 4 4 3 3 2 2 2 1
-- 6 5 4 3 3 2 2 1 1 1
-- 6 5 4 3 2 2 1 1 0 1
-- 5 5 4 3 2 1 1 0 1 1
-- 4 4 4 3 2 1 0 2 1 0
-- 3 3 3 3 3 3 3 2 1 0
-- 2 2 2 2 2 2 2 2 2 1
-- 1 1 1 1 1 1 1 1 1 1
]]
Demo 3: Heuristics
--- Example of use for Heuristics
local Grid = require "Jumper/grid"
local Pathfinder = require "Jumper/pathfinder"
local map = {
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,1,1,0,1,1,0},
{0,1,1,0,1,1,0},
{0,1,1,0,1,1,0},
{0,1,1,0,1,1,0},
{0,1,1,0,1,1,0},
{0,1,1,0,1,1,0},
{0,1,1,0,1,1,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
}
local walkable = 0
local grid = Grid(map)
local myFinder = Pathfinder(grid, "ASTAR", walkable)
-- Use Euclidean heuristic to evaluate distance
myFinder:setHeuristic("EUCLIDEAN")
myFinder:setHeuristic("DIAGONAL")
myFinder:setHeuristic("MANHATTAN")
-- Custom
local h = function(nodeA, nodeB)
return (
0.1 * (-(nodeA:getX() - nodeB:getX()) <> (nodeA:getX() - nodeB:getX())) +
0.9 * (-(nodeA:getY() - nodeB:getY()) <> (nodeA:getY() - nodeB:getY()))
)
end
myFinder:setHeuristic(h)
local p = myFinder:getPath(1,1, 6,10)
for node, count in p:nodes() do
print(("%d. Node(%d,%d)"):format(count, node:getX(), node:getY()))
end
print(("Path length: %.2f"):format(p:getLength()))
-- etc ...
Demo 4: Benchmark
-- A stress test for the pathfinding library Jumper (v1.8.1)
-- Source: https://github.com/Yonaba/Jumper/tree/jumper-1.8.1-1
-- The purpose of this is to compare the relative performance of different
-- search algorithms implemented in Jumper. Time measurements uses Lua's
-- native os.clock with (milliseconds precision).
-- Library setup
local Grid = require "Jumper/grid"
local Pathfinder = require "Jumper/pathfinder"
-- Local references
local cg = collectgarbage
local floor, rand = math.floor, math.random
local ipairs = ipairs
-- Random seed for random generation
math.randomseed(os.time())
-- This function adds unwalkable tiles to a given map.
-- P is the percentage of unwalkable locations, in [0 .. 1]
-- In this demo, we can let it be 0.3 (i.e. 30%)
local function obstruct(map, h, w, p)
-- skipping the borders to ensure generating a solvable problem
for y = 2, h-1 do
for x = 2, w-1 do
map[y][x] = math.random() < p and 1 or 0 -- random weighting
end
end
end
-- A custom function to draw visually the collision map.
local function drawGrid(m)
for y,row in ipairs(m) do print(table.concat(row)) end
end
-- Creates the collision map, adds unwalkable tiles
-- and returns it along with the memory consumed to store the grid
local function makeGrid(w, h, p)
local m = {}
for y = 1, h do m[y] = {}
for x = 1, w do m[y][x] = 0 end
end
obstruct(m, h, w, p)
-- drawGrid(m)
local sizeCount = cg("count")
local grid = Grid(m)
return grid, (cg("count")-sizeCount)
end
-- Performs a path request and return the path, its length and the time of search in ms.
local function findPath(finder, w, h)
local tm = os.clock()
local path = finder:getPath(1, 1, w, h)
local etm = os.clock()
assert(path, "path not found")
return path, path:getLength(), (etm-tm)*1000
end
local walkable = 0
--local test_sizes = {10, 20, 50, 100, 250, 500, 600, 1000} -- set of grid resolutions to be tested
local test_sizes = {8, 16, 32, 256} -- set of grid resolutions to be tested
local percentage_of_unwalkable_tiles = 0.3
for i, resol in ipairs(test_sizes) do
collectgarbage()
print(("\nGenerating a grid of : %d cells x %d cells..."):format(resol, resol))
local grid, size = makeGrid(resol, resol, percentage_of_unwalkable_tiles)
print(("Memory used to store the grid (%d x %d): %d kiB"):format(resol, resol, size))
local results = {}
for _, finderName in ipairs(Pathfinder:getFinders()) do
local finder = Pathfinder:new(grid, finderName, walkable)
local p, len, tm = findPath(finder, resol, resol)
if p then
results[#results+1] = {f = finderName, len = len, time = tm}
end
end
table.sort(results, function(a,b) return a.time < b.time end)
for k, v in ipairs(results) do
print((" %-08s - path length: %d - Time: %.2f ms"):format(v.f, v.len, v.time))
end
end
