--- /dev/null
+return {
+ default = {
+ verbose = true,
+ coverage = false,
+ ROOT = {"tests"},
+ }
+}
--- /dev/null
+example/lua-star.lua
# lua-star
+
Easy A* path finding for Lua
+
+[lua star example screenshot](example/lua-star-01.png)
+
+# Quick Start
+
+Easy to use, it will make you more attractive and you feel sensual doing so.
+
+ local luastar = require("lua-star")
+
+ function positionIsOpenFunc(x, y)
+ -- should return true if the position is open to walk
+ return mymap[x][y] == walkable
+ end
+
+ local path = luastar:find(width, height, start, goal, positionIsOpenFunc, useCache)
+
+`path` will be false if no path was found, otherwise it contains a list of points that travel from `start` to `goal`:
+
+ if path then
+ for _, p in ipairs(path) do
+ print(p.x, p.y)
+ end
+ end
+
+Lua star does not care how your map data is arranged, it simply asks you if the map position at `x,y` is walkable via a callback.
+
+`width` and `height` is your map size.
+
+`start` and `goal` are tables with at least the `x` and `y` keys.
+
+ local start = { x = 1, y = 10 }
+ local goal = { x = 10, y = 1 }
+
+`positionIsOpenFunc(x, y)` is a function that should return true if the position is open to walk.
+
+`useCache` is optional and defaults to `false` when not given. If you have a map that does not change, caching can give a speed boost.
+
+If at any time you need to clear all cached paths;
+
+ luastar:clearCached()
+
+# Requirements
+
+* [Lua 5.x](http://www.lua.org/)
+
+For running unit tests:
+
+* [Lua Rocks](https://luarocks.org/)
+* busted
+
+These commands are for apt-based systems, please adapt to them as needed.
+
+ sudo apt-get install luarocks
+ sudo luarocks install busted
+
+Unit testing is done with busted, the `.busted` config already defines everything, so simply run:
+
+ busted
+
+# Example
+
+There is an [interactive example](example/main.lua) that can be run with [Love](https://love2d.org).
+
+# License
+
+See the file [LICENSE](LICENSE)
--- /dev/null
+--[[
+
+ Lua star example - Run with love (https://love2d.org/)
+
+ Copyright 2017 wesley werner <wesley.werner@gmail.com>
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see http://www.gnu.org/licenses/.
+
+]]--
+
+local luastar = require("lua-star")
+
+-- a 2D map where true is open and false is blocked
+local map = { }
+local mapsize = 10
+local screensize = 500
+local tilesize = screensize / mapsize
+
+-- path start and end
+local path = nil
+local start = { x = 1, y = 10 }
+local goal = { x = 10, y = 1 }
+
+function love.load()
+
+ love.window.setMode( screensize, screensize )
+
+ -- build an open map
+ for x=1, mapsize do
+ map[x] = {}
+ for y=1, mapsize do
+ map[x][y] = true
+ end
+ end
+
+ requestPath()
+
+end
+
+function love.keypressed(key)
+
+ if key == "escape" then
+ love.event.quit()
+ end
+
+end
+
+function love.draw()
+
+ -- draw walls
+ love.graphics.setColor(255, 255, 255)
+ for x=1, mapsize do
+ for y=1, mapsize do
+ local fillstyle = "line"
+ if map[x][y] == false then fillstyle = "fill" end
+ love.graphics.rectangle(fillstyle, (x-1)*tilesize, (y-1)*tilesize, tilesize, tilesize)
+ end
+ end
+
+ -- draw start and end
+ love.graphics.print("START", (start.x-1) * tilesize, (start.y-1) * tilesize)
+ love.graphics.print("GOAL", (goal.x-1) * tilesize, (goal.y-1) * tilesize)
+
+ -- draw the path
+ if path then
+ for i, p in ipairs(path) do
+ love.graphics.setColor(0, 128, 0)
+ love.graphics.rectangle("fill", (p.x-1)*tilesize, (p.y-1)*tilesize, tilesize, tilesize)
+ love.graphics.setColor(255, 255, 255)
+ love.graphics.print(i, (p.x-1) * tilesize, (p.y-1) * tilesize)
+ end
+ end
+
+end
+
+function love.mousepressed( x, y, button, istouch )
+
+ local dx = math.floor(x / tilesize) + 1
+ local dy = math.floor(y / tilesize) + 1
+ map[dx][dy] = not map[dx][dy]
+ requestPath()
+
+end
+
+function positionIsOpenFunc(x, y)
+
+ -- should return true if the position is open to walk
+ return map[x][y]
+
+end
+
+function requestPath()
+
+ path = luastar:find(mapsize, mapsize, start, goal, positionIsOpenFunc)
+
+end
--- /dev/null
+--[[
+ lua-star.lua
+
+ Copyright 2017 wesley werner <wesley.werner@gmail.com>
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see http://www.gnu.org/licenses/.
+
+ References:
+ https://en.wikipedia.org/wiki/A*_search_algorithm
+ https://www.redblobgames.com/pathfinding/a-star/introduction.html
+ https://www.raywenderlich.com/4946/introduction-to-a-pathfinding
+]]--
+
+--- Provides easy A* path finding.
+-- @module lua-star
+
+local module = {}
+
+--- Clears all cached paths.
+function module:clearCached()
+ module.cache = nil
+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)
+end
+
+-- (Internal) Returns the cached path for start and end points.
+local function getCached(start, goal)
+ if module.cache then
+ local key = keyOf(start, goal)
+ return module.cache[key]
+ end
+end
+
+-- (Internal) Saves a path to the cache.
+local function saveCached(start, goal, path)
+ module.cache = module.cache or { }
+ local key = keyOf(start, goal)
+ module.cache[key] = path
+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 dx = x1 - x2
+ local dy = y1 - y2
+ local s = dx * dx + dy * dy
+ return s
+end
+
+-- (Internal) Clamp a value to a range.
+local function clamp(x, min, max)
+ return x < min and min or (x > max and max or x)
+end
+
+-- (Internal) Return the score of a node.
+-- G is the cost from START to this node.
+-- H is a heuristic cost, in this case the distance from this node to the goal.
+-- Returns F, the sum of G and H.
+local function calculateScore(previous, node, goal)
+
+ local G = previous.score + 1
+ local H = distance(node.x, node.y, goal.x, goal.y)
+ return G + H, G, H
+
+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
+ return true
+ end
+ end
+ return false
+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
+ return test
+ end
+ end
+end
+
+-- (Internal) Requests adjacent map values around the given node.
+local function getAdjacent(width, height, node, positionIsOpenFunc)
+
+ local result = { }
+
+ local positions = {
+ { x = 0, y = -1 }, -- top
+ { 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
+ }
+
+ 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 )
+ if value then
+ table.insert( result, { x = px, y = py } )
+ end
+ end
+
+ return result
+
+end
+
+-- Returns the path from start to goal, or false if no path exists.
+function module:find(width, height, start, goal, positionIsOpenFunc, useCache)
+
+ if useCache then
+ local cachedPath = getCached(start, goal)
+ if cachedPath then
+ return cachedPath
+ end
+ end
+
+ local success = false
+ local open = { }
+ local closed = { }
+
+ start.score = 0
+ start.G = 0
+ start.H = distance(start.x, start.y, goal.x, goal.y)
+ start.parent = { x = 0, y = 0 }
+ table.insert(open, start)
+
+ while not success and #open > 0 do
+
+ -- sort by score: high to low
+ table.sort(open, function(a, b) return a.score > b.score end)
+
+ local current = table.remove(open)
+
+ table.insert(closed, current)
+
+ success = listContains(closed, goal)
+
+ if not success then
+
+ local adjacentList = getAdjacent(width, height, current, positionIsOpenFunc)
+
+ for _, adjacent in ipairs(adjacentList) do
+
+ if not listContains(closed, adjacent) then
+
+ if not listContains(open, adjacent) then
+
+ adjacent.score = calculateScore(current, adjacent, goal)
+ adjacent.parent = current
+ table.insert(open, adjacent)
+
+ end
+
+ end
+
+ end
+
+ end
+
+ end
+
+ if not success then
+ return false
+ end
+
+ -- traverse the parents from the last point to get the path
+ local node = listItem(closed, closed[#closed])
+ local path = { }
+
+ while node do
+
+ table.insert(path, 1, { x = node.x, y = node.y } )
+ node = listItem(closed, node.parent)
+
+ end
+
+ saveCached(start, goal, path)
+
+ -- reverse the closed list to get the solution
+ return path
+
+end
+
+return module
--- /dev/null
+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 map = nil
+
+ -- define some test maps (10 x 10)
+ local mapsize = 10
+ local openmap = [[
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ ]]
+
+ 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 },
+ }
+
+ local simplemap = [[
+ 0000000000
+ 0000000110
+ 0000001110
+ 0000011100
+ 0000111000
+ 0001110000
+ 0011100000
+ 0111000000
+ 0000000000
+ 0000000000
+ ]]
+
+ 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 },
+ }
+
+ local complexmap = [[
+ 0000000000
+ 1111111110
+ 0000000000
+ 0111111111
+ 0100110000
+ 0101010100
+ 0001010110
+ 1111011010
+ 0000000010
+ 0000000010
+ ]]
+
+ 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 },
+ }
+
+ local unsolvablemap = [[
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 1111111111
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ 0000000000
+ ]]
+
+ -- convert a string map into a table
+ local function makemap(template)
+ map = { }
+ template:gsub(".", function(c)
+ if c == "0" or c == "1" then
+ table.insert(map, c)
+ end
+ end)
+ end
+
+ -- get the value at position xy on a map
+ local function mapTileIsOpen(x, y)
+ return map[ ((y-1) * 10) + x ] == "0"
+ end
+
+ local function printSolution(path)
+ print(#path, "points")
+ for i, v in ipairs(path) do
+ print(string.format("{ x = %d, y = %d },", v.x, v.y))
+ end
+ for h=1, mapsize do
+ for w=1, mapsize do
+ local walked = false
+ for _, p in ipairs(path) do
+ if p.x == w and p.y == h then
+ walked = true
+ end
+ end
+ if walked then
+ io.write(".")
+ else
+ io.write("#")
+ end
+ end
+ io.write("\n")
+ end
+ end
+
+ -- begin tests
+
+ it("find a path with no obstacles", function()
+
+ local luastar = require("lua-star")
+ makemap(openmap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
+ --printSolution(path)
+ assert.are.equal(10, #path)
+ assert.are.same(openmapSolution, path)
+
+ end)
+
+ it("find a path on a simple map", function()
+
+ local luastar = require("lua-star")
+ makemap(simplemap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
+ --printSolution(path)
+ assert.are.equal(17, #path)
+ assert.are.same(simplemapSolution, path)
+
+ end)
+
+ it("find a path on a complex map", function()
+
+ local luastar = require("lua-star")
+ makemap(complexmap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
+ --printSolution(path)
+ assert.are.equal(38, #path)
+ assert.are.same(complexmapSolution, path)
+
+ end)
+
+ it("find no path", function()
+
+ local luastar = require("lua-star")
+ makemap(unsolvablemap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen)
+ assert.is_false(path)
+
+ end)
+
+ it("does not cache paths by default", 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)
+ assert.is_not.equal(path, samepath)
+
+ end)
+
+ it("caches paths", 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)
+ assert.are.equal(path, samepath)
+
+ end)
+
+ it("clears cached paths", function()
+
+ local luastar = require("lua-star")
+ makemap(openmap)
+ local path = luastar:find(mapsize, mapsize, start, goal, mapTileIsOpen, true)
+ luastar:clearCached()
+ assert.is_nil(luastar.cache)
+
+ end)
+
+end)
+
projects / lua-star.git / commitdiff
