best container for RTS units?

[rego]

Hi guys,

i'm investigating which STL container to use for storing/accessing/retrieving RTS units

I'm guessing the use of a mutlimap or vector would be appropriate. However lists can me merged and so i thought that might come in handy for creating unit groups perhaps???

what do you guys think?

cheers

[anubis]

I usually start out with a vector and start implementing and either create new containers, when I need them, like additional maps to better access data, or change the vector, if it turns out to be the wrong data structure.

A vector is very efficient if you only want to randomly access the data and not search for it. As long as you don't do other operations very regularly, that probably outweighs the advantages a list may have.

[Reedbeta]

Probably the most common operation on units is to find a list of all the units in a specified area. This is done for instance for rendering (finding all the units visible on screen), for AI (finding enemy units to attack, etc), and for miscellaneous other game logic purposes. It would be good to choose a data structure that makes this operation fast.

Given that units typically move around a lot, a tree-based structure is probably not ideal, since it would have to be rebuilt too often. A grid-based data structure would be more appropriate. You can slice up the map into grid squares (larger than tiles - say about the size of one screen), and keep a list of all the units in each grid square, updating it when units move from one to the next. Then, to find all the units in an area, you just need to find which grid squares that area intersects, and then find which units within those grid squares are actually in the area.

However, on the assumption that you don't yet have enough units for any of the above to be relevant at all, I'd use a vector. ;) A multimap isn't appropriate since you're not really mapping one kind of thing to some other kind of thing, and a vector is simpler and faster than a list since units aren't created and destroyed very often (the main area where a vector performs worse than a list is in insert/delete).

[poita]

Agreed with Reedbeta, a grid structure would be best once you have lots of units. It also makes the process of finding enemy units that are within firing range easier as you can just check the cells adjacent to the unit (or further, if required).

[rego]

thanks guys much appreciated! a vector it is then :)