return mymap[x][y] == walkable
end
- local path = luastar:find(width, height, start, goal, positionIsOpenFunc, useCache)
+ local path = luastar:find(width, height, start, goal, positionIsOpenFunc, useCache, excludeDiagonalMoving)
`path` will be false if no path was found, otherwise it contains a list of points that travel from `start` to `goal`:
luastar:clearCached()
+`excludeDiagonalMoving` also optional value defaults to `false`. If you want to exclude the possibility of moving diagonally set the value `true`. i.e, by default, diagonal movement is **enabled**
+
# Requirements
* [Lua 5.x](http://www.lua.org/)
end
-- (Internal) Requests adjacent map values around the given node.
-local function getAdjacent(width, height, node, positionIsOpenFunc)
+local function getAdjacent(width, height, node, positionIsOpenFunc, includeDiagonals)
local result = { }
{ x = -1, y = 0 }, -- left
{ x = 0, y = 1 }, -- bottom
{ x = 1, y = 0 }, -- right
- -- include diagonal movements
- { x = -1, y = -1 }, -- top left
- { x = 1, y = -1 }, -- top right
- { x = -1, y = 1 }, -- bot left
- { x = 1, y = 1 }, -- bot 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
+ 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)
end
-- Returns the path from start to goal, or false if no path exists.
-function module:find(width, height, start, goal, positionIsOpenFunc, useCache)
+function module:find(width, height, start, goal, positionIsOpenFunc, useCache, excludeDiagonalMoving)
if useCache then
local cachedPath = getCached(start, goal)
if not success then
- local adjacentList = getAdjacent(width, height, current, positionIsOpenFunc)
+ local adjacentList = getAdjacent(width, height, current, positionIsOpenFunc, not excludeDiagonalMoving)
for _, adjacent in ipairs(adjacentList) do
{ x = 10, y = 10 },
}
+ 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 },
+ }
+
local complexmap = [[
0000000000
1111111110
end)
+ it("find a path on a simple map without diagonam movement", function ()
+
+ local luastar = require("lua-star")
+ local excludeDiagonals = true
+ makemap(simplemap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, false, excludeDiagonals)
+ --printSolution(path)
+ assert.are.equal(19, #path)
+ assert.are.same(simplemapDiagonalSolution, path)
+
+ end)
+
it("find a path on a complex map", function()
local luastar = require("lua-star")
end)
+ it("find no diagonal path", function()
+
+ local luastar = require("lua-star")
+ local excludeDiagonals = true
+ makemap(unsolvablemap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, false, excludeDiagonals)
+ assert.is_false(path)
+
+ end)
+
+ it("find no diagonal path on a complex map", function()
+
+ local luastar = require("lua-star")
+ local excludeDiagonals = true
+ makemap(complexmap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, false, excludeDiagonals)
+ assert.is_false(path)
+
+ end)
+
it("does not cache paths by default", function()
local luastar = require("lua-star")