A stress test for the pathfinding library Jumper (v1.8.1)

Jumper_Stress_Test.lua

-- 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'

-- Some 
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 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

Test_Output

> Tested on a Intel(R) Core(TM) i3-3110M CPU @2.40Ghz (Dual)
>lua -e "io.stdout:setvbuf 'no'" "test.lua" 

Generating a grid of : 10 cells x 10 cells...
Memory used to store the grid (10 x 10): 11 kiB
  DIJKSTRA - path length: 16 - Time: 0.00 ms
  ASTAR    - path length: 16 - Time: 0.00 ms
  DFS      - path length: 23 - Time: 0.00 ms
  BFS      - path length: 16 - Time: 15.00 ms
  JPS      - path length: 16 - Time: 16.00 ms

Generating a grid of : 20 cells x 20 cells...
Memory used to store the grid (20 x 20): 39 kiB
  BFS      - path length: 31 - Time: 0.00 ms
  DFS      - path length: 36 - Time: 0.00 ms
  DIJKSTRA - path length: 31 - Time: 0.00 ms
  ASTAR    - path length: 31 - Time: 15.00 ms
  JPS      - path length: 33 - Time: 16.00 ms

Generating a grid of : 50 cells x 50 cells...
Memory used to store the grid (50 x 50): 226 kiB
  JPS      - path length: 81 - Time: 0.00 ms
  DIJKSTRA - path length: 77 - Time: 0.00 ms
  ASTAR    - path length: 81 - Time: 15.00 ms
  DFS      - path length: 102 - Time: 16.00 ms
  BFS      - path length: 78 - Time: 16.00 ms

Generating a grid of : 100 cells x 100 cells...
Memory used to store the grid (100 x 100): 887 kiB
  DFS      - path length: 272 - Time: 15.00 ms
  ASTAR    - path length: 161 - Time: 15.00 ms
  JPS      - path length: 160 - Time: 15.00 ms
  DIJKSTRA - path length: 156 - Time: 32.00 ms
  BFS      - path length: 157 - Time: 63.00 ms

Generating a grid of : 250 cells x 250 cells...
Memory used to store the grid (250 x 250): 5395 kiB
  ASTAR    - path length: 424 - Time: 16.00 ms
  JPS      - path length: 424 - Time: 46.00 ms
  DFS      - path length: 614 - Time: 125.00 ms
  DIJKSTRA - path length: 399 - Time: 187.00 ms
  BFS      - path length: 403 - Time: 343.00 ms

Generating a grid of : 500 cells x 500 cells...
Memory used to store the grid (500 x 500): 21555 kiB
  DFS      - path length: 1248 - Time: 46.00 ms
  JPS      - path length: 840 - Time: 82.00 ms
  ASTAR    - path length: 840 - Time: 94.00 ms
  DIJKSTRA - path length: 778 - Time: 780.00 ms
  BFS      - path length: 783 - Time: 1685.00 ms

Generating a grid of : 600 cells x 600 cells...
Memory used to store the grid (600 x 600): 32957 kiB
  JPS      - path length: 963 - Time: 93.00 ms
  ASTAR    - path length: 972 - Time: 125.00 ms
  DFS      - path length: 1490 - Time: 718.00 ms
  DIJKSTRA - path length: 935 - Time: 1295.00 ms
  BFS      - path length: 940 - Time: 2537.00 ms

Generating a grid of : 1000 cells x 1000 cells...
Memory used to store the grid (1000 x 1000): 86151 kiB
  JPS      - path length: 1640 - Time: 126.00 ms
  DFS      - path length: 2665 - Time: 206.00 ms
  ASTAR    - path length: 1645 - Time: 313.00 ms
  DIJKSTRA - path length: 1564 - Time: 3556.00 ms
  BFS      - path length: 1582 - Time: 8689.00 ms
Program completed in 23.91 seconds (pid: 1420).