I''m curious, how do you guys control passability of tiles where the tile is occupied by a creature or living entity. I''ve heard someone say that they limit tile population to 1, is that really necessary? It seems that you can place as many ''entities'' onto a tile as will fit within the bounds of your collision detection scheme. How do you guys do it? This post is written with many fond memories of hundreds of Zerglings running around my screen back when I played StarCraft...

It depends on your game. In civ and games like that, you could have thousands of units on a tile. In rts games, there can only be 1 unit. In the latter case you simply have a flag, or a class function returning True if the tile is occupied or false if its empty or what ever.

Possibility

Thanks for the quick reply!

I wonder why you would say in an RTS you can only have one unit per tile though? Of course, if your entire map is filled with multiple units per tile, I can see a performance degradation, however why is there a hard limit of 1 opposed to the unlimited nature of ''god'' games?

I''m not sure what you mean, fingh. If you had more than one unit per ''tile'' in an RTS, it would look like they are standing on top of each other. This would probably not be the look that you want unless you are dealing with flying units.

You will notice in Starcraft that zerglings cannot stand on the same space on the map. But maybe you mean something different by ''tile?'' There is a difference between the tiled graphics and the grid that the game internally uses to break up the map in a game like SC. Maybe you could be a bit more specific as to what you mean?

You can have many creatures on a "tile", and not have them necesarily be directly on top of each other in a stack. Take StarCraft and the Zerglings.

For instance, if your tile is 64x64 and your Zlings are 8x8, it''s conceivable you''d have a ton of those guys on one square. The trick then becomes decent collision detection.

There, you just break the problem down a bit.
1. ok, is anyone near my tile?
2. if yes, are they near me?

Of course, it''s a little more complicated than that, but you get the idea.

One way to do it would be to store creatures in a separate list, with an x and y coordinates for every one of them. Don''t think about it in terms of "creature being on a tile" but rather "creature has certain position in the world". As Buster said, you''d use collision detection to ensure that 2 creatures do not "overlap". For example, you could define a 2d bounding box for every creature and use that to prevent those fuzzy little buggers from getting too intimate with each other.

Also, this approach will somewhat complicate your rendering code. For every tile you blit you''d need to figure out which creatures to blit and in what order. If you traverse the creature list every time you''ll kill your framerate. So, you''d need to presort the creature list or cache some kind of data from the last frame or whatever other optimization you can think of.



v.

The first step is to design your map structure with this in mind. In FATE, my map is an array of MAPPT structs:

typedef struct MAPPT{     unsigned char Illum;   //Light Level (1 - 255)     MAPPTNODE *ObjList;    //The start of a linked list                            //  of objects over this map                            //  point     char Reserved[3];      //Padding to make struct 32bit                            //  aligned} *LPMAPPT;MAPPT *Map;

With this struct representing a map point, I can now have unlimited number of objects over a given point/tile. (NOTE: In FATE, a tile is also a map object so it is usually the first object in the list).

When you want to know if an object can move into a map point, you goto that map point and ask every object over that point if it occupies that spot, or a spot that would be taken up by the object you are moving there. It is simple collision detection.

Remember that if you will be implementing a map stucture like this one, every object will need to have an offset value (X, Y, Altitude) for it''s position within a map point.

Good Luck.



Dino M. Gambone

Good judgement is gained through experience. Experience, however, is gained through bad judgement.

Another thing you might want to consider:

for units, characters, and other objects that move, you may want to store a position within a tile as well as the tile that it''s in.

in an isometric tile field, this means you split up the tiles into smaller "tilets". the diamond shape is well suited to doing this.... you just make each tile be a diamond shaped map.

for rendering purposes, you keep track of where a unit is two places. one, you keep the tile position and tilets position within the CUnit class (or whatever you''re calling it), and you keep a linked list in each map tile to store what creatures are there (just pointers to CUnits, because all of the calculations are based on stuff gained from CUnit)

for collision detection, you should do this only when the unit is moved. because of the linked list in each tile, you can minimize the number of comparisons to only those other units that occupy the same tile or neighboring tiles (you then only have to scan 9 tiles worth of units, and you could optimize this down to four).