Created
November 6, 2010 14:28
-
-
Save tobiassjosten/665458 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
require('pathing.php'); | |
$gmap = array( | |
array(6, 5, 6, 4, 6, 1, 2, 6, 9, 6, 6, 5, 6, 4, 6, 1, 2, 6, 9, 6), | |
array(8, 5, 3, 2, 9, 9, 3, 2, 4, 7, 8, 5, 3, 2, 9, 9, 3, 2, 4, 7), | |
array(4, 8, 7, 7, 3, 5, 2, 8, 3, 5, 4, 8, 7, 7, 3, 5, 2, 8, 3, 5), | |
array(7, 5, 5, 8, 7, 7, 8, 4, 8, 5, 7, 5, 5, 8, 7, 7, 8, 4, 8, 5), | |
array(4, 5, 1, 6, 4, 6, 9, 3, 8, 1, 4, 5, 1, 6, 4, 6, 9, 3, 8, 1), | |
array(4, 6, 6, 4, 2, 7, 8, 8, 2, 2, 4, 6, 6, 4, 2, 7, 8, 8, 2, 2), | |
array(9, 4, 4, 5, 8, 4, 9, 5, 5, 2, 9, 4, 4, 5, 8, 4, 9, 5, 5, 2), | |
array(2, 9, 4, 9, 4, 8, 4, 1, 4, 6, 2, 9, 4, 9, 4, 8, 4, 1, 4, 6), | |
array(5, 8, 1, 2, 2, 2, 9, 1, 6, 9, 5, 8, 1, 2, 2, 2, 9, 1, 6, 9), | |
array(8, 9, 2, 7, 5, 1, 2, 9, 8, 9, 8, 9, 2, 7, 5, 1, 2, 9, 8, 9), | |
array(6, 5, 6, 4, 6, 1, 2, 6, 9, 6, 6, 5, 6, 4, 6, 1, 2, 6, 9, 6), | |
array(8, 5, 3, 2, 9, 9, 3, 2, 4, 7, 8, 5, 3, 2, 9, 9, 3, 2, 4, 7), | |
array(4, 8, 7, 7, 3, 5, 2, 8, 3, 5, 4, 8, 7, 7, 3, 5, 2, 8, 3, 5), | |
array(7, 5, 5, 8, 7, 7, 8, 4, 8, 5, 7, 5, 5, 8, 7, 7, 8, 4, 8, 5), | |
array(4, 5, 1, 6, 4, 6, 9, 3, 8, 1, 4, 5, 1, 6, 4, 6, 9, 3, 8, 1), | |
array(4, 6, 6, 4, 2, 7, 8, 8, 2, 2, 4, 6, 6, 4, 2, 7, 8, 8, 2, 2), | |
array(9, 4, 4, 5, 8, 4, 9, 5, 5, 2, 9, 4, 4, 5, 8, 4, 9, 5, 5, 2), | |
array(2, 9, 4, 9, 4, 8, 4, 1, 4, 6, 2, 9, 4, 9, 4, 8, 4, 1, 4, 6), | |
array(5, 8, 1, 2, 2, 2, 9, 1, 6, 9, 5, 8, 1, 2, 2, 2, 9, 1, 6, 9), | |
array(8, 9, 2, 7, 5, 1, 2, 9, 8, 9, 8, 9, 2, 7, 5, 1, 2, 9, 8, 9), | |
array(6, 5, 6, 4, 6, 1, 2, 6, 9, 6, 6, 5, 6, 4, 6, 1, 2, 6, 9, 6), | |
array(8, 5, 3, 2, 9, 9, 3, 2, 4, 7, 8, 5, 3, 2, 9, 9, 3, 2, 4, 7), | |
array(4, 8, 7, 7, 3, 5, 2, 8, 3, 5, 4, 8, 7, 7, 3, 5, 2, 8, 3, 5), | |
array(7, 5, 5, 8, 7, 7, 8, 4, 8, 5, 7, 5, 5, 8, 7, 7, 8, 4, 8, 5), | |
array(4, 5, 1, 6, 4, 6, 9, 3, 8, 1, 4, 5, 1, 6, 4, 6, 9, 3, 8, 1), | |
array(4, 6, 6, 4, 2, 7, 8, 8, 2, 2, 4, 6, 6, 4, 2, 7, 8, 8, 2, 2), | |
array(9, 4, 4, 5, 8, 4, 9, 5, 5, 2, 9, 4, 4, 5, 8, 4, 9, 5, 5, 2), | |
array(2, 9, 4, 9, 4, 8, 4, 1, 4, 6, 2, 9, 4, 9, 4, 8, 4, 1, 4, 6), | |
array(5, 8, 1, 2, 2, 2, 9, 1, 6, 9, 5, 8, 1, 2, 2, 2, 9, 1, 6, 9), | |
array(8, 9, 2, 7, 5, 1, 2, 9, 8, 9, 8, 9, 2, 7, 5, 1, 2, 9, 8, 9), | |
array(6, 5, 6, 4, 6, 1, 2, 6, 9, 6, 6, 5, 6, 4, 6, 1, 2, 6, 9, 6), | |
array(8, 5, 3, 2, 9, 9, 3, 2, 4, 7, 8, 5, 3, 2, 9, 9, 3, 2, 4, 7), | |
array(4, 8, 7, 7, 3, 5, 2, 8, 3, 5, 4, 8, 7, 7, 3, 5, 2, 8, 3, 5), | |
array(7, 5, 5, 8, 7, 7, 8, 4, 8, 5, 7, 5, 5, 8, 7, 7, 8, 4, 8, 5), | |
array(4, 5, 1, 6, 4, 6, 9, 3, 8, 1, 4, 5, 1, 6, 4, 6, 9, 3, 8, 1), | |
array(4, 6, 6, 4, 2, 7, 8, 8, 2, 2, 4, 6, 6, 4, 2, 7, 8, 8, 2, 2), | |
array(9, 4, 4, 5, 8, 4, 9, 5, 5, 2, 9, 4, 4, 5, 8, 4, 9, 5, 5, 2), | |
array(2, 9, 4, 9, 4, 8, 4, 1, 4, 6, 2, 9, 4, 9, 4, 8, 4, 1, 4, 6), | |
array(5, 8, 1, 2, 2, 2, 9, 1, 6, 9, 5, 8, 1, 2, 2, 2, 9, 1, 6, 9), | |
array(8, 9, 2, 7, 5, 1, 2, 9, 8, 9, 8, 9, 2, 7, 5, 1, 2, 9, 8, 9), | |
); | |
$map = $queue = $visited = array(); | |
$result = findLowest(array(0, 0, 19, 39), $gmap); | |
print_r($result); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* A* implementation. | |
* | |
* PHP version 5 | |
* | |
* @category Algorithms | |
* @package Astar | |
* @author Tobias Sjösten <tobias.sjosten@gmail.com> | |
* @license http://www.gnu.org/licenses/gpl.html GNU License | |
* @link http://vvv.tobiassjosten.net/ | |
*/ | |
/** | |
* Calculate the cheapest path between two points in a map. | |
* | |
* @param array $endpoints Start and end positions. | |
* @param array $map Grid to calculate path within. | |
* | |
* @return Array with keys 0=>cost and 1=>path from $start to $end. | |
*/ | |
function findLowest($endpoints, $map) | |
{ | |
$queue = $visited = array(); | |
// Add start position to queue. | |
$queue[$endpoints[0].'x'.$endpoints[1]] = array( | |
array($endpoints[0], $endpoints[1]), | |
true, | |
$map[$endpoints[1]][$endpoints[0]] | |
); | |
while (true) { | |
/* START FETCH ITEM */ | |
if (!count($queue)) { | |
return false; | |
} | |
$cost = INF; | |
$next_item = false; | |
foreach ($queue as $item) { | |
if ($item[2] < $cost) { | |
$next_item = $item; | |
$cost = $item[2]; | |
} | |
} | |
unset($queue[$next_item[0][0].'x'.$next_item[0][1]]); | |
if (!$next_item) { | |
break; | |
} | |
$item = $next_item; | |
/* END FETCH ITEM */ | |
$item_id = $item[0][0].'x'.$item[0][1]; | |
if (!empty($visited[$item_id])) { | |
continue; | |
} | |
$visited[$item_id] = $item[1]; | |
// If current node is the end node, we've found our path! | |
if ($item[0][0] == $endpoints[2] && $item[0][1] == $endpoints[3]) { | |
$path = array(); | |
$cost = 0; | |
$node = $item[0]; | |
while ($parent = $visited[$node[0].'x'.$node[1]]) { | |
$cost += $path[] = $map[$node[1]][$node[0]]; | |
if ($parent === true) { | |
break; | |
} | |
$node = $parent; | |
} | |
return array($cost, array_reverse($path)); | |
} | |
/* START QUEUE ADJACENTS */ | |
$directions = array(array(0, -1), array(1, 0), array(0, 1), array(-1, 0)); | |
foreach ($directions as $direction) { | |
$adjacent = array( | |
$item[0][0] + $direction[0], | |
$item[0][1] + $direction[1] | |
); | |
$in_range = !empty($map[$adjacent[1]]) | |
&& !empty($map[$adjacent[1]][$adjacent[0]]); | |
if (!empty($visited[$adjacent[0].'x'.$adjacent[1]]) || !$in_range) { | |
continue; | |
} | |
/* START QUEUE ADD */ | |
$adjacent_id = $adjacent[0].'x'.$adjacent[1]; | |
$adjacent_cost = $item[2] + $map[$adjacent[1]][$adjacent[0]]; | |
$adjacent_queue = true; | |
if (!empty($visited[$adjacent_id])) { | |
$adjacent_queue = false; | |
} | |
if (!empty($queue[$adjacent_id])) { | |
if ($adjacent_cost < $queue[$adjacent_id][2]) { | |
$queue[$adjacent_id][1] = true; | |
$queue[$adjacent_id][2] = $adjacent_cost; | |
} | |
$adjacent_queue = false; | |
} | |
if ($adjacent_queue) { | |
$queue[$adjacent_id] = array($adjacent, $item[0], $adjacent_cost); | |
} | |
/* END QUEUE ADD */ | |
} | |
/* END QUEUE ADJACENTS */ | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Any time. :)