AS 2: Pathfinding with direction tiles

[mavoric]

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[i][0]][openList[i][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[i][0] == y) {
        if (openList[i][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[i] = 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[i][0];
    var nowX = openList[i][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

[mavoric]

bumping for any ideas please

Thanks