在六角形地图上行走时识别并处理 2 条有效路径

Question

我正在编写一个用于六边形地图的成本路径脚本。目前我正处于“学习如何走路”的发展阶段。

一般来说，代码可以工作。我可以可靠地从 A 到达 B。但是，请考虑以下地图：

两个序列 第0406章第0405章0505 和 0406 ->第0506章0505 有效。我想遍历并输出两条路径。

我的代码如下：

public function walkMap($origCol, $origRow, $destCol, $destRow) {
    $curRow = $origRow;
    $curCol = $origCol;
    while (($curRow != $destRow) || ($curCol != $destCol)) {
        $newRow = self::getNextMove($curRow,$destRow);
        if ($newRow == $curRow) {
            $curCol = self::getNextMove($curCol,$destCol);
        } else {
            $curRow = $newRow;
        }
    }
}

private function getNextMove($cur,$dest) {
    if ($cur < $dest) {
        ++$cur;
    } else if ($cur > $dest) {
        --$cur;
    }
    return $cur;
}

我想要的结果是 step => 的数值数组hexCoord 显示所采取的路径。但我不确定如何采用上述工作代码来智能分支，并且完成后，如何最好地塑造输出数据结构......

提前致谢。

Answer 1

我注意到，目前，您的路径选择只是“到达正确的行，然后到达正确的列”。我意识到您仍处于起步阶段，但您可能需要提前考虑如何将成本纳入您的路径，并让它告诉您有关数据结构的信息。

例如，您可以使用 Dijkstra 算法 以最低成本标记地图上的每个点从该点到指定目的地。找到一条路径就是选择一个原点并以最小的成本重复移动到相邻的六角形，从而构建您想要的路径数组。如果在任何点有两条最佳路径，您将看到它是一个具有两个最低成本邻居的十六进制 - 您将为每个路径数组创建一个新副本并独立完成它们。采用这种方法，您将使用（并返回）路径数组的数组。

Answer 2

我使用了两个类：Cubicles 是那些具有列号和行号的六角形物体，而 Paths 是 Cubicles 的有序列表。小隔间有一个功能分支来获取所有在通往目的地的路径上处于“正确方向”的小隔间。只需执行一步即可从 Cubicle 直接访问。

然后，我从长度为 1 的路径（仅开始）开始，并通过所有分支稳步扩展该路径，为每个分支生成一条路径，比旧的长 1 条路径。如果它不能再扩展，我们就在$dest并且可以输出这个路径。

希望有帮助。花了一些时间来调试。如果它不适用于任何情况，请告诉我。

<?php

class Cubicle
{
    public $col;
    public $row;

    public function branch(Cubicle $dest)
    {
        $result = array();

        // move up
        if ($this->row > $dest->row)
            $result[] = new Cubicle($this->col, $this->row - 1);

        // move down
        elseif ($this->row < $dest->row)
            $result[] = new Cubicle($this->col, $this->row + 1);

        // move right
        if ($this->col < $dest->col)
        {
            // right-up
            if ($this->row >= $dest->row)
                $result[] = new Cubicle($this->col + 1, $this->row);

            // right-down
            else
                $result[] = new Cubicle($this->col + 1, $this->row - 1);
        }

        // move left
        elseif ($this->col > $dest->col)
        {
            // left-up
            if ($this->row > $dest->row)
                $result[] = new Cubicle($this->col - 1, $this->row - 1);

            // left-down
            else
                $result[] = new Cubicle($this->col - 1, $this->row);
        }

        return $result;
    }

    public function __construct($col, $row)
    {
        $this->col = $col;
        $this->row = $row;
    }
}

class Path
{
    public $cubicles = array();

    public function __construct(Cubicle $start)
    {
        $this->cubicles[] = $start;
    }

    public function getLast()
    {
        return $this->cubicles[count($this->cubicles)-1];
    }

    public function append($nextCubicle)
    {
        $clone = clone $this;
        $clone->cubicles[] = $nextCubicle;
        return $clone;
    }
}

function walk(Cubicle $start, Cubicle $dest) {
    $process = array(new Path($start));
    $output = array();

    while(count($process) > 0)
    {
        $currentPath = array_pop($process);

        $branches = $currentPath->getLast()->branch($dest);

        if (count($branches) == 0)
            $output[] = $currentPath;

        foreach ($branches as $branch)
            $process[] = $currentPath->append($branch);
    }

    return $output;
}

$start = new Cubicle(4, 6);
$dest = new Cubicle(5, 5);


$paths = walk($start, $dest);
var_dump($paths);
?>

输出

array
  0 => 
    object(Path)[8]
      public 'cubicles' => 
        array
          0 => 
            object(Cubicle)[1]
              public 'col' => int 4
              public 'row' => int 6
          1 => 
            object(Cubicle)[5]
              public 'col' => int 5
              public 'row' => int 6
          2 => 
            object(Cubicle)[3]
              public 'col' => int 5
              public 'row' => int 5
  1 => 
    object(Path)[9]
      public 'cubicles' => 
        array
          0 => 
            object(Cubicle)[1]
              public 'col' => int 4
              public 'row' => int 6
          1 => 
            object(Cubicle)[4]
              public 'col' => int 4
              public 'row' => int 5
          2 => 
            object(Cubicle)[7]
              public 'col' => int 5
              public 'row' => int 5

这是一种非常低效的方法，因为如果有重叠的路径，算法将为每个路径重新计算这些路径的部分内容。如果您想要一个性能良好的算法，您将需要创建某种图，其中仅包含有效路径并对其进行深度优先搜索以输出所有可能的路径。