（Godot 引擎）用 Tilemap 瓦片填充 2D 多边形

Question

我在 Godot 引擎中遇到了一个我无法解决的问题：怎么可能（在代码中）用瓷砖填充 Polygon2D 区域？我试图获得点位置。使用 2D for 循环遍历线的顶点，我就是无法解决这个问题。

这是我期待的结果模型

Answer 1

我有解决方案，但有一点“hacky”部分，但我们会解决的。

遍历多边形的各个部分

首先，我们的想法是迭代构成多边形的线段。为此，让我们使用范围从 0 到多边形中点数的 index。

我们得到 index 的点和 index - 1 的点是我们线段的终点。 请注意，索引 -1 将为我们提供最后一点。

for index in range(0, polygon.polygon.size()):
    var segment_start = polygon.polygon[index - 1]
    var segment_end = polygon.polygon[index]

我们需要在瓦片地图坐标中工作。所以让我们转换它们，为此我将有一个自定义函数 polygon_to_map，我们稍后会回来。

for index in range(0, polygon.polygon.size()):
    var segment_start = polygon_to_map(polygon.polygon[index - 1])
    var segment_end = polygon_to_map(polygon.polygon[index])

然后我们需要获取构成该片段的单元格。同样，另一个自定义函数 segment 将处理该问题。我们可以迭代单元格，并将它们设置在瓦片地图上：

for index in range(0, polygon.polygon.size()):
    var segment_start = polygon_to_map(polygon.polygon[index - 1])
    var segment_end = polygon_to_map(polygon.polygon[index])
    var cells = segment(segment_start, segment_end)
    for cell in cells:
        tile_map.set_cell(celle.x, cell.y, 0)

我在设置磁贴0，你设置对你有意义的。

坐标转换

瓦片地图有一个方便的 world_to_map 函数，我们可以用它来转换，这意味着我们可以像这样简单地实现我们的自定义函数 polygon_to_map：

func polygon_to_map(vector:Vector2) -> Vector2:
    return tile_map.world_to_map(vector)

但是，那总是 return 整数坐标。结果，我们丢失了 segment 函数的信息。相反，我将使用 cell_size:

来实现它

func polygon_to_map(vector:Vector2) -> Vector2:
    return vector/tile_map.cell_size

迭代段的单元格

我们必须定义我们的 segment 函数…

func segment(start:Vector2, end:Vector2) -> Array:
    # ???

为此，我将使用“快速体素遍历算法”。 其他画线算法也可以，我喜欢这个。

我经常觉得“快速体素遍历算法”的解释有点难以解析，而是让我们推导它。

我们想以参数化的方式处理片段。让我们从遍历长度作为参数开始。如果遍历的长度是0，我们在start。如果遍历的长度是段的长度，我们就在end。使用沿线段的遍历长度，我们可以选择沿线段的任何单元格。

事实上，我们正在定义构成线段的点的形式：

point = start + direction_of_the_segment * traversed_length

看，我们这里要讨论的都是段，让我们简单地称这个变量为direction，好吗？

point = start + direction * traversed_length

好吧，我说过我们将使用 traversed_length 选取单元格，所以我们将有一个循环，如下所示：

func segment(start:Vector2, end:Vector2) -> Array:
    var length = start.distance_to(end)     # (end - start).length()
    var direction = start.direction_to(end) # (end - start).normalized()
    var traversed_length = 0
    while traversed_length < length:
        var cell = start + direction * traversed_length
        # something that increments traversed_length and other stuff

现在，诀窍是要知道在到达 x 轴上的下一个整数值之前我们必须遍历多少，以及在 y 轴上到达下一个整数值之前需要遍历多少。

现在，假设我们有一个函数 next2，它根据方向给出沿轴的下一个值：

var next = next2(start, direction)

next2的细节我们稍后再说

现在，我们需要计算到达下一个值之前需要遍历的长度。让我们使用之前的方程式：

point = start + direction * traversed_length

但是现在，点将是开始后的下一个，长度就是我们要找的

next = start + direction * length_to_next

=>

next - start = direction * length_to_next

=>

(next - start) / direction = length_to_next

因此：

var length_to_next = (next - start)/direction

让我们更新我们的代码（记住当我们递增 traversed_length 时我们必须更新 length_to_next）：

func segment(start:Vector2, end:Vector2) -> Array:
    var length = start.distance_to(end)     # (end - start).length()
    var direction = start.direction_to(end) # (end - start).normalized()
    var next = next2(start, direction)
    var length_to_next = div2(next - start, direction)
    var traversed_length = 0
    while traversed_length < length:
        var cell = start + direction * traversed_length
        if length_to_next.x < length_to_next.y:
            traversed_length += length_to_next.x
            length_to_next.x = # ??
            length_to_next.y -= length_to_next.x
        else:
            traversed_length += length_to_next.y
            length_to_next.x -= length_to_next.y
            length_to_next.y = # ??

那是什么div2？啊，对，我们有它是因为零除以零。当线段完全垂直或水平时会发生这种情况。在这种情况下，我们想要的值是 INF，因此它永远不会更小，并且代码不会进入该分支。为此，您可以这样定义：

func div2(numerator:Vector2, denominator:Vector2) -> Vector2:
    return Vector2(div(numerator.x, denominator.x), div(numerator.y, denominator.y))

func div(numerator:float, denominator:float) -> float:
    return numerator / denominator if denominator != 0 else INF

好的，我们还有一个问题。如果我们遍历到x上的下一个位置，例如，到x的下一个位置的长度是多少（y也一样）？

回到我们的等式，这次我们假设 start 是 0:

point = start + direction * length_between

=> 

point = direction * length_between

=> 

point/direction = length_between

点应该是什么？好吧，如果我们从 0 开始，沿着 direction 的方向前进到下一个整数……根据段的方向。即sign的方向

因此，我们有（这次不需要div2）：

var direction_sign = direction.sign()
var length_between = direction_sign/direction

更新我们的代码：

func segment(start:Vector2, end:Vector2) -> Array:
    var length = start.distance_to(end)     # (end - start).length()
    var direction = start.direction_to(end) # (end - start).normalized()
    var direction_sign = direction.sign()
    var next = next2(start, direction)
    var length_to_next = div2(next - start, direction)
    var length_between = direction_sign/direction
    var traversed_length = 0
    while traversed_length < length:
        var cell = start + direction * traversed_length
        if length_to_next.x < length_to_next.y:
            traversed_length += length_to_next.x
            length_to_next.x = length_between.x
            length_to_next.y -= length_to_next.x
        else:
            traversed_length += length_to_next.y
            length_to_next.x -= length_to_next.y
            length_to_next.y = length_between.y

啊，对，应该return。让我们构建一个结果数组，填充它并 return 它：

func segment(start:Vector2, end:Vector2) -> Array:
    var length = start.distance_to(end)     # (end - start).length()
    var direction = start.direction_to(end) # (end - start).normalized()
    var direction_sign = direction.sign()
    var next = next2(start, direction)
    var length_to_next = div2(next - start, direction)
    var length_between = direction_sign/direction
    var traversed_length = 0
    var result = []
    result.append(start)
    while traversed_length < length:
        if length_to_next.x < length_to_next.y:
            traversed_length += length_to_next.x
            length_to_next.x = length_between.x
            length_to_next.y -= length_to_next.x
        else:
            traversed_length += length_to_next.y
            length_to_next.x -= length_to_next.y
            length_to_next.y = length_between.y
        result.append(start + direction * traversed_length)
    return result

这个有用吗？是的，这有效。这是“快速体素遍历算法”吗？不完全是。让我们称它为“慢体素遍历算法”以供将来参考（也是因为从这里开始它是 mostly 优化）。

让我们从保留一个 current 向量开始（这将允许我们进行下一次重构）：

func segment(start:Vector2, end:Vector2) -> Array:
    var length = start.distance_to(end)     # (end - start).length()
    var direction = start.direction_to(end) # (end - start).normalized()
    var direction_sign = direction.sign()
    var next = next2(start, direction)
    var length_to_next = div2(next - start, direction)
    var length_between = direction_sign/direction
    var traversed_length = 0
    var result = []
    var current = start
    while traversed_length < length:
        if length_to_next.x < length_to_next.y:
            current += direction * length_to_next.x
            traversed_length += length_to_next.x
            length_to_next.x = length_between.x
            length_to_next.y -= length_to_next.x
        else:
            current += direction * length_to_next.y
            traversed_length += length_to_next.y
            length_to_next.x -= length_to_next.y
            length_to_next.y = length_between.y
        result.append(current)
    return result

在我的测试中，这个版本有时会跳格。

现在，我们有 current，traversed_length 就没那么重要了。要删除它，我们将累加长度，而不是减去（这样我们每个循环都做的更少）：

func segment(start:Vector2, end:Vector2) -> Array:
    var length = start.distance_to(end)     # (end - start).length()
    var direction = start.direction_to(end) # (end - start).normalized()
    var direction_sign = direction.sign()
    var next = next2(start, direction)
    var length_to_next = div2(next - start, direction)
    var length_between = direction_sign/direction
    var result = []
    var current = start
    result.append(current)
    while length_to_next.x < length or length_to_next.y < length:
        if length_to_next.x < length_to_next.y:
            current.x += direction_sign.x
            length_to_next.x += length_between.x
        else:
            current.y += direction_sign.y
            length_to_next.y += length_between.y
        result.append(current)
    return result

这种作品。四舍五入搞砸了。请参阅“hacky”部分。

让我们将长度缩小 length（就好像我们的原始参数是从 0 到 1）。我们也可以去掉 direction，并在此期间内联 next。通过这样做，我们不需要平方根。我们也不再需要 div2。

func segment(start:Vector2, end:Vector2) -> Array:
    var difference = end - start
    var direction_sign = difference.sign()
    var length_to_next = (next2(start, direction_sign) - start)/difference
    var length_between = direction_sign/difference
    var result = []
    var current = start
    result.append(current)
    while length_to_next.x < 1 or length_to_next.y < 1:
        if length_to_next.x < length_to_next.y:
            current.x += direction_sign.x
            length_to_next.x += length_between.x
        else:
            current.y += direction_sign.y
            length_to_next.y += length_between.y
        result.append(current)
    return result

如果您更喜欢更接近论文“Fast Voxel Traversal Algorithm”的命名法，则将length_between重命名为tDelta，length_to_next重命名为tMax，以及 direction_sign 到 step。另一个区别是我假设网格大小是 1.

关于 next 和“hacky”部分

我们需要一个next2函数，它看起来像这样：

func next2(vector:Vector2, direction:Vector2) -> Vector2:
    return Vector2(next(vector.x, direction.x), next(vector.y, direction.y))

还有一个next函数。对于“Slow Voxel Traversal Algorithm”，是这样的：

func next(value:float, direction:float) -> float:
    if direction > 0:
        return max(ceil(value), floor(value + 1.0))

    return min(floor(value), ceil(value - 1.0))

那里发生了什么事？好吧，如果 value 不是整数，那么 ceil 或 floor 取决于 direction 就足够了。但是，如果 value 是整数，我们要加或减 1。这么写就不用我去检查value是不是整数了

但是请注意，我说的是“慢体素遍历算法”。对于“快速体素遍历算法”我通过实验发现应该是：

func next(value:float, direction:float) -> float:
    if direction > 0:
        return max(ceil(value), floor(value + 1.0))

    return floor(value)

在远离问题之后，我找到了一个更好的版本：

func next(value:float, direction:float) -> float:
    return floor(value) + clamp(sign(direction), 0, 1)

我不确定为什么会这样。然而，据我所知，这是因为我们增加了 direction_sign.

（Godot 引擎）用 Tilemap 瓦片填充 2D 多边形

(Godot Engine) Fill an 2D Polygon with Tilemap tiles

gdscript

godot

遍历多边形的各个部分

迭代段的单元格