I've been working on a implementing

**Astar pathfinding algorithm**for a basic real time strategy I will start working on in a few.

Then I wanted to share the results it with all those who might be interested in.

I have used

**Patrick Lester**tutorial (on Polyalmanac) on A-star pathfinding and Amit's A-star pages for theory learning purposes.

I don't pretend my implementation is the best, but i can consider this is a good job on the overall. It uses an internal node class (local to the libary) and provides you a set of functionnalities packed in a Lua table.

Plus, I have added some speed up tricks in the code for a quick computing.

- openList is not maintained in order. The code keeps track of the lowercost node each loop so that there is no need to skim trough the openList to find it.

- distance heuristic uses integers rather than the common squared root value to speed up computing on large maps.

**A simple usage example:**

Code: Select all

```
--Assuming one wants to compute a path from cell (1,1) to cell ( 3,2) on a grid containing obstacles.
local Astar = require 'Lib.Astar'
Astar(map) -- inits the library
Astar:setObstValue(1) -- specifies that a value of 1 on the grid refers to an unwalkable location
Astar:setInitialNode(1,1)
Astar:setFinalNode(3,2)
local path = Astar:getPath()
```

A lot of metamethods are provided with this Astar class:

- setObstValue(value)
- getObstValue()
- enableDiagonalMove()
- disableDiagonalMove()
- setSearchDepth(value)
- getSearchDepth()
- setInitialNode()
- getInitialNode()
- setFinalNode()
- getFinalNode()
- isWalkable()
- getPath()
- reset()

Any feedback, suggestions on how to improve, or wrong coded parts will be strongly appreciated.

Thanks in advance.