代码语言：php

所属分类：算法

代码描述：php A star(A *)寻路算法代码，从A到B，绿色背景表示最短路径，黑色背景表示障碍，刷新会重新生成路障。

代码标签： ( A * ) 寻路 算法

下面为部分代码预览，完整代码请点击下载或在bfwstudio webide中打开

<?php

$config = array(
    'start' => array(1, 2), // 开始坐标
    'end' => array(9, 10), // 结束坐标
    'x' => 10, // 最大x
    'y' => 10, // 最大y
    'disable_num' => 30, // 障碍点个数
);
 
$a = new aStar($config['start'], $config['end'], $config['x'], $config['y'], $config['disable_num']);
$a->displayPic();
 
 
/**
 * astar寻路算法
 */
class aStar
{
 
    private $_start; // 开始点
    private $_end; // 结束点
    private $_x; // 最大x轴
    private $_y; // 最大y轴
    private $_num; // 障碍点数量
 
    private $_around; // 当前节点的可能四周节点数组
    private $_g; // g值数组
 
    public $open; // 开放节点数组
    public $close; // 关闭节点数组
    public $disable = array(); // 随机生成的障碍点数组
 
    public $route = array(); // 结果路径数组
 
    /**
     * @param $start array 开始点
     * @param $end array 结束点
     * @param $x int 最大x轴
     * @param $y int 最大y轴
     * @param $num int 最大随机障碍点数量
     */
    public function __construct($start, $end, $x, $y, $num)
    {
        $this->_start = $start;
        $this->_end = $end;
        $this->_x = $x;
        $this->_y = $y;
        $this->_num = $num;
 
        // 开始寻路
        $this->_route();
    }
 
    private function _route()
    {
        // 生成随机路障点
        $this->_makeDisable();
        // 算法开始
        $this->_start();
    }
 
    private function _start()
    {
        // 设置初始点的各项值
        $point[0] = $this->_start[0]; // x
        $point[1] = $this->_start[1]; // y
        $point['i'] = $this->_pointInfo($this->_start); // 当前节点 point info
        $point['f'] = 0; // f 值
        $this->_g[$point['i']] = 0; // g 值
        $point['h'] = $this->_getH($this->_start); // h 值
        $point['p'] = null; // 父节点 point info
 
        $this->open[$point['i']] = $this->close[$point['i']] = $point; // 开始节点加入open和close
        while (count($this->open) > 0) {
            // 查找最小的f值
            $f = 0;
            foreach ($this->open as $info => $node) {
                if ($f === 0 || $f > $node['f']) {
                    $minInfo = $info;
                    $f = $node['f'];
                }
            }
 
            // 将当前节点从open中删除
            $current = $this->open[$minInfo];
            unset($this->open[$minInfo]);
            // 将当前节点加入close
            $this->close[$minInfo] = $current;
 
            // 如果到达了终点，根据各节点的父节点算出其route
            if ($current[0] == $this->_end[0] && $current[1] == $this->_end[1]) {
                // 反向推出路径
                while ($current['p'] !== null) {
                    $tmp = $this->close[$this->_pointInfo($current['p'])];
                    array_unshift($this->route, array($tmp[0], $tmp[1]));
                    $current = $this->close[$this->_pointInfo($current['p'])];
                }
                array_push($this->route, $this->_end);
                break;
            }
 
            // 设置当前节点的四周节点
            $this->_setAround($current);
            // 四周节点状态更新
            $this->_updateAround($current);
        }
 
    }
 
    private function _updateAround($current)
    {
        foreach ($this->_around as $v) {
            if (!isset($this->close[$this->_pointInfo($v)])) { // 不在close里面才处理
                if (isset($this->open[$this->_pointInfo($v)])) { // 在open里面，比较值，小则更新
                    if ($this->_getG($current) < $this->_g[$this->_pointInfo($v)]) {
                        $this->_updatePointDetail($current, $v);
                    }
                } else { // 不在open里面，直接更新
                    $this->open[$this->_pointInfo($v)][0] = $v[0];
                    $this->open[$this->_pointInfo($v)][1] = $v[1];
                    $this->_updatePointDetail($current, $v);
                }
            }
        }
    }
 
    private function _updatePointDetail($current, $around)
    {
        $this->open[$this->_pointInfo($around)]['f'] = $this->_getF($current, $around);
        $this->_g[$this->_pointInfo($around)] = $this->_getG($current);
        $this->open[$this->_pointInfo($around)]['h'] = $this->_getH($around);
        $this->open[$this->_pointInfo($around)]['p'] = $current; // 重新设置父节点
    }
 
    /**
     * 返回当前节点的可能四周节点
     */
    private function _setAround($point)
    {
        // 可能的X点
        $roundX[] = $point[0]; // 当前x点
        ($point[0] - 1 > 0) &&.........完整代码请登录后点击上方下载按钮下载查看

网友评论0

取消

评论提交中...

提交评论