Pathfinding

From GiderosMobile
Revision as of 09:49, 6 December 2023 by MoKaLux (talk | contribs) (Created page with "__TOC__ === Pathfinding === ==== Jumper by Roland Yonaba ==== "'''''Jumper, very fast pathfinder for 2d grid based games'''''" Our first Pathfinder library will be '''''Jump...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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


Retrieved from ‘https://wiki.gideros.rocks/index.php?title=Pathfinding&oldid=23226’