распознавание и использование 2 допустимых путей при ходьбе по гексагональной карте

Question

Я пишу сценарий пути затрат для использования на гексагональных картах. В настоящее время я участвую в «обучении, как идти», этап развития.

В общих чертах код работает. Я могу надежно получить от А до В. Однако, рассмотрим следующую карту:

И последовательность 0406 -> 0405 -> 0505 и 0406 -> 0506 -> 0505 действительны. Я хотел бы пересекать и выводить BOTH пути.

Мой код следующим образом:

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's algorithm, чтобы отметить каждую точку на карте с наименьшей стоимостью от этой точки до заданного места назначения. Поиск пути - это вопрос выбора источника и многократного перехода в соседний гексагон с наименьшей стоимостью, создавая массив путей, который вы хотите, когда идете. Если в любой точке есть два оптимальных пути, вы увидите, что в качестве шестнадцатеричного кода с двумя минимально дешевыми соседями вы создадите новую копию массива путей для каждого и завершите их самостоятельно. Используя этот подход, вы будете работать с (и возвращать) массив массивов путей.

Answer 2

Я использовал два класса: кубические элементы, которые являются шестнадцатиричными вещами, которые получили столбец и номер строки, а также пути, которые являются упорядоченным списком кубов. У кубиков есть ветвь функции, чтобы получить все 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 

это очень неэффективный подход, потому что если у вас есть пересекающиеся пути, алгоритм перерасчета части этих путей для каждого пути. если вам нужен хорошо выполняющийся алгоритм, вам нужно будет создать какой-то график, который содержит только допустимые пути и поиск по глубине сначала для вывода всех возможных путей.