How to handle 2D tiles with different sizes

This topic is 810 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Guys I have a technical problem!

Let's say we have a 2D world with tiles which have all the same size!

We can simply store the world in a 2D Array and

we can simply draw the tiles which is in the visible area of the camera, without looping trough the whole array.

This is very efficient!

My problem is now, I want to achieve something efficient like this with tiles which have different sizes!

So, I have a Tile class with a Vector2 for the position.

If I store all the Tiles in a List<Tiles>  I have to loop trough the whole list until I found the tiles which are in the cameras visible area.

This is really unefficient.

What I tried is to Split this List into multiple smaller lists,

Like this Dictionary<Rectangle, List<Tiles>>

Let's say for example splitting the world into 4x4 = 16 areas and loop only trough the areas which are in the cameras visible area.

This attempt is more efficient then storing them in a single list.

But this isn't that efficient if you use too few or too much areas and the drawing order is messed up!

Does someone has other ideas how to manage this?

Share on other sites

Some form of Quad Tree seems to be what you are looking for.

Share on other sites

Some form of Quad Tree seems to be what you are looking for.

Thank you I'll try this one!

Share on other sites

First, if you have a large number of tiles of one particular size that are in a regular grid (for example, the tilemap itself), keep that separate if you've already got an efficient way to handle that. If you're mixing all these map tiles into what are probably a much smaller number of odd-sized sprites/tiles, then your problem is really that you're paying the high cost of your search-a-single-list approach for probably several times as many graphics as you need to. You only want to pay that cost for the items that you don't have a better solution for.

A quad-tree or similar spacial-partitioning system is the general approach and if you have a fairly even mix of tile sizes and such it might be the best fit. But it comes at some complexity -- for example, if a movable image like an NPC or enemy moves between partitions, you have to update those lists. Its not especially hard, but other solutions are simpler if you don't need the full generality of that solution, and if the number of odd-sized/non-gridded objects is relatively low.

Sorting your list in various ways can help too, so that you don't have to iterate the entire thing every frame. For example, you could sort the entire list based on distance to the viewport, and decide on some larger-than-the-viewport distance that includes the entities you need to consider every frame. Now, you iterate through only those "near" objects every frame, and periodically you resort the whole list -- maybe once per second. You don't even need to do a full sort, you just need to partition the list into 'near' and 'far' parts -- in C++ that would be std::partition or std::stable_partition, but I'm not sure what the best C# equivalent would be.

Some other implementation details to be aware of are:

• You don't want to literally move the list contents around if they're expensive to copy, you'd probably want to sort a list of references. In C# this is probably already taken care of, just be sure you know about how structs/classes differ. In C++ this would be an issue you'd have to deal with yourself, either by sorting through a list of references, or possibly by making the objects cheap to move.
• You probably don't care about the *actual* distance for this sorting, so save yourself the cost of a square-root per object by just squaring the threshhold (once) instead. You'll get the same order/partition out regardless.
Edited by Ravyne

1. 1
2. 2
Rutin
17
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• Forum Statistics

• Total Topics
633735
• Total Posts
3013596
×