README.md

   1 # lua-star
   2
   3 [![Build Status](https://travis-ci.org/wesleywerner/lua-star.svg?branch=master)](https://travis-ci.org/wesleywerner/lua-star) Lua-star is a pure Lua A* path-finding library.
   4
   5 ![lua star example screenshot](example/lua-star-01.png)
   6
   7 # Quick Start
   8
   9 Easy to use, it will make you more attractive and you feel sensual doing so.
  10
  11     local luastar = require("lua-star")
  12
  13     function positionIsOpenFunc(x, y)
  14         -- should return true if the position is open to walk
  15         return mymap[x][y] == walkable
  16     end
  17
  18     local path = luastar:find(width, height, start, goal, positionIsOpenFunc, useCache)
  19
  20 `path` will be false if no path was found, otherwise it contains a list of points that travel from `start` to `goal`:
  21
  22     if path then
  23         for _, p in ipairs(path) do
  24             print(p.x, p.y)
  25         end
  26     end
  27
  28 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.
  29
  30 `width` and `height` is your map size.
  31
  32 `start` and `goal` are tables with at least the `x` and `y` keys.
  33
  34     local start = { x = 1, y = 10 }
  35     local goal = { x = 10, y = 1 }
  36
  37 `positionIsOpenFunc(x, y)` is a function that should return true if the position is open to walk.
  38
  39 `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.
  40
  41 If at any time you need to clear all cached paths:
  42
  43     luastar:clearCached()
  44
  45 # Requirements
  46
  47 * [Lua 5.x](http://www.lua.org/)
  48
  49 For running unit tests:
  50
  51 * [Lua Rocks](https://luarocks.org/)
  52 * busted
  53
  54 These commands are for apt-based systems, please adapt to them as needed.
  55
  56     sudo apt-get install luarocks
  57     sudo luarocks install busted
  58
  59 Unit testing is done with busted, the `.busted` config already defines everything, so simply run:
  60
  61     busted
  62
  63 # Performance
  64
  65 There is a performance measurement tool in `tests/performance.lua`, it calculates the average time to find a path on a large, random map.
  66
  67     # copy the lib to tests
  68     $ cp ../src/lua-star.lua .
  69
  70     # measure performance
  71     $ lua performance.lua
  72     Running with seed 1540584306
  73     Building a map of 3000x3000...
  74     Precalculating 6000 random start/goal positions...
  75     Finding 1000 paths...
  76         Done in 16.37 seconds.
  77         That is 0.0164 seconds, or 16 milliseconds, per path.
  78         The map has 9.0 million locations, with about 65% open space.
  79
  80
  81 # Example
  82
  83 There is an [interactive example](example/main.lua) that can be run with [Love](https://love2d.org).
  84
  85 # License
  86
  87 See the file [LICENSE](LICENSE)