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

現時点では、あなたのパスの選択は単純に「正しい行に移動してから、正しい列に移動する」ことであることに気付きました。まだ始めたばかりだとは思いますが、パスにコストをどのように組み込むかについて事前に検討し、データ構造について教えてもらいたいと思うかもしれません。

たとえば、ダイクストラのアルゴリズムを使用して、マップ上の各ポイントを、そのポイントから特定の目的地までの最小コストでマークできます。パスを見つけるには、原点を選択し、最小コストで隣接するヘクスに繰り返し移動し、必要なパス配列を構築します。任意の時点で 2 つの最適なパスがある場合、2 つの最小限のコストが隣接する 16 進数として表示されます。それぞれに対してパス配列の新しいコピーを作成し、それらを個別に完成させます。そのアプローチを取ると、パス配列の配列を操作 (および返す) ことになります。

于 2012-02-27T23:32:29.853 に答える
0

私は2つのクラスを使用しました。列と行の番号を取得した六角形のものであるCubiclesと、Cubiclesの順序付きリストであるPathsです。キュービクルには、宛先へのパス上で「正しい方向」にあるすべてのキュービクルを取得するための関数ブランチがあります。一歩を踏み出すだけで、キュービクルから直接アクセスできます。

次に、長さ1のパス（開始のみ）から開始し、このパスをすべてのブランチで着実に拡張して、ブランチごとに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 に答える