Datastructures of Tile-Worlds
As far as pathfinding goes i would again have to say an array is best. Now about using linked lists yes you can use them yes they do save memory on certain tiles(e.g. your engine uses up to 3 layers of tiles on each tile using this in a array is a big waste of memory becasue each tile takes 3x the memory with a linked list you can just store each tile where you know this doesnt have any tiles on top of it) The down side,well it can be slower and if your just using 1 layer then your probally wasting memory by all the 32bit pointers. Now using an array for the tile world and a linked list for the objects/units in that world is a bit differnt. Anyways hope this helped some(doubt it writting emails seem a little off today).
I know that it's somewhat confusing to search around the area for now, but we're revamping. :-)
Khawk
Admin for GameDev.net.
As a beginner in this area, I was wondering if anyone could share some info on how the data for the tile-world is stored.
Of course the easy answer is array[x,y] of word, but how do games store objects on these coordinates?
StarCraft seems to have several layers. Are these just additionally arrays?
Age of Emp - Has trees with different (and variable) ressources, is this just an array with pointers.
Pointers seems to solve the problems for storing data, but does not seem very effective, when for instance, the path-finding routine needs to traverse the world-data!(?)
My own thoughts considers an array of pointers with additional "bitmaps" to show passability etc.
Also how are heights implemented (witout using vectors). Again a height array is obvious, but if you allow your units to move independently of the tileworld, how do you affect their speed, when they move across a slope while just running a bit up at a time? Do you calculate the exit-point of the tile, and continue from there?
These are "problems" I would like to see a discussion about, because when one starts to search the web, all concern about tiles are put into storing "numb" tile-data in some sort of array-struct. Not much concern is given to how good this model will perform for the pathfinding, line-of-sight and AI algorithms.
------------------
Robert Madsen
rkm@logimatic.dk
[This message has been edited by rkm (edited August 10, 1999).]
rkm@logimatic.dk
I use for my hexmap a 256 x 256 array of Pointers to this structure
struct mapinfo
{
char pathmark;
short tilenum; // holds a tile# that links to a tile array
short tilefore;
short foregroundtile;
short alphagraphic;
short int hexsides[6];
unsigned char height;
short xhex, yhex;
int cost_so_far;
int trigger;
int g;
int h;
int f;
unsigned char flag;
unsigned char objectpts;
unsigned char control;
RECT TSource;
struct Udata *unit; //pointer to unit
struct tilehex *parent, *lnext, *lprev;
void *ddsSource;
void *SourceCoords;
} *CEMap[MAXCOL][MAXROW];
You might notice f,g,h, and *parent, *lnext. This is my path-finding info that I keep in each hex. I just keep the pointers in an array and dynamically load/malloc & delete/free the memory for it. You could have an sub-array
(int tile-types[10])
for different levels/type of tiles(i.e. background, foreground, alpha-blended tiles and others.
The above array at one time was 80 bytes. That can eat up a fair bit of memory even for a 100 x 100 map(80x100x100 = 800k). A 256x256 map = 5.2Mb. As you can guess, I don't program in DOS with it's 640k limit. When it comes to obstacles, I store them in the hex-sides array but if you have a large map with few obstacles you could just make up a linked-list of obstacles that you have to avoid or quickly side-step.
You can check out a tile-editor I've created on http://www.geocities.com/Area51/Atlantis/7739/