diff options
| -rw-r--r-- | src/lua-star.lua | 61 | ||||
| -rw-r--r-- | tests/lua-star_spec.lua | 200 | ||||
| -rw-r--r-- | tests/performance.lua | 27 |
3 files changed, 144 insertions, 144 deletions
diff --git a/src/lua-star.lua b/src/lua-star.lua index 7c337b0..37b3dc9 100644 --- a/src/lua-star.lua +++ b/src/lua-star.lua @@ -26,7 +26,7 @@ end -- (Internal) Returns a unique key for the start and end points. local function keyOf(start, goal) - return string.format("%d,%d>%d,%d", start.x, start.y, goal.x, goal.y) + return string.format("%d,%d,%d>%d,%d,%d", start.x, start.y, start.z, goal.x, goal.y, goal.z) end -- (Internal) Returns the cached path for start and end points. @@ -47,10 +47,11 @@ end -- (Internal) Return the distance between two points. -- This method doesn't bother getting the square root of s, it is faster -- and it still works for our use. -local function distance(x1, y1, x2, y2) +local function distance(x1, y1, z1, x2, y2, z2) local dx = x1 - x2 local dy = y1 - y2 - local s = dx * dx + dy * dy + local dz = z1 - z2 + local s = dx * dx + dy * dy + dz * dz return s end @@ -66,7 +67,7 @@ end local function calculateScore(previous, node, goal) local G = previous.score + 1 - local H = distance(node.x, node.y, goal.x, goal.y) + local H = distance(node.x, node.y, node.z, goal.x, goal.y, goal.z) return G + H, G, H end @@ -74,7 +75,7 @@ end -- (Internal) Returns true if the given list contains the specified item. local function listContains(list, item) for _, test in ipairs(list) do - if test.x == item.x and test.y == item.y then + if test.x == item.x and test.y == item.y and test.z == item.z then return true end end @@ -84,43 +85,39 @@ end -- (Internal) Returns the item in the given list. local function listItem(list, item) for _, test in ipairs(list) do - if test.x == item.x and test.y == item.y then + if test.x == item.x and test.y == item.y and test.z == item.z then return test end end end -- (Internal) Requests adjacent map values around the given node. -local function getAdjacent(width, height, node, positionIsOpenFunc, includeDiagonals) +local function getAdjacent(width, height, depth, node, positionIsOpenFunc, includeDiagonals) local result = { } - local positions = { - { x = 0, y = -1 }, -- top - { x = -1, y = 0 }, -- left - { x = 0, y = 1 }, -- bottom - { x = 1, y = 0 }, -- right - } - - if includeDiagonals then - local diagonalMovements = { - { x = -1, y = -1 }, -- top left - { x = 1, y = -1 }, -- top right - { x = -1, y = 1 }, -- bot left - { x = 1, y = 1 }, -- bot right - } - - for _, value in ipairs(diagonalMovements) do - table.insert(positions, value) - end + local positions = {} + + for x = -1, 1 do + for y = -1, 1 do + for z = -1, 1 do + local a = math.abs(x) + math.abs(y) + math.abs(z) + + if a ~= 0 and includeDiagonals or a == 1 then + table.insert(positions, {x = x, y = y, z = z}) + end + end + end end for _, point in ipairs(positions) do local px = clamp(node.x + point.x, 1, width) local py = clamp(node.y + point.y, 1, height) - local value = positionIsOpenFunc( px, py ) + local pz = clamp(node.z + point.z, 1, depth) + + local value = positionIsOpenFunc( px, py, pz ) if value then - table.insert( result, { x = px, y = py } ) + table.insert( result, { x = px, y = py, z = pz } ) end end @@ -129,7 +126,7 @@ local function getAdjacent(width, height, node, positionIsOpenFunc, includeDiago end -- Returns the path from start to goal, or false if no path exists. -function module:find(width, height, start, goal, positionIsOpenFunc, useCache, excludeDiagonalMoving) +function module:find(width, height, depth, start, goal, positionIsOpenFunc, useCache, excludeDiagonalMoving) if useCache then local cachedPath = getCached(start, goal) @@ -144,8 +141,8 @@ function module:find(width, height, start, goal, positionIsOpenFunc, useCache, e start.score = 0 start.G = 0 - start.H = distance(start.x, start.y, goal.x, goal.y) - start.parent = { x = 0, y = 0 } + start.H = distance(start.x, start.y, start.z, goal.x, goal.y, goal.z) + start.parent = { x = 0, y = 0, z = 0 } table.insert(open, start) while not success and #open > 0 do @@ -161,7 +158,7 @@ function module:find(width, height, start, goal, positionIsOpenFunc, useCache, e if not success then - local adjacentList = getAdjacent(width, height, current, positionIsOpenFunc, not excludeDiagonalMoving) + local adjacentList = getAdjacent(width, height, depth, current, positionIsOpenFunc, not excludeDiagonalMoving) for _, adjacent in ipairs(adjacentList) do @@ -193,7 +190,7 @@ function module:find(width, height, start, goal, positionIsOpenFunc, useCache, e while node do - table.insert(path, 1, { x = node.x, y = node.y } ) + table.insert(path, 1, { x = node.x, y = node.y, z = node.z } ) node = listItem(closed, node.parent) end 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 )) |