A*(A星,A star)寻路算法说明:A* Pathfinding for Beginners
测试地址 https://xkelai.com/astar.php?start[x]=5&start[y]=5&goal[x]=5&goal[y]=20&isCross=1&closeZone=0
参数说明:
isCross:1对角可穿越,0不可穿越
closeZone:1封闭区域,0不封闭
trace:1显示节点的选择,0不显示
代码
//限制脚本运行时间
set_time_limit(20);
$start = isset($_GET['start'])&&is_array($_GET['start'])?$_GET['start']: array('x' => 5, 'y' =>5);
$goal = isset($_GET['goal'])&&is_array($_GET['goal'])?$_GET['goal']:array('x' => 10, 'y' => 23);
$isCross = intval($_GET['isCross']);
$isTrace = intval($_GET['trace']);
$closeZone = intval($_GET['closeZone']);
$open = array();
$closed = array();
//设置障碍物坐标
$hindrance[10][11] = 1;
$hindrance[11][11] = 1;
$hindrance[12][11] = 1;
$hindrance[13][11] = 1;
$hindrance[14][11] = 1;
$hindrance[15][11] = 1;
$hindrance[16][11] = 1;
$hindrance[17][11] = 1;
$hindrance[18][11] = 1;
//TODO 此处省略N行......
//初始化节点
$nodes = array();
$rowCount = $colCount = 25;
for ($x = 0; $x < $colCount; $x++) {
for ($y = 0; $y < $rowCount; $y++) { $nodes[$x][$y] = array('x' => $x, 'y' => $y, 'v' => isset($hindrance[$x][$y]) ? 1 : 0);
}
}
//起始节点加入open
$open[] = $nodes[$start['x']][$start['y']];
$bestNode = $nodes[$start['x']][$start['y']];
$isGoal = false;
$loop = 0;
while (!$isGoal && !empty($open)) {
$loop++;
$bestNode = popBestNodeFromOpen();
$isTrace && $msg.= "bestNode:({$bestNode['x']},{$bestNode['y']}) g:{$bestNode['g']} h:{$bestNode['h']} f:{$bestNode['f']}" . nl2br(PHP_EOL);
addBestNodeToClosed($bestNode);
$arroundNodes = getArroundNodes($bestNode);
//var_dump($arroundNodes,$open,$closed);if($loop==2)die;
foreach ($arroundNodes as $node) {
//周边节点不在closed中时,进行处理
if (isNodeIn($closed, $node) === FALSE) {
//如果节点在open中
if (($key = isNodeIn($open, $node)) !== FALSE) {
//检查是否可获得更小的g值,如果是,则把该周边节点的父节点设为当前节点(即经由当前节点,可更快到达goal)
$tmpG = distance($nodes[$x][$y], $bestNode) + $bestNode['g'];
if ($tmpG < $node['g']) { $node['p'] = $bestNode; //重新计算g和f //$node['g'] = $tmpG+1; //也可以使用calcG,但浪费了一次tmpG的计算 calcG($node); calcF($node); //更新open中的节点信息 $open[$key] = $node; } } else {//如果节点不在open中,判断是否是goal,如不是则加入open,同时把它的父节点设为当前节点 if (isGoal($node)) { $isGoal = true; break; } $node['p'] = $bestNode; //重新计算g h f //$node['g'] = $bestNode['g']+1; calcG($node); calcH($node); calcF($node); addNodeToOpen($node); } } } } $path = $isGoal ? getPath() : array(); /** * 获取路径 * @global array $closed closed * @return array path */ function getPath() { global $closed; $count = count($closed); $p = $closed[$count - 1]; while (!empty($p)) { $path[] = array('x' => $p['x'], 'y' => $p['y']);
$p = $p['p'];
}
return $path;
}
/**
* 获取周边节点
* @global array $nodes 所有节点
* @global array $bestNode 当前选中节点
* @param boolean $isCross 对角节点是否可穿越
* @return int
*/
function getArroundNodes($bestNode) {
global $nodes;
global $bestNode;
global $isCross;
$arroundNodes = array();
for ($x = $bestNode['x'] - 1; $x <= $bestNode['x'] + 1; $x++) {
for ($y = $bestNode['y'] - 1; $y <= $bestNode['y'] + 1; $y++) { //如果节点存在,且不是障碍物,且不是当前节点,则为可用的周边节点 if (isset($nodes[$x][$y]) && ($nodes[$x][$y]['v'] !== 1) && !($x == $bestNode['x'] && $y == $bestNode['y'])) { //如果不允许对角线穿越,且周边节点为对角节点时,跳过 if (!$isCross && ($x !== $bestNode['x'] && $y !== $bestNode['y'])) { continue; } $arroundNodes[] = $nodes[$x][$y]; } } } return $arroundNodes; } /** * 判断是否是目标节点 * @global array $goal 目标 * @param array $node 节点 * @return boolean 是否达到目标 */ function isGoal($node) { global $goal; if ($node['x'] == $goal['x'] && $node['y'] == $goal['y']) { return true; } return false; } /** * 判断节点是否在列表中 * @param array $nodes 节点列表 * @param array $newNode 节点 * @return boolean 节点是否在列表中 */ function isNodeIn($nodes, $newNode) { foreach ($nodes as $key => $node) {
if ($node['x'] == $newNode['x'] && $node['y'] == $newNode['y']) {
return $key;
}
}
return false;
}
/**
* 添加节点到open
* @global array $open open
* @param array $node 节点
*/
function addNodeToOpen($node) {
global $open;
$open[] = $node;
}
/**
* 从open中取出f最小的节点
* @global array $open open
* @return array 最优节点
*/
function popBestNodeFromOpen() {
global $open;
$minF = $minDistance = PHP_INT_MAX;
$minNodeKey = 0;
foreach ($open as $key => $node) {
if ($node['f'] <= $minF) {
$minF = $node['f'];
$minNodeKey = $key;
}
}
$returnNode = $open[$minNodeKey];
unset($open[$minNodeKey]);
return $returnNode;
}
/**
* 添加节点到closed
* @global array $closed closed
* @param array $bestNode 最优节点
*/
function addBestNodeToClosed($bestNode) {
global $closed;
$closed[] = $bestNode;
}
/**
* 计算节点间距离
* @param array $node1 节点1
* @param array $node2 节点2
* @return int 距离
*/
function distance($node1, $node2) {
return abs($node1['y'] - $node2['y']) + abs($node1['x'] - $node2['x']);
}
/**
* 计算G值,即节点到起点距离
* @global array $start 起始节点
* @param type $node 节点
*/
function calcG(&$node) {
global $start;
//mahanttan
if(!isset($node['g'])){
$node['g'] = PHP_INT_MAX;
}
if(isset($node['p'])){
$tmpG = $node['p']['g']+1;
$node['g'] = $tmpG<$node['g']?$tmpG:$node['g'];
}
}
/**
* 计算H值,即节点到目标的估计距离
* @global array $goal 目标节点
* @param array $node 节点
*/
function calcH(&$node) {
global $goal;
$node['h'] = abs($goal['y'] - $node['y']) + abs($goal['x'] - $node['x']);
}
/**
* 计算F值,即经由节点到达目标的估计距离
* @param array $node 节点
*/
function calcF(&$node) {
$node['f'] = $node['g'] + $node['h'];
}