3
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your detailed answer! It´s kind of technical ;-) To sum up: I should get rid of the Jagged array and use a single array with vectors (or should I prefer a list<>?) and store the Ids in there. I should also use parallel arrays to store indices. I do have parallel stuff right now and I would love to get rid of it cause I think it would be the easiest way to handle everything at one place. Seems like I need to do a lot of code review though. \$\endgroup\$ – Yheeky Jun 26 '14 at 7:32
  • \$\begingroup\$ parallel stuff doesn't make much sense. its not the "stuff" part, its the "parrallel" part. (just another java concept). Parallel container in java and C# just means they don't break when used without locks. nothing prevents you from keeping using them. Secondly, when I say "vector" I often mean "array", because of C++ terminology std::vector. I think I say vector2d when I mean a pair of coordinates. Third, don't store IDs into the main array, store the tiles directly. IDs will go into other things, like the space partition structure, or... \$\endgroup\$ – v.oddou Jun 26 '14 at 9:01
  • \$\begingroup\$ ...parts of code that deal with tiles later, like collisions, or walking noise reader that needs to evaluate what texture is under the player. these stuff will work with IDs of tiles. \$\endgroup\$ – v.oddou Jun 26 '14 at 9:02
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Yes, I prefer lists cause they are more flexible. Your primary cell advice is good! I´ll think about that! Thanks! :) \$\endgroup\$ – Yheeky Jun 26 '14 at 7:35
  • \$\begingroup\$ You know there is a cost to flexibility? Given you have max values of 50 you are gaining nothing unless you have a sparse grid. But then you would keep the xy as a pair. In a btree map. I call your lack of knowledge as flexibility bluff. \$\endgroup\$ – Simeon Pilgrim Jun 26 '14 at 7:39
  • \$\begingroup\$ Maybe you didn't get it...that's not my original object I´m using in my engine. This is a conceptual question. My "lack of knowledge" has brought me far already so I can deal with it ;) \$\endgroup\$ – Yheeky Jun 26 '14 at 9:24
  • \$\begingroup\$ Fair call on the example code, I went to far, sorry. \$\endgroup\$ – Simeon Pilgrim Jun 26 '14 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.