Efficiently Handling Entity-Interactions in a Tile-Based World

I've been programming Roguelike games lately and there's a common problem I always run into. I can't seem to find a satisfactory solution for handling Monster-Monster interactions.

For the intents and purposes of this question, let's assume my Game-Map just is an array of bytes.

struct Map{
unsigned char tiles[100][100];
};


Now, I've got Monsters, which have an X and a Y position.

struct Monster{
unsigned int x, y;
};


Handling Monster-Map interactions is trivial. For example, if a monster wants to move to the left, I just have to check if tiles[x - 1][y] is a passable tile. This is very nice because no-matter how large the map is, I only have to check one tile.

But here's where I run into problems. What if a monster wants to breath fire onto a tile to the left. To ignite any monster that might be on the tile, I'd have to iterate through every monster in the entire world, checking if it's x, y matches the coordinates of the tile. This is not-so-nice, as the cost of breathing fire scales linearly with the amount of monsters in the world. If only there were a way to access monsters using tile-coordinates...

Which leads me to one solution. Tiles could hold a pointer to a monster. When a monster moves to a tile, it sets the previous tile's pointer to a nullptr and sets the current tile's pointer to this.

struct Map{
unsigned char tiles[100][100];
Monster* resident;
};


Now, when a monster breaths fire, it just ignites whatever monster is on that tile by using the tile's monster-pointer. Now the cost of breathing fire is constant, and the cost of moving is constant. Perfect!

But...

Now a tile is 9 bytes instead of 1 byte. sizeof(map) has more-than octoupled! Ouch!

My question is: What other solutions could be used to solve this problem? Maybe one's that meet in the middle on memory usage vs. number of operations.

• You say this is a common problem you encounter, but to be frank, it doesn't sound like a problem at all. You have linear scaling on one hand, and extra memory usage on the other, but I'm not hearing any indication that you have actual performance problems. Until you do, you should be much more concerned with keeping your code simple and easy to change while you're prototyping ideas. – Chris Hayes Nov 30 '15 at 1:11
• Consider that if you allow items on top of (or even under) tiles, you'll end up with an even larger data structure anyway. – Keith Nov 30 '15 at 3:01

You have 3 major options:

1: Implement some kind of sorting or data structure.

For example: Keep monsters in a list/array (Something you are probably already doing) and sort them by x and y. This would enable you to perform a binary search (Which has O(log n) performance) for locating a monster at a given tile. However, this introduces the need to sort the list once per game tick(Sorting is O(n log n)). This means that if there are a small number of monsters that need to breath fire, the performance will almost certainly be worse. This would only help performance if they are a very large number of monsters that need to breath fire (Probably somewhere in the hundreds to thousands).

Although that was just an example algorithm, the same general characteristics will hold true. In short, complex algorithms will only save time if there are a large number of monsters.

2: Simply go through the list of monsters (O(n)). This is simple and likely to be quick enough in almost all cases.

3: Use the pointer system you suggested. Although this increases the size of the map considerably, it is unlikely to cause any problems unless your map is extremely large. This system lets you handle both small and large numbers of monsters simply and efficiently. Basically, the size increase is probably irrelevant and this is possibly the best option overall.

• Note that sorting by x and y is just another view for the K-d tree with k=2. In this case, you don't have to sort at each tick, but use the delete and insert operations whenever the position of a monster/entity is changed (O(logN) average). Overall slightly more efficient than linear search. – Mephy Nov 30 '15 at 1:42
• @Mephy I didn't think of that. I'll update that portion of the answer in a day or two. Thanks for that info. – NitrogenReaction Nov 30 '15 at 3:06

Why this is overkill

Although you've probably heard the phrase premature optimisation is the root of all evil, it took a while for me to fully grasp its meaning.

Consider a game that runs two procedures (A and B) every game loop. Procedure A takes 10,000 cycles to perform its task. But really it only needs 100 cycles. It could be 100x faster, how wasteful!

Procedure B takes 1,000,000 cycles to perform its task. But really it only needs 500,000. It could be 2x faster, it doesn't seem very wasteful.

If we optimise procedure A, we save 9,900 cycles. If we optimise procedure B we save 500,000 cycles. So optimising procedure B is the wise choice. But if we follow our intuition it will probably tell us to optimise the "wasteful" or "inefficient" procedure - procedure A!

But let's do it anyway

Of course, you will never learn how to write an efficient algorithm if you do not take opportunities to practice. And in some instances (depending on how much you deviate from the typical roguelike, or how constrained your hardware is) you might legitimately need to optimise this.

So, here are some options:

1. Restrict active monsters to those on/near screen. Any monsters that are far enough offscreen are either completely "frozen" or just wander around. Monsters that are active are kept in a list.

Pros: Not only is the list of monsters much shorter, but you can also save work on the actions of "inactive" monsters.

Cons: Potential loss of realism, especially if the user can cast a spell to view the entire map, etc.

2. Chunk by chunk basis. Divide the map into chunks of (say) 16x16 tiles, and for each chunk keep a list of monsters within the chunk. Like the previous option this considerably restricts the number of monsters that needs to be checked.

3. Have monster list permanently sorted by x co-ordinate. For example, if you wanted to check the (x-1, y) tile, you would simply go backwards in the monsters list until you found a monster whose x co-ordinate was x-2 or lower. To check the (x,y-1) tile you would have to go backwards and forwards until you hit different x co-ordinates. Intuitively this might seem like it would cut the list from n to √n, but actually because monsters are quite sparse it will cut it even further.

4. Keep monster info in the tiles themselves. Since a pointer to a Monster is 8 bytes, if you can cram all the monster information into a comparable amount of storage then you might as well do so. For instance, if you use unsigned chars for the monster type and health, you would only use 3 bytes per tile (probably 4 if compiler adds padding). For example:

struct Tile {
unsigned char terrain;
unsigned char monster_type; //if ==0 then there is no monster here
unsigned char monster_health;
}
struct Map {
Tile tiles[100][100];
};

1. Implement some kind of space partitioning trees. As discussed in this question, you could use Quad-trees or BSP. The main advantage of these over simple chunking (AKA grid system) is that when there are large regions devoid of objects, less space is taken up in the data structure. (The extreme example is space-travel games where there are lots of objects in some areas but others are very very empty.) I don't see any advantage for the typical roguelike. But you can implement it to learn something.

2. Integrate with pathfinding algorithm. Your procedural generation probably knows about the rooms and corridors it creates. This can be used to implement efficient pathfinding (e.g. to have enemies home in on the player): by considering the graphs of rooms/corridors and doors, only a few nodes need to be considered, rather than all the tiles. Then, you would need to keep track of which room each monster is in, so you could only consider monsters in the same room. I don't see much point to this aside from coding practice.

By the way, a very very easy optimisation you can do is to not search through your monster list if you know the target tile is empty.

Have fun!

I am also working on a (somewhat/partially) roguelike game, though in C# (using Monogame), not C++. What I am doing is storing all my map objects (monsters, stairs, traps, the player, other NPCs, etc.) in a 2D array of lists.

public List<MapObject>[,] MapObjects;


This allows there to be more than one map object on one tile (e.g. a flying monster on a trap). The last object in the list is almost always the one that will be interacted with by other objects. It also makes rendering the objects easier if the map is larger than the screen.

• Nice. I've seen this structure suggested on RogueBasin :) std::array<std::forward_list<GameObject>, WIDTH * HEIGHT> In this case, items could be ignited by fire-breath if you wanted, haha. – Willy Goat Dec 1 '15 at 20:33

What sort of machine are you targeting? If your pointers are 8 bytes (64-bit machine), I'm extremely confused with you saying "ouch", since 9 bytes per tile is teeny with a 64-bit addressing space, and actually with padding for proper alignment, it'll tend to be 16 bytes per tile:

struct Tile
{
Monster* monster;
unsigned char value;
// 7 bytes padding for proper alignment of 'monster' field
// assuming 64-bit pointers
};


... unless you use a parallel array (SoA rep):

struct Map
{
unsigned char tiles[100][100];
Monster* tile_monsters[100][100];
};


... at which point you can avoid the padding. Still, with 100x100 (10,000) tiles, that's less than 80 kilobytes for these pointers. That said, I'll just give you the benefit of the doubt and assume this actually matters on the hardware you're targeting or maybe your real example has a hundred million tiles.

Just Partition One Dimension

In that case, what I recommend is store a singly-linked list pointer inside your monsters to the next monster in the same row of tiles:

struct Monster
{
// Next monster on the same row of tiles or NULL if we're
// at the end of the list.
Monster* next_row_monster;

// Monster position on map.
int x, y;
};


Now for your map, you can store a pointer to the first monster for each row of tiles:

struct Map
{
unsigned char tiles[100][100];

// Points to first monster on a row of tiles or NULL if there are
// no monsters for a given row (for a given Y position).
Monster* row_monster[100];
};


Now you've cut the map memory overhead down to 1/100th, though it does introduce a pointer to each monster. I'm assuming you have way less monsters than there are tiles for the entire map.

Why Use 8 Bytes For Monster Positions?

That said, if you're this concerned about memory use, you're wasting a lot of memory by storing two integers (which I assume to be 32-bit) for each monster position. You can just use one:

struct Monster
{
// Next monster on the same row of tiles or NULL if we're
// at the end of the list.
Monster* next_row_monster;

// Monster position on map. To get the x and y values, use:
//   y = tile / map_width;
//   x = tile % map_width;
unsigned int tile;

// 4 bytes of padding to align 'next_row_monster'.
};


... or two 16-bit integers, though that limits the maximum width and height of your map as opposed to using the above method which only limits the total number of cells you can have to a little over 4 billion tiles.

However, as we can see we end up getting 4 bytes of padding again for alignment which brings us to the question, why even use pointers?

Why Use 64-Bit Pointers?

struct Monster
{
// Index to next monster on the same row of tiles or -1 if we're
// at the end of the list.
int next_row_monster;

// Monster position on map. To get the x and y values, use:
//   y = tile / map_width;
//   x = tile % map_width;
unsigned int tile;

};

struct Map
{
unsigned char tiles[100][100];

// Indexes the first monster on a row of tiles or -1 if there are
// no monsters for a given row (for a given Y position).
int row_monster[100];

// Array of all monsters in the map.
Monster monster[num_monsters];
};


Just 400 Bytes More instead of 80,000! 0.5% Memory Use!

Voila, now you've made it so you only need 400 bytes more than what you started with assuming 100x100 tiles. We didn't increase the memory use of monsters at all since we squashed down the two ints for x and y into one integer.

With this, when you are checking to see if a monster is on a given tile, you only need to look through the monsters on the same row. You can even radix sort the monsters for a given row (using x as key) if it gets really crowded and cache the results to an array of monster indices at which point you can do a binary search to find a monster at a particular X coordinate on a given row.

And there we have it. We solved your whole problem by just requiring 400 bytes more in total as opposed to 80,000 bytes, using only 0.5% of the memory of your proposed solution!

If you can afford to use another 400 bytes, then you store two indices per grid row and partition the monsters to the left half of a row separately away from monsters on the right half of a row, and so on (choosing the appropriate memory/processing trade-off to accelerate searches).

4-Color DOS Days!

That said, I haven't needed to squash memory usage down this much in almost 30 years. This is an interesting and fun question making me relive the old glory days of DOS programming with 4-color CGA graphics. I wish there were more like these -- fun stuff! Though this question kind of gave me a mid-life crisis. I miss programming back in the 80s. I actually think programming is harder these days with all the fancy 3D stuff everyone is doing and all the APIs you gotta learn and having to deal with multi-tasking environments. The tools and hardware are absolutely superior, but I miss the old days. Things were simpler back then.

Here is some music from the late 70s and 80s: https://youtu.be/h7LmxEsme94

And some good programming music: https://www.youtube.com/watch?v=ZzQ3eBerHfM