php - PHP 中的 Bresenham 直线算法

Question

我正在开发基于文本的(控制台)WW2 战略游戏，设置在二维方形网格 map 上。我想要一种方法来计算从 map 上的一个图 block 到另一个图 block 的视线。我用过 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 填充一个多维数组。

使用 (0, 0, 4, 4, 4) 作为输入的测试结果:

1100
0110
0011
0001

我已经尝试过映射线的方法:一种是 Franz D. 使用的正常实现(目前在我上面的示例中已注释掉)，另一种是 Franz D. 展示的修改后的实现。也没有给我想要的结果；一种“抗锯齿”。当焊料从 0,0 看 2,2 并且在 1,2 和 2,1 有建筑物时，2,2 处的任何东西都应该被挡住。注释掉的实现将完全忽略建筑物，修改确实“命中”2,1 但不是 1,2。我将如何调整我的代码以“命中”在线下方和在线上方？

Answer 1

您面临的“问题”是由于查看精确对角线时的特殊边缘情况而发生的。处理这个问题“只有”两种(简单的)可能性:

1) 对角线同时增加水平和垂直的瓦片。在您的游戏中，这意味着单位将能够看到对角线，即使主要方向会被阻挡。

2) 在优先考虑水平方 block 或垂直方 block 以及只递增两者之一之间进行选择。这是 Franz D. 的算法，您最终编写并放置在您的帖子中。在这里，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)坐标而不是完整 map 的二维数组，您随后循环以提取所有 (x, y)结果为 1 的坐标.

祝游戏好运!