All geek questions in one place

Collision avoidance with new ways

I am creating a program that goes through the matrix (nxn), avoiding collisions with certain obstacles. I had a problem with introducing a universal algorithm that works for all possible collision situations, the ultimate goal is to go through all the points of the matrix.

The algorithm I built is a loop and cannot complete the matrix.

Note . The red square can move in any direction (horizontal, vertical and diagonal movement), but only one cell (square) at a time.

var WALL = 0;
var started = false;
var gridSize = 20;

class Agent {
  constructor(x, y, charge, cap, distance) {
    this.x = x;
    this.y = y;
    this.charge = charge;
    this.cap = cap;
    this.distance = distance;
  }
}

$(function() {
  var $grid = $("#search_grid");

  var opts = {
    gridSize: 20
  };

  var grid = new GraphSearch($grid, opts);

  //Initializes the agent
  $("#btnInit").click(function() {
    if (!started) {
      var agent = new Agent(0, 0, 100, 50, 0);
      agent.initialize();
      started = true;
    }

  });
});

//Initializes the matrix
function GraphSearch($graph, options) {
  this.$graph = $graph;
  this.opts = options;
  this.initialize();
}

//Initializes the matrix
GraphSearch.prototype.initialize = function() {
  this.grid = [];
  $graph = this.$graph;
  $graph.empty();

  var cellWidth = ($graph.width() / this.opts.gridSize) - 2,
    cellHeight = ($graph.height() / this.opts.gridSize) - 2,
    lineHeight = (this.opts.gridSize >= 30 ? "9.px" : ($graph.height() / this.opts.gridSize) - 10 + "px"),
    fontSize = (this.opts.gridSize >= 30 ? "10px" : "20px");
  $cellTemplate = $("<span />").addClass("grid_item").width(cellWidth).height(cellHeight).css("line-height", lineHeight).css("font-size", fontSize);

  for (var x = 0; x < this.opts.gridSize; x++) {
    var $row = $("<div class='row' />");
    for (var y = 0; y < this.opts.gridSize; y++) {
      var id = "cell_" + x + "_" + y,
        $cell = $cellTemplate.clone();
      $cell.attr("id", id).attr("x", x).attr("y", y);
      $row.append($cell);

      var isWall = addWall(x, y, this.opts.gridSize);
      if (isWall === 1) {
        $cell.addClass("wall");
      } else {
        $cell.addClass('weight1');
      }
    }
    $graph.append($row);

    //Fix for stackoverflow snippet
    if ($(window).width() < 700) {
      $("#search_grid").css("width", "320px");
      $("#main").css("width", "38%");
    } else {
      $("#search_grid").css("width", "300px");
      $("#main").css("width", "20%");
    }

  }
};

//Where will be wall in the matrix
addWall = function(x, y, size) {
  var limitPointLeftUp = [2, 3];
  var limitPointRightUp = [2, size - 4];

  var limitPointLeftDown = [size - 4, 2];
  var limitPointRightDown = [size - 4, size - 4];

  if ((x == 2 && y == 2) || (x == 2 && y == size - 3)) {
    return 1;
  }

  if ((x == size - 3 && y == 2) || (x == size - 3 && y == size - 3)) {
    return 1;
  }

  if (x >= 2 && (y == 3 && x >= limitPointLeftUp[0] && x <= limitPointLeftDown[0] + 1)) {
    return 1;
  }

  if (x >= 2 && (y == size - 4 && x >= limitPointRightUp[0] && x <= limitPointRightDown[0] + 1)) {
    return 1;
  }

  if ((x == 1 && y == 5) || (x == 9 && y == 17) || (x == 6 && y == 0) || (x == 9 && y == 7) || (x == 15 && y == 0) || (x == 15 && y == 2) || (x == 18 && y == 15)) {
    return 1;
  }
}

//Initializes the agent
Agent.prototype.initialize = function() {
  var agent = this;
  var lastDir = "right";
  var tryTo = "";
  var trying = false;

  var right = true;
  var up = false;
  var down = false;
  var left = false;
  var timerId = 0;

  //Simulates agent movement [Here is my problem]
  timerId = setInterval(function() {
    RemoveAgent();
    var cell = $("#search_grid .row .grid_item[x=" + agent.x + "][y=" + agent.y + "]");
    cell.css("background-color", "#e2e2e2");
    cell.addClass("agent");
    //start direction: right
    if (right) {
      lastDir = "right";
      if (tryTo == "down" && trying) {
        if (EmptySqm(agent.x + 1, agent.y)) {
          trying = false;
          right = false;
          down = true;
          agent.x++;
        }
      } else if (tryTo == "up" && trying) {
        if (EmptySqm(agent.x - 1, agent.y)) {
          trying = false;
          right = false;
          up = true;
          agent.x--;
        }
      }

      if (right) {
        //check if is valid sqm
        if (ValidSqm(agent.x, agent.y + 1)) {
          //go right if empty
          if (EmptySqm(agent.x, agent.y + 1)) {
            agent.y++;
          } else {
            right = false;
            //check up sqm
            if (EmptySqm(agent.x - 1, agent.y)) {
              up = true;
              trying = true;
            }
            //check down 
            else if (EmptySqm(agent.x + 1, agent.y)) {
              down = true;
              trying = true;
            }
          }
        } else {
          agent.x++;
          right = false;
          left = true;
        }
      }
      //left direction
    } else if (left) {
      lastDir = "left";
      if (tryTo == "down" && trying) {
        if (EmptySqm(agent.x + 1, agent.y)) {
          trying = false;
          left = false;
          down = true;
          agent.x++;
        }
      } else if (tryTo == "up" && trying) {
        if (EmptySqm(agent.x - 1, agent.y)) {
          trying = false;
          left = false;
          up = true;
          agent.x--;
        }
      }

      if (left) {
        if (ValidSqm(agent.x, agent.y - 1)) {
          if (EmptySqm(agent.x, agent.y - 1)) {
            agent.y--;
          } else {
            left = false;
            if (EmptySqm(agent.x + 1, agent.y)) {
              down = true;
              trying = true;
            } else if (EmptySqm(agent.x - 1, agent.y)) {
              up = true;
              trying = true;
            }

          }
        } else {
          agent.x++;
          right = true;
          left = false;
        }
      }
      //up direction	
    } else if (up) {
      tryTo = "down";
      if (lastDir == "left") {
        if (EmptySqm(agent.x, agent.y - 1)) {
          up = false;
          left = true;
          agent.y--;
        }
      } else if (lastDir == "right") {
        if (EmptySqm(agent.x, agent.y + 1)) {
          up = false;
          right = true;
          agent.y++;
        }
      }
      if (up) {
        if (ValidSqm(agent.x - 1, agent.y)) {
          if (EmptySqm(agent.x - 1, agent.y)) {
            agent.x--;
          } else {
            up = false;
            //check left sqm
            if (EmptySqm(agent.x, agent.y - 1)) {
              left = true;
              agent.y--;
            }
            //check right sqm
            else if (EmptySqm(agent.x, agent.y + 1)) {
              right = true;
              agent.y++;
            }
            //check down sqm
            else if (EmptySqm(agent.x + 1, agent.y)) {
              down = true;
              agent.x++;
            }

          }
        } else {
          agent.x++;
          up = false;
          down = true;
        }
      }
      //down direction
    } else if (down) {
      tryTo = "up";
      if (lastDir == "left") {
        if (EmptySqm(agent.x, agent.y - 1)) {
          down = false;
          left = true;
          agent.y--;
        }
      } else if (lastDir == "right") {
        if (EmptySqm(agent.x, agent.y + 1)) {
          down = false;
          right = true;
          agent.y++;
        }
      }

      if (down) {
        if (ValidSqm(agent.x + 1, agent.y)) {
          if (EmptySqm(agent.x + 1, agent.y)) {
            agent.x++;
          } else {
            down = false;
            //check left sqm
            if (EmptySqm(agent.x, agent.y - 1)) {
              left = true;
              agent.y--;
            }
            //check right sqm
            else if (EmptySqm(agent.x, agent.y + 1)) {
              right = true;
              agent.y++;
            }
            //check up sqm
            else if (EmptySqm(agent.x - 1, agent.y)) {
              up = true;
              agent.x--;
            }
          }
        } else {
          agent.x--;
          up = true;
          down = false;
        }
      }
    }
  }, 100);

  var stopInterval = function() {
    clearInterval(timerId);
  };
};

EmptySqm = function(x, y) {
  var bNotWall = !$("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]").hasClass("wall");
  return bNotWall;
}

RemoveAgent = function() {
  $("#search_grid .row .grid_item").removeClass("agent");
}

ValidSqm = function(x, y) {
  return ((x >= 0 && x < gridSize) && (y >= 0 && y < gridSize));
}
html,
body {
  height: 100%;
  margin: 0;
}

.buttons {
  float: right;
  position: relative;
  right: 10px;
  top: 10px;
}

.buttons a {
  text-decoration: none;
}

#content {
  margin: 0 auto;
  width: 98%;
  text-align: center;
}

#controls {
  text-align: center;
  margin-bottom: 25px;
  padding: 5px;
}

#search_grid {
  width: 320px;
  height: 300px;
  position: relative;
}

#main {
  margin: auto;
  width: 20%;
}

.grid_item {
  display: block;
  border: 1px solid #bbb;
  float: left;
  line-height: 12px;
  font-size: 10px;
}

.grid_item.wall {
  background-color: #000000;
}

.grid_item.weight1 {
  background-color: #ffffff;
}

.agent {
  text-align: center;
  color: grey;
  font-size: 20px;
  background-color: red !important;
  color: blue;
  font-weight: bold;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

<body>
  <div id="content">
    <input type="button" id="btnInit" value="Start" /><br><br>
    <div id="main">
      <div id="search_grid">Loading...</div>
    </div>
  </div>
  <div id="footer"></div>
</body>
Run codeHide result
+4
source share
1 answer

a *, , move,

path = grid.move(currentCell, endCell);


var agentSpeed = 10;
var WALL = 0;
var started = false;
var gridSize = 20;
var x = 0;
var y = 0;
var runsSameLine = false;

class Agent {
  constructor(x, y, charge, cap, distance) {
    this.x = x;
    this.y = y;
    this.charge = charge;
    this.cap = cap;
    this.distance = distance;
  }
}

$(function() {
  var $grid = $("#search_grid");

  var opts = {
    gridSize: gridSize
  };

  var grid = new GraphSearch($grid, opts, astar.search);

  //Initializes the agent
  $("#btnInit").click(function() {
    if (!started) {
      var agent = new Agent(0, 0, 100, 50, 0);
      agent.initialize();
      started = true;
    }

  });
});

//Initializes the matrix
function GraphSearch($graph, options, implementation) {
  this.$graph = $graph;
  this.search = implementation;
  this.opts = options;
  this.initialize();
}

var grid;

GraphSearch.prototype.move = function($start, $end) {
  var end = this.nodeFromElement($end);
  if ($end.hasClass("wall")) {
    return;
  }
  var start = this.nodeFromElement($start);
  var path = this.search(this.graph.nodes, start, end, true);
  if (!path || path.length == 0) {
    //this.animateNoPath();
  } else {
    return path;
  }
};

GraphSearch.prototype.nodeFromElement = function($cell) {
  return this.graph.nodes[parseInt($cell.attr("x"))][parseInt($cell.attr("y"))];
};

//Initializes the matrix
GraphSearch.prototype.initialize = function() {
  this.grid = [];
  var self = this,
    nodes = [],
    $graph = this.$graph;

  $graph.empty();

  var cellWidth = ($graph.width() / this.opts.gridSize) - 2,
    cellHeight = ($graph.height() / this.opts.gridSize) - 2,
    lineHeight = (this.opts.gridSize >= 30 ? "9.px" : ($graph.height() / this.opts.gridSize) - 10 + "px"),
    fontSize = (this.opts.gridSize >= 30 ? "10px" : "20px");
  $cellTemplate = $("<span />").addClass("grid_item").width(cellWidth).height(cellHeight).css("line-height", lineHeight).css("font-size", fontSize);

  for (var x = 0; x < this.opts.gridSize; x++) {
    var $row = $("<div class='row' />");
    nodeRow = [],
      gridRow = [];

    for (var y = 0; y < this.opts.gridSize; y++) {
      var id = "cell_" + x + "_" + y,
        $cell = $cellTemplate.clone();
      $cell.attr("id", id).attr("x", x).attr("y", y);
      $row.append($cell);
      gridRow.push($cell);

      var isWall = addWall(x, y, this.opts.gridSize);
      if (isWall === 1) {
        $cell.addClass("wall");
        nodeRow.push(1);
      } else {
        $cell.addClass('weight1');
        nodeRow.push(0);
      }

    }
    $graph.append($row);
    this.grid.push(gridRow);
    nodes.push(nodeRow);

    //Fix for stackoverflow snippet
    if ($(window).width() < 700) {
      $("#search_grid").css("width", "320px");
      $("#main").css("width", "38%");
    } else {
      $("#search_grid").css("width", "300px");
      $("#main").css("width", "20%");
    }
  }
  this.graph = new Graph(nodes);
  this.$cells = $graph.find(".grid_item");
  grid = this;
};

//Where will be wall in the matrix
addWall = function(x, y, size) {
  var limitPointLeftUp = [2, 3];
  var limitPointRightUp = [2, size - 4];

  var limitPointLeftDown = [size - 4, 2];
  var limitPointRightDown = [size - 4, size - 4];

  if ((x == 2 && y == 2) || (x == 2 && y == size - 3)) {
    return 1;
  }

  if ((x == size - 3 && y == 2) || (x == size - 3 && y == size - 3)) {
    return 1;
  }

  if (x >= 2 && (y == 3 && x >= limitPointLeftUp[0] && x <= limitPointLeftDown[0] + 1)) {
    return 1;
  }

  if (x >= 2 && (y == size - 4 && x >= limitPointRightUp[0] && x <= limitPointRightDown[0] + 1)) {
    return 1;
  }

  if ((x == 1 && y == 5) || (x == 9 && y == 17) || (x == 6 && y == 0) || (x == 9 && y == 7) || (x == 15 && y == 0) || (x == 15 && y == 2) || (x == 18 && y == 15)) {
    return 1;
  }
}

//Initializes the agent
Agent.prototype.initialize = function() {
  var agent = this;
  var goToLeft = false;
  var goToRight = true;
  var rightLimit = gridSize - 1;
  var leftLimit = 0;
  var lastPos = 0;
  var path = [];
  var completedPath = true;

  timerId = setInterval(function() {
    agent.x = x;
    agent.y = y;
    currentCell = $("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]");
    currentCell.css("background-color", "#e2e2e2");

    if (agent.x == gridSize - 1 && agent.y == 0) {
      stopInterval(timerId);
      return false;
    }

    if (goToRight && y == rightLimit) {
      if (runsSameLine) {
        goToLeft = true;
        goToRight = false;
        runsSameLine = false;
      } else {
        if (FreeCell((x + 1), y)) {
          endCell = $("#search_grid .row .grid_item[x=" + (x + 1) + "][y=" + y + "]");
          x++;
          goToLeft = true;
          goToRight = false;
        } else {
          endCell = FindNextFreeCell(x, y, "limDir");
          goToLeft = true;
          goToRight = false;
        }
      }
    } else if (goToLeft && y == leftLimit) {
      if (runsSameLine) {
        goToLeft = false;
        goToRight = true;
        runsSameLine = false;
      } else {
        if (FreeCell((x + 1), y)) {
          endCell = $("#search_grid .row .grid_item[x=" + (x + 1) + "][y=" + y + "]");
          x++;
          goToLeft = false;
          goToRight = true;
        } else {
          endCell = FindNextFreeCell(x, y, "limEsq");
          goToLeft = false;
          goToRight = true;
        }
      }

    } else if (goToRight) {
      if (FreeCell(x, (y + 1))) {
        endCell = $("#search_grid .row .grid_item[x=" + x + "][y=" + (y + 1) + "]");
        y++;
      } else {
        endCell = FindNextFreeCell(x, y, "dir");
      }
    } else if (goToLeft) {
      if (FreeCell(x, (y - 1))) {
        endCell = $("#search_grid .row .grid_item[x=" + x + "][y=" + (y - 1) + "]");
        y--;
      } else {
        endCell = FindNextFreeCell(x, y, "esq");
      }
    }

    if (completedPath) {
      path = grid.move(currentCell, endCell);
    }

    if (path) {
      if (lastPos == path.length - 1) {
        completedPath = true;
      }



      if (path.length > 1 && lastPos < path.length && lastPos != path.length - 1) {
        x = path[lastPos].x;
        y = path[lastPos].y;
        lastPos++;
        completedPath = false;
      } else if (completedPath) {
        x = path[lastPos].x;
        y = path[lastPos].y;
        lastPos = 0;

      }
    }
    grid.$cells.removeClass("agent");
    $("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]").addClass("agent");
  }, agentSpeed);

  var stopInterval = function() {
    clearInterval(timerId);
  };
};

FindNextFreeCell = function(x, y, dir) {
  if (dir == "limDir") {
    if (x != gridSize) {
      for (var y = y; y >= 0; y--) {
        if (FreeCell((x + 1), y)) {
          return getCell((x + 1), y);
        }
      }
    }
  } else if (dir == "limEsq") {
    if (x != gridSize) {
      for (var y = y; y <= gridSize; y++) {
        if (FreeCell((x + 1), y)) {
          return getCell((x + 1), y);
        }
      }
    }
  } else if (dir == "dir") {
    for (var y = y; y < gridSize - 1; y++) {
      if (FreeCell(x, (y + 1))) {
        return getCell(x, (y + 1));
      }
    }
    for (var x = x; x <= gridSize - 1; x++) {
      if (FreeCell((x + 1), y)) {
        runsSameLine = true;
        return getCell((x + 1), y);
      }
    }

  } else if (dir == "esq") {
    for (var y = y; y > 0; y--) {
      if (FreeCell(x, (y - 1))) {
        return getCell(x, (y - 1));
      }
    }
    for (var x = x; x <= gridSize - 1; x++) {
      if (FreeCell((x + 1), y)) {
        runsSameLine = true;
        return getCell((x + 1), y);
      }
    }
  }
}

EmptySqm = function(x, y) {
  var bNotWall = !$("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]").hasClass("wall");
  return bNotWall;
}

getCell = function(x, y) {
  return $("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]");
}

FreeCell = function(x, y) {
  var bNaoTemParede = !$("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]").hasClass("wall");
  var bNaoTemLixeira = !$("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]").hasClass("lixeira");
  var bNaoTemRecarga = !$("#search_grid .row .grid_item[x=" + x + "][y=" + y + "]").hasClass("pontoRecarga");
  return bNaoTemParede && bNaoTemLixeira && bNaoTemRecarga;
}

ValidSqm = function(x, y) {
  return ((x >= 0 && x < gridSize) && (y >= 0 && y < gridSize));
}

// javascript-astar
// http://github.com/bgrins/javascript-astar
// Freely distributable under the MIT License.
// Implements the astar search algorithm in javascript using a binary heap.

var astar = {
  init: function(grid) {
    for (var x = 0, xl = grid.length; x < xl; x++) {
      for (var y = 0, yl = grid[x].length; y < yl; y++) {
        var node = grid[x][y];
        node.f = 0;
        node.g = 0;
        node.h = 0;
        node.cost = node.type;
        node.visited = false;
        node.closed = false;
        node.parent = null;
      }
    }
  },
  heap: function() {
    return new BinaryHeap(function(node) {
      return node.f;
    });
  },
  search: function(grid, start, end, diagonal, heuristic) {
    astar.init(grid);
    heuristic = heuristic || astar.manhattan;
    diagonal = !!diagonal;

    var openHeap = astar.heap();

    openHeap.push(start);

    while (openHeap.size() > 0) {

      // Grab the lowest f(x) to process next.  Heap keeps this sorted for us.
      var currentNode = openHeap.pop();

      // End case -- result has been found, return the traced path.
      if (currentNode === end) {
        var curr = currentNode;
        var ret = [];
        while (curr.parent) {
          ret.push(curr);
          curr = curr.parent;
        }
        return ret.reverse();
      }

      // Normal case -- move currentNode from open to closed, process each of its neighbors.
      currentNode.closed = true;

      // Find all neighbors for the current node. Optionally find diagonal neighbors as well (false by default).
      var neighbors = astar.neighbors(grid, currentNode, diagonal);

      for (var i = 0, il = neighbors.length; i < il; i++) {
        var neighbor = neighbors[i];

        if (neighbor.closed || neighbor.isWall() || $("#search_grid .row .grid_item[x=" + neighbor.x + "][y=" + neighbor.y + "]").hasClass("pontoRecarga") || $("#search_grid .row .grid_item[x=" + neighbor.x + "][y=" + neighbor.y + "]").hasClass("lixeira")) {
          // Not a valid node to process, skip to next neighbor.
          continue;
        }

        // The g score is the shortest distance from start to current node.
        // We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
        var gScore = currentNode.g + neighbor.cost;
        var beenVisited = neighbor.visited;

        if (!beenVisited || gScore < neighbor.g) {

          // Found an optimal (so far) path to this node.  Take score for node to see how good it is.
          neighbor.visited = true;
          neighbor.parent = currentNode;
          neighbor.h = neighbor.h || heuristic(neighbor.pos, end.pos);
          neighbor.g = gScore;
          neighbor.f = neighbor.g + neighbor.h;

          if (!beenVisited) {
            // Pushing to heap will put it in proper place based on the 'f' value.
            openHeap.push(neighbor);
          } else {
            // Already seen the node, but since it has been rescored we need to reorder it in the heap
            openHeap.rescoreElement(neighbor);
          }
        }
      }
    }

    // No result was found - empty array signifies failure to find path.
    return [];
  },
  manhattan: function(pos0, pos1) {
    // See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

    var d1 = Math.abs(pos1.x - pos0.x);
    var d2 = Math.abs(pos1.y - pos0.y);
    return d1 + d2;
  },
  neighbors: function(grid, node, diagonals) {
    var ret = [];
    var x = node.x;
    var y = node.y;

    // West
    if (grid[x - 1] && grid[x - 1][y]) {
      ret.push(grid[x - 1][y]);
    }

    // East
    if (grid[x + 1] && grid[x + 1][y]) {
      ret.push(grid[x + 1][y]);
    }

    // South
    if (grid[x] && grid[x][y - 1]) {
      ret.push(grid[x][y - 1]);
    }

    // North
    if (grid[x] && grid[x][y + 1]) {
      ret.push(grid[x][y + 1]);
    }

    if (diagonals) {

      // Southwest
      if (grid[x - 1] && grid[x - 1][y - 1]) {
        ret.push(grid[x - 1][y - 1]);
      }

      // Southeast
      if (grid[x + 1] && grid[x + 1][y - 1]) {
        ret.push(grid[x + 1][y - 1]);
      }

      // Northwest
      if (grid[x - 1] && grid[x - 1][y + 1]) {
        ret.push(grid[x - 1][y + 1]);
      }

      // Northeast
      if (grid[x + 1] && grid[x + 1][y + 1]) {
        ret.push(grid[x + 1][y + 1]);
      }

    }

    return ret;
  }
};

// javascript-astar
// http://github.com/bgrins/javascript-astar
// Freely distributable under the MIT License.
// Includes Binary Heap (with modifications) from Marijn Haverbeke.
// http://eloquentjavascript.net/appendix2.html


var GraphNodeType = {
  OPEN: 0,
  WALL: 1
};

// Creates a Graph class used in the astar search algorithm.
function Graph(grid) {
  var nodes = [];

  for (var x = 0; x < grid.length; x++) {
    nodes[x] = [];

    for (var y = 0, row = grid[x]; y < row.length; y++) {
      nodes[x][y] = new GraphNode(x, y, row[y]);
    }
  }

  this.input = grid;
  this.nodes = nodes;
}

Graph.prototype.toString = function() {
  var graphString = "\n";
  var nodes = this.nodes;
  var rowDebug, row, y, l;
  for (var x = 0, len = nodes.length; x < len; x++) {
    rowDebug = "";
    row = nodes[x];
    for (y = 0, l = row.length; y < l; y++) {
      rowDebug += row[y].type + " ";
    }
    graphString = graphString + rowDebug + "\n";
  }
  return graphString;
};

function GraphNode(x, y, type) {
  this.data = {};
  this.x = x;
  this.y = y;
  this.pos = {
    x: x,
    y: y
  };
  this.type = type;
}

GraphNode.prototype.toString = function() {
  return "[" + this.x + " " + this.y + "]";
};

GraphNode.prototype.isWall = function() {
  return this.type === GraphNodeType.WALL;
};


function BinaryHeap(scoreFunction) {
  this.content = [];
  this.scoreFunction = scoreFunction;
}

BinaryHeap.prototype = {
  push: function(element) {
    // Add the new element to the end of the array.
    this.content.push(element);

    // Allow it to sink down.
    this.sinkDown(this.content.length - 1);
  },
  pop: function() {
    // Store the first element so we can return it later.
    var result = this.content[0];
    // Get the element at the end of the array.
    var end = this.content.pop();
    // If there are any elements left, put the end element at the
    // start, and let it bubble up.
    if (this.content.length > 0) {
      this.content[0] = end;
      this.bubbleUp(0);
    }
    return result;
  },
  remove: function(node) {
    var i = this.content.indexOf(node);

    // When it is found, the process seen in 'pop' is repeated
    // to fill up the hole.
    var end = this.content.pop();

    if (i !== this.content.length - 1) {
      this.content[i] = end;

      if (this.scoreFunction(end) < this.scoreFunction(node)) {
        this.sinkDown(i);
      } else {
        this.bubbleUp(i);
      }
    }
  },
  size: function() {
    return this.content.length;
  },
  rescoreElement: function(node) {
    this.sinkDown(this.content.indexOf(node));
  },
  sinkDown: function(n) {
    // Fetch the element that has to be sunk.
    var element = this.content[n];

    // When at 0, an element can not sink any further.
    while (n > 0) {

      // Compute the parent element index, and fetch it.
      var parentN = ((n + 1) >> 1) - 1,
        parent = this.content[parentN];
      // Swap the elements if the parent is greater.
      if (this.scoreFunction(element) < this.scoreFunction(parent)) {
        this.content[parentN] = element;
        this.content[n] = parent;
        // Update 'n' to continue at the new position.
        n = parentN;
      }

      // Found a parent that is less, no need to sink any further.
      else {
        break;
      }
    }
  },
  bubbleUp: function(n) {
    // Look up the target element and its score.
    var length = this.content.length,
      element = this.content[n],
      elemScore = this.scoreFunction(element);

    while (true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) << 1,
        child1N = child2N - 1;
      // This is used to store the new position of the element,
      // if any.
      var swap = null;
      var child1Score;
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.content[child1N];
        child1Score = this.scoreFunction(child1);

        // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore) {
          swap = child1N;
        }
      }

      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[child2N],
          child2Score = this.scoreFunction(child2);
        if (child2Score < (swap === null ? elemScore : child1Score)) {
          swap = child2N;
        }
      }

      // If the element needs to be moved, swap it, and continue.
      if (swap !== null) {
        this.content[n] = this.content[swap];
        this.content[swap] = element;
        n = swap;
      }

      // Otherwise, we are done.
      else {
        break;
      }
    }
  }
};
html,
body {
  height: 100%;
  margin: 0;
}

.buttons {
  float: right;
  position: relative;
  right: 10px;
  top: 10px;
}

.buttons a {
  text-decoration: none;
}

#content {
  margin: 0 auto;
  width: 98%;
  text-align: center;
}

#controls {
  text-align: center;
  margin-bottom: 25px;
  padding: 5px;
}

#search_grid {
  width: 300px;
  height: 300px;
  position: relative;
}

#main {
  margin: auto;
  width: 20%;
}

.grid_item {
  display: block;
  border: 1px solid #bbb;
  float: left;
  line-height: 12px;
  font-size: 10px;
}

.grid_item.wall {
  background-color: #000000;
}

.grid_item.weight1 {
  background-color: #ffffff;
}

.agent {
  text-align: center;
  color: grey;
  font-size: 20px;
  background-color: red !important;
  color: blue;
  font-weight: bold;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

<body>
  <div id="content">
    <input type="button" id="btnInit" value="Start" /><br><br>
    <div id="main">
      <div id="search_grid">Loading...</div>
    </div>
  </div>
  <div id="footer"></div>
</body>
Hide result
0

Source: https://habr.com/ru/post/1684243/

More articles:


All Articles