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

in Engine

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

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

This was a huge help!

Ended up implementing it using the Geometry class to support multiple polygons and I think even holes are generated correctly.

https://gist.github.com/afk-mario/15b5855ccce145516d1b458acfe29a28

This post goes into more detail on how it works.

https://stackoverflow.com/questions/67412060/godot-engine-merging-more-than-two-polygons-using-geometrys-merge-polygons-2d

+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 (29,360 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 :)