Data Structure for Maps?

Here''s how I do tile grids:
--
// UNTESTED CODE

// Tile Grid
unsigned char *tileGrid;

// Initialization:
unsigned short gridSize = mapXSize * mapYSize;
tilegrid = new unsigned char [gridSize];
--
Then, address the appropriate square with x+(y*mapXSize).
The main point is that the array is allocated dynamically, and you can deallocate and reallocate each time you load a new level...

Yeh, it''s a little hard to get used to the addressing, but I did...

Why not just make a Tile class? Your map would then be a 2D array of Tiles. The tile class would store pointers to the correct Bitmap and any overlay Sprites that need to be draw there as well. The only other thing you would need is an array for the Bitmaps and Sprites, but you will only need it to set the pointers in newly created Tile object and then you can leave it alone. Using a Tile class is much more flexible too, since you can easily add extra info to your tiles (like visibility if fog of war is on or anything else you can imagine...)

Check out the GPI project today!

Hi

Thank you for your answers.

To VGASteve:

Yes. Doing allocation of maps/levels dynamically is a good idea. But I originally left it out of my post because that wasn''t really the problem. The problem is the container (array, list, big bitmap or whatever) that holds your tile bitmaps. You didn''t specify how you intend to draw the tiles with the correct bitmaps.

To chippydip:

Yes. I have also thought of using a class for each tile. And I propaly do so in my game. Using pointers to bitmaps at runtime is a very good idea. Then I can add and remove bitmaps to the list of all the available bitmaps without worying of destroying indexes in the map.

But pointers can''t be stored to a disk. So here is my next question:

What should I then write in my *.map files to indentify the type of tile on a given (x,y) coordinate in the map? Should I still use constants for each type of tile? Or should I instead name each type of tile with a string, as for example ''STONEFLOOR'', ''GRASS'' and so on?

How do you ensure that the map/level editor and the game "agrees" on which tiles can be used in the game and the identifiers used to describe each type of tile is consistent between the game and the editor?

For example if i place a ''grass'' tile on (x,y) in the editor, the game should be able to read this from the map file and not place a ''stone'' tile on that coordinate instead.

Regards

nicba

I would suggest using constants, the computer does not need to store 16bytes of data to destinguish a stone texture from a grass texture, a 1 or 2 byte field will do for it.

As for the editor agreeing with the game on what each graphic is, just use the same data files between the two. This way any modifiactions to the data files will be reflected by both.

Hope that helps.

OneEyeLessThanNone

quote:

---

Original post by OneEyeLessThanNone

I would suggest using constants, the computer does not need to store 16bytes of data to destinguish a stone texture from a grass texture, a 1 or 2 byte field will do for it.

As for the editor agreeing with the game on what each graphic is, just use the same data files between the two. This way any modifiactions to the data files will be reflected by both.

Hope that helps.

OneEyeLessThanNone

---

Yes it helps. Thank you for answering. I think I have figured out how to do it now.

The reason I suggested using strings instead of constants is that I plan to use the same set of tiles for more than one map. So the identifiers for each tile must never change once it has been assigned to a specific tile type. Even if you add new tile types to the set or edit the existing ones.

I thought that maybe giving each tile a descriptive name would make this easier to achieve, but after seening your post and thinking things over a second time I realized that the user never needed to see or modify these identifiers. It could all be handled by the map editor. So probality I go for the constants after all.

Thanks for all the answers.

Regards

nicba

Identifiers or constants:

One of the things I often see overlooked in almost all samples of codes is the enum type. It''s really useful for combining constants in a sensible way.

At its simplest form:

typedef enum {
  
  TILE_GRASS_1 = 0,
  TILE_GRASS_2,
  TILE_GRASS_3,
  TILE_GRASS_4,
  TILE_WATER_1,
  TILE_CHEST_OPEN,
  TILE_CHEST_CLOSED,
  TILE_OAK_TREE,
} TileTypes;

In this case, each of these defines are given numbers, the first starting with 0 and going up from there. This is great because in your code you can refer to an index as tile_array[TILE_OAK_TREE] and never have to worry about where exactly it is going. You would do a LoadBitmap(&tile_array[TILE_OAK_TREE], "oaktree.bmp") so that it would be loaded into TILE_OAK_TREE and from there on you can refer to it anytime you need to. I really like using enums to handle indexing into arrays. I often use them like this

typedef enum {
  
  OBJECT_CLOCK = 0,
  OBJECT_DOOR,
  OBJECT_MAN,
  OBJECT_KEY,

  OBJECT_LIST_SIZE, // this must always be last
} ObjectList;

struct ObjectType g_ObjectArray[OBJECT_LIST_SIZE];

This lets me add new objects after OBJECT_KEY and it will expand the array for me. I just need to be sure that OBJECT_LIST_SIZE is always last in the list. The other benefit is that I now always have the size of the array for loop code:

for (int i = 0; i < OBJECT_LIST_SIZE; i++)
{
  if (object_list != NULL)
  {
    free(object_list[i]);
    object_list[i] = NULL;
  }
}

This code will always free all the objects no matter how many I have in the enumerated type list.

Additionally, you can specify a numeric equivalance often:

typedef enum
{
  // zone 1 objects
  ZONE1_CLOCK = 0,
  ZONE1_DOOR,
  ZONE1_MAN
  // zone 2 objects
  ZONE2_HUMAN = 20,
  ZONE2_PERSON,
  ZONE2_TREE,
  // zone 3 objects
  ZONE3_DOG = 40,
  ZONE3_ROBBER,
  // ..

After each number is set, the following constants are an increment of the above. ZONE2_PERSON == 21, ZONE3_ROBBER == 41. This is a good scheme if you are refering to objects in zones in a file and don''t want to have to shuffle numbers around too much when you add a new bitmap - you just make all ZONE2 objects in the object_list[20 .. 39] range..

Anyways..

I've thought about various ways to implement tiles and this is what I came up with...

I'm intending this to be for a game similar to Jagged Alliance/X-com but with more emphasis on character development.

I use a linked list approach so I can stack as many or as few tiles on top of each other as I want. The npc* could (and probably should) be a byte that indexes a particular non-player character in an array.

struct tile_type{
_8pos alt,//altitude or y-offset
gfx,//index to gfx
flags;//misc flags
restrict_type restrictions;//line of sight/walking
tile_type* next;//next tile in list
};

class base_tile{
private:
_8pos myflags,//misc flags
mygfx;//gfx index
restrict_type myrestricts;//line of sight/walking
npc* mynpc;//npc at this spot?
item* myitem;//item?
tile_type* mycurrent,//for list
myfirst,
myprevious;
...
Hopefully the formatting wasn't too screwed up.

And then I would have an array of base_tile s:
base_tile map[MAX_Y][MAX_X];

Edited by - Jman on 4/11/00 4:11:53 PM

You might want to consider a more flexible method for storing the tile indexes in a file. If you use a simple enum then the program (and editor, etc.) will need to be rebuilt any time a new type of tile is added to the system. Instead, why not have a header section in your *.map file that defines constants for the bitmap resources that will be used in that map. It might look something like this:

0 "grass.bmp"
1 "stone.bmp"
2 "forest.bmp"

... etc ...

<map tile entries go here...>

The map tile entries would then include the number (0..n) for the desired bitmap. In effect you are storing both the array of bitmaps and the arrray of tiles. This method will allow you to add tiles whenever you want without changing your code yet doesn''t require all the overhead of a tile name for each map tile (and it should be easier to reassemble both data structures with this format)

Also, the header does not need to include the file name of the bitmap. It could include other information if you decided to use a more complex resource management system, but the basic priciple remains the same... just provide whatever info you need to read in the correct tile image.

Check out the GPI project today!

Hi fellow Dane...I'm making a tilebased game (and an editor) at the moment. Here is my fileformat.
It is not fancy but it works...

int number_of_tilescreens //number of bmp´s with tiles.

for each number_of_tilescreens
{
int TileXSize //size of tiles in particular bmp.
int TileYSize
int Transparency //if =0 blit from bmp using no trans.
char[256] filename //bmp filename
}

int number_of_layers

for each number_of_layers
{
int MapSizeX
int MapSizeY
int TileSizeX
int TileSizeY
}

The tiledata:

for each layer I just save bunch of shorts at the end of the file...The data can easily be extracted by using the data above...

short Gfx_screen
short Tilenr

I don't use arrays to store my tiledata in memory.
I load the tiledata into memory-chunks freed by malloc().
This makes it more difficult to find a specific tile but not much.


-- There IS something rotten in the state of Denmark --

Edited by - granat on 4/13/00 1:08:14 AM

Edited by - granat on 4/13/00 1:12:51 AM

Oh yeah...One more thing...

I use a seperate layer to indicate tiletypes..
A layer that will not be drawn...
100% green tile for grass, brown for dirt etc...

This way i can have terrain like grass, stone, whatever.
It''s a bit easier to keep track of 10 terrain-types than
100´s of normal gfx-tiles.

quote:

---

Original post by chippydip

You might want to consider a more flexible method for storing the tile indexes in a file.
...
It might look something like this:

0 "grass.bmp"
1 "stone.bmp"
2 "forest.bmp"

... etc ...

---

I actually (independently of this thread) decided to go with this method a couple of days ago. I don't want to hardcode in either the filenames or the order of my tiles, especially since they are going to be changing throughout the course of my project. I also want it to be trivial for end users to be able to supply their own tilesets for their own maps. It just requires a little more effort on the part of the level editing program, which now has to compile a list of 'used tiles' and generate the array from that, which is a little extra work but brings all the flexibility you mentioned.

As for my representation of my map...

class TerrainType
{
Graphic* theTile; // What to display for MapSquares using this terraintype
// Impassibility and line of sight info
};

class MapSquare
{
TerrainType* itsType; // What kind of terrain do we have here
int x, y; // Our position, sometimes helpful to have it stored here
// Also - Fog of War, ownership (whose territory)
// List of creatures here, list of items here, etc
};

class Level
{
MapSquare* [MAP_WIDTH][MAP_HEIGHT] map;
}

Member functions left out for clarity.

Note that the Level class exposes the main interface for the rest of the program, which gets info from MapSquare, which often gets it from TerrainType. So, instead of:
bool can_walk_here = theLevel.map[x][y]->itsType->CanWalkHere();
I can use:
bool can_walk_here = theLevel.CanWalkHere(x, y);

This means my Level class is a little more tedious to write (effectively duplicating functions already in the other 2 classes), but the overall code is cleaner, and I can change the implementation of both MapSquare and TerrainType behind the scenes, or even remove them and replace with other classes, without breaking AI or Pathing code. I'm sure this is a formalised Design Pattern, but I have no idea which

Hope that helps someone...

Edited by - Kylotan on 4/13/00 4:36:42 AM

quote:

---

Original post by granat

Oh yeah...One more thing...

I use a seperate layer to indicate tiletypes..
A layer that will not be drawn...
100% green tile for grass, brown for dirt etc...

This way i can have terrain like grass, stone, whatever.
It''s a bit easier to keep track of 10 terrain-types than
100´s of normal gfx-tiles.

---

Storing a colour with each tile is a good idea for 2 reasons. Firstly, you have something to draw even before you have the graphics all done. Secondly, if you ever want a mini-map, just drawing this colour as 1 pixel on the map should suffice.

quote:

---

Original post by Kylotan

class TerrainType
{
Graphic* theTile; // What to display for MapSquares using this terraintype
// Impassibility and line of sight info
};

class MapSquare
{
TerrainType* itsType; // What kind of terrain do we have here
int x, y; // Our position, sometimes helpful to have it stored here
// Also - Fog of War, ownership (whose territory)
// List of creatures here, list of items here, etc
};

Edited by - Kylotan on 4/13/00 4:36:42 AM

---

This was also more or less what I was thinking of. But if you place your Impassibility and line of sight info in the TerrainType, don''t you get a problem with more ''dynamic'' tiles such as doors (open: passable, closed:impasable)? And what if the tile is occupied by another creature? Then it need to modify its impassibility dosn''t it?

Regards

nicba

quote:

---

Original post by nicba
But if you place your Impassibility and line of sight info in the TerrainType, don''t you get a problem with more ''dynamic'' tiles such as doors (open: passable, closed:impasable)?

---

Not necessarily. This is where the beauty of object oriented design and encapsulation come in.

bool MapSquare::GetPassability() const
{
if (HasDoor() && DoorClosed())
return false;
else
return itsType->GetPassability();
}

No changes to any member variables were needed, just a few added checks. And again, this can be done without the AI ever needing to know anything has changed behind the scenes - it still just calls Level::GetPassability(x,y).

quote:

---

And what if the tile is occupied by another creature? Then it need to modify its impassibility dosn''t it?

---

You never need to modify anything if you use member functions. Then you can only ''fall back'' on the standard value if there are no other weird circumstances. Another example:

int Creature::GetAttackSkill() const
{
// Special cases
if (asleep // unconscious)
return 0;
if (blind)
return itsType->GetAttackSkill() / 3;
if (berserk)
return itsType->GetAttackSkill() * 2;
// Default
return itsType->GetAttackSkill();
}

The basic AttackSkill still only needs to be implemented in the CreatureType class as it is the same for all Creatures like that.

As it happens, I am intending implementing doors as objects that sit on a mapsquare, rather than part of the mapsquare. the movement algorithm for a creature first checks if there is an enemy creature there, then if there''s a blocking object, and finally the call to mapsquare impassibility is made (which obviously doesn''t include creature or object blockages in my engine.)

Hi

Kylotan what do you do about the properties of your terrain types (impassable, transparent and so on)?

Do you hard-code the different properties into your engine and tile editor and then set up a row of checkboxes in the editor to set/unset the properties? Or do you allow for the user of the editor to input any properties in the form of pairs of property names and values?

I could see an advantage of just loading the tile editor and prees ''add new property'' whenever I found out that I needed another crazy property (ex. if I needed to make some tiles ''slipery''). But on the other hand I must still edit the engine to support the new property so perhaps the advantage would be quite small after all?

Regards

nicba

I had a slightly longer reply to this but Windows crashed, so I'll try and be brief but still say everything...

Firstly Nicba, thanks for the kind words. I am fairly happy with my design, and although it is not perfect, it is doing what I want, and that is the main thing And if sharing it helps someone else, I am glad too.

I think that perhaps the reason there is little in the way of object-oriented design (whether minimal, like my encapsulation approach, or more extensive, like using a deep hierarchy of classes) is because C++ only came into popularity in game development once 3D acceleration was already on the scene, and many advanced programmers moved on to that side of things. Which is a shame, as I feel there is still a lot to be said for 2D, and there's no reason the 3D hardware can't be used to enhance it anyway.

Properties... yes, I hardcode them in this engine. I have little reason to be able to add them dynamically as the only way you would be able to check a user-added property is for the user to ask for it. As you said, the engine itself would never know the new property existed unless you amended it. This probably means implementing some sort of scripting in the game so that level designers can access properties they create themselves without the engine needing to know. Which in my case, is complexity I don't really need. I figured I could get enough versatility for my game in a preset number of properties, providing I thought them through beforehand. (Note - I store my boolean properties, or flags, as individual bits within a single int - this means that my file format can stay the same until I exceed 32 flags per mapsquare. Which is unlikely since I never seem to need more than 6 flags anyway.)

Of course, if I wanted such a system (as I have in a totally different game I am making), I would do it like this:

struct Property
{
Property(String n, int v) : name(n), value(v) {}; // Basic constructor
String name;
int value;
};

void Entity::AddProperty(String name, int value)
{
propertylist.add(Property(name, value));
}

int Entity::GetProperty(String name)
{
for (each property in list)
{
if (property->name == name)
return property->value;
}
// Not found - return 0 (or any other default you choose)
return 0;
}

void Entity::SetProperty(String name, int newvalue)
{
for (each property in list)
{
if (property->name == name)
{
property->value = newvalue;
return;
}
return;
}

How you implement the lists may depend on how many properties you expect to need to support. I might use an STL map to store them if I had more than 10 or so per entity, for a quicker lookup time. There will be better ways of doing it than I did above: that is just for illustration purposes. Again, you can change the internal representation of the properties to whatever you like, as the rest of the game only needs to know the AddProperty, GetProperty, and SetProperty function calls. (Note: you could technically combine AddProperty and SetProperty, but I didn't here, for clarity.)

But again, I stress that all the above has not been found necessary in my tilebased game so far as there seem to be so few cases (ie. none) where I need the user to be able to set some 'custom' property. Your situation may vary, though.

Happy to help.

Edited by - Kylotan on 4/13/00 9:40:17 PM

going back to an earlier comment, another way to allocate and deallocate a map is by creating it on the heap (using the NEW operator).

int *Map;

void CreateMap(int Width, int Height) {
Map = new int[Width][Height];
}

void DeleteMap(void) {
map = delete [] Map;
}

dont quote me on the exact source code, it''s probably wrong.

when using heap memory, you MUST delete it, or else it stays there, taking up useless space (which is why i included the DeleteMap function).

you have been warned (well, bored)

MENTAL