   best way to store units?
  I want to do a 2D RTS with each player having a maximum number of a few hundred units (thus thousands of units), and I do not want them to be standing each on its own tile. I thought about refining the grid to some degree especially for units, maybe by a factor of 4, but I don''t know if that''s the best solution. It has to be fast for a unit to check if it collides with another unit, to check if an enemy unit is in its attack range, to check what units are on the screen, to have them sorted for top to bottom drawing, to know quickly what unit the cursor is above etc without checking each unit on the map. Having the map divided into cells wouldn''t help much because, especially in battles, many units can gather up in a single cell and it would be the same problem all over again. 
  I just seen this on flip code... Maybe it will help?   -UltimaX-"You wished for a white christmas... Now go shovel your wishes!"   [edited by - UltimaX on August 5, 2003 7:43:37 PM];  Thanks but that page doesn''t seem to be too useful for what I need. The way the units are stored affects how the collision detection works, and more importantly how the unit avoidance is handled. For example, if I have some units arranged in a "U" shape formation, and there is a unit inside the U and it''s trying to go down, it has to know how to get out first. It would be easy if there could be only one unit on a tile, you would just do normal path-finding. But that is so ugly! Age1 and Age2 seem to be able to achieve unit avoidance with sub-tile accuracy. ;  http://www.gamasutra.com/features/20000809/marselas_02.htmhas a description of AOK as well as AOM pathfinding alogrithims.http://www.gamasutra.com/features/19990122/movement_01.htmis another good article. You need to register with gamasutra to acess them though.As for your question on unit storage, using a simple quadtree will suffice. Group each unit into a squad, a group from 1-10 units say. Each squad is bounded by an area consisting of all the memebers of that squad. Squads should stay close together to prevent the area from growing too large.A single unit is bounded by a sphere. This provides the basic and fast collision detection u need. To check what a unit can collde with, u check the pertient bounds that intersect the current unit squad bounds, using a quatree this should be a reasonably fast operation even for sets of 1000''s.Then u check each inidividual unit within those intersecting areas, and ofcoruse its own squadmates.As for position information, u could tie your positional scheme to your tiling scheme, but if u ever wanted to change tiling schemes it would be a nightmare to manage. Make the unit position independent of the tile scheme. Let the basic unit behaivor define how close they can get ( as defined by thier sphere-sphere intersection test ).With this simple scheme, i can see 1000s of units being managed in a single world without problem.Good Luck!-ddn ;  That''s nice, but I don''t think that''s how AoK does it. ;  I had a ponder a few days ago about how AOK does it and if not, that''s ok because I will use it.. You have map tiles that are made up of 4x4 subtiles. Map tiles are the tiles where you have trees, grass, water, etc. In the map editor, this is the smallest brush.The subtiles are not draw separately, but are used to calculate paths and positions. For example, a certain tile might only allow certain paths through the tile. Also, different units take up different numbers of subtiles. For example, infantry take up one, cavalry take up two, and elephants, siege, etc. take up four. I think scorpions take up three.Since there might be hundreds of units on the screen and only a few map tiles in range of a unit, you might want to just check the tiles adjacent to each unit for an enemy unit. The map tiles could have a running tally for how many units and what team are on them. When a unit moves it can update the tally to each tile it visits and leaves. This way, you don''t have to look at each opposing units'' position to determine if they are in fact in that adjacent tile.I haven''t done this yet, but that''s what my notes say I am going to do. gl hf ;  Maybe you should start a bit simplier (ie only one per tile), and then work up to 4...? ;  Yes, that was my ideea too. But it seems like in AoK many units can overlap if you force them a little. I never stopped to count them, but it looked like there could be more than 16 units on a tile. ;  You could use a RECT to track the world pos of each unit. ;  You could assign an linked list to each tile, with references to the units currently standing on that tile.... ? 