## LuAstar, a simple A* pathfinding class

Roland_Yonaba
Inner party member
Posts: 1562
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### LuAstar, a simple A* pathfinding class

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.
Attachments
LuAstar.love
LuAstar + technical Demo (fixed)

kraftman
Party member
Posts: 277
Joined: Sat May 14, 2011 10:18 am

### Re: LuAstar, a simple A* pathfinding class

Looks great! Good job.

Robin
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

### Re: LuAstar, a simple A* pathfinding class

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

Roland_Yonaba
Inner party member
Posts: 1562
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: LuAstar, a simple A* pathfinding class

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
Prole
Posts: 10
Joined: Mon Jul 25, 2011 7:01 pm

### Re: LuAstar, a simple A* pathfinding class

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
Inner party member
Posts: 1562
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: LuAstar, a simple A* pathfinding class

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
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

### Re: LuAstar, a simple A* pathfinding class

Cantide wrote: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
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Contact:

### Re: LuAstar, a simple A* pathfinding class

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.
When I write def I mean function.

SoggyWaffles
Citizen
Posts: 72
Joined: Sun Jan 02, 2011 3:27 am
Location: Wyoming, USA

### Re: LuAstar, a simple A* pathfinding class

kikito wrote: 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.
"Beneath the clouds lives the Earth-Mother from whom is derived the Water of Life, who at her bosom feeds plants, animals and men." ~Larousse

Robin
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

### Re: LuAstar, a simple A* pathfinding class

kikito wrote: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.)