[F8] A* pathfinding

I needed a pathfinding algorithm for a tilebased game, and the best option was the A* algorithm. Unfortunately there isn't one out there for flash, so I made one. This algorithm will find the shortest path between two points in a grid of tiles where the tiles can either be walkable or unwalkable. It implements a min-heap, so it's quite efficient.

Demo
AStarPathfinding.zip

The following code shows you how to use the pathfinder. The map has to be a 2D array of objects, where the objects need to have the property walkable.

Code:

---

import pathfinding.*;
var map:Array = [[{walkable:true}, {walkable:false}, {walkable:true}],
[{walkable:true}, {walkable:true}, {walkable:true}]];
var pfinder:Astar = new Astar(map);
var sx:Number = Math.round(game.startPos._x/32);
var sy:Number = Math.round(game.startPos._y/32);
var gx:Number = Math.round(game.stopPos._x/32);
var gy:Number = Math.round(game.stopPos._y/32);
var path:Array = pfinder.find(sx,sy,gx,gy);

---

It returns an array of Node objects in the order the tiles should be walked. Each Node has an x and y variable which you can use to get the next tile in the path.

The demo demonstrates how the pathfinding is performed. The numbers you see indicate the distance from start to finish. The red tiles indicate the path the algorithm found.

If you find any bugs or have any suggestions/questions, then reply here, and I'll see what I can do.

Quote:

---

Originally Posted by ihoss.com

I needed a pathfinding algorithm for a tilebased game, and the best option was the A* algorithm. Unfortunately there isn't one out there for flash, so I made one.

---

Whaaat? A* has been used in Flash for years...

Yeah, I know, but try finding the source code for it on the net.

Took me less than a minute. Googled "Flash A* pathfinder source", got this:

http://www.gotoandplay.it/_articles/...athfinder2.php

weird. Oh well, now there are at least two sources out there :D

A* is not always the most efficient one and most examples (there are a ton of those online) show examples grid based.
In my tankmove game-concept for example I used some techniques described in Tonypa´s tutorials but changed it so that it wouldn´t search outside a certain area to begin with and skip path finding trees if a certain time difference was exceeded.

another way is handling patfinding via a node network like almost any modern computer game uses today. If you modify the A* concept it works even with nodes.

Infact I like to do it the other way, implement A* that works on nodes, and then a 2d map is really just a grid of nodes.

Me too. It gives my pathfinding routines the flexibility to be used with or without a grid. I guess I'll share my pathfinding stuff too sometime, it's pretty old code but quite fast.

The game I needed pathfinding for is a tilebased game, so it's a grid, but most importantly, the walls are destructible. This means that precalculated pathfinding was not an option.

Tonypa's algorithm is great if your map is not a labyrinth, but an open field with scattered hindrances.

I bet you could do something with calculus. Set up an equation like a min/max problem and then solve for zero.

I didn't really think it through.

That's a great little demo :)

great demo, I have a question. Can this be used to find the path of a moving object, instead of a static goal?

Al Capwan, that could be used if there was no obstructions.

Thanks Pincus

moony, if you call the pathfinding algorithm every time you reach a new tile, then you can find the path to a moving target. This could also be used to find the path around moving obstructions.

Just to add to what ihoss said, you might need to consider where the moving obstruction will be when the character will reach the intersection between it's path to the goal and the moving path of said obstruction. If you don't consider this, there's a pretty good chance the character will hit the obstruction anyhow, or wind up in some moving loop between points.

Depending on the complexity, you could simply extrapolate the targets and any moving objects position based on the current path length.

More complex solutions include things like corporative path finding where pathfinding is not only done on a 2d grid of tiles (/nodes), but a 3d Tile/Time layer where objects register their future paths to avoid collisions.
grid[y][x];
grid[y][x][timeInFuture];

Recalculating the path upon a collision is an implementation of dynamic repair and, as expected is rather slow. The advantage of cooperative path finding is that you must only generate a single path. To save memory it is often combined with dynamic repair, and only takes a set period of time into the future (say 10 steps) into account.

Cooperative pathfinding looks cool, but I'm not sure how well it would work in my game. I might take a look at it later though.