Archived

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

best way to store units?

This topic is 5229 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

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
http://www.gamasutra.com/features/20000809/marselas_02.htm

has a description of AOK as well as AOM pathfinding alogrithims.

http://www.gamasutra.com/features/19990122/movement_01.htm

is 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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You could assign an linked list to each tile, with references to the units currently standing on that tile.... ?

Share this post


Link to post
Share on other sites