Question regarding 2D map array.

[jupiter 999]

Good day, everyone,

I had a question that bugs me for quite long time already.
Say, I had a 2D array to represent my wilderness map.
What's the pros and cons if:-
1) each cell in the 2D array shall store int that represents terrain
type using enumeration, or, in other words, a 2D array that stores
terrain ID, or,
2) each cell in the 2D array shall store the instance of terrain
class.
I'd tried to find articles or readings from web, but not quite
successful.
I hope to hear as many comments / advices from you all. Appreciate all
of them.
Thanks in advance.

Best Regards,
jupiter999

[Radomir Dopieralski]

We had this discussion here several times and the approach 1) seems to
be much more sane and convenient, not to mention memory problems with
approach 2) when you make large maps.

To summarize previous discussion, a map square is not a game object in
this case -- the map as a whole is. The monsters should not hold a reference
to the square on which they stand -- they should have a reference to the
map, which knows where each creature is and takes care of moving them.

This approach not only results in clearer structure, but also makes it easier
to implement various AI and FOV algorithms.

--
Radomir Dopieralski, sheep.art.pl

[Tapio]

lauantaina 24. maaliskuuta 2012 11.20.54 UTC+2 Radomir Dopieralski kirjoitti:

Well, this depends on the situation. For example, my latest 7DRL uses lots of colors and dynamically generated tiles - I don't find it that sane to create thousands of tile enums to accommodate that, but rather have instances of a Tile class which color and other attributes I can modify freely and conveniently.

Furthermore, by having an instance for each tile, I can attach extra attributes dynamically (e.g. there's an item in this tile). That way I have a fast and simple O(1) complexity look-up for what's there, instead of e.g. iterating over a list of stuff in Map class to check if coordinates match.

These days I'm not worrying about memory consumption much, but arguably in my use case there is actually a memory benefit: as most tiles are unique, putting them to a straight array is not only easier, but also saves you the memory of the int array (it's assumed that the tile prototypes would consume roughly the same amount of memory as the tile instance array).

A map class is still useful for managing the tiles And I do think monsters should be kept in separate list, although that doesn't need to prevent the tiles from having a reference to the current occupant for speedy look-up.

[Radomir Dopieralski]

On 2012-03-24, Tapio <tapiov...@gmail.com> wrote:
> lauantaina 24. maaliskuuta 2012 11.20.54 UTC+2 Radomir Dopieralski kirjoitti:
>> To summarize previous discussion, a map square is not a game object in
>> this case -- the map as a whole is. The monsters should not hold
>> a reference to the square on which they stand -- they should have
>> a reference to the map, which knows where each creature is and takes
>> care of moving them.
>>
>> This approach not only results in clearer structure, but also makes it
>> easier to implement various AI and FOV algorithms.
>

> Well, this depends on the situation. For example, my latest 7DRL uses
> lots of colors and dynamically generated tiles - I don't find it that
> sane to create thousands of tile enums to accommodate that, but rather
> have instances of a Tile class which color and other attributes I can
> modify freely and conveniently.

Of course you don't create thousands of enums for all combinations of your
parameters. You create a 2d array (or dict, or list with coordinates) for
every parameter you need to track.

> Furthermore, by having an instance for each tile, I can attach extra
> attributes dynamically (e.g. there's an item in this tile). That way
> I have a fast and simple O(1) complexity look-up for what's there,
> instead of e.g. iterating over a list of stuff in Map class to check if
> coordinates match.

Since when is dict lookup O(1)?

> These days I'm not worrying about memory consumption much, but arguably
> in my use case there is actually a memory benefit: as most tiles are
> unique, putting them to a straight array is not only easier, but also
> saves you the memory of the int array (it's assumed that the tile
> prototypes would consume roughly the same amount of memory as the tile
> instance array).

The memory taken by the instances can baloon very fast with your map size,
since they grow quadratically or worse.

> A map class is still useful for managing the tiles And I do think
> monsters should be kept in separate list, although that doesn't need to
> prevent the tiles from having a reference to the current occupant for
> speedy look-up.

Unless all of your AIs are based on cellular automata, you will not need
that current occupant check very often.

(Please wrap long lines.)
--
Radomir Dopieralski, sheep.art.pl

[yam655]

This is basically:

1. Each terrain cell references a generic instance of a type. In the simplest cases, this could be an enum or an int -- or even a 'char' indicating the standard visual of the terrain.

2. Each terrain cell is separately instantiated. Now, if there is no per-instance data for the terrain, this has overhead without any benefit. If you need per-cell data -- such as for fully destructible/modifiable terrain -- this is the only way to do it if you want to maintain state.


My preferred solution is a hybrid approach. When creating the map, each cell gets a generic/common reference. When the player starts modifying the terrain the terrain changes to an instance and maintains the state.

Such a hybrid approach works for more than just terrain. You can add generic instances of monsters and instantiate them when they wake. You can instantiate objects when something picks them up (or looks at them if they're some sort of random-artifact).

[Krice]

On 24 maalis, 11:41, jupiter 999 <jupiter999jupiter...@gmail.com>
wrote:

> 1) each cell in the 2D array shall store int that represents terrain

> 2) each cell in the 2D array shall store the instance of terrain

I think 1) is better for simple roguelikes where the terrain has
no other function than block or allow movement. 2) is better if
you want to create a complex roguelike, because terrain tiles
as objects allow more flexible options without special
hacky code you would need in 1).

[jupiter 999]

On Mar 25, 11:20 am, yam655 <yam...@gmail.com> wrote:
> This is basically:
>
> 1. Each terrain cell references a generic instance of a type. In the simplest cases, this could be an enum or an int -- or even a 'char' indicating the standard visual of the terrain.
>
> 2. Each terrain cell is separately instantiated. Now, if there is no per-instance data for the terrain, this has overhead without any benefit. If you need per-cell data -- such as for fully destructible/modifiable terrain -- this is the only way to do it if you want to maintain state.
>

Regarding your point 2, well for my case, say I have a 5x5 map just
like this:-
#####
#...#
#.^.#
#.~~#
#####

where, # is a wall, ^ is a trap, ~ is a water, and . is a floor.
But all I need to do is create 4 terrain instances only, in which
referenced by these 25 map cells accordingly. Does is still means
"Each terrain cell is separately instantiated"?
I supposed there should be no overhead issue in this way.
But do comment, because I'm still not sure how reference type would
benefit over value type in map array.
Appreciate your advice.
Thanks~

[jupiter 999]

Agree. At the moment I'm using the 1st method. But most of the time I
felt that my coding are a bit hacky...
I can see that if I change them into reference type in map array, the
coding should be not that hacky...
But I wish to know what's the downside if I use reference type for my
map array...
That's why I brought up this old topics again because perhaps there
are new perspective / findings regarding this issue.
Again thanks for all your responses. I'll read again and again to
fully understand and digest them for my game design.

[Tapio]

sunnuntaina 25. maaliskuuta 2012 2.11.23 UTC+2 Radomir Dopieralski kirjoitti:

> On 2012-03-24, Tapio <tapio...@gmail.com> wrote:
> > Furthermore, by having an instance for each tile, I can attach extra
> > attributes dynamically (e.g. there's an item in this tile). That way
> > I have a fast and simple O(1) complexity look-up for what's there,
> > instead of e.g. iterating over a list of stuff in Map class to check if
> > coordinates match.
>
> Since when is dict lookup O(1)?

> --
> Radomir Dopieralski, sheep.art.pl

You are right, that O(1) doesn't hold. I think I was simultaneously also
thinking of other languages than JavaScript. My main point was that I don't
think it's automatically more convenient and better. I think Krice sums it up
perfectly:

> On 24 maalis, 11:41, jupiter 999 <jupiter999jupiter...@gmail.​com>
> wrote:

> > 1) each cell in the 2D array shall store int that represents terrain

> > 2) each cell in the 2D array shall store the instance of terrain
>

[Krice]

On 25 maalis, 11:16, jupiter 999 <jupiter999jupiter...@gmail.com>
wrote:

> That's why I brought up this old topics again because perhaps there
> are new perspective / findings regarding this issue.

The way I see this is that 2D array of ints is just an array
container of int type objects. So there is no difference
in that aspect, int is just a simple object that can change
itself to another int (terrain type). Making terrain tiles
"real" objects simply allows more dynamic data to be stored in
a tile.

What I have thought of is to make no difference between
terrain objects and other type of objects. Terrain objects are
just big rectangular pieces of object with location and other
data just like monsters or items. The distinction between
simple terrain and other objects creates a need for a duplicate
system for each one which I have found out to be a source of
various problems.

[Gerry Quinn]

In article <5577914.869.1332645625101.JavaMail.geo-discussion-
forums@ynim7>, yam...@gmail.com says...

> My preferred solution is a hybrid approach. When creating the map, each cell
> gets a generic/common reference. When the player starts modifying the terrain
> the terrain changes to an instance and maintains the state.

I incline towards a Tile object, containing an int for terrain type, a
reference to a possible occupant, a reference to an item or pile of
items, and maybe some flags (e.g. whether the square has been seen by
the main character).

- Gerry Quinn

[Jeff Lait]

On Saturday, March 24, 2012 4:41:12 AM UTC-4, jupiter 999 wrote:

> Good day, everyone,
>
> I had a question that bugs me for quite long time already.
> Say, I had a 2D array to represent my wilderness map.
> What's the pros and cons if:-
> 1) each cell in the 2D array shall store int that represents terrain
> type using enumeration, or, in other words, a 2D array that stores
> terrain ID, or,
> 2) each cell in the 2D array shall store the instance of terrain
> class.

3) It doesn't matter to users of your map class which one of those
it is.

By users, I mean the rest of your code base outside of map.C.

I'm strongly against "Tile Classes" - they are really painful to keep
up to date and result in array of struct implementations rather than
structs of arrays. For any reasonable efficiency, the latter is always
preferable as you can take advantage of different storage algorithms
for different parts of your virtualized tile class.

To pick monsters, for an example. If you store them inside your
tile, you can end up with very expensive searches when you ask for
"All monsters in this area" since you have to iterate over all tiles
in that area, which might be much larger than the total number of
monsters in your game! Likewise, if the monsters live only in the
tile, you have a lot of very careful code to write when you move a
monster for fear of accidentally leaving one orphaned. With a
separate list of monsters that is the "official" monster list, and
the in-tile storage of monsters being but a cache, you can ensure
there are at worse drawing peculiarities with these mistakes rather
than having monsters just disappear.

With this in mind, it is *very* important not to expose these tiles
to anyone outside of your map class. If the monster class can go
modifying tile contents, any caching structure you build in your
map class won't be properly invalidated.

This doesn't mean you can't have all the convenience of something
that looks like a tile class. You just have to realize you never
actually wanted tiles in the first place.

The thing that you should be exposing is a very different class:
Position.

class POS
{
public:
POS delta(int dx, int dy);
TERRAIN_ENUM terrain() const { return map->getTerrain(x, y); }
MONSTER *monster() const { return map->getMonster(x, y); }
private:
int x, y;
MAP *map;
};

This is a flyweight object you can construct and use to refer to
locations on the map, (ie, tiles!) but is *not* a tile itself. It
will have all the functions you want to read and edit tiles: getting
the terrain, monsters, items, etc. But it will know how to pass that
through the map.

With this approach, the exact storage in MAP is quite moot. There
are no syntax advantages to an array of heavy weight tiles, while
there are significant advantages to having multiple arrays of stuff...

class MAP
{
public:
...
private:
GRID<TERRAIN_ENUM> myTerrain;
GRID<MONSTER *> myMonsterCache; // Per square cache
std::vector<MONSTER *> myMonsters; // All monsters
GRID<ITEM *> myItemCache; // Only stores top item!
std::vector<ITEM *> myItems; // All items
GRID<float> myUraniumOre; // Random attribute
};

Of course, you can have your name-value pair dictionary of grids
to store arbitrary run-time attributes. You can also replace a 2d
dense grid with any other structure you like.

Now, what do we do in the monster class?

With tiles-as-objects, people might do
class MONSTER
{
TILE *myTile;
};
which means every tile needs to store it's x,y coordinate! And, if
you want to find the positions next to the tile, you need to store a
back pointer to the map! Ugh!

Instead,
class MONSTER
{
POS myPosition;
}

Note POS is not a pointer - the monster owns this object. (For those
who think Java means they can forget ownership: no, it doesn't, this
is important.)

In summary:
1) It is essential how you implement the guts of your map is not polluting
the rest of your roguelike.
2) The convenience of TILE * only occurs if you expose it, violating 1.
3) You will want a POS class anyways to consolidate (x, y) pairs. And
very quickly after doing that you'll notice you really want (x, y, map).
4) So, make POS your TILE class.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

[Gerry Quinn]

In article <24220181.871.1333399722352.JavaMail.geo-discussion-
forums@ynjw14>, torespon...@hotmail.com says...

> To pick monsters, for an example. If you store them inside your
> tile, you can end up with very expensive searches when you ask for
> "All monsters in this area" since you have to iterate over all tiles
> in that area, which might be much larger than the total number of
> monsters in your game! Likewise, if the monsters live only in the
> tile, you have a lot of very careful code to write when you move a
> monster for fear of accidentally leaving one orphaned. With a
> separate list of monsters that is the "official" monster list, and
> the in-tile storage of monsters being but a cache, you can ensure
> there are at worse drawing peculiarities with these mistakes rather
> than having monsters just disappear.

The way I work it is that monster positions are indeed doubly-stored.
Monsters don't live in the tiles, but the tiles do contain references to
the monsters that are currently in them. [Yes, data is duplicated.
Sometimes efficiency requires this.]

What this means is that every time you move a monster, you must do so by
calling Map.MoveMonster(). Once you do that, the end result is much
like the way you have it, just implemented in a different way. The
tiles are real rather than virtual, but non-Map classes don't get to
play with them freely. In C++ you can enforce this (sort of) with const
qualifiers. In languages where references are passed around
promiscuously you must often make contracts with yourself, but it's not
too hard really.

- Gerry Quinn

[Konstantin Stupnik]

This is exactly the same approach I've used in Wizard's Quest.
Can't say anything bad about it.
I use refcounting smart pointers for almost everything.
Monsters are stored in timeline and in tile of the map.
As for "All monsters in this area" - I have relatively big
maps with significant amount of monsters.
Iterating over area while checking if there are monsters in tiles
doesn't seems way less efficient than iterating over all monsters of
the level while checking if they are in range/area.