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/example.gif)
   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, excludeDiagonalMoving)
  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 `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**
  46
  47 # Requirements
  48
  49 * [Lua 5.x](http://www.lua.org/)
  50
  51 For running unit tests:
  52
  53 * [Lua Rocks](https://luarocks.org/)
  54 * busted
  55
  56 These commands are for apt-based systems, please adapt to them as needed.
  57
  58     sudo apt-get install luarocks
  59     sudo luarocks install busted
  60
  61 Unit testing is done with busted, the `.busted` config already defines everything, so simply run:
  62
  63     busted
  64
  65 # Performance
  66
  67 There is a performance measurement tool in `tests/performance.lua`, it calculates the average time to find a path on a large, random map.
  68
  69     # copy the lib to tests
  70     $ cp ../src/lua-star.lua .
  71
  72     # measure performance
  73     $ lua performance.lua
  74     Running with seed 1540584306
  75     Building a map of 3000x3000...
  76     Precalculating 6000 random start/goal positions...
  77     Finding 1000 paths...
  78         Done in 16.37 seconds.
  79         That is 0.0164 seconds, or 16 milliseconds, per path.
  80         The map has 9.0 million locations, with about 65% open space.
  81
  82
  83 # Example
  84
  85 There is an [interactive example](example/main.lua) that can be run with [Love](https://love2d.org).
  86
  87 # License
  88
  89 See the file [LICENSE](LICENSE)