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?

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

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

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.

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.

- All categories
- Engine 30,404