Tile entity stacks c++ question
skreeg
I have a general question on C++ and data structures for tiles.
I have an array of map tiles (Tile.h). Each tile used to have a
Terrain object and also a pointer to a Creature* object. However, I've
realised a lot of properties of both terrain, creatures and later
items are the same so I've created an Entity object to be the parent
class of both my Terrain, Creature and Item classes.
Now in my Tile class I have a vector<Entity*> entities that holds a
vector of all the things that inhabit that particular tile. This means
I can have terrain, a creature and multiple items inhabiting the one
tile. I intend to use a flag (isPassable) to ensure there's only one
creature on it at a time. In my Creature.move() method I erase the
creatures pointer from the current tile's vector and add it to the
vector of the tile I'm moving to. All good.
Now, my problem is I don't know quite how to extract this data from
the Tile class from elsewhere in my progam when I need it. At times I
need to be able to pull the pointer to the occupying Creature if one
exists in the vector. I looked at the STL find() algo but have no idea
what to make the "value" field. If I go this route I need to find a
Creature object in a vector of pointers to Entities. Same with terrain
and other Entity subclasses.
Basically. If I make a vector of pointers to Entity classes (of which
may differ due to subclassing) how do I differentiate between them?
Am I attempting something that's bad practise or possibly illegal?
skreeg
Terrain, Creatures and Items (weapons, medikits, modifiers etc) and my
plan was to make them all the same in order to make things a bit
easier inside the Tile class. Since I only have 3 types per tile then
I'm probably better off keeping them separate and just dealing with
them explicitly when encountered inside the Tile class code.
Gerry Quinn
@f20g2000prn.googlegroups.com>, skr...@gmail.com says...
> Now, my problem is I don't know quite how to extract this data from
> the Tile class from elsewhere in my progam when I need it. At times I
> need to be able to pull the pointer to the occupying Creature if one
> exists in the vector. I looked at the STL find() algo but have no idea
> what to make the "value" field. If I go this route I need to find a
> Creature object in a vector of pointers to Entities. Same with terrain
> and other Entity subclasses.
>
> Basically. If I make a vector of pointers to Entity classes (of which
> may differ due to subclassing) how do I differentiate between them?
Two obvious ways:
(1) Test all the entities pointed to to see if one is a Creature
(2) Keep a certain vector element for Creatures (perhaps the first or
second, you could do this for Terrain also assuming there is only one
Terrain per tile. If there is no Creature you can put in a null
pointer, or a pointer to a null Creature.
It seems like it would be simpler to keep them separate always, for
example making a Tile class like the following. I imagine something
like this is commonly used in roguelikes:
class Tile
{
Terrain * m_pTerrain;
Creature* m_pCreature;
vector< Item* > m_Items;
};
- Gerry Quinn
Ray
> Basically. If I make a vector of pointers to Entity classes (of which
> may differ due to subclassing) how do I differentiate between them?
The simple suggestion is that you can walk the vector and test things
until you find a creature or reach the end of the vector. If the vector
is fairly short (20 items or so) that's not at all unreasonable.
Slightly more complex is that you can adopt an invariant that, if there
is a creature on the tile, it is referenced by cell 0 of the vector.
That way you only ever have to check cell 0. The additional cost is
in the code that adds something to a tile; if it's a creature, you
check cell 0 for another creature (and yell about the one-creature-
per-tile rule if you find one), then move whatever's in cell 0 to
the end of the vector and replace it with the creature.
No problem so far. But if you suspect there's a real design
problem here, I think I may have spotted it.
Simply put, what data structure "owns" the pointers to your
creatures? Putting direct pointers to your creatures in the map
sounds like the map owns 'em. That's reasonable, because you have
to be able to find the creature on a particular tile when the @
next to that tile attacks in its direction or when an area effect
somethingorother affects that tile.
But you also have to be able to find that creature when it's that
creature's turn to act, so the schedule wants a pointer to the
creatures too. And that creates a problem when it's time to
deallocate the creature, because if you drop it from the map and
the schedule still has a dangling pointer to it, then when its turn
comes up the schedule dereferences a dangling pointer - and gets
either the wrong object or a protection fault.
Anyway, the design question is this: Do you have multiple
different data structures that all have pointers to creatures?
And if so, how do you keep them synchronized to avoid segfaults
when you deallocate one?
Bear
Jeff Lait
> Now, my problem is I don't know quite how to extract this data from
> the Tile class from elsewhere in my progam when I need it.
You make a
Creature *Tile::getCreature() const;
method on Tile.
Note this does not address your real question. But your original
wording suggests you would look at the raw entity list anywhere in the
program you want to get a creature. This is very bad practice.
Your decision to collapse all your entities into one vector<> should
not be readily apparent in the rest of your code (excluding any place
you genuinely want all Entities!)
> At times I
> need to be able to pull the pointer to the occupying Creature if one
> exists in the vector. I looked at the STL find() algo but have no idea
> what to make the "value" field. If I go this route I need to find a
> Creature object in a vector of pointers to Entities. Same with terrain
> and other Entity subclasses.
>
> Basically. If I make a vector of pointers to Entity classes (of which
> may differ due to subclassing) how do I differentiate between them?
Thankfully, you aren't asking this question a decade ago. We have a
nice answer now: dynamic_cast.
foreach entity in list:
Creature *foo = dynamic_cast<Creature *> entity;
if (foo)
return foo;
> Am I attempting something that's bad practise or possibly illegal?
Not illegal, but, IMHO, a bad practice. I'm a believer in Tile
classes being fly-weights or non-existent. I'm really opposed to the
idea of monsters being held by tiles.
Monsters are, IMHO, logically held by the *map*. Rather than
Tile *tile = map->getTile(x, y);
Creature *creature = tile->getCreature();
I prefer
Creature *creature = map->getCreature(x, y);
Now, you can always implement Map::getCreature(x, y) by passing down
to Tile::getCreature(), but in practice I find I usually have a
location which I want to query and a map, and not yet the Tile.
My first approximation of a roguelike (before premature optimization)
thus consists of the Map which contains a list of Creatures and Items
that lie on that map. The Creatures and Items contain their x/y
cooridinates on the map. This is surprisingly efficient for most
operations since total number of creatures and items is usually much
less than the number of map cells. When you are iterating over all
map cells, such as for display, you don't look up items and creatures
once per cell, but do it as a second pass.
1) Draw all terrain cells
2) For each creature/item, draw it on top of the cell
This avoids the O(n^3) of the naive approach
The big problem with storing pointers on your Tiles is that you now
have redundant information about where your creatures are. Your
creature's location is defined by which Tile points to them and also
by their (x,y) value. This is just asking for synchronization issues
and lots of pain and suffering.
Particularly bad, IMHO, is that when you move a creature you have to
take it off the map or duplicate it on the map during the move.
Movement is so very common (teleportation, spawning, etc) I get very
worried if it is possible to screw it up.
My second approximation of a roguelike is usually to build a cache of
Creature * for each cell to speed up getCreature(x, y) calls.
Inevitably this results in ghost creatures or other peculiarities as
one screws up the programming.
In Jacob's Matrix I took all this a bit farther as I replaced all my
(x, y) cooridinates with a POS class. This position class is where I
could then add getCreature(), etc. So, if I had a creature "rat" and
wanted to get the creature one step up from him...
Creature *mobtonorth = rat->getPos().delta(0, 1).getCreature();
POS::delta(dx, dy) does the logical equivalent of (x+dx, y+dy) and
returns the result. Note that these positions aren't Tile types, they
don't actually contain any data about the tile, they just hold the
(map, roomid, x, y, orient) tuple.
I found with these 90% of my position code only dealt with relative
positions so I rarely had to worry about the actual Map pointer.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
skreeg
made me realise that not only was I heading in the wrong direction
with my design but also that I should be moving in a direction I
wasn't aware of before and this also fixes a niggling thought that I
was having an increasing amount of potential dangling pointers
everywhere.
I'm now removing creatures and items from the tiles and using my map
"overlay" to display them. I'll also be expanding use of my Position()
class which I didn't realise was such a good idea when I created it.
Back on track. 2 months till child 2 is born. Must get playable
release out before then. :)
Gerry Quinn
37g2000yqm.googlegroups.com>, torespon...@hotmail.com says...
> The big problem with storing pointers on your Tiles is that you now
> have redundant information about where your creatures are. Your
> creature's location is defined by which Tile points to them and also
> by their (x,y) value. This is just asking for synchronization issues
> and lots of pain and suffering.
>
> Particularly bad, IMHO, is that when you move a creature you have to
> take it off the map or duplicate it on the map during the move.
> Movement is so very common (teleportation, spawning, etc) I get very
> worried if it is possible to screw it up.
> I found with these 90% of my position code only dealt with relative
> positions so I rarely had to worry about the actual Map pointer.
For me this is a legitimate case where a redundant representation may
well be better for efficiency and ease of access. You want to have
easy and quick access to all monsters, but you also want easy and quick
access to the monster on a given tile. (I would apply similar logic to
the case of a chesslike game, though admittedly speed of access might
be more important there.)
The solution is to create a small set of functions which maintain the
data structure, and go through those for all cases when monsters move,
or are created or destroyed. I did that for my game Lair of the Demon
Ape and had no problems from this source.
Of course we all know about the pitfalls of premature optimisation. but
having to search the list of monsters to determine what if any monster
is on a given tile would just cause me so much mental pain that I just
could not implement them that way, even knowing it would work fine!
This is despite the fact that I had very little interest overall in
optimisation and efficiency when coding Lair...
- Gerry Quinn
Gelatinous Mutant Coconut
> The solution is to create a small set of functions which maintain the
> data structure, and go through those for all cases when monsters move,
> or are created or destroyed. I did that for my game Lair of the Demon
> Ape and had no problems from this source.
What data structure do you use?
Going aside into optimization: It seems to me that the best option in
terms of speed and simplicity would be a bijective hash-map. That way:
Using a monster* as a key, if the monster is on a tile, return a
pointer to that tile; otherwise return NULL.
Using a tile* as a key, if the tile has a monster, return a pointer to
that monster; otherwise return NULL.
Invariant: If monster* and tile* are in the BiMap, then BiMap.keyTile
(BiMap.keyMonster(monster*)) == monster*, and BiMap.keyMonster
(BiMap.keyTile(tile*)) == tile*.
Unfortunately as far as I am aware bijective maps aren't available in
most language's standard library, although Boost has a C++
implementation called Boost.Bimap, and Apache Commons provides Java
implementations for BidiMap, OrderedBidiMap and SortedBidiMap
interfaces, including one called a DualHashBidiMap.
If you decide to implement your own, it should be relatively
straightforward to build and maintain using two hashmaps.
Joshua Day
> Hmm, I'm sure this is a bad idea now. I only 3 types of entities.
> Terrain, Creatures and Items (weapons, medikits, modifiers etc) and my
> plan was to make them all the same in order to make things a bit
> easier inside the Tile class.
Are you planning to replicate X-COM's multi-cell units? That will be a
greater constraint on your code than anything else.
--
Joshua
Ray
> Going aside into optimization: It seems to me that the best option in
> terms of speed and simplicity would be a bijective hash-map.
> If you decide to implement your own, it should be relatively
> straightforward to build and maintain using two hashmaps.
Why two? One is after all guaranteed that no tile* is also a creature*,
and vice versa. It seems to me that your bijective hashmap would just
map entries to other entries. Caring about types, while usually a good
idea, in this case leads to needless duplication of code. Just write
an untyped function and provide typed public interfaces to it.
In fact, I'm bored. Here, I'll bang out some C code for it. If
you want to use it you get to debug it.
Bear
Note: beware bugs in the code below; I have not tested it.
-------------------------------------------------------
define ERASED -1 /* signal value */
typedef struct {
void *key;
int assoc;
} bimapentry;
typedef struct {
int tablesize; /* how much currently allocated */
int keycount; /* how many keys currently stored */
bimapentry *table; /* dynamically allocated resizable array */
} bimap;
bimap *newmap(){
bimapentry* newtable = (bimapentry*)calloc(16, sizeof(bimapentry));
bimap* newbimap = (bimap *)calloc(1, sizeof(bimap));
assert (newtable != NULL);
assert (newbimap != NULL);
newbimap->table = newtable;
newbimap->tablesize = 16;
return(newbimap);
}
/* Not exposed in .h for nonlocal calls - use only locally. */
void *bimaplookup(void *key, bimap *map){
int rehash;
int index;
for (rehash = 0; rehash < map.keycount; rehash++){
/* note the hash function needs to have the property
that it never repeats a number on rehashes until
it has tried 'em all from 0 to tablesize. Consult
Knuth v3 if uncertain how to implement. */
index = hash(key, rehash, map->tablesize);
/* an unused, unerased entry means the key isn't stored. */
if (map->table[index].key == NULL &&
map->table[index].assoc != ERASED) return(NULL);
else if (map->table[index].key == key){
assert(map->table[map->table[index].assoc].assoc == index);
return(map->table[map->table[index].assoc].key);
}
/* The other possible cases are erased entries and non-key
entries. In both cases we do nothing and fall through
to the next for-loop iteration. */
} /* end for. */
/* we get here only if the table is completely full,
and we searched the whole thing and didn't find it. */
return(NULL);
}
/* public interface in .h */
tile* tilelookup(creature *key, bimap *map){
return ((tile*)bimaplookup( (void*)key, map));
}
/* public interface in .h */
creature* creaturelookup(tile *key, bimap *map){
return ((creature*)bimaplookup( (void*)key, map));
}
/* forward reference for resizetable. */
void bimapinsert(void *key1, void *key2, bimap *map);
/* no public interface, only for internal use. */
void resizetable(bimap *map){
int size = map->tablesize;
int newsize = size;
int index;
bimapentry *newtable;
bimap newmap;
void *key1;
void *key2;
/* guarantees no "sensitive" sizes at which adding and deleting a
single association can cause consecutive resizings. */
while ((newsize > 8 * map->keycount) && newsize > 16) newsize /= 2;
while ((newsize < 2 * map->keycount) || newsize < 16) newsize *= 2;
if (newsize == size) return;
newtable = (bimapentry*)calloc(newsize, sizeof(bimapentry));
assert(newtable != NULL);
newmap.keycount = 0;
newmap.tablesize = newsize;
newmap.table = newtable;
for (index = 0; index < size; index++){
key1 = map->table[index].key;
if (key1 != NULL){
assert(map->table[index].assoc != ERASED);
key2 = map->table[map->table[index].assoc].key;
assert (map->table[map->table[index].assoc].assoc != ERASED;
bimapinsert(key1, key2, &newmap);
}
}
map->tablesize = newsize;
map->keycount = newmap.keycount;
free(map->table);
map->table = newtable;
}
/* no public interface, accessible to users via typed wrapper */
void bimapinsert(void *key1, void *key2, bimap *map){
int index1;
int index2;
int rehash;
do { index1 = hash(key1, rehash++, map->tablesize);
} until (map->table[index1].key == NULL);
rehash = 0;
do { index2 = hash(key2, rehash++, map->tablesize);
} until (map->table[index2].key == NULL && index2 != index1);
map->table[index1].key = key1;
map->table[index2].key = key2;
map->table[index1].assoc = key2;
map->table[index2].assoc = key1;
map->keycount += 2;
}
/* no public interface, accessible to users via typed wrapper */
void bimapdelete(void *key1, void *key2, bimap *map){
int index1;
int index2;
int rehash;
do { index1 = hash(key1, rehash++, map->tablesize);
} until (map->table[index1].key == key1 ||
map->table[index1].assoc == ERASED);
/* key1 unindexed, hence no such association, cannot delete */
if ( map->table[index1].assoc == ERASED) return;
rehash = 0;
do { index2 = hash(key2, rehash++, map->tablesize);
} until (map->table[index2].key == key2 ||
map->table[index2].assoc == ERASED);
/* key2 unindexed, hence no such association, cannot delete. */
if (map->table[index2].assoc == ERASED) return;
/* both indexed - check to make sure they're associated,
and if so delete. */
if (map->table[index1].assoc == index2 &&
map->table[index2].assoc == index1){
map->table[index1].assoc = ERASED;
map->table[index2].assoc = ERASED;
map->table[index1].key = NULL;
map->table[index2].key = NULL;
map->keycount -= 2;
resizetable(map);
}
}
/* typed wrapper for bimapdelete, interface in .h
User needs to call this to remove creatures from map
when they are GONE, dead, kaput, not reappearing
anywhere on the map. If just moving monster around on
the map, addmonstertotile is sufficient.
*/
void removemonsterfromtile(creature *monster, tile *tile, bimap *map){
bimapdelete( (void *)monster, (void *)tile, bimap *map);
}
/* wrapper for bimapinsert, also sorts some usage-generalization,
collision-detection, etc for invariant maintenance. Public
interface in .h. User needs to call this to move creatures
to a new square - it will automatically delete them from
the old square. Also call it to insert a new monster into
the map at an arbitrary location. Fails silently if you
try to move a creature onto a tile that's already occupied,
so if you care about that, check before or after by using
creaturelookup. */
void addmonstertotile(creature *monster, tile* tile, bimap *map){
tile *checktile = tilelookup(monster, map);
creature *checkmonster = creaturelookup(tile, map);
/* monster and tile already associated - can't stand on the
same square twice */
if (checktile == tile) return;
/* something else is standing there - fail. */
if (checkmonster != NULL) return;
/* monster and tile are unassociated - make association */
else if (checktile == NULL)
bimapinsert((void *)monster, (void *)tile, map);
else { /* monster associated with different tile.
remove from there and make new assoc. */
bimapdelete((void *)monster, (void *)checktile, map);
bimapinsert((void *)monster, (void *)tile, map);
}
}
Gerry Quinn
d9473c...@a32g2000yqm.googlegroups.com>,
gelatinousm...@gmail.com says...
> On Nov 3, 5:49 pm, Gerry Quinn <ger...@indigo.ie> wrote:
> > The solution is to create a small set of functions which maintain the
> > data structure, and go through those for all cases when monsters move,
> > or are created or destroyed. I did that for my game Lair of the Demon
> > Ape and had no problems from this source.
>
> What data structure do you use?
Basically: the level holds a vector containing all the monsters, and
the tile holds an ID which is essentially the index into the vector.
That's the simplest concept, but since Monster and Character were
separate classes, I couldn't make it quite so simple.
So the reality ws the same idea but slightly more complex, because I
used two vectors, one for monsters and another one for character(s) and
pets, which were a subclass of Monster. The ID was, IIRC, (index+1)
for monsters, and -(index+1) for characters/pets, leaving 0 for an
unoccupied square. But it may have been some other encoding, I don't
recall exactly.
Obviously there are numerous ways to deal with this complication, none
obviously better than any other.
At the end of the day, though, when this was all wrapped up in a few
standard function calls, I had no need to think any more about any of
it. And that's the important thing, whatever your solution.
Note: using a vector of monsters did introduce one interesting
'premature optimisation' bug - in some functions (always within a
single character or monster move) I passed a pointer to a Monster
instance, rather than an index. This worked perfectly well right until
I implememted summoning, and my vector started getting reallocated from
time to time! My clunky fix was to ensure that the capacity of the
vector before every turn exceeded its size by more than the maximum
number of monsters that might be summoned on a turn.
Another clunky choice was to mark dead monsters and leave them on the
vector. Since the game had no going back and not a huge amount of
summons, the vector would not grow too much, and would be cleared and
generated from scratch at the start of each new level.
I'm not sure it's wrong to do things like this. On one basis it may be
a positive indicator in that it means you know the general shape of
your final roguelike and don't have an open-ended project where you
write lots of code to cater for stuff that may never matter. On the
downside, it reduces your options for re-use, though of course in a
roguelike it would be okay to occasionally call a clean-up function to
garbage-collect any dead monsters, so the above wouldn't really be a
roadblock.
- Gerry Quinn
Ray
> On Nov 3, 5:49 pm, Gerry Quinn <ger...@indigo.ie> wrote:
> Going aside into optimization: It seems to me that the best option in
> terms of speed and simplicity would be a bijective hash-map. That way:
> Using a monster* as a key, if the monster is on a tile, return a
> pointer to that tile; otherwise return NULL.
> Using a tile* as a key, if the tile has a monster, return a pointer to
> that monster; otherwise return NULL.
> Invariant: If monster* and tile* are in the BiMap, then BiMap.keyTile
> (BiMap.keyMonster(monster*)) == monster*, and BiMap.keyMonster
> (BiMap.keyTile(tile*)) == tile*.
A problem with this general approach (and the code I posted, now that I
think more clearly about it) is that if you're doing closed hashing
(which the code I posted does, and which is what most folks think of
when they say "hash tables"), then the data structure doesn't match
the use case very well.
As monsters move around and become associated with new tiles, ERASED
entities build up in the table. In fact, after every monster has
taken just eight steps, your table that's 30% occupied will have
only about 4% of its space both free and unerased. After every
monster has taken 16 steps, only 0.233% of the entries will be
free and unerased. In practical terms, this means that shortly
after you start the level, odds are there will be ZERO cells
both free and unerased.
This doesn't slow down insertions, successful lookups, or
successful deletions.
But because a lookup can only stop on an unerased empty node or a
match, the case where there is no match becomes expensive as
unerased empty nodes become scarce. Unsuccessful lookups once
the table is packed with erased entities take time linear in
the size of the table.
That means every time you check and find that a tile is empty (such
as right before moving a monster onto it, or to determine whether @
attacks or moves when the player mashes an arrow key) you're doing
an expensive operation.
For a better match between problem and data structure, this approach
should use open hashing rather than closed hashing.
Bear
skreeg
> Are you planning to replicate X-COM's multi-cell units? That will be a
> greater constraint on your code than anything else.
>
I'll probably never reach such a level of complexity and currently I'm
still toying with how to style this game after I've got the engine
stable. I don't intend to make a strict XCom clone so multi-cell may
never enter into it.
Jotaf
> I'll probably never reach such a level of complexity and currently I'm
> still toying with how to style this game after I've got the engine
> stable. I don't intend to make a strict XCom clone so multi-cell may
> never enter into it.
I once felt the same visceral opposition to the linear search that
Gerry described (when checking for presence of a monster in a tile),
but I lost it after I realized that it was *this exact optimization*
that screwed up most of my RL/RPG projects; they all died with hard-to-
track segfaults. The synchronization issues are smallish at first, but
they'll escalate very quickly as you add features. I'm glad it worked
for Lair of the Demon Ape! But I wasn't so fortunate. So now I use a
single list of objects and linear search. It's fast enough, even in
python; dozens of monsters without a hitch. Remember this is 2009 ;)
Anyway I've got it planned out for the eventuality of needing to speed
it up; I'll just switch from a list to a dictionary (a.k.a. hash map).
The keys will be the objects' positions (a tuple with (x,y), but you
could just as easily use x*map_width+y). Then retrieving an object by
position will be trivial and blazing fast. But for now I don't need
it!
Jotaf
Jeff Lait
> On 4 Nov, 22:44, skreeg <skr...@gmail.com> wrote:
>
> > I'll probably never reach such a level of complexity and currently I'm
> > still toying with how to style this game after I've got the engine
> > stable. I don't intend to make a strict XCom clone so multi-cell may
> > never enter into it.
>
> I once felt the same visceral opposition to the linear search that
> Gerry described (when checking for presence of a monster in a tile),
> but I lost it after I realized that it was *this exact optimization*
> that screwed up most of my RL/RPG projects; they all died with hard-to-
> track segfaults. The synchronization issues are smallish at first, but
> they'll escalate very quickly as you add features. I'm glad it worked
> for Lair of the Demon Ape! But I wasn't so fortunate. So now I use a
> single list of objects and linear search. It's fast enough, even in
> python; dozens of monsters without a hitch. Remember this is 2009 ;)
For a long time, POWDER used only a linear search for monster and item
lookups. No per-tile caches at all. And it ran fast enough on a
Gameboy Advance.
It now has a cache for (x,y) lookups of monsters and the top item in a
tile. When some of my monster AI got smarter it started to bog down
in the deeper levels with lots of monsters and items. You would never
have noticed this on something more modern, like a DS, however. And
when we talk about PC hardware?
Stephan Houben
> In article <38afb97f-2a85-4f4b-b3ee-bcfd1760a903
> @f20g2000prn.googlegroups.com>, skr...@gmail.com says...
>
>> Now, my problem is I don't know quite how to extract this data from
>> the Tile class from elsewhere in my progam when I need it. At times I
>> need to be able to pull the pointer to the occupying Creature if one
>> exists in the vector. I looked at the STL find() algo but have no idea
>> what to make the "value" field. If I go this route I need to find a
>> Creature object in a vector of pointers to Entities. Same with terrain
>> and other Entity subclasses.
> Two obvious ways:
<snip>
A third way which I have used to good result is to not store
the creatures and the items in a dense array, but use a
std::map for them. Most of the tiles don't contain any items
or creatures at all so a sparse data structure is much more appropriate.
In fact, after some experiments with measuring memory and runtime I now
even throw the Terrain in a map. This means your levels don't have
to be rectangular at all, but can be completely free-form.
So in C++:
typedef std::pair<int,int> Position;
std::map<Position,Terrain*> TerrainMap;
std::map<Position,Creature*> CreatureMap;
typedef std::vector<Item*> ItemVector;
std::map<Position,ItemVector> ItemMap;
Also very easy to extend with some additional attribute
which is only very seldomly needed and in this way
doesn't waste some memory for each tile.
BTW, I would also use boost::shared_ptr rather than raw
pointers, but that is an orthogonal issue.
Stephan