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

Question

I have an issue in the Godot Engine that I can't figure it out: How could it be possible (in code) to fill an Polygon2D area with tiles? I have tried to get point positions. Iterate through line's vertex using 2D for loops, and I just can't wrap my head around this.

This is an mockup of the result I am expecting

Answer 1

I have solution, with a little "hacky" part, but we will get to that.

---

Iterate over the Segments of the Polygon

First, the idea is to iterate over the segments that make up the polygon. To do that, let us use an index in the range from 0 to the number of points in the polygon.

We get the point with that index and the point at index - 1 to be the ends of our segment. Note that the index -1 will give us the last point.

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

We need to work in tile map coordinates. So let us convert them, for that I'll have a custom function polygon_to_map, to which we will come back later.

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])

Then we need to get the cells that make up that segment. Again, another custom function segment will handle that. We can iterate over the cells, and set them on the tile 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])
    var cells = segment(segment_start, segment_end)
    for cell in cells:
        tile_map.set_cell(celle.x, cell.y, 0)

I'm setting tile 0, you set what makes sense for you.

---

Coordinate conversion

The tile map has a handy world_to_map function that we can use to convert, meaning we can implement our custom function polygon_to_map simply like this:

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

However, that would always return integer coordinates. As a consequence we lose information for our segment function. Instead I will implement it using cell_size:

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

---

Iterate over the Cells of the Segment

We have to define our segment function…

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

To do this, I'll use the "Fast Voxel Traversal Algorithm". Other line drawing algorithms would work, I'm fond of this one.

I often find the explanations of "Fast Voxel Traversal Algorithm" a little hard to parse, instead let us deduce it.

We want to work with the segment in parametric terms. Let us start with traversed length as parameter. If the traversed length is 0, we are at start. If the traversed length is the length of the segment, we are at end. Using the traversed length along the segment we can pick any cell along the segment.

In fact, we are defining that the points that make up the segments are of the form:

point = start + direction_of_the_segment * traversed_length

Look, everything we will be talking here is about the segment, let us call that variable simply direction, ok?

point = start + direction * traversed_length

Alright, I said we will be picking cells with traversed_length, so we will have a loop, something like this:

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

Now, the trick is to know how much we have to traverse until we reach the next integer value along the x axis, and how much until the next integer value along the y axis.

For now, let us say we have a function next2 that gives the next value along the axis, according to the direction:

var next = next2(start, direction)

We will talk about the details of next2 later.

Now, we will need to compute what is the length we need to traverse until we reach the next value. Let us use our equation form before:

point = start + direction * traversed_length

But now, the point will be the next after start, and the length is what we are looking for

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

Let us update our code (remember that we have to update length_to_next when we increment 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 = # ??

What is that div2? Ah, right, we have it because zero divided by zero. This happens when the segment is perfectly vertical or horizontal. The value we want in that case is INF, so it is never smaller and the code does not enter on that branch. To do that, you can define this:

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

Ok, we have another problem. If we traversed to the next position on x, for example, what is the length to the next position of x (And the same for y)?

Back to our equation, this time we assume start is 0:

point = start + direction * length_between

=> 

point = direction * length_between

=> 

point/direction = length_between

What should point be? Well, if we started at 0, and advanced in the direction of direction to the next integer… That point is a vector with -1, 0 or 1 on its components, according to the direction of the segment. That is the sign of the direction.

Thus, we have (we don't need div2 this time):

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

Update our code:

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

Ah, right, we should return. Let us build a result array, populate it and return it:

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

Does this work? Yes, this works. Is this "Fast Voxel Traversal Algorithm"? Not exactly. Let us call it the "Slow Voxel Traversal Algorithm" for future reference (also because from here it is mostly optimizations).

---

Let us start by keeping a current vector (this will allow us to do the next refactor):

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

In my tests, this version sometimes skips tiles.

Now, that we have current, having traversed_length is less vital. To remove it, we will accumulate length, never subtract (this way we are doing less each cycle):

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

This kind of works. Something got messed up with the rounding. See the "hacky" part.

Let us scale lengths down by length (as if our original parameter was from 0 to 1). We can also get rid of direction, and while we are at it, inline next. By doing this we don't need the square root. Also we don't need div2 anymore.

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

If you prefer a nomenclature closer to the paper "Fast Voxel Traversal Algorithm", then rename length_between to tDelta, length_to_next to tMax, and direction_sign to step. Another difference is that I'm assuming that the grid size is 1.

---

On next and the "hacky" part

We need a next2 function, it looks like this:

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

And a next function. For the "Slow Voxel Traversal Algorithm", it is like this:

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))

What is going on there? Well, if value is not integer, then ceil or floor depending on direction would suffice. However, if value is integer, we want to add or subtract 1. Written the way it is written, I don't need to check if the value is an integer.

Note, however, I said that is for "Slow Voxel Traversal Algorithm". For the "Fast Voxel Traversal Algorithm" I found experimentally that it should be:

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

    return floor(value)

And after distancing myself form the problem I found a better version:

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

I'm not sure why that is the case. However, as far as I can tell, it is because we are incrementing by direction_sign.