diff options
Diffstat (limited to 'tests')
| -rw-r--r-- | tests/lua-star_spec.lua | 200 | ||||
| -rw-r--r-- | tests/performance.lua | 27 |
2 files changed, 115 insertions, 112 deletions
diff --git a/tests/lua-star_spec.lua b/tests/lua-star_spec.lua index 53df343..593c710 100644 --- a/tests/lua-star_spec.lua +++ b/tests/lua-star_spec.lua @@ -2,8 +2,8 @@ describe("Lua star", function() -- start is always top left (1,1) -- goal is always bottom right (10, 10) - local start = { x = 1, y = 1 } - local goal = { x = 10, y = 10 } + local start = { x = 1, y = 1, z = 1 } + local goal = { x = 10, y = 10, z = 1 } local map = nil -- define some test maps (10 x 10) @@ -22,16 +22,16 @@ describe("Lua star", function() ]] local openmapSolution = { - { x = 1, y = 1 }, - { x = 2, y = 2 }, - { x = 3, y = 3 }, - { x = 4, y = 4 }, - { x = 5, y = 5 }, - { x = 6, y = 6 }, - { x = 7, y = 7 }, - { x = 8, y = 8 }, - { x = 9, y = 9 }, - { x = 10, y = 10 }, + { x = 1, y = 1, z = 1 }, + { x = 2, y = 2, z = 1 }, + { x = 3, y = 3, z = 1 }, + { x = 4, y = 4, z = 1 }, + { x = 5, y = 5, z = 1 }, + { x = 6, y = 6, z = 1 }, + { x = 7, y = 7, z = 1 }, + { x = 8, y = 8, z = 1 }, + { x = 9, y = 9, z = 1 }, + { x = 10, y = 10, z = 1 }, } local simplemap = [[ @@ -48,45 +48,45 @@ describe("Lua star", function() ]] local simplemapSolution = { - { x = 1, y = 1 }, - { x = 2, y = 2 }, - { x = 3, y = 3 }, - { x = 4, y = 4 }, - { x = 4, y = 5 }, - { x = 3, y = 6 }, - { x = 2, y = 7 }, - { x = 1, y = 8 }, - { x = 2, y = 9 }, - { x = 3, y = 10 }, - { x = 4, y = 10 }, - { x = 5, y = 10 }, - { x = 6, y = 10 }, - { x = 7, y = 10 }, - { x = 8, y = 10 }, - { x = 9, y = 10 }, - { x = 10, y = 10 }, + { x = 1, y = 1, z = 1 }, + { x = 2, y = 2, z = 1 }, + { x = 3, y = 3, z = 1 }, + { x = 4, y = 4, z = 1 }, + { x = 4, y = 5, z = 1 }, + { x = 3, y = 6, z = 1 }, + { x = 2, y = 7, z = 1 }, + { x = 1, y = 8, z = 1 }, + { x = 2, y = 9, z = 1 }, + { x = 3, y = 10, z = 1 }, + { x = 4, y = 10, z = 1 }, + { x = 5, y = 10, z = 1 }, + { x = 6, y = 10, z = 1 }, + { x = 7, y = 10, z = 1 }, + { x = 8, y = 10, z = 1 }, + { x = 9, y = 10, z = 1 }, + { x = 10, y = 10, z = 1 }, } local simplemapDiagonalSolution = { - { x = 1, y = 1 }, - { x = 1, y = 2 }, - { x = 1, y = 3 }, - { x = 1, y = 4 }, - { x = 1, y = 5 }, - { x = 1, y = 6 }, - { x = 1, y = 7 }, - { x = 1, y = 8 }, - { x = 1, y = 9 }, - { x = 2, y = 9 }, - { x = 3, y = 9 }, - { x = 4, y = 9 }, - { x = 5, y = 9 }, - { x = 6, y = 9 }, - { x = 7, y = 9 }, - { x = 8, y = 9 }, - { x = 9, y = 9 }, - { x = 9, y = 10 }, - { x = 10, y = 10 }, + { x = 1, y = 1, z = 1 }, + { x = 1, y = 2, z = 1 }, + { x = 1, y = 3, z = 1 }, + { x = 1, y = 4, z = 1 }, + { x = 1, y = 5, z = 1 }, + { x = 1, y = 6, z = 1 }, + { x = 1, y = 7, z = 1 }, + { x = 1, y = 8, z = 1 }, + { x = 1, y = 9, z = 1 }, + { x = 2, y = 9, z = 1 }, + { x = 3, y = 9, z = 1 }, + { x = 4, y = 9, z = 1 }, + { x = 5, y = 9, z = 1 }, + { x = 6, y = 9, z = 1 }, + { x = 7, y = 9, z = 1 }, + { x = 8, y = 9, z = 1 }, + { x = 9, y = 9, z = 1 }, + { x = 9, y = 10, z = 1 }, + { x = 10, y = 10, z = 1 }, } local complexmap = [[ @@ -103,44 +103,44 @@ describe("Lua star", function() ]] local complexmapSolution = { - { x = 1, y = 1 }, - { x = 2, y = 1 }, - { x = 3, y = 1 }, - { x = 4, y = 1 }, - { x = 5, y = 1 }, - { x = 6, y = 1 }, - { x = 7, y = 1 }, - { x = 8, y = 1 }, - { x = 9, y = 1 }, - { x = 10, y = 2 }, - { x = 9, y = 3 }, - { x = 8, y = 3 }, - { x = 7, y = 3 }, - { x = 6, y = 3 }, - { x = 5, y = 3 }, - { x = 4, y = 3 }, - { x = 3, y = 3 }, - { x = 2, y = 3 }, - { x = 1, y = 4 }, - { x = 1, y = 5 }, - { x = 1, y = 6 }, - { x = 2, y = 7 }, - { x = 3, y = 6 }, - { x = 4, y = 5 }, - { x = 5, y = 6 }, - { x = 5, y = 7 }, - { x = 5, y = 8 }, - { x = 6, y = 9 }, - { x = 7, y = 9 }, - { x = 8, y = 8 }, - { x = 7, y = 7 }, - { x = 7, y = 6 }, - { x = 8, y = 5 }, - { x = 9, y = 6 }, - { x = 10, y = 7 }, - { x = 10, y = 8 }, - { x = 10, y = 9 }, - { x = 10, y = 10 }, + { x = 1, y = 1, z = 1 }, + { x = 2, y = 1, z = 1 }, + { x = 3, y = 1, z = 1 }, + { x = 4, y = 1, z = 1 }, + { x = 5, y = 1, z = 1 }, + { x = 6, y = 1, z = 1 }, + { x = 7, y = 1, z = 1 }, + { x = 8, y = 1, z = 1 }, + { x = 9, y = 1, z = 1 }, + { x = 10, y = 2, z = 1 }, + { x = 9, y = 3, z = 1 }, + { x = 8, y = 3, z = 1 }, + { x = 7, y = 3, z = 1 }, + { x = 6, y = 3, z = 1 }, + { x = 5, y = 3, z = 1 }, + { x = 4, y = 3, z = 1 }, + { x = 3, y = 3, z = 1 }, + { x = 2, y = 3, z = 1 }, + { x = 1, y = 4, z = 1 }, + { x = 1, y = 5, z = 1 }, + { x = 1, y = 6, z = 1 }, + { x = 2, y = 7, z = 1 }, + { x = 3, y = 6, z = 1 }, + { x = 4, y = 5, z = 1 }, + { x = 5, y = 6, z = 1 }, + { x = 5, y = 7, z = 1 }, + { x = 5, y = 8, z = 1 }, + { x = 6, y = 9, z = 1 }, + { x = 7, y = 9, z = 1 }, + { x = 8, y = 8, z = 1 }, + { x = 7, y = 7, z = 1 }, + { x = 7, y = 6, z = 1 }, + { x = 8, y = 5, z = 1 }, + { x = 9, y = 6, z = 1 }, + { x = 10, y = 7, z = 1 }, + { x = 10, y = 8, z = 1 }, + { x = 10, y = 9, z = 1 }, + { x = 10, y = 10, z = 1 }, } local unsolvablemap = [[ @@ -167,8 +167,8 @@ describe("Lua star", function() end -- get the value at position xy on a map - local function mapTileIsOpen(x, y) - return map[ ((y-1) * 10) + x ] == "0" + local function mapTileIsOpen(x, y, z) + return z == 1 and map[ ((y-1) * 10) + x ] == "0" end local function printSolution(path) @@ -200,7 +200,7 @@ describe("Lua star", function() local luastar = require("lua-star") makemap(openmap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen) --printSolution(path) assert.are.equal(10, #path) assert.are.same(openmapSolution, path) @@ -211,7 +211,7 @@ describe("Lua star", function() local luastar = require("lua-star") makemap(simplemap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen) --printSolution(path) assert.are.equal(17, #path) assert.are.same(simplemapSolution, path) @@ -223,7 +223,7 @@ describe("Lua star", function() local luastar = require("lua-star") local excludeDiagonals = true makemap(simplemap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, false, excludeDiagonals) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, false, excludeDiagonals) --printSolution(path) assert.are.equal(19, #path) assert.are.same(simplemapDiagonalSolution, path) @@ -234,7 +234,7 @@ describe("Lua star", function() local luastar = require("lua-star") makemap(complexmap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen) --printSolution(path) assert.are.equal(38, #path) assert.are.same(complexmapSolution, path) @@ -245,7 +245,7 @@ describe("Lua star", function() local luastar = require("lua-star") makemap(unsolvablemap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen) assert.is_false(path) end) @@ -255,7 +255,7 @@ describe("Lua star", function() local luastar = require("lua-star") local excludeDiagonals = true makemap(unsolvablemap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, false, excludeDiagonals) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, false, excludeDiagonals) assert.is_false(path) end) @@ -265,7 +265,7 @@ describe("Lua star", function() local luastar = require("lua-star") local excludeDiagonals = true makemap(complexmap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, false, excludeDiagonals) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, false, excludeDiagonals) assert.is_false(path) end) @@ -274,8 +274,8 @@ describe("Lua star", function() local luastar = require("lua-star") makemap(openmap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) - local samepath = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen) + local samepath = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen) assert.is_not.equal(path, samepath) end) @@ -284,8 +284,8 @@ describe("Lua star", function() local luastar = require("lua-star") makemap(openmap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true) - local samepath = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, true) + local samepath = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, true) assert.are.equal(path, samepath) end) @@ -294,7 +294,7 @@ describe("Lua star", function() local luastar = require("lua-star") makemap(openmap) - local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true) + local path = luastar:find(mapsize, mapsize, 1, start, goal, mapTileIsOpen, true) luastar:clearCached() assert.is_nil(luastar.cache) diff --git a/tests/performance.lua b/tests/performance.lua index dfdbafa..eebe536 100644 --- a/tests/performance.lua +++ b/tests/performance.lua @@ -10,39 +10,42 @@ local luastar = require("lua-star") local map = { } -local mapsize = 3000 -local numberOfTests = 1000 -local mapDensity = 0.65 +local mapsize = 20 +local numberOfTests = 1 +local mapDensity = 0.1 local seed = os.time() math.randomseed(seed) print (string.format("Running with seed %d", seed)) -print (string.format("Building a map of %dx%d...", mapsize, mapsize)) +print (string.format("Building a map of %dx%dx%d...", mapsize, mapsize, mapsize)) for x=1, mapsize do map[x] = {} for y=1, mapsize do - map[x][y] = math.random() + map[x][y] = {} + for z=1, mapsize do + map[x][y][z] = math.random() + end end end -- precalculate a bunch of start and goal positions -- doubled up for each start/goal pair -print (string.format("Precalculating %d random start/goal positions...", mapsize * 2)) +print (string.format("Precalculating %d random start/goal positions...", numberOfTests * 2)) local testPoints = { } -for i = 1, mapsize * 2 do - table.insert (testPoints, { x = math.random(1, mapsize), y = math.random(1, mapsize)}) +for i = 1, numberOfTests * 2 do + table.insert (testPoints, { x = math.random(1, mapsize), y = math.random(1, mapsize), z = math.random(1, mapsize)}) end print (string.format("Finding %d paths...", numberOfTests)) -function positionIsOpenFunc(x, y) - return map[x][y] > mapDensity +function positionIsOpenFunc(x, y, z) + return map[x][y][z] > mapDensity end local testStart = os.clock() for testNumber = 1, numberOfTests do luastar:find( - mapsize, mapsize, -- map size + mapsize, mapsize, mapsize, -- map size table.remove (testPoints), -- start table.remove (testPoints), -- goal positionIsOpenFunc) @@ -58,6 +61,6 @@ print (string.format([[ totalSec, -- total seconds pathSec, -- seconds per path pathSec*1000, -- milliseconds per path - (mapsize*mapsize)/1000000, -- number of locations + (mapsize*mapsize*mapsize)/1000000, -- number of locations mapDensity*100 -- % open space on the map )) |