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?
How about 32-bit indices?
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;
// No more padding!
};
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
