Archived

This topic is now archived and is closed to further replies.

Layers

This topic is 5054 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Use a 3D array - X,Y and the third dimension are the layers. So [0] is the map, [1] is objects and [2] are enemies.

I prefer to only use a single layer representing the map and a Z-ordered list for all other items.

Share this post


Link to post
Share on other sites
Do not use a 3D array, only use a 2D array for the static bottom layer of tiles. and put all the other layers in linked lists.

Imagine having a 10000x10000 tiles map (yeah I know, big) and a struct with info for each tile containing mayeb 15 byte per tile.

thats a 1.5 Gig map. now, for each added layer you''ll add another 1.5 GB, but maybe you only have 1000 enemies on the map, so it would be a huge masive unthinkable waste to use an array for them. Look up lined lists, and use a sorted linked list for each layer. That way you waste no memory, and lose nearlyu no speed.

Of course in the massively huge stupid example above, you''d have some culling method, so you only load a small part of the map to RAM. but it still holds true in smaller more real world examples...

(Jeez guys! Imagine building a 10000x10000 map by hand...)

The more I think, the more confused I get.
The best 2D game developer site out there!

Share this post


Link to post
Share on other sites
it''s split up into loads of sub maps though, one part of the world handled per server, and it''s stored in some weirdo compressed archives on your PC, byt yeah, the world in total is actually bigger than that. They do not use arrays though

One more point against arrays is, what happens when you want to be able to drop multiple items on each tile? you''d need an n-dimensional array, wich is not viable. So I still say an aray for the base map, split up into zones of some kind, and one or more linked lists for the rest.

Share this post


Link to post
Share on other sites
i would differentiate between the terrain (dirt, water, grass), static tiles (walls, trees, rocks), and objects (characters, items, enemies).

the terrain might as well be an array, since every space will need one and only one tile. the rest could be in an independent list, or per-tile lists, or whatever.

that''s just how i would do it.

Share this post


Link to post
Share on other sites
Yep, that''s about the best way of doing it. unless of course you have maps smaller than a few hundred tiles each way, and only one object per tile, in wich case arrays will be enough. depends a bit on the scenario.

Share this post


Link to post
Share on other sites
If you are a beginner I believe that a 2-deminsional array is not too bad(not knocking linked list!!!). I am a beginner in game programming, but I am extremely good at math and I use formula to determine layers and everythin else. The next game I plan on making I am going to implement linked list. I have grasped most of the concepts of c++ except linked list and vectors. I have just read and played with vectors, good, but I like to have full control. Also I would like to learn how to use linked lists but I have no idea how to implement them in a game.

For example, doesn''t searching through a linked list have the same performance penalty as searching through an array. If anyone can give me a link to to a website that explains how o do tile games with linked list would be greatly appreciated

Robert

Share this post


Link to post
Share on other sites
The way I did it was to use a two dimensional array of map cells like this:


struct MAP_CELL
{
short base_layer;
short fringe_layer;
short object_layer;
short data;
};

MAP_CELL map[MAP_WIDTH][MAP_HEIGHT];


In another game I did something similar to this (yes I know it isn''t about layers but it''s a dynamic map size storage structure):


MAP_CELL *map;

void SomeInitFunction(int width, int height)
{
//create a map in a one-dimensional array
map_width = width;
map_height = height;
map = new MAP_CELL(map_width, map_height);
}

inline int GetMapCellIndex(int x, int y)
{
return map_width * y + x;
}

Share this post


Link to post
Share on other sites
ive found the storage method i use works rather well...

you have a contiguous array of pointers

each pointer points to a tile structure

which contains all the data for each tile, all it's layers and data header.

this gives the enumeration speed of an array

and yet keeps the array considerably smaller since it uses a 32bit pointer to a larger structure, thus making the brunt of the map data not confined to a contiguous block.

example:

struct IsoTile
{
string m_name;
Ground *m_lpbase;
Ground *m_lpoverlay;
Sprite *m_lpitem;
Sprite *m_lpcharacter;
//other stuff...
};

IsoTile **tilearray;

tilearray=new IsoTile*[width*height];


IsoTile* GetTile(long x,long y)
{
//validate dimensions
return tilearray+(y*width+x);
}

Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com



[edited by - EDI on January 9, 2004 4:14:08 PM]

Share this post


Link to post
Share on other sites
I don't like to store pointers in the map cell structure, so I do this instead:

My objects and enemies are stored in linked lists based on a quad-tree approach (a structure where the map is divided into square zones). When I draw the world I only look through the object lists that are shown by the camera. This is also great for things like collision detection, because I only need to check for collisions for objects in the same zone (or 2, 3 or 4 depending on if the first object stands between zones).

Also this linked list approach removes those pointers in the map cell structure. That way memory usage is reduced considerably when there are no enemies in cells, which might be or might not be an issue depending on the map size. Another reason why I dislike to save pointers in the map cell structure is that I couldn't do a simple binary save or load of the whole array, since I'd have to do something about the pointers.

An additional benefit with the separate object lists is of course the fact there can be more than one enemy and one object per cell. Although this is most probably more a matter to the design of the game, one might want to allow only one enemy for each map cell (as in chess for example).

EDIT: By the way, the "object_layer" in my tile structure is essentially a third layer for static objects. It may be removed if of no use, and it has nothing to do with the objects I've discussed in this post.

[edited by - Unwise owl on January 10, 2004 6:30:40 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Unwise owl
I don''t like to store pointers in the map cell structure, so I do this instead:

My objects and enemies are stored in linked lists based on a quad-tree approach (a structure where the map is divided into square zones). When I draw the world I only look through the object lists that are shown by the camera. This is also great for things like collision detection, because I only need to check for collisions for objects in the same zone (or 2, 3 or 4 depending on if the first object stands between zones).


Wait, so you have a quadtree where the leaf nodes correspond to individual tiles, and each node contains a linked list of the objects/enemies for that tile? Or something else? Just want to be clear... If that''s how it is, well I guess you''ll sav
e a lot of pointers that would be null otherwise, but it sure seems like a lot of extra work...

quote:
Also this linked list approach removes those pointers in the map cell structure. That way memory usage is reduced considerably when there are no enemies in cells, which might be or might not be an issue depending on the map size. Another reason why I dislike to save pointers in the map cell structure is that I couldn''t do a simple binary save or load of the whole array, since I''d have to do something about the pointers.


And saving a representation of the quadtree is easier? Oh, you don''t care about the contents? Then just go ahead and save the pointer values, or zero them out or something. Shouldn''t be too difficult...

quote:
An additional benefit with the separate object lists is of course the fact there can be more than one enemy and one object per cell. Although this is most probably more a matter to the design of the game, one might want to allow only one enemy for each map cell (as in chess for example).


Which is what the pointers in the tile struct of other people''s representations are supposed to accomplish, I thought. Being either the pointer to the head of an external linked list, or having internal linking in the enemy/object structs.

Yeah, use fields of a non-listy sort for things that are restricted to one per tile, and fields of a listy sort for things that can be accumulated.

Share this post


Link to post
Share on other sites
I guess I didn't express myself clearly enough. No, each leaf does not correspond to a map cell. That'd clearly be a waste in most cases. I still experiment with the "optimal" number of map cells per leaf, if there is such a thing. Right now however each leaf is used to represent the objects on 16x16 map cells, but I'll refine that number based on the end result.

To add upon my dislike for pointers in the map structure but not the object lists; indeed the lists can't be saved like the array is saved(the lazy approach of just saving the entire structure into a file) However, each object or enemy is dynamic and might need to have custom data saved, and so I couldn't use that simple approach in any case if it would stored differently in an array for example.

Neither are the quad tree and the leaf lists stored close to how they look. They are regenerated each time a new game is started or loaded. Instead when I'm saving each leaf is stepped through and the according list is gone through and each object gets to call its save function. Also the saving routine saves the type of the object so it can be initialized during loading time.

I'll appologize and take my statement that only one object can be saved for each cell when a pointer is stored the cell structure. I didn't think it over, and of course it can be an address into a linked list as much as a single object. Still I find that objects that are separated from the map provide some benefits I wouldn't want to give away.

[edited by - Unwise owl on January 11, 2004 7:14:49 AM]

Share this post


Link to post
Share on other sites
Snippet from my code in Java, I use an array (encapsulated in the Terrain class) for the map, and linked lists for layers (every element in the layers array is a reference to the head Entity in each layer.

private Terrain terrain;//Map data
private Entity[] layers;//Layers for drawing


***
For Java games and Java related resources, go to http://www.javaengines.dk
***

Share this post


Link to post
Share on other sites
Why would you store the items, enemies, etc in an array the size of a map, as if it was part of the map. The way I do it is, I render the viewable section of the map and. if any entities exist in this viewable area, I render them.

[grammar correction]

/*
I use DirectX 8.1 and C++ (Microsoft Visual C++ 6.0 Professional edition)
*/

[edited by - Programmer16 on February 3, 2004 1:18:22 AM]

Share this post


Link to post
Share on other sites
For a few reasons, actually--

1) If there are lots of objects, it can be unnecessarily slow to search through one giant list for objects which intersect with the visible area. With smaller lists stored per tile, you don''t have to search through all the objects--you just loop through the list corresponding to each tile you draw, and draw the objects in that list.

2) Finding nearby objects in the map is easier. Say a warrior NPC wants to target the nearest hostile enemy. Rather than searching through the entire global list for an object that is hostile and nearby and visible, the warrior can instead merely search the smaller lists corresponding to the tiles in his field of view, thus automatically excluding from consideration any enemy not in his field of view.

3) Rendering order. In an isometric especially, the order in which objects are drawn is important. Objects in a list to draw should be sorted from back to front with respect to the viewing angle. Sorting of these objects dynamically, with objects whizzing all over the place, is much faster if it can be broken up into smaller lists restricted to smaller areas such as per-tile. Consider that each time an object moves it has to re-sort itself in it''s relevant display list. If this display list is one giant list filled with hundreds or thousands of objects, this can cause unnecessary list shuffling on a large scale. However, each tile is likely to have only a small handful of objects occupying it, so it will be much faster to sort on a per-tile basis.

It''s mostly about performance, really.


Golem



Blender--The Gimp--Python--Lua--SDL
Nethack--Crawl--ADOM--Angband--Dungeondweller

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"However, I believe I should mention that linked lists are not appropriate for anything and everything. Here are two examples describing what not to use linked lists for (normally in favour of arrays):

Terrain, trees, plants, 2D tiles etc in an overhead game (such as an RPG or RTS)…

Normally you will want to store data like this in an array. Arrays allow ultra-fast access and are normally better in a case like this.

Player information…"


Directly from the front page featured article of gamedev.net. So what''s up, linked lists or no linked lists?

Share this post


Link to post
Share on other sites
Use linked lists when appropriate, use arrays when appropriate. It''s not an either-or situation. Dynamic objects such as monsters etc. are always moving around, never guaranteed to be in the same place at once, and thus require a more flexible system for handling them than a simple array. At one point, there could be three monsters on a tile; a minute later, there could be none. Linked lists in this case are an appropriate choice, as they can accomodate as many or as few objects as are needed. A fixed-length array could not handle this with anywhere near the degree of flexibility required. If you only allocate your array for three objects, and a fourth one comes along and crams itself in, where does it go?

Trees, rocks, etc... don''t move around, so it might be appropriate to put them in a separate array dynamically allocated for each tile. If there are 3 rocks on a tile, those 3 rocks will always be there (barring terrain modification/deformation of course) so you can place them in an array without worrying that a fourth rock is going to come along and overflow your array.

Problem with this arises in a game such as an isometric, wherein objects on a tile need to be drawn in properly sorted back-to-front order. If you have all the objects needing to be drawn in a single list, and you keep the list sorted at insertion/deletion time, it is a simple matter of iterating through the list and drawing each object. However, if your objects are split up between dynamic objects in a list and static objects in an array, you need to compile them both together at render time into some sort of order before drawing, or you will get incorrect drawing and overlap.

My personal preference is to maintain the map as a dynamically allocated 2D array of tiles, with all objects (static or dynamic) that are not map tile graphics (floor, walls and roofs) being sorted into per-tile linked lists. Sure, having an array of static objects per-tile might be marginally faster in some cases, but if there is only one rock on a tile, the overhead and inconvenience of maintaining a separate array for one rock far outweighs any possible performance gains from having that rock in an array rather than a linked list. Static objects are usually distributed sparsely enough across the map that any performance loss from having them in the same linked lists as dynamic objects is rendered insignificant, even irrelevant. I mean, these aren''t 8086 CPUs we are running on anymore; they can handle an extra list operation or two per frame without missing a beat, if it means a cleaner drawing sequence and increased flexibility.



Golem



Blender--The Gimp--Python--Lua--SDL
Nethack--Crawl--ADOM--Angband--Dungeondweller

Share this post


Link to post
Share on other sites
Came up with a framework im rather satisfied with, Dynamic Array for the "base" first layer, and linked lists wil be used for the others i think

[edited by - decsonic on February 14, 2004 11:36:21 AM]

Share this post


Link to post
Share on other sites