Greatly improve Y-sort performance on TileMaps

[groud]

This greatly improves the performance of TileMaps that are Y-sorted (basically any isometric game). On a relatively large map, the default quadrant size went from 60 fps to 800fps, so more than 10 times more frames!

This PR basically makes it so Y-sorting creates quadrants by grouping them in large horizontal rows. Instead of forcing the quadrant size to be (1, 1). The new size is thus Size2i(quadrant * quadrant, 1). Quandrant size is squared so that, by default, the quadrant contains as many tiles whether or no Y-sort is enabled.

The previous, and I guess safer behavior can be found again when quadrant size is set to 1, but that makes only sense when you rotate the TileMap, which is super unusual for isometric TileMaps.

Bugsquad edit:

• Fixes #74478.

[groud]

Sorry, this PR still need some work. I wrongly assumed that two tiles with the same Y coordinate would share a same Y local position. However, depending on the tile_layout and the tile_offset_axis, this can be wrong. Also, I forgot to consider that y_sort_origin can be modified from a tile to another. This PR would lead to issues.

[Exerionius]

Can this be implemented for 3.5 tilemap as well?

By tinkering around I found out that if you replace this:

int TileMap::_get_quadrant_size() const {
	if (y_sort_mode) {
		return 1;
	} else {
		return quadrant_size;
	}
}

with this:

int TileMap::_get_quadrant_size() const {
	return quadrant_size;
}

then performance of an isomentric y-sorted tilemap with 400x400 tiles goes from 21 FPS to 720 FPS (34x gain) on my system.

Here's were this function is in 3.5 branch: https://github.com/godotengine/godot/blob/16f6a5b13967205e34f323d37b8915c8b7437544/scene/2d/tile_map.cpp#L50

I'm not very proficient with C++ or Godot codebase and thus not sure if I should open a PR myself and what kind of complications/regressions it might bring.

[groud]

Can this be implemented for 3.5 tilemap as well?

I guess it could. But it's not simple to implement in general.

then performance of an isomentric y-sorted tilemap with 400x400 tiles goes from 21 FPS to 720 FPS (34x gain) on my system.

Well, yeah. But it means it would not Y-sort anymore.

We know the culprit is here. The fact the quadrant size is forced to 1 causes a lot more CanvasItems to be created, which is needed as sorting a tile requires it to be in its own canvas item.

The solution to this problem is to group tiles into quadrants according to their Y-value in global space, but this requires a rework of the way quadrants are created. This is why I set this PR as draft.

[Exerionius]

Well, yeah. But it means it would not Y-sort anymore.

That's not true (at least or 3.5):

[groud]

That's not true (at least or 3.5):

It might look like it works, but it's likely not. If I am not mistaking, tiles are drawn from top to bottom, left to right anyway, so the drawing order might stay correct in your situation. The problem arises when you need to add a scene (like a character) on the tiles. In that case the sorting cannot be done correctly.

It's would be more obvious with a TileSet which has some more height.

[Exerionius]

The buildings on the screenshot above are actually scenes, not tiles.

But the tiles are flat, you're right. I didn't check it with tiles that have some height.

[groud]

But the tiles are flat, you're right. I didn't check it with tiles that have some height.

In general, if the tiles are flat, then you do not need Y-sorting on the TileMap anyway.

[Exerionius]

In general, if the tiles are flat, then you do not need Y-sorting on the TileMap anyway.

At this point I feel extremely stupid :D
I was so preoccupied with the idea that isometric maps should be y-sorted that forgot to think if I actually need this in my particular case.

But anyway, I'm glad that at least the culpit of performance problems in clear, so it can be fixed sometime in the future.

Thanks.

[Calinou]

Performance figures for this PR can be found here: https://github.com/godotengine/godot/issues/74478#issuecomment-1528915321

[groud]

Alright, pushed an update to this PR. The MRP in https://github.com/godotengine/godot/issues/74478 gives me 120 FPS on my machine, which sounds reasonable enough.

[dotROLU]

Alright, pushed an update to this PR. The MRP in #74478 gives me 120 FPS on my machine, which sounds reasonable enough.

This is awesome! Is this will implemented to Godot 3.5.x or Godot 4.2 only?

Thank you so much, was waiting for this fix for a long time ❤️

[Calinou]

This is awesome! Is this will implemented to Godot 3.5.x or Godot 4.2 only?

This work is based on the TileMap rewrite only present in 4.x, so this won't be backported to 3.x.

[kleonc]

Alright, pushed an update to this PR. The MRP in #74478 gives me 120 FPS on my machine, which sounds reasonable enough.

@groud I suppose the PR description is outdated and needs an update?

[groud]

Alright, pushed an update to this PR. The MRP in #74478 gives me 120 FPS on my machine, which sounds reasonable enough.

@groud I suppose the PR description is outdated and needs an update?

Not really, maybe the numbers are not the exact same but I didn't use the same project. The changes are still more or less what is described.

[KoBeWi]

Some crash when opening project:

CrashHandlerException: Program crashed
Engine version: Godot Engine v4.2.dev.custom_build (4613bfc9df46670fd1c14a63b78e8117a83ee186)
Dumping the backtrace. Please include this when reporting the bug to the project developer.
[0] SelfList<RenderingQuadrant>::in_list (C:\godot_source\core\templates\self_list.h:176)
[1] TileMapLayer::_rendering_quadrants_update_cell (C:\godot_source\scene\2d\tile_map.cpp:523)
[2] TileMapLayer::_rendering_update (C:\godot_source\scene\2d\tile_map.cpp:258)
[3] TileMapLayer::internal_update (C:\godot_source\scene\2d\tile_map.cpp:1968)
[4] TileMap::_internal_update (C:\godot_source\scene\2d\tile_map.cpp:3021)
[5] call_with_variant_args_helper<TileMap> (C:\godot_source\core\variant\binder_common.h:308)
[6] call_with_variant_args<TileMap> (C:\godot_source\core\variant\binder_common.h:418)
[7] CallableCustomMethodPointer<TileMap>::call (C:\godot_source\core\object\callable_method_pointer.h:105)
[8] Callable::callp (C:\godot_source\core\variant\callable.cpp:51)
[9] CallQueue::_call_function (C:\godot_source\core\object\message_queue.cpp:220)
[10] CallQueue::flush (C:\godot_source\core\object\message_queue.cpp:326)
[11] SceneTree::process (C:\godot_source\scene\main\scene_tree.cpp:512)
[12] Main::iteration (C:\godot_source\main\main.cpp:3526)
[13] OS_Windows::run (C:\godot_source\platform\windows\os_windows.cpp:1474)
[14] widechar_main (C:\godot_source\platform\windows\godot_windows.cpp:182)
[15] _main (C:\godot_source\platform\windows\godot_windows.cpp:204)
[16] main (C:\godot_source\platform\windows\godot_windows.cpp:218)
[17] WinMain (C:\godot_source\platform\windows\godot_windows.cpp:232)
[18] __scrt_common_main_seh (D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:288)
[19] <couldn't map PC to fn name>
-- END OF BACKTRACE --

[groud]

Some crash when opening project:

I've just pushed a new version, it might be fixed (I will need an MRP if it still happen, as I could not really reproduce the bug).

[KoBeWi]

It's fixed.

[groud]

It's buggy (tested the latest artifact v4.2.dev.custom_build [https://github.com/godotengine/godot/commit/968d174f4819f811e46c54178dcb71d03ffc3431], things work fine in 4.2.dev5).

Oh right, I can reproduce the bug. I'll have a look.

[kleonc]

BTW as shown in the previous GIFs, this PR inverts the problem in #71257:

v4.2.dev5.official [e3e2528ba]	this PR

Sorting left to right (by ascending x) like in this PR seems more intuitive, just not sure if the change itself could be problematic.

[groud]

It's buggy (tested the latest artifact v4.2.dev.custom_build [https://github.com/godotengine/godot/commit/968d174f4819f811e46c54178dcb71d03ffc3431], things work fine in 4.2.dev5).

I pushed a new version, it should be solved now.

Sorting left to right (by ascending x) like in this PR seems more intuitive, just not sure if the change itself could be problematic

That might be an issue, though I am not sure how to solve it :thinking: . I guess I could maybe implement a custom sorting when Y-sort is enabled, but that is tricky to implement. maybe I could sort and reverse the list in that case. Though that needs some addition to selflist.

But well that's a bit corner case, so I think I would keep this new behavior for now, and implement the "more complex" solution if someone asks for it to be brought back.

[kleonc]

I pushed a new version, it should be solved now.

Indeed, seems to work fine now. :+1: And the code makes more sense also. :upside_down_face:

---

That might be an issue, though I am not sure how to solve it 🤔 . I guess I could maybe implement a custom sorting when Y-sort is enabled, but that is tricky to implement. maybe I could sort and reverse the list in that case. Though that needs some addition to selflist.

Not sure if I'm missing something but wouldn't it be just a matter of replacing rendering_quadrant->cells.sort(); with rendering_quadrant->cells.sort_custom<SomeCustomVector2iComparator>();? :thinking:

But well that's a bit corner case, so I think I would keep this new behavior for now, and implement the "more complex" solution if someone asks for it to be brought back.

I mean if we want to preserve the previous sorting then we could add it in here. As per above I think it's a matter of defining a proper comparator.

Actually now I've realized that currently in this PR sorting of each "Y-slice" is using Vector2i::operator<(const Vector2i &p_vec2) const: https://github.com/godotengine/godot/blob/fe5b1c8d49313d63fbe91cb7cdf463e10fb86afa/core/math/vector2i.h#L106 Meaning it sorts by X first, then by Y. Looking at the code each such Y-slice has 0.01 "height", meaning theoretically it can include tiles with different Y values and hence these could be sorted incorrectly. Highly unlikely to happen but still.

So it makes even more sense to use a custom comparator, sorting by Y first. Then X values could be compared as before (https://github.com/godotengine/godot/pull/73813#issuecomment-1729381779) in case we'd want to avoid potential regressions (some users might rely on the previous ordering). (Allowing/exposing a way to choose X ordering would indeed be more problematic and is out of scope of this PR.)

[groud]

I mean if we want to preserve the previous sorting then we could add it in here. As per above I think it's a matter of defining a proper comparator.

You were right, it didn't need anything more than that.

But I think to keep compatibility, there's no need to look into the "local coordinate" space. There was no sorting before done using local coordinates, so using map coordinates like (I did there) should be enough.

[kleonc]

But I think to keep compatibility, there's no need to look into the "local coordinate" space. There was no sorting before done using local coordinates, so using map coordinates like (I did there) should be enough.

Right, these are in map coordinates, I guess I somehow got into thinking about them as being local. :smile: So kinda nevermind the comment. Indeed should be good enough, at least until some edge case is reported. :upside_down_face:

[akien-mga]

Thanks!