Pathfinding
From GiderosMobile
Pathfinding
Jumper by Roland Yonaba
"Jumper, very fast pathfinder for 2d grid based games"
Our first Pathfinder library will be Jumper written by Roland Yonaba. It 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
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:
Media:GJumper.zip
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
