City Development and Bigger Maps

[MayaPepe]

Hi Wildfire Team!

So today played some 0 A.D. and thought up something. How about that when/if you make bigger maps like really huge maps, put a phase called like "Empire" or "Capitol" phase or something and with that you could acces a bigger map like first with the town phase you maximum can have a like 4x4 map but with the "Empire" phase you'd acces a map on what other players are playing on simoltaniously with you and if you are allied with that dude/lady or playing the same nation you'd share resources and all and "get rights" to trade with each other.

Just some thoughts, If already in development or planned, i think it'd be a great addition to the game.

Thanks for reading-MayaPepe

[sanderd17]

The main limiting factor in bigger maps is the performance. Several algorithms we use loop in O(n²) or worse on the number of terrain tiles. So if the map becomes 4 times as big (which is just doubling the sides), calculation of that method takes 16 times as long (or worse).

There are some demo maps that are really huge, but they're not decorated (there are no trees, no resources, no ...), and even then, they can be quite slow. Let alone what would happen if the map would be filled with trees, buildings and units.

So with the same game mechanics, this doesn't seem possible to have a huge map that allows all online players to play together.

If such a gametype is made, the game mechanics should be simplified a lot.

[causative]

What algorithm do you use that takes O(n^2) in the number of tiles?

[sanderd17]

O(n²) isn't that rare. Though it probably happens more in the number of entities than the number of tiles (but that's a linear relation on most maps).

[causative]

Then what takes O(n^2) in the number of entities?  Could it be done more efficiently?

[sanderd17]

Entities constantly reference each other. F.e. for finding the best target (economically, military, ...). So the more entities there are, the more these searches need to be performed, and the bigger the search space is.

n² isn't generally considered that bad, and we normally optimise the average case by doing early returns. So no, most of these can't be optimised, and are just what we have to live with.

The only option to make the game playable on huge maps is by having less entities, and certainly less versatile entities, so less detailed gameplay.

[causative]

Finding units (targets?) within a limited area is optimized with SpatialSubdivision and should be much faster than O(n) per unit, closer to O(log n).  If it's not then that could be fixable.

SpatialSubdivision is defined in source/simulation2/helpers/Spatial.h.  I know that at least the pathfinder/unit motion uses it when checking for collisions, hopefully it's used elsewhere as well.

Edited May 13, 2016 by causative

[sanderd17]

It's not necessarily within a limited area. The AI could query a lot further. And I mentioned target finding, but there are other per-unit tasks that run in O(n) or worse, like pathfinding.

But I don't think this should be discussed here. It was a stupid idea from my side to mention complexity in this thread. I just meant it as a general note that when doubling the size of the map, without changing the game mechanics, the calculation time can be more than doubled, which means there is a limit to how big we can make our maps.