LuAstar, a simple A* pathfinding class

[Roland_Yonaba]

Hi,

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()

I have included a technical demo for more details on how to use this. See the .love attached file.
Any feedback, suggestions on how to improve, or wrong coded parts will be strongly appreciated.
Thanks in advance.

[kraftman]

Looks great! Good job.

[Robin]

Nice. Shame it crashes when you start on an unwalkable tile.

[Roland_Yonaba]

Yeah, i've defined the code that way...
But never mind, you can refactor the setInitialNode() method for your own purposes.
Thanks, you all.

[Cantide]

I like this a lot! I've been wondering how to tackle AI for a while now, and this is great!!
Any chance of modifying it to work with love.physics and not tile-based?

[Roland_Yonaba]

Well, since I have never used love.physics, I dunno..Maybe, I guess. WHat do you mean exactly when saying 'not tile-based' ? kinda confused...

[Robin]

Any chance of modifying it to work with love.physics and not tile-based?

You mean something like "pixel-perfect"? No, that is not how A* works

[kikito]

I think I know what he means by tile-based.

A* isn't "an algorithm to find a path inside a grid". It's a bit more generic than that; it finds a solution given a list of nodes and a way to find the neibors of each node.

In videogames, while it's often desirable to represent the game space as a grid, it's not always the best solution. Sometimes you want to represent the map as a group of irregular polygons. Sometimes it's a grid, but there're several "levels" (some of the tiles are "elevators" or "stairs"). Sometimes there're teleporters.

Since you are hard-coding " the nodes to be "tiles in a grid" and the neighbors to be "either the 4 or 8 tiles touching a given one, you are making the algorithm less usable.

[SoggyWaffles]

Since you are hard-coding " the nodes to be "tiles in a grid" and the neighbors to be "either the 4 or 8 tiles touching a given one, you are making the algorithm less usable.

I wouldn't call it less usable. He did preface it as "a simple A*..", I would say his take on it is just more elementary. Almost all A* tutorials I've read use a standard square grid, they do however elude to the fact that you can do it anyway you want to.

[Robin]

I think I know what he means by tile-based.

You say very true things, however, judging by the "can you make it work with love.physics" part, I assume he does not understand A*.

(For reference: see Wikipedia.)