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:
Any feedback, suggestions on how to improve, or wrong coded parts will be strongly appreciated.
Thanks in advance.