Алгоритм линии Брезенхема в PHP

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

1100
0110
0011
0001

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


php oop multidimensional-array algorithm bresenham
person Somentus    schedule 20.11.2016    source источник
comment
если вы считаете, что этот алгоритм лучше всего подходит для вашей задачи, почему бы не попробовать его сначала, если вы еще не использовали PHP, сначала изучите инструмент, а затем портируйте алгоритм в версии PHP   -  person Kevin    schedule 21.11.2016
comment
Я попробовал и разработал реализацию, но все еще сталкиваюсь с проблемой (см. редактирование в сообщении)   -  person Somentus    schedule 21.11.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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.

Удачи в игре!

person Qqwy    schedule 21.11.2016