3D Support

diff --git a/src/lua-star.lua b/src/lua-star.lua
index 7c337b065528dcb32ee1e69d339bfbea7c72c68b..37b3dc95a1c31f52b6a31b6e139b4c646498a42a 100644 (file)
--- 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 53df343a9925d278ec964d4ad63a55642e8ee125..593c710912c85731f0b86b77a37989e5a6e09f56 100644 (file)
--- 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 dfdbafac8eecfb1359c9b9395d52792987441e1a..eebe536a5a18db15d6bf3c66583606a8abc066d1 100644 (file)
--- 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
 ))