a星寻路算法 php

A星寻路算法（A*算法）是一种常用于解决路径寻找问题的算法，特别适用于在网格图中寻找最短路径。下面是一个使用PHP实现A*算法的简单示例：

<?php

class Node {
    public $x;
    public $y;
    public $f;
    public $g;
    public $h;
    public $parent;

    function __construct($x, $y) {
        $this->x = $x;
        $this->y = $y;
        $this->f = 0;
        $this->g = 0;
        $this->h = 0;
        $this->parent = null;
    }
}

function astar($start, $goal, $grid) {
    $open = array();
    $closed = array();

    $start->g = 0;
    $start->h = heuristic($start, $goal);
    $start->f = $start->g + $start->h;

    array_push($open, $start);

    while (!empty($open)) {
        $current = $open[0];

        foreach ($open as $node) {
            if ($node->f < $current->f || ($node->f == $current->f && $node->h < $current->h)) {
                $current = $node;
            }
        }

        $key = array_search($current, $open);
        array_splice($open, $key, 1);
        array_push($closed, $current);

        if ($current->x == $goal->x && $current->y == $goal->y) {
            $path = array();
            while ($current->parent) {
                array_push($path, $current);
                $current = $current->parent;
            }
            return array_reverse($path);
        }

        $neighbors = getNeighbors($current, $grid);

        foreach ($neighbors as $neighbor) {
            $gScore = $current->g + 1;
            $hScore = heuristic($neighbor, $goal);
            $fScore = $gScore + $hScore;

            if (in_array($neighbor, $closed) && $fScore >= $neighbor->f) {
                continue;
            }

            if (!in_array($neighbor, $open) || $fScore < $neighbor->f) {
                $neighbor->g = $gScore;
                $neighbor->h = $hScore;
                $neighbor->f = $fScore;
                $neighbor->parent = $current;

                if (!in_array($neighbor, $open)) {
                    array_push($open, $neighbor);
                }
            }
        }
    }

    return null;
}

function heuristic($node, $goal) {
    return abs($node->x - $goal->x) + abs($node->y - $goal->y);
}

function getNeighbors($node, $grid) {
    $neighbors = array();
    $offsets = array(array(-1, -1), array(-1, 0), array(-1, 1), array(0, -1), array(0, 1), array(1, -1), array(1, 0), array(1, 1));
    foreach ($offsets as $offset) {
        $x = $node->x + $offset[0];
        $y = $node->y + $offset[1];
        if ($x >= 0 && $x < count($grid) && $y >= 0 && $y < count($grid[0]) && $grid[$x][$y] != 1) {
            array_push($neighbors, new Node($x, $y));
        }
    }
    return $neighbors;
}

// 测试
$grid = array(
    array(0, 0, 0, 0),
    array(1, 1, 0, 1),
    array(0, 0, 0, 0),
    array(0, 0, 0, 0)
);

$start = new Node(0, 0);
$goal = new Node(3, 3);

$path = astar($start, $goal, $grid);

if ($path) {
    foreach ($path as $node) {
        echo "(" . $node->x . ", " . $node->y . ") ";
    }
} else {
    echo "No Path Found";
}
?>

上述代码实现了A*寻路算法，其中`astar`函数用于执行算法的主要逻辑，`heuristic`函数用于计算启发式函数的值，`getNeighbors`函数用于获取节点的相邻节点。在给定的网格图中，我们从起点`(0, 0)`到目标点`(3, 3)`寻找最短路径。路径的结果将根据节点坐标依次打印出来。若找不到路径，则输出"No Path Found"。