+1 vote

I want to programmatically build a collision shape/polygon (for a rigidbody) from the outline of a tilemap.
Does one have a good solution to do that?

example image

in Engine by (107 points)

3 Answers

0 votes
Best answer

I've solved it after studying this: https://github.com/SSYGEN/blog/issues/5

extends Node2D

# https://github.com/SSYGEN/blog/issues/5
var edges = []

var grid = [
    [0,0,0,0,0,0],
    [0,1,1,1,1,1],
    [0,1,1,1,1,1,1,1,1,1,1],
    [0,1,1,1,1,1],
    [0,1,1,1,1,1,1],
    [0,1,1,1,1,1],
]

func getPoints(x, y, cellSize):
    #1   2
    #  
    #0   3  
    return [
        Vector2(x * cellSize.x, y * cellSize.y + cellSize.y), # 0
        Vector2(x * cellSize.x, y * cellSize.y), # 1
        Vector2(x * cellSize.x + cellSize.x, y * cellSize.y), # 2
        Vector2(x * cellSize.x + cellSize.x, y * cellSize.y + cellSize.y) # 3
    ]

func getLines(points):
    return [
        [points[0], points[1]],
        [points[1], points[2]],
        [points[2], points[3]],
        [points[3], points[0]]
    ]

func createEdges(grid, cellSize = Vector2(48, 48)):
    var edges = []
    for y in range(grid.size()):
        for x in range(grid[y].size()):
            var tile = grid[y][x]
            if tile == 1:
                for line in getLines(getPoints(x, y, cellSize)):
                    edges.append(line)
    return edges

func deleteEdges(edges):
#   print(edges.size())
#   print("EDGES 1:", edges)
    var markForDeletion = []
    for currentLineIdx in range(edges.size()):
        var currentLine = edges[currentLineIdx]
        var currentLineInverted = [currentLine[1], currentLine[0]]
        for lineIdx in range(edges.size()):
            var line = edges[lineIdx]
            if lineIdx == currentLineIdx: continue # skip ourself
            if currentLine == line or currentLineInverted == line:
                markForDeletion.append(currentLine)
                markForDeletion.append(currentLineInverted)
    for line in markForDeletion:
        var idx = edges.find(line)
        if idx >= 0: 
            edges.remove(idx)
#   print(edges.size())     
    return edges


func toShape(edges):
    var result = []
    var nextLine = edges[0] 
    for idx in range(edges.size()):
#       # find the "next" point
        for otherLine in edges:
            if otherLine == nextLine: continue
            if nextLine[1] == otherLine[0]:
                print("the next line should be:", otherLine)
                nextLine = otherLine
                break
            elif nextLine[1] == otherLine[1]:
                print("next line is reversed:", otherLine)
                nextLine = [otherLine[1], otherLine[0]]
        for point in nextLine:
            result.append(point)

    return result

func _ready():
    # Called when the node is added to the scene for the first time.
    # Initialization here.
    update()

func _draw():
    var edges = createEdges(grid)
    var cleanedEdges = deleteEdges(edges)
    var shape = toShape(cleanedEdges)
    var colors = PoolColorArray()
    for p in shape:
        colors.append(Color(1,1,1))
    print(edges)
    print(shape)
    var toDraw = PoolVector2Array(shape)
    print(toDraw)
    draw_multiline(toDraw, Color(1,1,1) )
    draw_polygon(toDraw, colors )
by (107 points)
+1 vote

One idea would be:
You can pick any border wall in the map, pick a direction along that wall and remember on which side the "empty" tiles are. Then walk along it, keeping the "empty" tiles on the same side and choose directions to follow until you get back to your original position.
As you do this, your algorithm can plot points of the polygon, and build the shape from it.

Why are you making this shape btw? Why not just surround the map with invisible collision tiles? (I've been doing that in a prototype).

Also, I'm not sure if rigidbodies support concave shapes.

by (28,972 points)

While I'm not the poster, one reason would be procedural game or game with a level editor that's not Godot. In both cases you'd need to build the tilemap and collisions yourself.

What I don't understand is why one would want a collision shape for a rigidbody that matches the entire tilemap area. Such a body won't be able to do much, also tiles can provide collision already.

Maybe it's for a ship building system? Think Pixel Piracy or FTL? In this case, it would be useful.

Zylan, as far as i understand it, your proposal does not work if there is connection with a single tile.

Exactly its for a ship building system!

It actually works if you take direction into account, you have to follow the edge, not the tile :)

0 votes

Hey I had to solve this problem recently. If your collisions polygons from each tile form a planar graph, that is, they don't self-intersect outside of shared vertices and edges, then the outline is formed by edges that appear only one time. You can then calculate the outline linearly on the number of edges by counting the number of times they appear and keeping only the ones that appear once.

This greatly reduces the number of collisions shapes on the map.

by (70 points)
Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read Frequently asked questions and How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to [email protected] with your username.