1

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

一般来说，代码有效。我可以可靠地从 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显示所走路径的数字数组。但是我不确定如何采用上述工作代码来智能分支，并且这样做了，如何最好地塑造输出数据结构......

提前致谢。

4

2 回答 2

1

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

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

于 2012-02-27T23:32:29.853 回答
0

我使用了两个类：Cubicles 是那些有列和行号的六边形事物，以及 Paths 是 Cubicles 的有序列表。Cubicles 有一个函数分支来获取所有 Cubicles，它们在通往目的地的路径上的“正确方向”。只需一步即可从隔间直接到达。

然后我从长度为 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

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

于 2012-02-23T12:09:14.350 回答