[LEFT]I’ve been experimenting with path finding, in particular the A* algorithm. I’ve understand the basics for it and can currently get an object to move from point A to B avoiding walls. However I’m trying to create one way blocks, (then eventually add turn left and right only and T juncs etc) so I don’t have to use thick walls to prevent the object from taking a certain route.
The code I have so far is…
_global.findPath = function(map, startY, startX, endY, endX) {
// Finds the way given a certain path
// Constants/configuration - change here as needed! -------------------------
var count = 0;
var HV_COST = 10; // "Movement cost" for horizontal/vertical moves
var D_COST = 14; // "Movement cost" for diagonal moves
var ALLOW_DIAGONAL = false; // If diagonal movements are allowed at all
var ALLOW_DIAGONAL_CORNERING = true; // Not implemented. Always true
// Complimentary functions ==================================================
isOpen = function (y, x) {
// Return TRUE if the point is on the open list, false if otherwise
return mapStatus[y][x].open;
};
isClosed = function (y, x) {
// Return TRUE if the point is on the closed list, false if otherwise
return mapStatus[y][x].closed;
};
nearerSquare = function() {
// Returns the square with a lower movementCost + heuristic distance
// from the open list
var minimum = 999999;
var indexFound = 0;
var thisF = undefined;
var thisSquare = undefined;
var i = openList.length;
// Finds lowest
while (i-->0) {
thisSquare = mapStatus[openList*[0]][openList*[1]];
thisF = thisSquare.heuristic + thisSquare.movementCost;
if (thisF <= minimum) {
minimum = thisF;
indexFound = i;
}
}
// Returns lowest
return indexFound;
};
closeSquare = function(y, x) {
// Drop from the open list
var len = openList.length;
for (var i=0; i < len; i++) {
if (openList*[0] == y) {
if (openList*[1] == x) {
openList.splice(i, 1);
break;
}
}
}
// Closes an open square
mapStatus[y][x].open = false;
mapStatus[y][x].closed = true;
};
openSquare = function(y, x, parent, movementCost, heuristic, replacing) {
// Opens a square
if (!replacing) {
openList.push([y,x]);
mapStatus[y][x] = {heuristic:heuristic, open:true, closed:false};
}
mapStatus[y][x].parent = parent;
mapStatus[y][x].movementCost = movementCost;
};
// Ok, now go back to our regular schedule. Find the path! ------------------
// Caches dimensions
var mapH = map.length;
var mapW = map[0].length;
// New status arrays
var mapStatus = new Array();
for (var i=0; i<mapH; i++) mapStatus* = new Array();
if (startY == undefined) return ("ERROR: No starting point");
if (endY == undefined) return ("ERROR: No ending point");
// Now really starts
var openList = new Array();
openSquare (startY, startX);
// Loops until there's no other way to go OR found the exit
while (openList.length > 0 && !isClosed(endY, endX)) {
// Browse through open squares
var i = nearerSquare();
var nowY = openList*[0];
var nowX = openList*[1];
// Closes current square as it has done its purpose...
closeSquare (nowY, nowX);
// Opens all nearby squares, ONLY if:
for (var j=nowY-1; j<=nowY+1; j++) {
for (var k=nowX-1; k<=nowX+1; k++) {
if (j >= 0 && j < mapH && k >= 0 && k < mapW && !(j==nowY && k==nowX) && (ALLOW_DIAGONAL || j==nowY || k==nowX)) {
// If not outside the boundaries or at the same point or a diagonal (if disabled)...
if (map[j][k] != 0) {
trace('--');
trace('Y:'+nowY+' X'+nowX);
trace('Y:'+j+' X:'+k);
var dir = '';
if(j>nowY)
{
dir = 'n';
}
else if(j<nowY)
{
dir = 's';
}else if(k>nowX)
{
dir = 'e';
}
else if(k<nowX)
{
dir = 'w';
}
delete doesntwork;
if(map[j][k] == 2 && dir != 's')
{
doesntwork = true;
}
else if(map[j][k] == 3 && dir != 'w')
{
doesntwork = true;
}
else if(map[j][k] == 4 && dir != 'n')
{
doesntwork = true;
}
else if(map[j][k] == 5 && dir != 'e')
{
doesntwork = true;
}
// 2 straight N -> S
// 3 straight E -> W
// 4 straight S -> N
// 5 straight W -> E
// 6 curved N -> E
// 7 curved N -> W
// 8 curved E -> N
// 9 curved E -> S
// 10 curved S -> E
// 11 curved S -> W
// 12 curved W -> N
// 13 curved W -> S
if(doesntwork != true)
{
// And if not a wall...
if (!isClosed(j,k)) {
// And if not closed... THEN open.
var movementCost = mapStatus[nowY][nowX].movementCost + ((j==nowY || k==nowX ? HV_COST : D_COST) * map[j][k]);
if (isOpen(j,k)) {
// Already opened: check if it's ok to re-open (cheaper)
if (movementCost < mapStatus[j][k].movementCost)
{
// Cheaper: simply replaces with new cost and parent.
openSquare (j, k, [nowY, nowX], movementCost, undefined, true);
}
// heuristic not passed: faster, not needed 'cause it's already set
} else {
// Empty: open.
var heuristic = (Math.abs (j - endY) + Math.abs (k - endX)) * 10;
openSquare (j, k, [nowY, nowX], movementCost, heuristic, false);
}
}
else
{
}
}
else
{
}
} else {
// Wall, ignore.
}
}
}
}
}
// Ended
var pFound = isClosed(endY, endX); // Was the path found?
// Clean up temporary functions
delete isOpen;
delete isClosed;
delete nearerSquare;
delete closeSquare;
delete openSquare;
if (pFound) {
// Ended with path found; generates return path
var returnPath = new Array();
var nowY = endY;
var nowX = endX;
while ((nowY != startY || nowX != startX)) {
returnPath.push([nowY,nowX]);
var newY = mapStatus[nowY][nowX].parent[0];
var newX = mapStatus[nowY][nowX].parent[1];
nowY = newY;
nowX = newX;
}
returnPath.push([startY,startX]);
returnPath.reverse();
return (returnPath);
} else {
// Ended with 0 open squares; ran out of squares, path NOT found
return ("ERROR: Could not reach the end");
}
};
The modifications I’ve made currently allow me to work out which direction it’s going in, however when checking to see if the object can go in that direction its seems to ignore the rule and go around. Plus it adds quite a bit of processor power causing a mini pause which isn’t ideal. Am I going the wrong way about this or are there any pathfinding algorithms that look at the direction(s) of the tile rather than a wall next to it?
Thank in advance for any advice 
[/LEFT]
