Physics bodies can collide with tile seams

[KoBeWi]

Tested versions

4.3 dev4 and earlier

System information

Windows 10.0.19045 - Vulkan (Forward+) - dedicated NVIDIA GeForce GTX 1060 (NVIDIA; 31.0.15.4633) - Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz (8 Threads)

Issue description

There is an issue with TileMap where a body can sometimes detect a wall collision on a completely flat surface. This causes bugs like projectile bouncing backwards instead of being reflected or characters turning at random point as if they hit something. Unfortunately the bug is very random - it depends on body shape, position and movement velocity. Sometimes I can reproduce it reliably in one very specific spot, but some time later it can fix itself and happen elsewhere.

Since it's so random, I didn't report it until now, because I though the issue is fixed multiple times. Apparently it's not and I just have another of these "reliable" cases.

Bug in action. Notice how the orange enemy turns for no reason, while the other enemy (which has a different shape) walks normally:

https://github.com/godotengine/godot/assets/2223172/edea97f4-b459-41f1-a118-baf0804ce943

Here I replaced the TileMap with a flat StaticBody2D and moved the TileMap below:

https://github.com/godotengine/godot/assets/2223172/a82c8e8a-7149-416a-a76b-d264132fe569

I suspect that it's caused by the fact that the TileMap is composed of multiple collision shapes and due to some physics glitches it's possible to hit corner of a tile. Related to #84163 and I assume solution would be merging the tiles into polygons (AFAIK navigation already does that).

Steps to reproduce

1. Use TileMap
2. It might happen

Minimal reproduction project (MRP)

The bug is too random to create a reliable MRP.

[smix8]

Ghost collision is a thing in all physics engines and always caused by using bad shape layouts.

Other physics engines already lost their teeth on this topic and ended up doing sub-optimal workarounds or not bothering at all.

Box2D and its extra "ghost vertices" definition "fix" that only works with one-sided surfaces. https://box2d.org/posts/2020/06/ghost-collisions/. Jolt physics giving you a friendly "good luck my naive friend". https://jrouwe.github.io/JoltPhysics/ (search for "Ghost Collisions" header line) Havok Physics giving you a "welding" option, which means "bye, bye performance" option. https://docs.unity3d.com/Packages/com.havok.physics@1.0/manual/collision-detection.html

There is a practical reason why all those legacy pixel games did not use physics polygons per cell like the TileMap does and instead used a simplified collision bit mask per grid cell.

[BrentonWildes]

Ghost collision is a thing in all physics engines and always caused by using bad shape layouts.

Other physics engines already lost their teeth on this topic and ended up doing sub-optimal workarounds or not bothering at all.

Box2D and its extra "ghost vertices" definition "fix" that only works with one-sided surfaces. https://box2d.org/posts/2020/06/ghost-collisions/. Jolt physics giving you a friendly "good luck my naive friend". https://jrouwe.github.io/JoltPhysics/ (search for "Ghost Collisions" header line) Havok Physics giving you a "welding" option, which means "bye, bye performance" option. https://docs.unity3d.com/Packages/com.havok.physics@1.0/manual/collision-detection.html

There is a practical reason why all those legacy pixel games did not use physics polygons per cell like the TileMap does and instead used a simplified collision bit mask per grid cell.

This also is and has been problematic for Gridmap in G4 3D, but wasn't present in G3. My shapes and setups between my two projects are identical, but G4 struggles with very very basic collision tasks (sliding along a wall cuts your movement speed; approaching a corner shoots you into the stratosphere).

[KoBeWi]

@smix8 I remember you once mentioned that navigation already merges the tile polygons into bigger ones. I think that's the solution, as merged polygons don't have seams, and using one big polygon is more performant than using hundreds of small shapes.

I did a quick test in GDScript and generating super polygon(s) for a TileMap with thousands of tiles takes 1 second (though the generator uses single layer for now):

https://github.com/godotengine/godot/assets/2223172/d7c0298f-7e09-4171-83f6-5236c30f9f72

I think doing it in C++ automatically for each layer would be very feasible. Though I imagine there are countless edge cases where invalid polygons could be generated.

EDIT: I integrated it in the game (I bake polygons in editor when saving scene and in game I just make static bodies instead of tilemap colliders). As expected, the bug mentioned in this issue is gone and it also fixes #84163 So I guess it's a viable workaround until the problem is resolved on the engine side.

The merging script if anyone is interested

```GDScript @tool extends RefCounted const neighs := [TileSet.CELL_NEIGHBOR_RIGHT_SIDE, TileSet.CELL_NEIGHBOR_BOTTOM_SIDE, TileSet.CELL_NEIGHBOR_LEFT_SIDE, TileSet.CELL_NEIGHBOR_TOP_SIDE] var tile_map: TileMap var layer: int var tile_data: TileData var map: Dictionary#[Vector2i, bool] var polygons: Array[PackedVector2Array] func make(): for cell in tile_map.get_used_cells(layer): if not is_valid_cell(cell): continue flood(cell) func is_valid_cell(cell: Vector2i) -> bool: if map.get(cell): return false tile_data = tile_map.get_cell_tile_data(layer, cell) if not tile_data or tile_data.get_collision_polygons_count(0) == 0: return false return true func flood(base: Vector2i): var polygon: PackedVector2Array var to_merge: Array[Vector2i] to_merge.append(base) while not to_merge.is_empty(): var cell: Vector2i = to_merge.pop_back() tile_data = tile_map.get_cell_tile_data(layer, cell) var poly := tile_data.get_collision_polygon_points(0, 0) var off := (Vector2(cell) + Vector2.ONE * 0.5) * Vector2(tile_map.tile_set.tile_size) for i in poly.size(): poly[i] = poly[i] + off if polygon.is_empty(): polygon = poly else: polygon = Geometry2D.merge_polygons(polygon, poly).front() map[cell] = true for i in neighs: var cell2 := tile_map.get_neighbor_cell(cell, i) if map.get(cell2): continue if not is_valid_cell(cell2): continue to_merge.append(cell2) polygons.append(polygon) ``` Usage: ```GDScript var polygon_merger = load("the above script.gd").new() polygon_merger.tile_map = $TileMap polygon_merger.layer = 0 polygon_merger.make() var polygons = polygon_merger.polygons ```

[markopolojorgensen]

IIRC, the 2D variety of this behavior has been around since at least the 2.x days; this issue may be a duplicate of https://github.com/godotengine/godot/issues/72372 (and https://github.com/godotengine/godot/issues/47148 and others). Another tilemap baker tool is at https://github.com/popcar2/GodotTilemapBaker

I forget where I first learned of another workaround for 2D metroidvanias/sidescrollers with gravity: you can use two CollisionShape2Ds - one for the "real" shape, and another just for a SeparationRayShape2D.

[smix8]

@KoBeWi Yes as mentioned in the other issue removing the tile-factor from the TileMap, how silly it may sound, is the solution to most of the TileMap performance and quality problems. At least it should move to using larger update units instead of just single cells.

The NavigationRegion2D merges TileMapLayer0 navigation polygons and collision shapes together when baked. The TileMap itself does not for its build-in navigation.

Yes there are many edge cases with polygon merging because as soon as overlap is caused it triggers hole calculation. The more complex a layout (e.g. polygon "holes") the more chances that an outline is interpreted wrong and flips the entire polygon outline stack in the wrong direction. If you only append a polygon neighbor one by one that risk is minimized. If you start to stack other layers on top with maybe collision "holes" things can get ugly very quickly.

I also discussed this multiple times with groud and I think the biggest hurdle (at least from my view) is creating a user interface to control all this bake and update behavior. Every user uses the TileMap layers differently and has different shapes in use. Also as soon as you start merging things to larger units you also make small tile runtime changes more difficult and costly.

[KoBeWi]

Well my script merges neighboring tiles using flood fill and it's fast enough (even in GDScript). I think each layer could have a separate body with polygons (with them being separate nodes it's the only way now), and we could also make separate bodies for physics layers. The problem are tiles with multiple polygons. You can't merge them using my naive method, because it assumes every next tile polygon will be adjacent to the previous one (which works for my use-case, but it's not sufficient).

Is the NavigationRegion2D any more smart?

[smix8]

Is the NavigationRegion2D any more smart?

The navigation mesh baking collects all the outlines and merges them together in a single operation before doing the same for collision shapes and then intersecting both. It uses the Clipper2 polytree for the result that can deal with polygon holes and nesting because it keeps an entire tree with the parent-child outline relations.

If you only add one polygon after another and the polygons have holes you will run into many issues that is why the navigation mesh baking does it all at once. This can not be done with the Geometry2D class as it has only the single polygon functions exposed. It also uses the old Clipper1 lib that is slower and less robust. Reminds me that the Geometry2D bool op functions should be upgrade at some point to use Clipper2.