Линейный алгоритм Брешенэма в PHP

Question

Я работаю над текстовой (консольной) стратегией WW2, установленной на 2-й квадратной сетке. Я хочу, чтобы метод вычислил линию визирования от одной плитки на карте к другой. Я использовал this Java пример базировать мой код выключен, это то, что я написал:

public function plotLine($x0, $y0, $x1, $y1, $size) 
{ 
    $arr = $this->getEmptyMap($size); 
    $xDist = abs($x1 - $x0); 
    $yDist = -abs($y1 - $y0); 
    if($x0 < $x1) { 
     $xStep = 1; 
    } else { 
     $xStep = -1; 
    } 

    if($y0 < $y1) { 
     $yStep = 1; 
    } else { 
     $yStep = -1; 
    } 

    $plotError = $xDist + $yDist; 

    $arr[$x0][$y0] = 1; 

    while($x0 != $x1 || $y0 != $y1) { 
     // if(2 * $plotError > $yDist) { 
     // // Horizontal step 
     // $plotError += $yDist; 
     // $x0 += $xStep; 
     // } 

     // if(2 * $plotError < $xDist) { 
     // // Vertical step 
     // $plotError += $xDist; 
     // $y0 += $yStep; 
     // } 

     if(2 * $plotError - $yDist > $xDist - 2 * $plotError) { 
      // Horizontal step 
      $plotError += $yDist; 
      $x0 += $xStep; 
     } else { 
      // Vertical step 
      $plotError += $xDist; 
      $y0 += $yStep; 
     }   


     $arr[$x0][$y0] = 1; 
    } 

    $this->line = $arr; 
} 

Примечание: getEmptyMap просто заполняет многомерный массив с 0-х.

TestResult используя (0, 0, 4, 4, 4) в качестве входных данных:

1100 
0110 
0011 
0001 

Я попытался способы отображения линии: одна нормальная реализация, которая используется Franz D. (в настоящее время прокомментирован в моем примере выше), другая - модифицированная реализация, показанная Францем Д.. И я не даю мне результата, который я ищу; своего рода «сглаживание». Когда припой будет смотреть от 0,0 до 2,2, и будут здания на 1,2 и 2,1, все, что должно быть в 2,2, должно быть заблокировано из виду. Замеченная реализация полностью игнорирует здания, модификация «поражает» 2,1, но не 1,2. Как мне настроить мой код на «удар» как под линией, так и над линией?

Answer 1

«Проблема», с которой вы сталкиваетесь, происходит из-за особого края, когда вы смотрите на точную диагональ. Имеются «только» две (простые) возможности обращения с этим:

1) Диагональ одновременно увеличивает горизонтальную и вертикальную плитки. В вашей игре это означало бы, что юниты смогут смотреть на диагонали, даже если основные направления будут заблокированы.

2) Выберите между присвоением приоритета горизонтальным плиткам или вертикальным плиткам и только приращение одного из двух. Это алгоритм Франца Д., который вы написали и разместили в своем посте. Здесь if -statement верно для диагоналей, что означает, что результат будет:

1100 
0110 
0011 
0001 

Если вы хотите вертикалей иметь преимущество, вы можете изменить его:

... 
     if(2 * $plotError - $yDist < $xDist - 2 * $plotError) { 
      // Vertical step 
      $plotError += $xDist; 
      $y0 += $yStep; 
     } else { 
      // Horizontal step 
      $plotError += $yDist; 
      $x0 += $xStep; 
     } 

... 

Обратите внимание, что оба тела if/else заменяются, а > был изменен на < в состоянии.

Теперь, результат будет:

1000 
1100 
0110 
0011 

Если вы хотите блок, чтобы только быть в состоянии смотреть на диагонали, если нет ничего блокировки либо из соседних кардиналов, самое простое решение было бы использовать оба из вышеперечисленных вариантов алгоритма, и объединить их результаты в один массив плиток.

Последнее замечание: если вас интересуют только координаты, а не их значения (как, например, в случае используемого вами варианта использования), может быть больше (памяти) эффективно использовать простой массив извлек (x, y) координаты вместо двумерного массива полной карты, которую вы потом завершите, чтобы извлечь все координаты (x, y), где результат равен 1.

Удачи вам в игре!