Designing a flexible tile-based engine

Question

I'm trying to create a flexible tile-based game engine to make all sorts of non-realtime puzzle games, just as Bejeweled, Civilization, Sokoban, and so on.

The first approach I had was to have a 2D array of Tile objects, and then have classes inheriting from Tile that represented the game objects. Unfortunately that way I couldn't stack more game elements on the same Tile without having a 3D array.

Then I did something different: I still had the 2D array of Tile objects, but every Tile object contained a List where I put and different entities. This worked fine until 20 minutes ago, when I realized that it's too expensive to do many things, look at this example:

I have a Wall entity. Every update I have to check the 8 adjacent Tiles, then check all of the entities in the Tile's List, check if any of those entities is a Wall, then finally draw the correct sprite. (This is done to draw walls that are next to each other seamlessly)

The only solution I see now is having a 3D array, with many layers, that could suit every situation. But that way I can't stack two entities that share the same layer on the same tile. Whenever I want to do that I have to create a new layer.

Is there a better solution? What would you do?

Answer 1

Did you actually see this problem, or have you just thought it up? Because I fail to see how iterating over objects list has any noticeable effect on performance. You'd have to have hundreds of objects per tile for this to matter. Most games I can think of have 10, tops.

If you really have a problem, the best idea is to cache data, not change representation. In your example, wall configuration probably doesn't change every frame. Just cache correct sprite type, don't recalculate it constantly.

If you want to make some crazy game that has lots of objects, and they change all the time, you can create different layers with different semantics. For example, wall layer contains only walls, no more than 1 per tile, and, say, decoration layer contains lists of objects that never change.

Finally, if you want to have ultra-flexible architecture that ideally supports every possible game - tough luck, there's no such thing.

Answer 2

Two suggestions. First, you should resolve the sprite that each tile will be drawn with during the load of your tile map/level. It should be easy enough to traverse the 2D array one your level is loaded and decide that a certian wall needs to be a L shape and another needs to be a | shape.

Second, I would store static data related to a tile in a different place than active data. So a tile object may have a list of objects which come and go from the tile but there is no need to traverse this to see if, e.g. we just want to know if the tile is walkable or not.

This psudo code is more or less how I have approached a tile based system.

Tile {
  Texture tex;
  //...other static data...
  List currentObjects;
}

Tile t = Tiles[x][y];

This assumes that there is static tiles in your game but that is a pretty good assumption in many tile based games where you are dealing with walls and the like.

Answer 3

You said:

I had was to have a 2D array of Tile objects, and then have classes inheriting from Tile that represented the game objects. Unfortunately that way I couldn't stack more game elements on the same Tile without having a 3D array.

Then I did something different: I still had the 2D array of Tile objects, but every Tile object contained a List where I put and different entities. This worked fine until 20 minutes ago, when I realized that it's too expensive to do many things

This is exactly the situation that you want to solve using the MVC (model view controller) pattern to separate out your model from your view. MVC makes this problem two parts:

• How to model a stack of tiles
• How do display a stack of tiles

Instead of having a 2D array of tiles, or a 2D array of a list of tiles, your model would store a 2D array of game objects. Then your 2D array of tile classes will look at the corresponding game objects and decide how to render them.

Instead of having a single Tile instance render a single game object, you can have a single Tile instance render something that looks like a stack of objects. This would be more efficient, and would give you clean separation of your core code logic, and how it looks.

Just like walls. The logic is very trivial, but the rendering is more complex.

Answer 4

I agree with @Omnion. Use the list approach, but keep it sorted if performance is a problem. That is to say use a hybrid approach. Use the list as your third dimension , but only identify the first 5 items as a specific type, and anything after that is an ink own type, or a type that won't require checking multiple times per frame.

Answer 5

You should "never" make separate classes for things like tiles. You should make a struct from bytes, shorts and ints that refer to the type of tile and objects on it. Performance wise ints are the best to go with or even long on 64 bit systems. But if you ever want to save your map you should go with bytes or shorts wherever you can, especially for huge maps.

In my games i have a map class that has just fields like: byte tileType; 256 different terrain types is enough for this game. Takes 1 byte. ushort tileObject; 65,536 different objects is plenty to go with. Takes 2 bytes etc.

If i take the example above each tile takes only 3 bytes in memory. So a 10000x10000 would be 300mb in memory and should not be a problem. Whenever you need to look for something you determine where on the map you want to look and what you are looking for and iterate the arrays accordingly.

If you have dynamic stuff all over the map ask yourself if the player really notices that stuff far out of it's viewport.