diff options
| -rw-r--r-- | .busted | 7 | ||||
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | README.md | 67 | ||||
| -rw-r--r-- | example/lua-star-01.png | bin | 0 -> 11209 bytes | |||
| -rw-r--r-- | example/main.lua | 107 | ||||
| -rw-r--r-- | src/lua-star.lua | 208 | ||||
| -rw-r--r-- | tests/lua-star_spec.lua | 250 |
7 files changed, 640 insertions, 0 deletions
@@ -0,0 +1,7 @@ +return { + default = { + verbose = true, + coverage = false, + ROOT = {"tests"}, + } +} diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..a813bbb --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +example/lua-star.lua @@ -1,2 +1,69 @@ # 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) diff --git a/example/lua-star-01.png b/example/lua-star-01.png Binary files differnew file mode 100644 index 0000000..50bbed8 --- /dev/null +++ b/example/lua-star-01.png diff --git a/example/main.lua b/example/main.lua new file mode 100644 index 0000000..460d99c --- /dev/null +++ b/example/main.lua @@ -0,0 +1,107 @@ +--[[ + + 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 diff --git a/src/lua-star.lua b/src/lua-star.lua new file mode 100644 index 0000000..38c512c --- /dev/null +++ b/src/lua-star.lua @@ -0,0 +1,208 @@ +--[[ + 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 diff --git a/tests/lua-star_spec.lua b/tests/lua-star_spec.lua new file mode 100644 index 0000000..65a8722 --- /dev/null +++ b/tests/lua-star_spec.lua @@ -0,0 +1,250 @@ +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) + |
