world_to_map() and map_to_world() are not inverse functions

[LucasCyka]

Godot version:
3.0.6

OS/device including version:
Windows 7 - 64 bits

Issue description:

I needed to do some conversions between map and world coordinates in a Tilemap, but I always get incorrect values.

Steps to reproduce:

func _ready():
	var tiles = $TileMap.get_used_cells()
	var original = Vector2(8,2) #this is tiles[0]
	var world = $TileMap.map_to_world(original) #(160, 40)
	print($TileMap.world_to_map(world)) #output: (7,1)

It should give me (8,2) again, right? But instead I get (7,1).

[akien-mga]

To be on the safe side, it's advised to add the half extents of your tile size to the map_to_world output if you want to have the position of the center of the tile, and then have a safe conversion back to world_to_map.

But yeah, in this situation I would expect that world_to_map(Vector2(160, 40)) should be able to reduce back to Vector2(8, 2).

This should be investigated in

godot/scene/2d/tile_map.cpp

Lines 1429 to 1449 in b902a2f

	Vector2 TileMap::world_to_map(const Vector2 &p_pos) const {
	Vector2 ret = get_cell_transform().affine_inverse().xform(p_pos);
	switch (half_offset) {
	case HALF_OFFSET_X: {
	if (ret.y > 0 ? int(ret.y) & 1 : (int(ret.y) - 1) & 1) {
	ret.x -= 0.5;
	}
	} break;
	case HALF_OFFSET_Y: {
	if (ret.x > 0 ? int(ret.x) & 1 : (int(ret.x) - 1) & 1) {
	ret.y -= 0.5;
	}
	} break;
	default: {}
	}
	return ret.floor();
	}

- I suspect affine_inverse might not do exactly what we want here - or maybe it's an issue of precision and the ret.floor() is the problem. CC @bojidar-bg

[akien-mga]

Fixing this would likely break compat, but I think it's an acceptable change even for 3.1, as long as we document it in release notes.

[groud]

Probably related to #2884

[bojidar-bg]

I would suspect a precision issue, affine_inverse should properly invert all commonly-found transformations just fine.
Maybe xform_inf should be tried instead of affine_inverse().xform, and .round instead of .floor.

[rxlecky]

Has anyone tested this? I ran the example code and I'm getting (8,2) back, instead of (7,1) that is the author getting.

[LucasCyka]

I have a reproduction project here:
bug.zip

[rxlecky]

Well, this is weird indeed. When running your reproduction project, I am getting yet another result - (5,2).

I won't have time to work on this issue this week, but I might be able to look into it the following week.

[LucasCyka]

Well, this is weird indeed. When running your reproduction project, I am getting yet another result - (5,2).

I won't have time to work on this issue this week, but I might be able to look into it the following week.

Sorry, I used different coordinates on the project above, but I forgot to remove the old comments

	var tiles = $TileMap.get_used_cells()
	print(tiles[0]) # output: (6, 3)
	var original = tiles[0] 
	var world = $TileMap.map_to_world(original) 
	print(world) #(120, 60)
	print($TileMap.world_to_map(world)) # output: (5, 2)

If you're getting (5, 2) this confirms the bug.
tiles[0] is (6,3), his world position is (120, 60)
making the conversion back gives (5,2), instead of (6,3).

bug.zip

[soockee]

A Friend and me are trying to look into it.
void Transform2D::affine_invert()
seems a bit suspicious at the first glance. Since we are new, we need to understands what this function wants to do and what it is actually doing.

[bojidar-bg]

I suggest trying the other options before suspecting the matrix code. The reason is that the matrix code has been tested for multiple years, unlike the tilemap code which is much newer than that.

[soockee]

ok, we'll look into the tilemap-code first. Thanks.

[soockee]

changed
return ret.floor();
to
return ret.round();

in tile_map.cpp in function world_to_map

The test inputs leading to expected results. This includes the bug-case. Pull Request incoming. Tested on Fedora and Majora by two diffrent users.

[soockee]

I think the variable idet in affine_inverse is causing the unexpected behaviour.
Try tilemap cellsize 5x5,10x10, 20x20, 40x40, 80x80, 160x160 etc. Causing rounding errors.

[akien-mga]

Continuing conversation here from #23315:

A hacky fix would be:

diff --git a/scene/2d/tile_map.cpp b/scene/2d/tile_map.cpp
index 67e25ec50..a7ac2bb98 100644
--- a/scene/2d/tile_map.cpp
+++ b/scene/2d/tile_map.cpp
@@ -1445,6 +1445,11 @@ Vector2 TileMap::world_to_map(const Vector2 &p_pos) const {
 		default: {}
 	}
 
+	// Account for precision errors on the border (GH-23250).
+	// 0.00005 is 5*CMP_EPSILON, results would start being unpredictible if
+	// cell size is > 15,000, but we can hardly have more precision anyway with
+	// floating point.
+	ret += Vector2(0.00005, 0.00005);
 	return ret.floor();
 }

But @Zylann proposes a better fix making integer calculations in pixel (world) space (thus without floating point precision errors), see #23315 (comment).

[akien-mga]

Or we could just forego the whole transform stuff and just do:

return (p_pos.x % CELL_SIZE, p_pos.y % CELL_SIZE)

I guess? (+ the offset calculations before that with floor(CELL_SIZE / 2))

[Zylann]

One use case that could be affected would be collision contacts:
typically, raycasting or hitting a tilemap made of square shapes will give contact points on the edge of the tile. Which will very likely be affected by any fix we do here, because devs then use world_to_map to get which tile was hit (although that case is already easy to get wrong).

If we apply an offset before floor(), that means this situation will always give us tile B, and working around that would involve advancing the hit position by a vector greater than the offset we added (or subtract 1 depending on the hit direction).

@akien-mga we need to use a Transform to account for scale and rotation of the tilemap.
@akien-mga hang on, I just realized it didn't account for that xD That's curious, world doesn't mean what it means then? So perhaps skipping step 1 could work, weird tho.

Another thing I thought about when reading this issue was, the fact that world_to_map and map_to_world are not inverses. If we consider just this issue, another approach would simply to return the center of the tile and not the top-left corner. But that would break compat ;p

Unfortunately even my solution of two-step transform could break compat due to the fact users can specify a custom cell transform, which has to be directly world-to-cell (at best we won't be able to do the round trick when it is active). It would work only on square tiles.

[akien-mga]

So should I just push my hack from #23250 (comment)? It should work fine as long as you don't have 16k tile sizes - which should be hopefully be safe for the near future :)