（Godot 引擎）用 Tilemap 瓷砖填充 2D 多边形

2023-12-15

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

这是我期待的结果的模型

我有解决方案，有一点“hacky”部分，但我们会解决这个问题。

迭代多边形的线段

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

我们明白了这一点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)

但是，这总是返回整数坐标。结果我们就失去了我们的信息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, ok?

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 later.

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

point = start + direction * traversed_length

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

next = start + direction * length_to_next

=>

next - start = direction * length_to_next

=>

(next - start) / direction = length_to_next

Thus:

var length_to_next = (next - start)/direction

让我们更新我们的代码（记住我们必须更新length_to_next当我们增加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 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 is 0:

point = start + direction * length_between

=> 

point = direction * length_between

=> 

point/direction = length_between

点应该是什么？好吧，如果我们从 0 开始，并沿着方向前进到下一个整数……该点是一个向量-1, 0 or 1根据线段的方向，在其组件上。那就是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

啊，对了，我们该回去了。让我们构建一个结果数组，填充它并返回它：

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

如果您更喜欢更接近论文“快速体素遍历算法”的命名法，请重命名length_between to tDelta, length_to_next to tMax, and direction_sign to step。另一个区别是我假设网格大小是1.

On next和“hacky”部分

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

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

And a next功能。对于“慢体素遍历算法”来说，是这样的：

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 or floor根据direction就足够了。然而，如果value是整数，我们要加或减1。按照它的写法，我不需要检查该值是否是整数。

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

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.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Godot

GDScript