Easy A* path finding for Lua
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
example
src
tests
.busted
.gitignore
.travis.yml
LICENSE
README.md

README.md

lua-star

Build Status Lua-star is a pure Lua A* path-finding library.

lua star example screenshot

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

For running unit tests:

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

Performance

There is a performance measurement tool in tests/performance.lua, it calculates the average time to find a path on a large, random map.

# copy the lib to tests
$ cp ../src/lua-star.lua .

# measure performance
$ lua performance.lua
Running with seed 1540584306
Building a map of 3000x3000...
Precalculating 6000 random start/goal positions...
Finding 1000 paths...
    Done in 16.37 seconds.
    That is 0.0164 seconds, or 16 milliseconds, per path.
    The map has 9.0 million locations, with about 65% open space.

Example

There is an interactive example that can be run with Love.

License

See the file LICENSE