Population Limit/Unit Cap - Containers - Inquiery

[jlwing]

Dear Reader,

I would like to enquire as to the current population limit/unit cap which is imposed as a direct result of technical limitations, such as secondary memory constraints or preferably CPU cycles (or any other unexpected average hardware specs, or perhaps software architecture related constraints).

I am researching for my dissertation the methods employed for dealing with large numbers of units (game objects equating to in game units).

Ultimately I require credible sources, of examples that cover ways one might store/arrange their units with respect an RTS based game.

In return for communications and advise on this topic, the results of my demonstration on how to improve performance with respect to numbers of units may be of use to you in the future.

I propose that I might learn of your methods in several different ways:
IÔÇÖm provided with an overview of the relevant areas of code and I join you as a developer and analyse the code.
Preferably you employed well documented general mechanics and I might refer to those.
Perhaps someone might be able to put me in contact with a person of knowledge.

Thank you Kindly
Friendly Regards
Jonathan Laurence Wing
Computer Games Software Engineering

[SpliFF]

That's an interesting choice of research project.

In my experience with this engine the primary cap is based on graphics limitations, you can run a simulation of thousands of units on a modern machine but your framerates drop once 10's of hundreds are in view. Obviously the exact numbers are based on your graphics hardware and settings.

The most CPU intensive tasks are path finding and line of sight updates.

The simulations runs in "sync" on each PC in the games so network related issues are minimised. Again the actual limits depend on the connectivity of different players and the geographic distance between them.

The engine makes heavy use of Lua scripting. In some cases data is structured for Lua integration rather than performance considerations. That's not to say everything is that way, performance considerations are still paramount in many areas.

There is development and discussion underway regarding scaling the engine to multiple CPU's. There is already a multithreaded build which splits some areas of the engine. As most new consumer systems have some form of multicore processor this should have a major impact on future performance and could dramatically change the bottlenecks in cases where parallelism is practical.

I haven't done enough thorough testing to give you anything more precise than that. In my opinion though the source code is well structured so finding the various "subsystems" of the engine is not particularly hard (start under the rts/ path).

[jlwing]

Thank you for the reply SpliFF,

I am looking more specifically at the way you deal with large spaces, i.e. what form of spatial units if you will is used.

Perhaps the project employs a database mechanism such as oracle and only has small code side buffers?

In this case does the oracle data based sort/arrange by world position and how effective is that?

Or are there code side containers on each client that are then synced?

Thanks again.
Friendly Regards
Jonathan Laurence Wing
Computer Games Software Engineering

[SpliFF]

The engine does not use a database, all objects are stored in the process memory on all machines (every machine has a complete copy of the world).

The map is broken in grids to allow partitioning of certain operations or to work at coarser resolutions.

Collision detection (hits and explosions) generally get filtered through sphere calculations so hits are only tested against unit pieces when the event occurred inside the unit "radius". This is a little oversimplified as there are options for choosing the behaviour and collision types on a per unit basis.

Many operations take into account all 3 spacial dimensions. Some are 2d only. In some cases the behaviour is a settable option (I believe LOS is one of these, but I'd have to check).

Syncing machines involves a fairly complex process but the simplest explanation is that only commands are sent (things you did with the mouse or keyboard, things that occurred in "unsynced" code that affect the simulation, orders given to units, messages between players, etc..). Each update is tied to a game frame it happened in and all machines "play" those commands only in that game frame. It's like you clicked on everybodies PC at the same time. The server (basically one of the players) dictates the order commands are run and broadcasts an "official" command queue to all machines.

[AF]

Sync:

• User/AI/Widget issues command in unsynced land on a machine
• This command is sent via the network to the host client.
• The host client then sends the command to all clients, including the sender
• All clients recieve the command and pass it to the synced simulation
• All clients execute the command, using the same simulation code, data, etc

This way all clients remain synced, because the simulation is running on every single machine, using the same data. Everything that differes from client to client is unsynced. Should the simulation not match, then a desync has occurred and the game is no longer deterministic.

As I understand it, there are no large scale units of measurements, no databases (Ive never heard of an oracle database being used in an RTS ), no special optimisations specifically for large unit counts.

All optimisations are general optimisations intended to benefit high unit counts and small unit counts, for an overall performance increase. Large unit counts will inevitably use up more resources, and thus the best optimisation an end user can do is buy more ram/cpu/gpu.

Should there be too many units, the game will still run, but the speed of the simulation will drop accordingly.

Most optimisations we have regarding scale of any kind are primarily related to map rendering and moving the camera around on a map that can be large and use strategic zoom.

[jlwing]

Thank you, very informative.

Now I would ask:
When you move about your map, I imagine you spool (if that is the correct term) the world and units in. So this implies there are only so many units spooled in for each player?
Though multiple players is not a topic I am going to cover.

But then how do you compute actions that happen outside that spooling radius? So perhaps all units exist at all times (within memory), which means they are all stored and accessed by this grid system you mentioned.

So am I correct in saying that you convert a position into an index of the grid? To access the units in that spatial definition.

Do you rebuild your grid and its contents at any point or does it happen automatically, as in is it inherent?

Lastly would you say that you could benefit from a system that involved little to no computation ("no computation" being improbable) when accessing a list of local units?

Additionally if anyone might know why; I've had trouble finding articles on this specific topic.

Once again tank you kindly.
Friendly Regards
Jonathan Laurence Wing
Computer Games Software Engineering

[AF]

That is completely different to our model of simulation.

The simulation is calculated and simulated in full on all clients machines, the spectators, the host, the players, they all run identical simulations, doing the same calculations.

If those calculations are different, or the simulation and its data are different, then a desync occurs, and you are not playing the same game.

All the simulation needs from the server is the commands and the information to construct the starting points (mapname, faction etc ).

We store unit positions etc in plain xyz coordinates. We have no grid system limiting how our units are positions. Any grid systems or units we do have are an implementation detail, and do not place limits on the game. For example, we have a footprint unit which is simply a unit of measurement for defining unit types, but it is not an integral part of the simulation outside of the UI for building placement.

We do not cache units either, as all units are in memory at all times. Since the simulation is ran in full on all machines, caching units in memory is somewhat meaningless as theyre all needed.

[jlwing]

Yes AF I see your point,

I get most of what you are saying and it seems like a sensible approach.

The part I do not understand is when it comes to an action such as moving the screen or selecting a unit, or rather any operation which would want to know the say X nearest units.

Without spatial hashing lets say, then one might have to cycle the list of all the units and check its proximity to the area in question.

Are you saying that this is the case?

Or do you arrange your units in the form of a say BSP tree?

Friendly Regards
Jonathan Laurence Wing
Games Software Engineering

[Kloot]

Read what people say...

The map is broken in grids [sectors] to allow partitioning of certain operations or to work at coarser resolutions.

The grid (quadfield) is a type of uniform spatial hashing, or rather binning. Each client knows the full state of the grid, there is no sharding ("spooling" as you call it) of grid sectors because that would not make sense with Spring's network model.

[jlwing]

Thank you Kloot,

What SpliFF wrote seemed to contradict what AF wrote. I have read and understand everything that has been posted, It just seemed incomplete. Now thanks to the specifics eg quadfield I see better how it might work.

Also thank you for the useful terminology.

Do you perhaps know of any articles that relate to this topic, I've not yet manage to find any Developers of commercial games willing to say "this is how we accomplished ...".

Now I might go on to investigate the forms of "uniform spatial hashing" particularly a quadfield.

Any further advice is welcome.

p.s. This is an area of interest to me, I will take a look at your implementations. Unfortunately I can not help with your current issues of syncing. I only know briefly of a wait state threads might have whilst waiting for shared "locked" resources, i.e. a mutex.

Thanks again.
Friendly Regards
Jonathan Laurence Wing
Computer Games Software Engineering

[zwzsg]

You speak in a very formal way, but you ideas are pretty wild.

Perhaps the project employs a database mechanism such as oracle and only has small code side buffers?

Muh? Do you even know any real-time game that use an oracle database, or any other dedicated database? I mean, turn based webgames, maybe, long term storage for MMO, maybe, but a game in real time, with few players, and good graphic and physic? Never! It's nearly always simple array in C++.

- We want speed and low memory usage.
- We don't have many sleeping object. About every entry refreshed everytime.
- We don't need the "relational" bit of a RDBMS.
A true database management system would be waaaay too heavy and bulky just to store a list of units.

But then how do you compute actions that happen outside that spooling radius? So perhaps all units exist at all times (within memory), which means they are all stored and accessed by this grid system you mentioned.

Every unit actions are computed every frame, no matter if in view or not. Stuff don't stop happening when you stop looking at them, you know.

So am I correct in saying that you convert a position into an index of the grid? To access the units in that spatial definition.

Muh? No, we don't index units by their position in the map, or any indexing system even remotely related to their spatial position. Each unit is assigned an index at creation, that is unique during its lifetime. Those index are just an integer between 1 and 5000 (or some similar number depending on unit count and player number). Whenever a new unit needs to be created, it picks the first free index from the end, or something like that, and use it for the newly created unit.

I can't even think of any other system a RTS could use to index its units.

Lastly would you say that you could benefit from a system that involved little to no computation

Of course, no computation would be faster, but those computations are what makes our units, move, aim, fire, die, etc... Simplifying computation would make gameplay shallow. We don't want to play Black Screen at 9001 Frames Per Second, we want an engaging, deep, game, with lots of stuff going on at once everywhere on the map, because that's what makes the game interesting.

Did you play a game or two or Spring, to get an idea of what it is, or are you a "Computer Games Software Engineering" that never indulged in playing?

Your idea about only doing the computation for units in view are interesting, that sort of thing is used alot in FPS, RPG or other game where you control a single character in a huge world. However they really are unsuited for the videogame genre commonly refered as "RTS", and that should have been obvious from playing.

Or do you arrange your units in the form of a say BSP tree?

Units move. What you'd gain in search time by having your units sorted in a nice BSP tree, you'd lose in having to reshape your tree every time an unit move.


Maybe stuff like inter-unit collision, unit-shots collision, knowing which unit are in view, could be sped up by partitioning the map into section and maintaining a list of every unit in each section, maybe that's already done, I don't know, I'm not an engine coder like Kloot or SpliFF, but that'd only be an added cache of unit index, that would not the main way by which unit are indexed.

I've not yet manage to find any Developers of commercial games willing to say "this is how we accomplished ...".

Spring is open source, and new dev routinely come and go, so it's not like there is any secret in the code. Might be a bit hard to get into the source, though, especially if all you want is to catch how were done one or two things instead of a real long term involvment.

But I'm still pretty sure you won't find in Spring what you're looking for. We just have a big array of unit ID, and loop through them every frame.

There's no fancy spatial sorting and ordering, or if there is, it's very limited in scope and use.

There's definitively no database, unless you broaden the term to basic arrays.

[SpliFF]

"Syncing" should not be confused with thread synchronisation. Springs sync issue are entirely due to the complexity and difficulty involved in performing billions of calculations on machines with different operating systems and architectures and ending up with exactly the same result (while still allowing each player their own private UI and scripts). Threads can make the problem worse but using 1 thread doesn't make it go away either. The biggest problem is probably 64-bit vs. 32-bit where your float accuracy and integer sizes change but fortunately there are third party libraries (streflop) Spring can use to help abstract the differences away.

Sync is a lot of trouble really but the alternative is worse - sending massive update packets across the internet would make large unit counts and framerates entirely bandwidth dependent.

Muh? No, we don't index units by their position in the map, or any indexing system even remotely related to their spatial position.

He means index into the quadfield. Kloot is saying objects are mapped to the sector they're in in a lookup table of some sort. You should be able to find nearby units by looking at the contents of nearby sectors.

The details are in rts/Sim/Misc/QuadField.cpp. A sample of which is:

Code: Select all

/**
 * Returns all units within @c radius of @c pos,
 * and treats each unit as a 3D point object
 */
std::vector<CUnit*> CQuadField::GetUnits(const float3& pos, float radius)
{
    GML_RECMUTEX_LOCK(qnum); // GetUnits

    std::vector<CUnit*> units;

    int* endQuad = tempQuads;
    const int tempNum = gs->tempNum++;

    GetQuads(pos, radius, endQuad);

    for (int* a = tempQuads; a != endQuad; ++a) {
        Quad& quad = baseQuads[*a];

        for (std::list<CUnit*>::iterator ui = quad.units.begin(); ui != quad.units.end(); ++ui) {
            if ((*ui)->tempNum != tempNum) {
                (*ui)->tempNum = tempNum;
                units.push_back(*ui);
            }
        }
    }

    return units;
}

That code gets the quads with a given radius and then returns the units in those quads. This is vastly more efficient than checking the distance to every single unit on the map.

[hoijui]

i guess when he mentioned database (oracle), he meant more an SQL like query language, which has been requested by others already. for example: "SELECT units in (pos, radius) where (health <= 50%)"

they primary way used in spring to prevent 32bit vs 64bit sync issues, is to only use float, not double. or at least i think that this is one of the reasons to use float only.

[jlwing]

zwzsg Sorry If I offended you with my questions your post is almost aggressive in nature. I was and am being formal because I thought it would help.

Thank you SpliFF, the way you deal with large numbers of units without having to check all of them for proximity based calculations, i.e. the quadfeild is informative.

Of coarse I understand that you would also probably update each unit, which is great, however other trains of though were along the line of a level of detail radius.

For example you might not have to calculate collision and other such things on quite the same level of detail when they are not in view.

As for the spooling, I was merely acting out a rational that disqualified spooling (sharding) as a something you might use. Although that needed confirmation, as you might find that in very large worlds with very very large numbers of units, say millions, then you might want to apply formula to represent what has gone on when you are nowhere near the area of interest.

You see concepts like these can apply to RTS's if you were thinking on a large enough scale, given the fact that I no experience of RTS making, I am merely a 4th year Computer Games Software Engineer who had 9 months experience with Ubisofts "Driver San Francisco", It would stand to reason that I might have some wild theories. However thanks to this post I now have a better understanding of how Spring accomplishes things, which is a reputable approach, after all your engine is impressive.

As with respect to the data base comment, that was a suggestion made by my supervising lecturer. Which has some bases to it if you inspect it further.

Also my work will include varied approaches good, bad and impossible even wild.

Thanks again.
Friendly Regards
Jonathan, the now slightly less formal poster.

[jlwing]

i guess when he mentioned database (oracle), he meant more an SQL like query language, which has been requested by others already. for example: "SELECT units in (pos, radius) where (health <= 50%)".

Not exactly my meaning but I do quite like that idea. Supporting more ways to query the unit container, such as using the SQL syntax.

[hoijui]

what you mention there (calculating stuff not in view different when stuff in view) is only possible applicable in a very limited scenario. there might be only one player (and probably no spectators), you can not record the match for later replay, or if, the camera would have to be fixed to where it was while the game took place.
you said your approach will not consider multi-player/networking, but i would suggest not going routes that disable a later extension in this area, because.. well... nobody would be using your findings.

[jlwing]

The details are in rts/Sim/Misc/QuadField.cpp. A sample of which is:

Code: Select all

/**
 * Returns all units within @c radius of @c pos,
 * and treats each unit as a 3D point object
 */
std::vector<CUnit*> CQuadField::GetUnits(const float3& pos, float radius)
{
    GML_RECMUTEX_LOCK(qnum); // GetUnits

    std::vector<CUnit*> units;

    int* endQuad = tempQuads;
    const int tempNum = gs->tempNum++;

    GetQuads(pos, radius, endQuad);

    for (int* a = tempQuads; a != endQuad; ++a) {
        Quad& quad = baseQuads[*a];

        for (std::list<CUnit*>::iterator ui = quad.units.begin(); ui != quad.units.end(); ++ui) {
            if ((*ui)->tempNum != tempNum) {
                (*ui)->tempNum = tempNum;
                units.push_back(*ui);
            }
        }
    }

    return units;
}

That code gets the quads with a given radius and then returns the units in those quads. This is vastly more efficient than checking the distance to every single unit on the map.

Great example.

Now lets say that GetUnits was at the basis of many other higher level methods/functionality. Imagine then a system whereby the position of an object could with only say 2 simple calculations such as two multiplication say a factor of .2 would in a way give a resulting index (i.e. unique whole number).

Opening the possibility of:

Pseudo Code:
Unit[GetIndex(Position,Radius)]

This is really a question, could functionality like this be of use (given the game was built based on this premises). Remember I am investigating not stating the way things should be

[jlwing]

what you mention there (calculating stuff not in view different when stuff in view) is only possible applicable in a very limited scenario. there might be only one player (and probably no spectators), you can not record the match for later replay, or if, the camera would have to be fixed to where it was while the game took place.
you said your approach will not consider multi-player/networking, but i would suggest not going routes that disable a later extension in this area, because.. well... nobody would be using your findings.

Point taken, I am suggesting that I would not need to deal with networking on the premises that the mechanisms I am investigating are not related. My demonstration will not include the networking elements, nor would they need to. My dissertation does not afford me the time to investigate the subject further nor would my supervisor allow me to go into more detail.

I understand that you issue commands to all the machines in essence, which could continue to happen if the use of a quadfield was changed to the use of an alternative. Yes I understand that my point of interest is limited in scope and might seem overly simplistic but my work involves other factors and goals I must accomplish, I unfortunately only have time to investigate one aspect, this does of coarse force me to at least generalize some of the other concepts.

Once again, Thank you for the response. The level of interest shown is pleasing and shows a professional level of skill behind the scenes.

[zwzsg]

Yes, sorry, I have often trouble expressing myself in a non-agressive way.

Your approach would indeed have merit, just in other kind of games. I mean, in most other games, you control a single character immersed in a vast world. And there it indeed makes sense to have efficient method to skip everything out of view, or at least everything outside the regions neighbouring the player. But RTS are one of the view game genres with:

1) A bird's eye view:
If you zoom out enough you can see all the map at a glance.
In older RTS with fixed or limited zoom, there is still the minimap, which shows all that is going on all over the map.

2) Action that keeps going even where you're not looking:
Even you are microing your attack unit at the front line, at the back the metal extractors keep extracting metals, the factory keeps building tank, etc...
Even when shrouded behind the fog of war, computer or human opponent develops.

It's the game genre that wants that. Sure, you could imagine a new sort of strategy game where only the unit are close to the camera are "alive", and everything else "paused". But then it would play so differently it would be a new game genre.

But again, in a different domain, say, a first person shooter, a role playing game, a GTA-like, the approach of "freezing" everything but objects close the player would not only make sense, but is indeed used in actual, sucessful commercial games.

So it's not that your approach is not good in itself, it's just not suited for the subset of games we call "RTS".

I still say you should play, or at least spectate, a Spring game or two to feel by yourself the kind of scale, unit count, and gameplay RTS are about.

[jlwing]

Yes you make a good point, features such as mini maps or zooming out to view the entire battle field like you would in SupCom are desirable features, I was not suggesting you could not have those features, I was hypothesizing with many different scenarios in mind, also I cover more than one concept they are not dependent on each other.

You are right that I do not have enough experience of the games implement via the Spring Project and that is only because this is my first week of research into this topic and this is the first day I've visited this site and on a University computer where installation is not an option. This is not however the only day I will be spending investigating the site nor the only computer I have access to.

Inactive units are undesirable and systems which might involve them using a time seed or such to bring them up to speed would only come into the realms of an RTS when dealing with exceptionally large spaces.

My research into spatial reasoning will not prohibit viewing the entire battle field or maintaining a minimap, just the implications of a spooling system(shard system) would, which you would only employ in an infinite world (procedural, as large as it can be).

When thinking on my comments you also need to consider things like LOD which is a standard method employed in many games, which does not have to only apply to 3rd person shooters or driving games. As i stated before you could have (not in-active units) lower level of detail units, i.e. less precise collision detection ect. I did not mention these other aspects before because they were not relevant.

The issue I face is that I can't gain any kind of formal confirmation of the use of things like spatial mechanisms in RTS games, or any form of spatial reasoning with respect to the arrangment of units. However this post has helped confirm the use of such mechanisms, you yourselves use a very appropriate quadfield.

So in the end I apologize for not being more clear as to my topic.

Indeed you as developers have chosen wisely the mechanisms with which to work and I commend you.

In any case even though I feel your criticisms are miss guided, they are in fact also very good points to add when discussing further the topic, I will be sure to make use of them when discussing what should not be done for an RTS.

Btw you can not zoom out in SCII and there is the fog of war effect (rendering related no doubt as well as game design ofc). When you have situations of multiple players fighting in a close space and the effects of the cloaking mother ship even the most ready gaming machine takes a hit especially on ultra settings. This is not an issue I would be looking to solve.

Really when you think of a game such as total annihilation where the unit cap could reach 1000 individual units per player if it were possible I imagine there would be people who would have enjoyed having a 100 000 unit cap. Why do you suppose you could not have that unit cap? You could already fill the screen with units, its not like you could get 100 000 onscreen. No this was a technical limitation, and one way they might solved it is by having more compact data and a structure aimed at supporting colossal units. I'm not saying it was possible, just that improvements can be useful.

Once again thank you kindly
Jonathan Laurence Wing