From fedc1dc38c4a6d3106de88acc1076e1fb2e53720 Mon Sep 17 00:00:00 2001
From: NickFlexer <nickkomarov.job@gmail.com>
Date: Mon, 24 May 2021 14:52:20 +0300
Subject: [PATCH] added option to disable diagonal movement

---
 README.md               |  4 ++-
 src/lua-star.lua        | 24 ++++++++++++------
 tests/lua-star_spec.lua | 54 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 73 insertions(+), 9 deletions(-)

diff --git a/README.md b/README.md
index 3bee2eb..1912d8d 100644
--- a/README.md
+++ b/README.md
@@ -15,7 +15,7 @@ Easy to use, it will make you more attractive and you feel sensual doing so.
         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`:
 
@@ -42,6 +42,8 @@ If at any time you need to clear all cached paths:
 
     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/)
diff --git a/src/lua-star.lua b/src/lua-star.lua
index b8306d9..7c337b0 100644
--- a/src/lua-star.lua
+++ b/src/lua-star.lua
@@ -91,7 +91,7 @@ local function listItem(list, item)
 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 = { }
 
@@ -100,13 +100,21 @@ local function getAdjacent(width, height, node, positionIsOpenFunc)
         { 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)
@@ -121,7 +129,7 @@ local function getAdjacent(width, height, node, positionIsOpenFunc)
 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)
@@ -153,7 +161,7 @@ function module:find(width, height, start, goal, positionIsOpenFunc, useCache)
 
         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
 
diff --git a/tests/lua-star_spec.lua b/tests/lua-star_spec.lua
index 65a8722..53df343 100644
--- a/tests/lua-star_spec.lua
+++ b/tests/lua-star_spec.lua
@@ -67,6 +67,28 @@ describe("Lua star", function()
         { 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
@@ -196,6 +218,18 @@ describe("Lua star", function()
 
     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")
@@ -216,6 +250,26 @@ describe("Lua star", function()
 
     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")
-- 
2.44.0