A simple A* pathfinder

A simple A* pathfinder I wrote in JavaScript.

Click Here to open the demo.

// -- Board and canvas operations--
// Board
var board;
var board_rows = 300, board_cols = 300;
var dot_r = 50, dot_c = 50;

// Canvas
var canvas_scale_factor = 2;
var canvas_width = board_cols * canvas_scale_factor;
var canvas_height = board_cols * canvas_scale_factor;

var canvas_main = document.getElementById('mainCanvas');
var canvas_main_context = canvas_main.getContext('2d');
var canvas_overlay = document.getElementById('overlayCanvas');
var canvas_overlay_context = canvas_overlay.getContext('2d');

var canvas_changed = false;
var canvas_mousedown = false;
var canvas_last_mouse_pos_x;
var canvas_last_mouse_pos_y;

// Board functions
function boardInit() {
  var b = new Array(board_rows);
  for (var r = 0; r < board_rows; r++)
    b[r] = new Array(board_cols);

  board = b;
}

function boardClear() {
  for (var r = 0; r < board_rows; r++)
    for (var c = 0; c < board_cols; c++)
      board[r][c] = 0;
}

// Canvas functions
function canvasInit() {
  canvasClear(canvas_main_context);
  canvasClear(canvas_overlay_context);

  canvas_main_context.fillStyle = "#F7F7F7";
  canvas_main_context.fillRect(0, 0, canvas_width, canvas_height);
}

function canvasClear(context) {
  canvas_changed = true;
  context.clearRect(0, 0, canvas_width, canvas_height);
}

function canvasFillRect(x, y, w, h, color) {
    canvas_overlay_context.fillStyle = color;
    canvas_overlay_context.fillRect(x, y, w, h);
}

function canvasDrawLine(x1, y1, x2, y2) {
  if (x1 >= canvas_width || x1 < 0 || y1 >= canvas_height || y1 < 0) return;
  if (x2 >= canvas_width || x2 < 0 || y2 >= canvas_height || y2 < 0) return;

  canvas_changed = true;
  canvas_main_context.beginPath();
  canvas_main_context.moveTo(x1, y1);
  canvas_main_context.lineTo(x2, y2);
  canvas_main_context.lineWidth = 3;
  canvas_main_context.stroke();
}

function canvasRandomLine() {
  var x1 = Math.floor(Math.random() * canvas_width);
  var y1 = Math.floor(Math.random() * canvas_height);
  var x2 = Math.floor(Math.random() * canvas_width);
  var y2 = Math.floor(Math.random() * canvas_height);
  canvasDrawLine(x1, x2, y1, y2);
}

function canvasCopyToBoard() {
  if (!canvas_changed) return;
  canvas_changed = false;

  var bitmap = canvas_main_context.getImageData(0, 0, canvas_width, canvas_height).data;
  for (var r = 0; r < board_rows; r++) {
    for (var c = 0; c < board_cols; c++) {
      if (bitmap[(r * canvas_scale_factor * canvas_width + c * canvas_scale_factor) * 4] != 0xF7)
        board[r][c] = 1;
      else
        board[r][c] = 0;
    }
  }
}

// -- Path searching--
var f_score;

// Comparator based on f-score
function minHeapComparator(a, b) {
  var f_a = f_score.get(a);
  var f_b = f_score.get(b);
  if      (f_a <  f_b) return 1;
  else if (f_a >  f_b) return -1;
  else if (f_a == f_b) return 0;
}

// h()
function heuristiceEstimation(r1, c1, r2, c2) {
  return Math.sqrt(Math.pow((r2 - r1), 2) + Math.pow((c2 - c1), 2));
  //return h_weight * (Math.abs(r2 - r1) + Math.abs(c2 - c1));
}

// A*
function findPath(r1, c1, r2, c2) {
  if (c1 >= board_cols || c1 < 0 || r1 >= board_rows || r1 < 0) return [];
  if (c2 >= board_cols || c2 < 0 || r2 >= board_rows || r2 < 0) return [];
  if (board[r2][c2] != 0) return [];

  // Get h_weight
  var h_weight = document.getElementById('sliHWeight').value;

  // Data structures
  var pq = buckets.PriorityQueue(minHeapComparator);
  var previous_node = buckets.Dictionary();
  var visited_nodes = buckets.Set();
  var g_score = buckets.Dictionary();
  f_score = buckets.Dictionary();

  // Process starting node
  var p_start = [r1, c1];
  var f, g = 0;

  // Calculate f-score
  f = g + heuristiceEstimation(r1, c1, r2, c2);
  g_score.set(p_start, g);
  f_score.set(p_start, f);

  // Enqueue starting node
  pq.enqueue(p_start);
  visited_nodes.add(p_start);

  // BFS
  while (!pq.isEmpty()) {
    var p_current = pq.dequeue();
    var p_current_r = p_current[0];
    var p_current_c = p_current[1];

    // Draw explored nodes
    canvasFillRect(p_current_c * canvas_scale_factor, p_current_r * canvas_scale_factor, 2, 2, '#0F0');

    if (p_current_r == r2 && p_current_c == c2) {
      // Solution found
      var result = [p_current];

      // Backtrack solution
      while (previous_node.containsKey(p_current)) {
        p_current = previous_node.get(p_current);
        result.push(p_current);

        // Draw path
        canvasFillRect(p_current[1] * canvas_scale_factor, p_current[0] * canvas_scale_factor, 2, 2, '#F00');
      }
      return result;
    }

    // Process neighbors
    for (var r = p_current_r - 1; r <= p_current_r + 1; r++) {
      for (var c = p_current_c - 1; c <= p_current_c + 1; c++) {
          if (r >= 0 && r < board_rows && c >= 0 && c < board_cols) {
            var neighbor = [r, c];

            if (board[neighbor[0]][neighbor[1]] != 0) continue;
            if (visited_nodes.contains(neighbor)) continue;

            // Calculate f-score
            g = g_score.get(p_current) + heuristiceEstimation(p_current_r, p_current_c, neighbor[0], neighbor[1]);
            f = g + h_weight * heuristiceEstimation(neighbor[0], neighbor[1], r2, c2);
            g_score.set(neighbor, g);
            f_score.set(neighbor, f);

            // Enqueue neighbor
            previous_node.set(neighbor, p_current);
            pq.enqueue(neighbor);
            visited_nodes.add(neighbor);
        }
      }
    }
  }

  // No solution
  return [];
}

// Animated path walker
var current_path;
var current_path_index;
var tmPathWalker;
var dot = document.getElementById('dot');

function walkPath(path) {
  clearInterval(tmPathWalker);
  current_path = path;
  current_path_index = current_path.length - 1;
  tmPathWalker = setInterval(doWalk, 2000 / current_path.length);
}

function doWalk() {
  dot.style.top = current_path[current_path_index][0] * canvas_scale_factor + 5 + 'px';
  dot.style.left = current_path[current_path_index][1] * canvas_scale_factor + 5 + 'px';
  dot_r = current_path[current_path_index][0];
  dot_c = current_path[current_path_index][1];

  current_path_index--;
  if (current_path_index < 0) {
    stopWalkingTimer();
  }
}

function stopWalkingTimer() {
  clearInterval(tmPathWalker);
}

// -- Initialization and UI code --
boardInit();
boardClear();
canvasInit();
chkShowOverlayCanvasOnClick();

var lblStatus = document.getElementById('lblStatus');

document.addEventListener('mousedown', mouseDown, false);
document.addEventListener('mouseup', mouseUp, false);
document.addEventListener('mousemove', mouseMove, false);
document.addEventListener('touchend', mouseUp, false);

function mouseDown(e) {
  if (e.button != 2) return;
  canvasClear(canvas_overlay_context);
  canvas_last_mouse_pos_x = e.pageX;
  canvas_last_mouse_pos_y = e.pageY;
  canvas_mousedown = true;
};

function mouseUp(e) {
  canvas_mousedown = false;

  if (e.pageX > canvas_width || e.pageY > canvas_height) return;
  if (typeof(e.button) == 'undefined' || e.button == 0) {
    stopWalkingTimer();
    lblStatusMsg('Generating path...');

    setTimeout(function() {
      // Re-initialize board
      canvasClear(canvas_overlay_context);
      canvasCopyToBoard();

      // Get path
      var path = findPath(dot_r, dot_c, Math.floor(e.pageY / canvas_scale_factor), Math.floor(e.pageX / canvas_scale_factor));
      if (path.length > 0) {
        // Walk
        walkPath(path);
        lblStatusMsg('');
      } else {
        lblStatusErr('No solution found.');
      }
    }, 100);
  }
};

function mouseMove(e) {
  if (!canvas_mousedown) return;
  canvasDrawLine(canvas_last_mouse_pos_x, canvas_last_mouse_pos_y, e.pageX, e.pageY);
  canvas_last_mouse_pos_x = e.pageX;
  canvas_last_mouse_pos_y = e.pageY;
};

function chkShowOverlayCanvasOnClick() {
  if (document.getElementById('chkShowOverlayCanvas').checked) {
    canvas_overlay.style.visibility = 'visible';
  } else {
    canvas_overlay.style.visibility = 'hidden';
  }
}

function lblStatusMsg(text) {
    lblStatus.style.backgroundColor = '#2979FF';
    lblStatus.textContent = text;
}

function lblStatusErr(text) {
    lblStatus.style.backgroundColor = '#FF3D00';
    lblStatus.textContent = text;
}