Линейный алгоритм Брезенхэма в переполнении стека

Question

Линейный алгоритм Брезенхэма в переполнении стека

Я работаю над текстовой (консольной) стратегической игрой WW2, основанной на 2-мерной квадратной сетке. Я хочу, чтобы метод для расчета линии видимости от одной плитки на карте к другой. Я использовал этот Пример 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, 0, 4, 4, 4) в качестве входных данных:

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

1

algorithm bresenham multidimensional-array oop php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

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

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

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

...

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

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

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

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

Удачи в игре!

1