findEasyPath - Tries to see if Manhatten Distance paths have no collision.

findEasyPath.js

  // Tries to see if Manhatten Distance paths have no collision.
  // @param grid - A two-dimensional array containing the y-axis and x-axis in that order.
  // @param start - A single array of the start coordinate start[0]=x, start[1]=y.
  // @param start - A single array of the end coordinate end[0]=x, end[1]=y.
  //
  var findEasyPath = function (grid, start, end) {
    var ts = G_TILESIZE; // 16 units in each grid coordinate.

    var sx, sy, ex, ey;

    sx = start[0];
    sy = start[1];
    ex = end[0];
    ey = end[1];

    sx = sx / ts;
    ex = ex / ts;
    sy = sy / ts;
    ey = ey / ts;

    var res = false;
    //log.info("easyPath: [sx,sy]:"+sx+","+sy);
    //log.info("easyPath: [ex,ey]:"+ex+","+ey);

    // Sort out the x-axis row.
    var xf = function (y) {
      var c2 = (y % 1 == 0);
      var fsx = Math.floor(sx), cex = Math.ceil(ex);
      if (fsx != cex) {
        var fy=Math.floor(y), cy=Math.ceil(y);
        for (var i=fsx; i < cex; i++) {
          if (c2) {
            if (grid[fy][i]) {
              return false;
            }
          }
          else {
            if (grid[fy][i] || grid[cy][i]) {
              return false;
            }
          }
        }
        return [ex,y];
      }
      return true;
    }

    // Sort out the y-axis column.
    var yf = function (x) {
      var c2 = (x % 1 == 0);
      var fsy = Math.floor(sy), cey = Math.ceil(ey);
      if (fsy != cey) {
        var fx=Math.floor(x), cx=Math.ceil(x);
        for (var j=fsy; j < cey; j++) {
          if (c2) {
            if (grid[j][fx]){
              return false;
            }
          }
          else {
            if (grid[j][fx] || grid[j][cx]) {
              return false;
            }
          }
        }
      }
      return true;
    }


    var success=0;

    var xfsy = xf(sy);
    var xfey = xf(ey);
    var yfsx = yf(sx);
    var yfex = yf(ex);

    if ((start[0] == end[0] && yfsx) || (start[1] == end[1] && xfsy))
    {
      res = true;
      success = 1;
    }
    else
    {
      if ((xfsy && yfex) || (xfey && yfsx)) {
        res = true;
        success=2;
      }
      else {
        return [];
      }
    }

    if (res) {
      var path = [];
      if (success == 1) {
        path = [[start[0],start[1]], [end[0],end[1]]];
        return path;
      }
      else {
        path.push([start[0],start[1]]);

        var d1 = (start[0] <= end[0]);
        var d2 = (start[1] <= end[1]);
        var dir = false;
        if (d1) {
          dir = (d2) ? false : true;
        }
        else {
          dir = (d2) ? false : true;
        }

        if (success == 2) {
          if (o)
            path.push([sx*ts, ey*ts]);
          else
            path.push([ex*ts, sy*ts]);
        }

        path.push([end[0],end[1]]);

        log.warn("PathFind - Easy Path Detected!");
        log.info("path: "+JSON.stringify(path));
        return path;
      }
    }
    return [];
  };