🔒 Locked

optimal unit storage

Started by Lord Pi Dec 24, 1999 at 8:12 PM 1 replies 750+ views

Original Post

Dec 24, 1999 at 8:12 PM

I have been trying to determine an optimal way of storing units for a game I am in the process of attempting.

Relevant Game Info:
-Isometric-ish. i.e. If there are tiles the majority are empty since there isn't any tile backgrounds.

-Lots of units, lots of bullets, lots of players.

Problem:
I understand that dynamic allocations within the game loop are bad for performance, but the units are fairly dynamic (or should be when I am farther along).

Right now there is a stl::vector<> holding pointers to a base class of all units. Iteration is fairly nasty with large numbers of units.

Solution:
Have a large pool of memory for units preallocated. Copy new units over and use a bitvector to manage which slots are used and which slots are empty. Have secondary indexes on this list for optomized traversal.

Does this sound like it would work? Has anyone done anything similar? Am I wasting my energy and my time for a marginal performance boost?

[One might notice I never mentioned what performance I am getting and what performance I hope for... although it is important I would appreciate it if this aspect was ignored]

Thank you in advance.

------------------
Dark Lord Pi

ghowland

Dec 24, 1999 at 5:30 PM

How many units are you going to have maximum? Over 1,000?

How much space does each unit's class/data structures take up? Is it worth the overhead of individual malloc()s?

For cases of several hundred units, Ive always just pre-allocated a maximum. Its fast, easy to sort, and there isnt a fluctuating memory useage as its pre-determined.

-Geoff

Lord Pi

Dec 24, 1999 at 8:12 PM

I do not think it should matter all that much. I am assuming that with heavy traffic ~100 units need to be created and/or killed every second. That would make for a lot of mallocs and frees (although they'd be news/deletes in my case... not that it should matter).

I thank you for your response, but it didn't answer the other half of my question:
How do you store the units?

Is it in one massive array?
ex.
class Unit { blah... }
Unit[30000000] units;

Or seperately by type? Or what?

The problem I am having is that I think I should make secondary indexes on units stored by type, but I have no idea if this is necessary or logical.

ex.
class OnePlayer {
blah...
(Unit *)[5000] uOwned;
};

class UnitStore {
blah...
makeOnePlayersUnitsIterator(PlayerID);
makeTypeIterator(TypeID);
randomAccessUnit(UnitID);
makeSuperHoohahIterator(struct SuperHoohah);

private:
UnitType1[1000] ut1;
UnitType2[1000] ut2;
:
:
UnitTypek[1000] utk;
};

class OnePlayersUnitsIterator {
OnePlayersUnitsIterator(PlayerID) {
lookup OnePLayer,
traverse its uOwned array
}
blah...
};

class OneTypeIterator {
OneTypeIterator(TypeID) {
go to UnitStore,
traverse a type's array
}
blah...
};

And that way the various iterators could be optimized and would not have to search the entire list.

This raises the problem of allocating memory for the various types, though. Maybe no one wants to use type4, but everyone uses a lot of type7? Urg.

------------------
Dark Lord Pi

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.