Path finding

pathfinding.php

<?
// Why do we need the nodes?
//$nodes = json_decode('[{"x":3,"y":6,"id":0},{"x":1,"y":1,"id":1},{"x":3,"y":1,"id":2},{"x":3,"y":4,"id":3},{"x":5,"y":1,"id":4},{"x":6,"y":1,"id":5},{"x":4,"y":3,"id":6},{"x":1,"y":6,"id":7},{"x":4,"y":6,"id":8},{"x":6,"y":6,"id":9},{"x":3,"y":9,"id":10},{"x":6,"y":11,"id":11}]');
$paths = json_decode('[[0,1],[0,2],[0,3],[3,2],[3,6],[6,4],[6,5],[3,9],[9,9],[9,10],[10,0],[10,11],[11,10],[10,8],[8,3],[3,1]]');

// Convert paths to a hash: from -> [to]
$newPaths = array();
foreach($paths as $path) {
  if (!$newPaths[$path[0]]) $newPaths[$path[0]] = array();
  array_push($newPaths[$path[0]], $path[1]);
}
$paths = $newPaths;

// Use a Depth First Search, where:
// $paths is the original $paths array
// $visited are the nodes that we already visited (in order to avoid loops)
// $from is the node where we are parting from
// $to is the node where we want to arrive
// $result is the result that will finally be returned
function findPath(&$paths, &$visited, $from, $to, &$result) {
  $next = $paths[$from];
  if (!$next) return false;

  foreach($next as $node) {
    if ($node == $to) {
      array_push($result, $from);
      array_push($result, $to);
      return $result;
    }

    if ($visited[$node]) continue;

    $visited[$node] = true;
    array_push($result, $from);
    if (findPath($paths, $visited, $node, $to, $result)) {
      return $result;
    }
    array_pop($result);
    unset($visited[$node]);
  }
}

$result = array();
$visited = array();
findPath($paths, $visited, '0', '11', $result);
print_r($result);
?>