I would think you would use a 2d array of linked lists. Each cell in your map could contain a linked list of multiple items stacked in that cell. Ne?

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Well, I use linked lists for:

- Basic map info
- Animation info
- Multiple layers of map

Using it for animation info though is a good idea, because you can add on bitmaps, etc. very easily.

Why in the heck would you want to use a link list?

simply use:

class TILE{         int Tile_Type;         int .....//other factors here that affect this particular tile         ect......} tile[256][256]; 

This will create a 256x256 map;

then have your tile types class like so:

class TILE_TYPES{           LPDIRECTDRAW7 surf;  //tile image           int walkability;           int .....what ever else you have that is particular to this Tile_Type           ect........} Tile_Types[NUM_TILE_TYPES];  

its pretty much that simple, why would you want to complicate it and slow it down with linked lists?

Possibility

Edited by - Possibility on June 4, 2000 11:21:03 PM

hmm.. I''ve thought about this too. It seems that a big advantage to using tiled graphics in the first place is memory efficiency. Tile reuse could conceivably save you a chunky piece of memory than if every level were just a huge bitmap. You sacrifice some looks, but then again diablo2 certainly looks okay. I''d even venture to say it looks somewhat prettier than baldur''s gate.
so as far as LL''s go, I''d say they''re pretty good for storing animation sequences and the like where you just cycle through the entire thing, but for fetching random tiles, I''d say a good old 2d array.

cheers,
muffin

I''ve written a tile engine or three, and in each one I''ve used indexes to tile info classes or structs for the map array. It seemed to be way more effecient to have a tile type that has texture id 5 and walkability 3 once, and have every tile lik that reference it, than to set each individual tile to id 5 and walkability 3. At the worst case scenario, you have as many tile info''s as as many tiles (which you would be doing if you used classes for each tile).

I''d say go array because of the speed. I agree linked list speed is to slow for something like this. However, what you could do is break your world (if large like mine) into "chunks" that are loaded occasionally. Each chunk is an array of the tiles. You could store your chunks in a linked list since you would be actually hitting it infrequently. While this hybrid works for me I think it really only is an advantage if you are using large worlds, such as an RPG (which is what I''ve been working on).

Sieggy

Make Map as an array of MapSquares. Or an array of linked lists of MapSquares, if you need a varying number of layers.

MapSquare holds information relevant to that place. For example, a list of creatures or objects there. Or whose territory it is. Or a pointer to the settlement in that tile. Whatever you like.

The MapSquare does not store passability or visibility data. Instead, it stores a pointer or an index to a Terrain/Tile class.

The Terrain/Tile class defines the graphics for a certain type of terrain, and whether you can walk on it, shoot over it.

Ideally, you encapsulate all these layers so that you ask the Map "Can I walk onto square x, y?" and Map calls the relevant function for that MapSquare, and MapSquare calls the relevant function for its Terrain.

This gives you the minimum of wasted space with all the flexibility you need.

Actually, Im doing it in pure C, so I have a little more elbow room speed wise. In fact, I have had very little problems with that, and if needed I could always optimize to the bone.

-----------------------------

A wise man once said "A person with half a clue is more dangerous than a person with or without one."

I''m curious if anyone else is making a tile-based game that will have multiple ''floors''? I was thinking of a map like so:

class level{
private:
flags myFlags;
_8pos myIndex;
item* myItems;
level* myLevel;
npc* myNpc;
tile* myTiles;
...
};

flags myFlags - just a struct that has line of sight & walkability values

_8pos myIndex - a byte index into my array of tiles

item* myItems - items in this floor

level* myLevel - the next floor above

npc* myNpc - the npc on this floor

tile* myTiles - a list of fringe tiles for adding extra effects like bushes, rocks, etc.


The map would be a two dimensional array of ''level''s

With this method, I can stack endless amounts of single tiles (rocks, bushes, etc.) on each floor, and also keep stacking more floors for big buildings and whatnot.

After a lot of thought, this is the best I could come up with. It could get memory intensive, but that''s the price you pay for flexibilty. Has anyone come up with a better method or possibly punch some holes in my idea? Constructive criticism would be greatly appreciated.

You mean layers?

You could always use what I am using:

struct map_lnode
{
node layer_one;
...
} map;

then just:

map.layer_one = blahblahblah

or I am sure you could do the same with an array.


-----------------------------

A wise man once said "A person with half a clue is more dangerous than a person with or without one."