LuAstar, a simple A* pathfinding class

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
Roland_Yonaba
Inner party member
Posts: 1562
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

LuAstar, a simple A* pathfinding class

Post by Roland_Yonaba » Thu Aug 04, 2011 1:02 pm

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

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.
Attachments
LuAstar.love
LuAstar + technical Demo (fixed)
(5.13 KiB) Downloaded 921 times

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

Re: LuAstar, a simple A* pathfinding class

Post by kraftman » Thu Aug 04, 2011 2:14 pm

Looks great! Good job.

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

Re: LuAstar, a simple A* pathfinding class

Post by Robin » Thu Aug 04, 2011 2:22 pm

Nice. Shame it crashes when you start on an unwalkable tile.
Help us help you: attach a .love.

User avatar
Roland_Yonaba
Inner party member
Posts: 1562
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: LuAstar, a simple A* pathfinding class

Post by Roland_Yonaba » Thu Aug 04, 2011 2:25 pm

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

User avatar
Cantide
Prole
Posts: 10
Joined: Mon Jul 25, 2011 7:01 pm

Re: LuAstar, a simple A* pathfinding class

Post by Cantide » Sat Aug 06, 2011 1:09 pm

I like this a lot! :D 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?

User avatar
Roland_Yonaba
Inner party member
Posts: 1562
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: LuAstar, a simple A* pathfinding class

Post by Roland_Yonaba » Sun Aug 07, 2011 7:25 pm

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... :o:

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

Re: LuAstar, a simple A* pathfinding class

Post by Robin » Sun Aug 07, 2011 7:28 pm

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
Help us help you: attach a .love.

User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: LuAstar, a simple A* pathfinding class

Post by kikito » Sun Aug 07, 2011 7:44 pm

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.

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

Re: LuAstar, a simple A* pathfinding class

Post by SoggyWaffles » Sun Aug 07, 2011 8:10 pm

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

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

Re: LuAstar, a simple A* pathfinding class

Post by Robin » Sun Aug 07, 2011 8:11 pm

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.)
Help us help you: attach a .love.

Post Reply

Who is online

Users browsing this forum: No registered users and 0 guests