Build a collision polygon from tilemap outline

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By David Krause

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?

:bust_in_silhouette: Reply From: Zylann

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.

darkhog | 2018-06-27 16:30

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.

Zylann | 2018-06-27 18:52

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

darkhog | 2018-06-27 19:28

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!

David Krause | 2018-06-28 14:41

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

Zylann | 2018-06-28 18:31

:bust_in_silhouette: Reply From: David Krause

I’ve solved it after studying this: Tilemap to Collision Geometry · Issue #5 · a327ex/blog · GitHub

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 )
	

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.

Godot 3.x Generate Collision Polygons from tilemap · GitHub

enter image description here

This post goes into more detail on how it works.

(Godot Engine) Merging more than two polygons using Geometry's merge_polygons_2d() Method - Stack Overflow

afk_mario | 2023-02-07 15:09

:bust_in_silhouette: Reply From: sinistro25

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.