Auto-generate collision polygon 2D

[baylorw]

Godot Version

4.3rc3

Question

i have a tile based game where range is in tiles. The overall shape is circularish, not square.

i want to avoid manually building a CollisionPolygon2D for every possible range (~50). Anyone know a clever way to do this?

More details: When the enemy enters the poly they are added to the potential targets list. When they exit they are removed. i could generate dozens of Area2Ds but that feels inefficient and i worry that about race conditions between exiting one and entering the next.

[snipercup]

Are these poly’s mobile? Or static? That may change the equation somewhat

You can create a new PackedVector2Array — Godot Engine (stable) documentation in English and use it’s append array method to add each point in the poly no matter it’s range.

You can then set the packedvector2Array to your CollisionPolygon2D — Godot Engine (stable) documentation in English

But I’m wondering if there’s an alternative:

• create a circleshape at the center and use that to detect if the player enters it. This will lead to inaccurate results, which is why:
• When the player is in the circle, check if the player is in any of the tiles if you know their position

It really depends on what your specific need is.

[ThreadAndSandpaper]

Take a look at the Geometry2D page in the docs. “merge_polygons” lets you to add a bunch of small individual polygons together to make a big one, or “clip_polygons” lets you trim a larger one. My experience is that merge gives you messy polygons that might not be valid while clip gives nice clean shapes, but I may just be feeding the numbers in wrong.

[baylorw]

Overlay a circle to determine if it’s worth doing the more expensive calculation, kind of like how they use quadtrees to detect collisions. That’s pretty creative. That might give the desired result.

[baylorw]

Jane, merge_polygons() took me most of a day to get working (that “it returns an array” thing killed me) but it works now! It’s not even a little efficient (merging all polies one at a time is probably slow and then it takes > 40 iterations of that to get half a screen) but it’s faster than a player can tell (since it’s only done once, not every frame) so it’s good enough.

Here’s the code i ended up with:

# covered_tiles_relative = Vector2i of tile positions in map coordinates
func create_tile_range_polygon():
	if covered_tiles_relative.is_empty():
		return
		
	var tiles_to_merge := covered_tiles_relative.keys().duplicate()
	var collision_poly := PackedVector2Array(get_tile_poly(Vector2i(0,0)))
	
	var i := 0
	var max_attempts := 100   # empirically, 40 covers most but not all of the screen
	while !tiles_to_merge.is_empty() and (i < max_attempts):
		collision_poly = merge_poly_array_to(collision_poly, tiles_to_merge)
		i = i+1
	if !tiles_to_merge.is_empty():
		printerr("Failed to merge in all the tiles. attempts=" + str(i))
	
	%RangeColliderTile.polygon = collision_poly

func merge_poly_array_to(merged_set : PackedVector2Array, tiles_to_merge: Array) -> PackedVector2Array:
	for coord_map in tiles_to_merge:
		var tile_poly = get_tile_poly(coord_map)
		var merge_results = Geometry2D.merge_polygons(merged_set, tile_poly)
		if 1 == merge_results.size():
			merged_set = merge_results[0]
			tiles_to_merge.erase(coord_map)
	return merged_set

func get_tile_poly(coord_map: Vector2i) -> PackedVector2Array:
	#--- Move from center of tile to top left corner.
	var offset := Vector2i(tile_width/2, tile_width/2)
	var tl = Vector2i(coord_map.x,   coord_map.y)   * tile_width - offset
	var tr = Vector2i(coord_map.x+1, coord_map.y)   * tile_width - offset
	var br = Vector2i(coord_map.x+1, coord_map.y+1) * tile_width - offset
	var bl = Vector2i(coord_map.x,   coord_map.y+1) * tile_width - offset
	
	var tile_vertices := PackedVector2Array([tl, tr, br, bl])
	return tile_vertices

The results are what i want:

i am on my way to becoming a millionaire!!!

(Pretty sure dynamic range collision polygon calculation was the only thing standing between me and a luxury yacht)

[ThreadAndSandpaper]

I’m not sure about your use case, but if you are reusing certain shapes over and over you could save the polygon arrays to a custom resource using a @tool script… Then you could swap those and save calculating at runtime for shapes that are context sensitive.

But also, I wouldn’t worry about the performance on this. This is what computers are really good at, after all. Especially if it’s only happening sporadically, not every frame.