A*(A星,A star)寻路算法说明:A* Pathfinding for Beginners

测试地址 https://aiddroid.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不显示

点击查看 运行效果(canvas绘图)

代码

//限制脚本运行时间
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'];
}

Post Navigation