How can I support objects larger than a single tile in a 2D tile engine?

Question

I´m currently working on a 2D Engine containing an isometric tile map. It´s running quite well but I'm not sure if I´ve chosen the best approach for that kind of engine. To give you an idea what I´m thinking about right now, let's have a look at a basic object for a tile map and its objects:

public class TileMap {
   public List<MapRow> Rows = new List<MapRow>();
   public int MapWidth = 50;
   public int MapHeight = 50;  
}

public class MapRow {
   public List<MapCell> Columns = new List<MapCell>();
}

public class MapCell {
   public int TileID { get; set; }
}

Having those objects it's just possible to assign a tile to a single MapCell. What I want my engine to support is like having groups of MapCells since I would like to add objects to my tile map (e.g. a house with a size of 2x2 tiles). How should I do that? Should I edit my MapCell object that it may has a reference to other related tiles and how can I find an object while clicking on single MapCells? Or should I do another approach using a global container with all objects in it?

Answer 1

I am going to talk about design and performance.

Performance

contenance

What you have right now is called a Jagged Array, it is flexible but not really serving any purpose here.

My opinion on that is that you should store objects (tiles) that have an existence into your world, as part of an array to reduce heap waste, memory fragmentation, increase locality, reduce indirection and totally avoid reference overhead. Unfortunately for you, you appear to be using java or C# which will not permit you to control any of these aspects. Jave/C# references are faster than C++ shared_ptr but slower than raw-pointers, and definitely even slower than in-place objects. Allocation has demerits and since in java/c# evreything has to be allocated individually you kind of are in a tough luck situation. But don't get me wrong, until your game becomes dual head 4k resolution and has to manage immense and rich terrains, today's desktop machines are not going to be bothered by these details.

research

1. iteration: Normally you need 2 things in games : fast iteration and fast locality-based access. Fast iteration is the best with memory contiguous containers, like I said before, e.g. std::vector, in java/C# you can't avoid the fact that your containers will all store references anyway so you loose in-place objects advantage for iteration. Iteration is useful when you absolutely need to consider all elements, like the logical update of a living entity, to run its IA routine. Or for animation of decors elements to update their current frame, even though this is discussable, animation update could be done during rendering because it could be decided that animation serves no purpose if the tile is off-screen, in which case the second approach will suffice, the research approach.
2. fast locality-based access. This is the most useful and most common access way for any game object, be it a decor tile or a living entity. You must be able to retrieve a list of stuff that overlaps some arbitrary region, quickly. For this purpose, either data must be stored in a grid, a full matrix where a dual index i,j indicates tile position, and each cell can be either empty of bear a cell. you need to allocate a huge base grid for this method, but it is the fastest because locality-based is instantaneous. You just have to take your pixel coordinate, add the screen view offset, divide by tile size, round to next smaller integer and you've got your direct index in the container. This is impracticable in cases of very large worlds. In such cases some people would use a quad-tree. I prefer to use a hash map. Just create a hashing function for a pair of integers (vector2) and store your tile ids this way. Access is almost constant and no games with pointers going to children nodes, especially with open address hash maps which are preferable for gaming environments, because they don't fragment the memory and are more efficient if the sizing is known in advance.

Store ids (indices) into your space partitionning structure, this way you get the main store which is just an array, and the locality-based store which stores ids into the main array.

If you have to delete something in your world, just keep a parallel array to store indices of the holes. This would be called the freelist. Some people prefer to swap the element to erase with the last element in the array, and pop back. This is also great but people already holding a pointer/reference/index to the last object must be updated, this can be difficult. notably your space partitionning structure is holding indices so this would have to be updated at least. In this regard, the freelist approach is simpler and fast. Next time you want to add an object just pick the last index in the freelist and pop it back. If you add too many objects in your world and the main array becomes full, crash the game immediately, find a new appropriate size and re-hard-code the new size. dynamic resizing is not desirable, gameing scenarios are well controlled, you just need to execute "profile" runs to determine how much of a max limit is acceptable. If your engine is to be shipped to clients for whom you do not know with what kind of scenarios they will use it, then make this constant appear in the build settings. (like some CMake variable) and document it well.

Design

In terms of design, your jagged array has maintenance problems, because it forces repetitive code to follow the double indirection in terms of rows and columns which helps no one really. the linear approach has the advantage of being flexible, if it must be changed into a hash map, indices can still serve as identifiers so other systems wont be affected. or ever crazier, a streaming-able virtual container. indices could be loaded on the fly in a world where (infinite?) roaming is necessary so the container could be particularly complicated but identifiers create a nice loose coupling in this sense.

Also when you deserialize, you don't have to think about row column order, you just push to the array in whatever order fate decides and it would be cool. locality access is accelerated by a different structure anyway. good luck

Answer 2

Ignoring the fact your using lists for data that looks like array's..

Just store TileID in multiple row,cells for were it's is placed.

That way if your doing some find closest/A* any edge/side will be found.

If your wanting there to be a primary cell, negate the minor cells, so you don't double count in a area search function, but still know it's type. And given your using an int for TitleID your not losing anything from your ID space.