What's the best way to implement a level map like this?

Started by
16 comments, last by mike3 12 years, 1 month ago
Hi.

I've got another little dilemma for you. I'm wondering what the best way is to implement this kind of level map for a game in C++ is. The map is supposed to be a regular 2D grid of. What I have is something similar to this:


enum TileType { // not an enum in the current code though but should be changed to one
...
};

class LevelTile {
private:
TileType tileType;
... (various flags and settings in here) ...
public:
...
};

class LevelMap {
private:
...
std::vector< std::vector< LevelTile > > mapTiles;
...
public:
...
};


The trick part is representing the different types of tiles. Here, I have the tiles referred to by a type-field. But then we need a bunch of switch statements to give different tile behaviors based on different types of tiles. Would it be better to use multiple types of LevelTile (i.e. derived classes)? But then comes the questions of:

1. we need to then store an array of pointers,

2. we need to allocate on the heap with new (and that takes more time, doesn't it, than just updating a type field) if we want to change a tile

3. when changing a tile, we need to be able to preserve its flags, which means we need some kind of "copyFlags()" function or something in LevelTile that would need to be called when doing such a change and so would complicate setting one tile to that of another type, or have conversion code for each kind of tile

Though these may not be insurmountable problems (e.g. in issue 3, we could have some kind of "mutateTile()" function in LevelMap that wraps up that calling of copyFlags() etc.). But I'd like to be clear as to which way is the "preferred" way of doing this: multiple types of Tile or type-field.
Advertisement

The trick part is representing the different types of tiles. Here, I have the tiles referred to by a type-field. But then we need a bunch of switch statements to give different tile behaviors based on different types of tiles. Would it be better to use multiple types of LevelTile (i.e. derived classes)?


What kinds of different behaviors are you referring to? It sounds like inheritance would complicate things in this case. Typically each cell of a map would contain an index (or key) into a seperate array (or dictionary) of tile info objects, each of which would store stateless data (such as texture, walkable flag, etc.). Each cell can also contain state data, which is not tied to specific tiles but to each cell. This looks like how you may have things set up, but I'm not sure why you think you will need a bunch of switch statements. For rendering? Animation? Checking collision? All these things can be handled fairly easily by just storing the correct data for each tile type, you shouldn't need switch statements for that.
I suggest to look at a more data-oriented approach.
Think at all the tiles you might want to use in your game. Say we have

  • stone
  • grass - special graphic effect on walk
  • water - animated, special graphics
  • lava - animated, will damage player
  • wall or solid - cannot go there
  • ghost - appears as solid

Then what I'd do would be to write a table and define all the tiles in terms of those basic properties.
That way, a single code entity could be instanced differently such as


Tile::Tile(Image *base, Animation *idle, Animation *walk, uint dmg, bool solid);
Tile stone(LoadImage("Stone.jpg"), nullptr, nullptr, 0, false);
Tile grass(nullptr, LoadAnim("grass-idle-anim"), LoadAnim("grass-walk-anim", 0, false);
Tile grass(nullptr, LoadAnim("lava-idle-anim"), LoadAnim("lava-walk-anim", 10, false);
Tile wall(LoadImage("Wall.jpg"), nullptr, nullptr, 0, true);

Of course this is quite simplified, I am confident you'll figure out there are not so many properties around.

Previously "Krohm"


[quote name='mike3' timestamp='1330387721' post='4917230']
The trick part is representing the different types of tiles. Here, I have the tiles referred to by a type-field. But then we need a bunch of switch statements to give different tile behaviors based on different types of tiles. Would it be better to use multiple types of LevelTile (i.e. derived classes)?


What kinds of different behaviors are you referring to? It sounds like inheritance would complicate things in this case. Typically each cell of a map would contain an index (or key) into a seperate array (or dictionary) of tile info objects, each of which would store stateless data (such as texture, walkable flag, etc.). Each cell can also contain state data, which is not tied to specific tiles but to each cell. This looks like how you may have things set up, but I'm not sure why you think you will need a bunch of switch statements. For rendering? Animation? Checking collision? All these things can be handled fairly easily by just storing the correct data for each tile type, you shouldn't need switch statements for that.
[/quote]

The switch statements would be needed when associating functions with tile types. E.g. a function to be executed on whatever creature moves across the tile.

And doesn't that dictionary have to be a ... gasp ... global?!
So is it possible to avoid the global, or is using a global okay here?

(Why I think a global is needed: the library of defined tile types needs to be accessed from multiple places.)

2. we need to allocate on the heap with new (and that takes more time, doesn't it, than just updating a type field) if we want to change a tile

3. when changing a tile, we need to be able to preserve its flags, which means we need some kind of "copyFlags()" function or something in LevelTile that would need to be called when doing such a change and so would complicate setting one tile to that of another type, or have conversion code for each kind of tile


Change a tile? You still would NOT create an entire instance for every tile on your map. As already suggested, create a list of prototype tiles in an array with all common data (textures, etc.), make all "unique" data function parameters and there shouldn't be any overhead worth mentioning. tile[y][x]->protoTile->onSomeEvent(x, y, list_of_stuff_on_tile).

Krohm suggested an easy way, but unless you clearly define your requirements from the beginning and don't care about modding or extending, this is going to be a pain later on. Imagine having defined tons of tile types like this. Now you figure "hey, a special healing tile would be neat" or "how about a teleport tile"? You'd have to extend the struct and add a silly amount of 0s to every tile, just because ONE is special.

This is easier solved by either virtual functions in your prototype tile types or simple function pointers. The latter has the big advantage of not needing a separate class and then having only this one single instance. It might also be a lot easier to change later on to execute an external script instead (allowing to add new tile types and their behavior without having to touch the actual code itself).

In that case, when a tile is "activated" you can do something like tileInfo[tileId]->onActivated(...) (downside compared to virtual functions with empty default implementation: you will have to either check the function pointer first or always assign some empty default function yourself).

Your average tile might not even need any information other than an id or pointer to its tile info. Eventually you will probably still need some generic info field (to store state or orientation, etc.). The exact meaning of those however might be completely different for every tile. You just stuff that data into the prototypes functions and it will know what to do with it.
f@dzhttp://festini.device-zero.de

[quote name='mike3' timestamp='1330387721' post='4917230']
2. we need to allocate on the heap with new (and that takes more time, doesn't it, than just updating a type field) if we want to change a tile

3. when changing a tile, we need to be able to preserve its flags, which means we need some kind of "copyFlags()" function or something in LevelTile that would need to be called when doing such a change and so would complicate setting one tile to that of another type, or have conversion code for each kind of tile


Change a tile? You still would NOT create an entire instance for every tile on your map. As already suggested, create a list of prototype tiles in an array with all common data (textures, etc.), make all "unique" data function parameters and there shouldn't be any overhead worth mentioning. tile[y][x]->protoTile->onSomeEvent(x, y, list_of_stuff_on_tile).

Krohm suggested an easy way, but unless you clearly define your requirements from the beginning and don't care about modding or extending, this is going to be a pain later on. Imagine having defined tons of tile types like this. Now you figure "hey, a special healing tile would be neat" or "how about a teleport tile"? You'd have to extend the struct and add a silly amount of 0s to every tile, just because ONE is special.

This is easier solved by either virtual functions in your prototype tile types or simple function pointers. The latter has the big advantage of not needing a separate class and then having only this one single instance. It might also be a lot easier to change later on to execute an external script instead (allowing to add new tile types and their behavior without having to touch the actual code itself).

In that case, when a tile is "activated" you can do something like tileInfo[tileId]->onActivated(...) (downside compared to virtual functions with empty default implementation: you will have to either check the function pointer first or always assign some empty default function yourself).

Your average tile might not even need any information other than an id or pointer to its tile info. Eventually you will probably still need some generic info field (to store state or orientation, etc.). The exact meaning of those however might be completely different for every tile. You just stuff that data into the prototypes functions and it will know what to do with it.
[/quote]


So then if I'm getting this right, you're suggesting a global(!!! argh !!!) array of tile prototypes, accessible from anywhere it's needed, and each map element is a reference to a tile prototype? But then what if we need to store information that can vary between individual map tile elements as opposed to between tile types?

And when you mention about using function pointers to make more extensibility, do you mean keeping an array of them in the thing to which new ones can be added? Like if we need that healing tile, and need to add a function for that, we can add it to that array instead of having to add a field that then needs to be filled on all tile types (which offers no advantage to Krohm's method)?

And what do you mean by "stuff the data into the prototype functions"?

Do you mean something like this?:


class TileRepresentation {
... graphics, anim., etc. stuff ...
};

class TilePrototype {
private:
TileRepresentation *tileRep;
int intrinsicFlag1;
int intrinsicFlag2;
SomeFunctionPtrType funcPtr1;
SomeFunctionPtrType funcPtr2; // but what if we need more functions in some kinds of tiles and less in others?
public:
...
};

class MapCell {
private:
TilePrototype *proto; // points into the pre-baked list of tile prototypes
int someCellSpecificFlag1;
int someCellSpecificFlag2;
public:
...
};

class Map {
private:
std::vector< std::vector<MapCell> > mapData;
...
public:
...
};
Why would this array be global? Every array can easily be made non-global by putting it in a .cpp file and just offer a global "getTilePrototype(id)" function. Or a static "get(id)" function of TilePrototype. The rule of "avoid globals" doesn't mean "avoid global functions" (in fact, you should avoid the opposite.. stuffing functions into classes when there is no reason for it).


And what do you mean by "stuff the data into the prototype functions"?

Do you mean something like this?:


I mean that the prototype functions take the tiles unique data as parameter. In fact, forget that and just pass a pointer to the actual tile, since the function might have to modify the tile (activating a door will obviously have to change its state).

If you need more functions, you add more and default initialize to 0 (or use empty virtual functions). Sure, you can just create one huge switch/case function for every event based on the type, but which one makes more sense very much depends on how flexible you want to be in terms of modding and extending. The switch/case version is for example a lot easier to debug, because the code is clearly telling you what goes where in a single place.

How many events will you need? Typical stuff like "onEntered", "onActivated", "onHit" and maybe quite important "onUpdate". The key is to be generic with your events and not just code reactions. So no "onZombieEntersWearingMetalArmor" and no "dealDamageToZombie" but simply "onEntered". Let the function figure out what entered and how to respond.

At the same time you shouldn't spend too much time on finding "the one true way to do it", because such a thing doesn't exist. Else you could argue that a vector of vector might not be as cache friendly and convenient to iterate over than a regular vector of size x*y. If you have a very good idea of what you want to do you can make plans and decisions. If you don't, trying to prepare for "everything you ever may like to do" will very efficiently keep you from ever really getting started.

Another thing is: only one tile per cell? What if I want to use "stone floor" and "wooden chair"? Would there be tons of tiles for each combination of "floor type" and "object on floor"? Not saying you should go overboard, but for example JA2 has a ton of layers in its map (ground, objects, structures, shadow, mercs, roof, onroof) AND each cell on each layer can have any number of tile elements. Of course the main reason for all those layers is that its a 2D iso engine. If you use actual 3D tiles or a simple top down view (where tiles don't overlap), you won't have to worry quite as much about what to draw when.
f@dzhttp://festini.device-zero.de

Why would this array be global? Every array can easily be made non-global by putting it in a .cpp file and just offer a global "getTilePrototype(id)" function. Or a static "get(id)" function of TilePrototype. The rule of "avoid globals" doesn't mean "avoid global functions" (in fact, you should avoid the opposite.. stuffing functions into classes when there is no reason for it).


However, it seems that even "hidden globals" can be bad too:

http://c2.com/cgi/wi...VariablesAreBad


Hidden Globals -- hidden globals have a well-defined access scope, and would include, for example, private 'static' variables in classes and 'static' variables in '.c' files and variables in anonymous namespaces in C++. This solution cages and localizes globals rather than tames them - you'll still get bitten when it comes to concurrency and modularization and testing/confinement, but at least all such problems will be localized and easy to repair, and there won't be linking problems.
[/quote]

So, what to do? Or is this a case where a global may really be the best solution? Note that it mentions as one of the biggest, if not the biggest problem with globals is:


Non-locality seems much much more convincing than any of concurrency, namespace, and memory allocation. However, the non-locality issue is much bigger than it seems. I'm thinking of situations when you come back to the code 2 weeks later, look at String important = global.getSomeImportantInfo(), and have to figure out why 'important' is getting the wrong value. Sure, non-locality describes it, but if Bob (above) asks "Why?" and Alice replies "Non-locality", I don't think Bob would learn the lesson.
[/quote]

So how to avoid this? Or is it necessary in this case -- really necessary? I.e. are these pages to be taken as inflexible dogma, or to be taken instead as more stuff along the lines of "don't just use this thing [globals, in this case] willy-nilly"?

[quote name='mike3' timestamp='1330733046' post='4918751']
And what do you mean by "stuff the data into the prototype functions"?

Do you mean something like this?:


I mean that the prototype functions take the tiles unique data as parameter. In fact, forget that and just pass a pointer to the actual tile, since the function might have to modify the tile (activating a door will obviously have to change its state).[/quote]

You mean have member functions of TilePrototype that take MapCells as argument? But doesn't that set up kind of a circular dependency between the two? Isn't that bad? Or what? What did you have in mind for the structure of the actual classes/data structures/etc. involved ("outline" code like I posted would be best)?

And I just noticed a new problem. Consider the "onMove" event. There may be certain kinds of things that should occur on a move to very specific tiles, e.g. one particular tile on a map, not one kind of tile. This means that "onMove" needs to be associated with individual map elements, no? Though I suppose one could then include in "MapCell" an onMove() function that mirrors that in TilePrototype (and probably have onXXXX() functions to mirror all events that need to go to TilePrototype and call the functions in the private TilePrototype member, but is this mirroring bad? If so, how to avoid it?) and include a functor that supplies an auxiliary move function, e.g. something like include a data member "AuxMoveFuncObject auxMoveFunc" in MapCell, which can be configured on a per-cell basis, and the onMove() function in MapCell wraps the calls to both. Is this good? Or what?


So, what to do? Or is this a case where a global may really be the best solution? Note that it mentions as one of the biggest, if not the biggest problem with globals is:


What to do indeed, especially since they neglect to mention that issues like concurrency won't magically go away just because the data is wrapped in 20 layers of object orientation. It doesn't matter if it is a simple array (with global access functions) or buried in an object that everybody has a reference to. Two threads accessing it at the same time will be a problem.

Even the non-locality example basically skips how to change your design. The problem isn't so much that the data is global, but that everybody is supposed to get to it somehow. In fact, even when you have a non-global object and just pass around references to it, how is that improving the basic problem of too many parts of the code touching it? It may even just hide the actual problem behind 10 layers of indirection, making it absurdly hard to debug.

Avoiding globals is a matter of designing (and limiting) your dependencies, not of candy wrapping some data and still try to use it from everywhere.

It's a bit like "thou shalt not goto" resulting in people not writing better code, but replacing goto with even less readable and more idiotic constructs to simulate a goto. If you ask "how to not make it global, but I still need it _everywhere_" then that's your problem right there.

You mean have member functions of TilePrototype that take MapCells as argument? But doesn't that set up kind of a circular dependency between the two? Isn't that bad? Or what? What did you have in mind for the structure of the actual classes/data structures/etc. involved ("outline" code like I posted would be best)?[/quote]

It's not always a matter of "but text book X said this is bad", but of "what's the lesser of two evils". If you can come up with a good way to do what needs to be done and which doesn't add 10 times the complexity for the sake of avoiding a circular dependency, then of course go for it.


Without any error checking etc.

// prototype.h
class Tile;
class TilePrototype
{
static const TilePrototype& get(TileId id);
void (*onActivated)(Tile& tile);
}

// prototype.cpp
vector<TilePrototype> prototypes;

const TilePrototype& TilePrototype::get(TileId id) { return prototypes[id]; }

// tile.h
class Tile
{
TileId tileId;
TileData data;
};


If you go with virtual functions, the vector needs to store TilePrototype*, if you go with scripting, the function pointer should instead be whatever script handle your favorite method is using (might be strings or wrappers or...).


And I just noticed a new problem. Consider the "onMove" event. There may be certain kinds of things that should occur on a move to very specific tiles, e.g. one particular tile on a map, not one kind of tile.[/quote]

I don't know how large you intend your maps to become. Personally I'd try not to bloat my map elements with lots of functions just because maybe some day I might like to do such and such. If this particular reaction to a very specific tile is not related to the tile or tile type itself, you have found your first example of why games use triggers as "invisible" game objects. For this special stuff, you don't have the tile perform some super special reaction, but you create a single trigger and "place" it on that tile.

You really don't want to end up with every tile having members like
MySpecialOnMove, MySpecialOnItIsFriday, MySpecialOnLightLowerThan10, just because on level 24 you have this one tile that when stepped on at the wrong time in darkness will close a door.

You can of course go ahead and "unify" those concepts by removing the above function pointers/virtual functions and instead simply place certain triggers on certain tiles by default. But keep in mind that moving too much stuff from prototype to tile instance can quickly increase your memory usage.
f@dzhttp://festini.device-zero.de

This topic is closed to new replies.

Advertisement