README.md

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