I’ve been playing around with doing some A* pathfinding scripts. I was looking around on the web and didn’t find any anywhere, so I decided to make my own rudimentary one. I’m going to be expounding on this later. I thought about looking into the A* method and a few others. Feel free to take the sample below. Here is a demo too.
<style>
* {
margin: 0px;
padding: 0px;
}
</style>
<body style="margin: 13px 0px 0px 0px; background: #000;">
<?php
/* Set the size of our target area */
$range = 3;
/* Build the pathfinding function */
function pathfind($current_square_x, $current_square_y, $map, $steps, $target) {
/* Give the function a step limit. We don't want to create an endless loop. */
$max_steps = 100;
/* Define the next steps */
$next_steps[$current_square_y + 1] [$current_square_x + 1] = "";
$next_steps[$current_square_y + 1] [$current_square_x] = "";
$next_steps[$current_square_y + 1] [$current_square_x - 1] = "";
$next_steps[$current_square_y - 1] [$current_square_x + 1] = "";
$next_steps[$current_square_y - 1] [$current_square_x] = "";
$next_steps[$current_square_y - 1] [$current_square_x - 1] = "";
$next_steps[$current_square_y] [$current_square_x + 1] = "";
$next_steps[$current_square_y] [$current_square_x - 1] = "";
/* Do some math to find the distance from here (as the crow flies) to the target) */
$height = sizeof($map);
$width = sizeof($map[0]);
$minimum = sqrt(($width * $width) + ($height * $height));
/* Find the closest tile */
foreach($next_steps as $y_key => $y_value) {
foreach($y_value as $x_key => $x_value) {
if(
isset($map[$y_key][$x_key]) &&
$map[$y_key][$x_key] != "closed" &&
$map[$y_key][$x_key] != "start" &&
$steps < $max_steps
) {
if($map[$y_key][$x_key] != "traversed") {
$width = abs($x_key - $target['x']) + 1;
$height = abs($y_key - $target['y']) + 1;
$c = round(sqrt(($width * $width) + ($height * $height)),2);
if($c < $minimum) {
$minimum = $c;
$lowest_distance_position = $x_key."x".$y_key;
}
}
}
}
}
/* Start the next calculation from the closest tile */
$position = explode("x",$lowest_distance_position);
if(
isset($map[$position[1]][$position[0]]) &&
!($position[0] == $target['x'] && $position[1] == $target['y'])
) {
$map[$position[1]][$position[0]] = "traversed";
$path[$position[0]."x".$position[1]] =
pathfind($position[0], $position[1], $map, $steps + 1, $target);
if($path) {
return $path;
break;
}
}
return array($position[0]."x".$position[1] => "target");
break;
}
/* Convert the three based array to a step based array. */
function build_path($path_array, $step_number) {
if(sizeof($path_array) > 0 && is_array($path_array)) {
foreach($path_array as $key => $value) {
$this_path[$step_number] = $key;
if(sizeof($path_array[$key]) > 0) {
$built_path =
array_merge(
$this_path,
build_path($path_array[$key], $step_number++)
);
return $built_path;
}
}
} else {
return array();
}
}
/* Set the map size. */
$map_size_x = 43;
$map_size_y = 22;
/* Build the blank map. */
for($y = 0; $y < $map_size_y; $y++) {
for($x = 0; $x < $map_size_x; $x++) {
$map[$y][$x] = "open";
}
}
/* Set special sections of the map. */
$map[15][25] = "closed";
$map[16][25] = "closed";
$map[17][25] = "closed";
$map[18][25] = "closed";
$map[19][25] = "closed";
$map[20][25] = "closed";
$target['x'] = 39;
$target['y'] = 18;
$start['x'] = 1;
$start['y'] = 1;
$path = pathfind($start['x'], $start['y'], $map, 0, $target);
$built_path = build_path($path, 1);
/* Output the final map. */
echo "<table style="margin: 0px auto;">";
foreach($map as $y_key => $y_value) {
echo "<tr>";
foreach($y_value as $x_key => $x_value) {
if($x_value == "closed") {
$background = "F99";
} elseif ($x_value == "path") {
$background = "9F9";
} elseif ($x_key == $start['x'] && $y_key == $start['y']) {
$background = "559";
} elseif (
$x_key < $target['x'] + $range &&
$x_key > $target['x'] - $range &&
$y_key < $target['y'] + $range &&
$y_key > $target['y'] - $range
) {
$background = "900";
} elseif(in_array($x_key."x".$y_key,$built_path)) {
$background = "353";
} else {
$background = "333";
}
echo
"<td
style="
background: #".$background.";
width: 20px;
height: 20px;
text-align: center;
">
</td>";
}
echo "</tr>";
}
echo "</table>";
?>
<pre>
<?php
//print_r($path);
?>
</pre>
</body>