I sat down today and decided to create a Breadth-Search first algorithm.
It is guaranteed to find the best existing path on any tiled based system.
I decided to share it, because I do not believe anyone else has provided it.
If you have any questions, research the algorithm first (try Wikipedia even!), but I will answer any other ones that you have.
Warning: The code is commented slightly, but it is not for beginners. You have to have a good grasp of actionscript, but mostly arrays, to be able to fully understand it.
// 11/3/09
// ~Breadth First Search~
// Created by Matt Bellis aka Pyromaniac
// 0 = walkable, 1 = wall, 2 = end, 3 = start
var map1:Array = [[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 1], [1, 0, 1, 1, 0, 0, 1], [1, 0, 1, 3, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1], [1, 0, 0, 0, 2, 0, 1], [1, 1, 1, 1, 1, 1, 1]];
var map2:Array = [[1, 1, 1, 1, 1, 1, 1], [1, 2, 0, 0, 0, 0, 1], [1, 0, 1, 1, 0, 0, 1], [1, 0, 1, 3, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1]];
var map3:Array = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1], [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1], [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1], [1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1], [1, 0, 0, 1, 0, 3, 0, 1, 0, 1, 0, 1], [1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1], [1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]];
var queue:Array = [];
var endPt:Array = [];
var sPt:Array = [];
var currentPt:Array = [];
var finalPath:Array = [];
var done:Boolean = false;
var ptPos:Number = 0;
var moves:Number = 0;
//
// use pathFind(map, queue) to call the function
// change map1 to whatever map you desire
// maps can be any size
pathFind(map2, queue);
function resetVar():Void {
queue = [];
endPt = [];
sPt = [];
currentPt = [];
finalPath = [];
done = false;
ptPos = 0;
moves = 0;
}
// Use resetVar() before finding a new path
// resetVar();
// pathFind(map1, queue);
function pathFind(map:Array, q:Array):Void {
findEnd(map);
while (done == false) {
addAdj(map, currentPt, q);
currentPt = q[ptPos];
ptPos++;
done = checkEnd(q);
}
if (done == true) {
reduceQ(q);
/*
trace("Queue");
for (i=0; i<q.length; i++) {
trace(q[i]);
}
//trace(q.length);
*/
showMap(map, q);
}
finalPath = findPath(map, q);
trace("Path");
for (a=0; a<finalPath.length; a++) {
trace(finalPath[a]);
}
// you can format pathFind to return finalPath (remember to change the :Void to :Array
// if you want
}
function findPath(map:Array, q:Array):Array {
// find the path from end to start
// based on the reduced que
var path:Array = [];
path.push(endPt);
while (moves>0) {
for (var i = 0; i<q.length; i++) {
if (q[i][2] == moves-1) {
path.push([q[i][0], q[i][1]]);
moves = q[i][2];
}
}
}
path.reverse();
return path;
}
function showMap(map:Array, queue:Array):Void {
var mapShow = map;
// translate
// blank squares ate _ , walls are X
// and the numbers are number of moves needed to be made
for (var x = 0; x<map.length; x++) {
for (var y = 0; y<map[0].length; y++) {
if (map[x][y] == 0) {
mapShow[x][y] = "_";
}
if (map[x][y] == 1) {
mapShow[x][y] = "X";
}
if (map[x][y] == 2) {
mapShow[x][y] = "E";
}
}
}
//
for (var z = 0; z<queue.length; z++) {
if (queue[z][0] == endPt[0] && queue[z][1] == endPt[1]) {
// ignore
} else {
mapShow[(queue[z][0])][(queue[z][1])] = queue[z][2];
}
}
// Shows a representation of the map using text - for very large maps gets messed up
// but dont worry, because the path the overall function returns works regardless of size
for (var w = 0; w<mapShow.length; w++) {
trace(mapShow[w]);
}
}
function findEnd(map:Array):Void {
for (var x:Number = 0; x<map.length; x++) {
for (var y:Number = 0; y<map[0].length; y++) {
if (map[x][y] == 3) {
queue.push([x, y, 0]);
currentPt.push([x, y, 0]);
sPt.push(x);
sPt.push(y);
}
if (map[x][y] == 2) {
endPt.push(x);
endPt.push(y);
}
}
}
//trace("End= "+endPt);
}
function addAdj(map:Array, pt:Array, qM:Array):Void {
var list:Array = [];
var x:Number = pt[0];
var y:Number = pt[1];
var ct:Number = pt[2];
if (map[x+1][y] != 1 && map[x+1][y] != undefined) {
list.push([x+1, y, ct+1]);
}
if (map[x-1][y] != 1 && map[x-1][y] != undefined) {
list.push([x-1, y, ct+1]);
}
if (map[x][y+1] != 1 && map[x][y+1] != undefined) {
list.push([x, y+1, ct+1]);
}
if (map[x][y-1] != 1 && map[x][y-1] != undefined) {
list.push([x, y-1, ct+1]);
}
checkQ(list, qM);
}
function checkEnd(q:Array):Boolean {
var end:Boolean = false;
for (var x:Number = 0; x<q.length; x++) {
if (q[x][0] == endPt[0] && q[x][1] == endPt[1]) {
moves = q[x][2];
end = true;
//trace("Solved");
}
}
return end;
}
function reduceQ(q:Array):Void {
var doneR = false;
while (doneR == false) {
doneR = true;
for (var x:Number = 0; x<q.length; x++) {
for (var z:Number = 0; z<q.length; z++) {
if (x != z) {
if (q[x][0] == q[z][0] && q[x][1] == q[z][1]) {
if (q[x][2]>=q[z][2]) {
q.splice(x, 1);
doneR = false;
//trace("splicing: "+q[x])
}
}
}
}
}
}
}
function checkQ(q:Array, qM:Array):Void {
for (var x:Number = 0; x<q.length; x++) {
for (var z:Number = 0; z<qM.length; z++) {
if (q[x][0] == sPt[0] && q[x][1] == sPt[1]) {
q.splice(x, 1);
}
if (q[x][0] == qM[z][0] && q[x][1] == qM[z][1]) {
if (q[x][2]>=qM[z][2]) {
//trace("splicing: "+q[x]);
q.splice(x, 1);
}
}
}
}
for (var i = 0; i<q.length; i++) {
qM.push(q[i]);
}
}
