Piszę skrypt ścieżki kosztów do użytku na mapach heksagonalnych. Obecnie jestem w fazie rozwoju „nauki chodzenia”.

Ogólnie kod działa. Mogę niezawodnie dostać się z punktu A do punktu B. Jednak weź pod uwagę poniższą mapę:

enter image description here

Obie sekwencje 0406 -> 0405 -> 0505 i 0406 -> 0506 -> 0505 są prawidłowe. Chciałbym przejść i wyprowadzić OBU ścieżki.

Mój kod wygląda następująco:

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;
}

Mój pożądany wynik to tablica liczbowa step => hexCoord pokazująca obraną ścieżkę. Ale nie jestem pewien, jak zaadaptować powyższy działający kod do inteligentnego rozgałęzienia, a po wykonaniu tego, jak najlepiej ukształtować strukturę danych wyjściowych...

Z góry dziękuję.

1
Drew 23 luty 2012, 15:21

2 odpowiedzi

Najlepsza odpowiedź

Zauważyłem, że w tej chwili wybór ścieżki to po prostu „dojdź do właściwego wiersza, a następnie przejdź do właściwej kolumny”. Zdaję sobie sprawę, że nadal zaczynasz, ale możesz pomyśleć z wyprzedzeniem o tym, jak chcesz pracować na swoich ścieżkach i pozwolić, aby to opowiedziało Ci o strukturze danych.

Na przykład możesz użyć algorytmu Dijkstry, aby jak najmniejszym kosztem zaznaczyć każdy punkt na mapie z tego punktu do określonego miejsca docelowego. Znalezienie ścieżki jest wtedy kwestią wybrania punktu początkowego i wielokrotnego przemieszczania się na sąsiedni heks przy najmniejszym koszcie, budując plan ścieżek, który chcesz w trakcie podróży. Jeśli w dowolnym momencie istnieją dwie optymalne ścieżki, zobaczysz to jako szesnastkę z dwoma minimalnie tanimi sąsiadami -- utworzysz nową kopię tablicy ścieżek dla każdego i uzupełnisz je niezależnie. Przyjmując takie podejście, będziesz pracować z (i zwracać) tablicą tablic ścieżek.

1
Dan Percival 28 luty 2012, 03:32

Użyłem dwóch klas: Przedziałów, które są tymi sześciokątnymi elementami, które mają kolumnę i numer wiersza, oraz Ścieżek, które są uporządkowaną listą Przegródek. Przestrzenie mają gałąź funkcji, która pozwala pobrać wszystkie Przestrzenie, które znajdują się we „właściwym kierunku” na ścieżce do miejsca przeznaczenia. i bezpośrednio osiągalny z kabiny, wykonując tylko jeden krok.

Następnie zaczynam od ścieżki o długości 1 (tylko początek) i stopniowo rozszerzam tę ścieżkę o wszystkie gałęzie, tworząc jedną ścieżkę dla każdej gałęzi, która jest o 1 dłuższa niż stara. jeśli nie można go już rozwinąć, jesteśmy w $dest i możemy wypisać tę ścieżkę.

Mam nadzieję, że to pomoże. debugowanie zajęło trochę czasu. daj mi znać, jeśli to nie zadziała w żadnym przypadku.

<?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);
?>

Wyjścia

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

Jest to bardzo nieefektywne podejście, ponieważ jeśli masz nakładające się ścieżki, algorytm ponownie obliczy części tych ścieżek dla każdej ścieżki. jeśli chcesz dobrze działającego algorytmu, będziesz musiał stworzyć jakiś wykres, który zawiera tylko prawidłowe ścieżki i najpierw przeszukać go w celu uzyskania wszystkich możliwych ścieżek.

0
Basti 23 luty 2012, 16:22