help: many objects

Blitz3D Forums/Blitz3D Beginners Area/help: many objects

BerndWill(Posted 2005) [#1]
Hello,

Does anyone know articles (or places to be), where I can get some profund information about how the worlds are calculated on server side with MMORPG's ?

I am trying to get some understanding, how people cope with 10.000 of objects to be calculated permanently while they live and move around in the world. I mean, if I move one spaceship and there are 10.000 of them in my solar system, does every ship object communicate with all others ... certainly not. So, how do these MMORPG guys calulcate the ships, that go in sight and have to be coped with instead of calculating 10.000 x 10.000 possible sightings, missile firings and crossovers ? How do they reduce the number of comparisons (ship A is near to B and should react) ? Do they calculate it at every renderpoint or is it calculated only one time per second ?

Ho do these guys reduce the calculation on server side during runtime ?

Thanks for getting me in there
Bernd


Matty(Posted 2005) [#2]
Use 'zones' - keep a list of all the ships in a particular zone and only check for sightings of those within the same zone (or within the zone and any adjacent zones)


BerndWill(Posted 2005) [#3]
As I understand it, you mean, 10.000 ship positions are divided into zones (e.g. solar systems) and for each zone, all ships are compared to each other each ... frame rate !? No, I think not every frame rate, but how often then to achieve a seamless representation on the client ? When is this calulcation done on server side ? Is the position of the ships calulacted every minute or second or is the recalculation triggered by events ?

If you have 100 ships in one zone and they all move around, and let's say we need to use 10 bytes to tell the clients, where one of those ships is and where it is heading to, we have to send 100(ships) x 10(bytes) around every second to get the clients updated. Is this correct ?

Found this nice article about minimal network transfer: http://www.gamasutra.com/features/20050613/amir_pfv.htm

Bernd


BlackJumper(Posted 2005) [#4]
Space is full of a lot of... err... empty space.

This means that you can find ways to compress the 'decision space' down into much smaller units. In addition to solar system zones, you could implement something like sparse arrays (hashing) or an octtree (binary space partition) to ignore much of the empty bits and focus on the actual objects in each zone.

This will be less effective if you have some sort of sensors that give a 'radar' reading of where all ships are within the zone - but at least you would avoid having to consider laser fire, etc. for events offscreen.


BerndWill(Posted 2005) [#5]
Hi Jumper,

the problem with radard sensors is, that every object has to calulcate whether the other objects are inside the radar. Even if you reduce the ships to the number inside the current zone of the ship, there is a huge calculation done this way that you suggest. If there are 10.000 ships in space and 100 ships in my ships zone, my ships radar has to check for the remaining 99 ships, whether they are in sight. And the 99 ships themselves have to check their radar again. So we easily get a factorial count of 100! calculations even for only one zone.

So, there must be some more intelligent techniques.

Bernd


Sir Gak(Posted 2005) [#6]
It would not be 100!, but 100^2, or 10,000. When you have 100 objects, each doing 100 calcs, that's 100 x 100 = 10,000. I'll take 10,000 over a factorial 100! anyday.

For enquiring minds that want to know, 100! =
9.332621544394415268169923885627e+157,
or roughly 9 followed by 157 zeroes. Even Blitz would take a while to run through that many calculations. In fact, at 1 million calculations per seconds, it would take
9.33e+151 seconds, or more seconds that the theoretical age of the known universe--by a factor of 1.479677439179733521716438972226e+134 times longer than the age of the universe. IN still other words, it would take more than 1.47 million million million million million million million million million million million million million million million million million million million million million million times the age of the universe (i.e. that being supposed at 20 million million years).

Come to think of it, that's a number VASTLY larger than the sum total of all sub-atomic particles in the entire universe, including the theoretical dark matter and dark energy photons.

Conclusion: You DON'T want to count to 100!


BerndWill(Posted 2005) [#7]
yep, you are right 100^2 is the right formula.

Nevertheless it is a lot CPU cost to be done 30 or 40 times per second, especially if most of the ships are most of the time out of radar access. I guess there must be a better / faster calculation strategy.

So, how do these MMORTS and MMORPG's games keep track of the distances ?

Bernd


Sir Gak(Posted 2005) [#8]
Dunno. Might hazard a guess that you could further subdivide the zones, and keep track of what zones are themselves close enough to take a look-see at with radar. If a zone were further subdivided, then maybe you only could put 10 per zone, and then you only need calculate 10 x 10 or 100 calcs. If a zone isn't close enough, then all 10 in that zone don't have to be calculated.


BerndWill(Posted 2005) [#9]
this means, that the network communication is depending on the number of ships inside a zone area - with big fights, we will have x^2 calculations anyway; if the number of ships inside a zone is limited, it could sort out maybe.

another question is, how often the ship positions are recalculated. I dont thnik it must be every frame; it could also guessed on client side for some time and synchronized every 5 seconds or so. is this makeable ?

Bernd


BlackJumper(Posted 2005) [#10]
If there are 10.000 ships in space and 100 ships in my ships zone, my ships radar has to check for the remaining 99 ships, whether they are in sight.

Might hazard a guess that you could further subdivide the zones


... this is what I was suggesting with the use of an octtree. (Google this !) Each solar system zone is treated as a cube that is split into 8 smaller cubes. In turn, each of these 8 cubelets is split into 8 even smaller cubes... etc. etc. click for diagram

For weak radar (or screen view) you would go down quite a few levels. For a powerful radar you would show everything only a few (one ?) level down from the root.

How many ships are likely to be within combat or radar range of each other at any one time ?

[edit]
Of course any attempt to split the space into units may lead to 'popping' as ships cross the boundary between adjacent zones - something to consider in the early design stages.

It might be worth looking at splitting space into tracks and sectors in a way similar to how harddisks are formatted (assuming most action will take place in the 'plane' of the solar system.) You could then create 'cylinders' by recording the height above/below the solar system plane for ships.
[/edit]


BerndWill(Posted 2005) [#11]
Thanks Jumper,

these are some very nice ideas. How do you find these kind of wonderfull documentations ? Simply by googling around ... !?

Thanks
Bernd


BlackJumper(Posted 2005) [#12]
{third go at this... the server ate my other two posts :-( }

I have some volumes from the "Game Programming Gems" series published by Charles River Media. These were real eye-openers about tricks and techniques used for game world representation.

Most of the articles in them are aimed at C++ coders, but the sheer variety of topics covered is invaluable. Most of the stuff is probably out there on the web - but until you know about its existence or what it is called you will be in the dark.

You may find GameDev.net or Gamasutra sites valuable, but I liked the option of reading books in bed :-)


BerndWill(Posted 2005) [#13]
and there you found that octree thing ?


Bernd


BlackJumper(Posted 2005) [#14]
I had a job interview with a Games Dev company a few years back. Completely out of the blue - saw an ad in the local paper for Science/Maths/Computing graduates with an interest in games. I was teaching IT in a high school at the time, but had a rich background in paper-based role-playing games.

At the first interview I was asked how I would model the wake of a boat... I had no clue, but was advised to look into "Binary Space Partition". By the second interview a week later I knew all about octrees, k-trees and BSPs. I had also managed to knock up a 2D demo of a boat wake using DX7 direct draw.

I didn't get the job (they were driving game specialists and I was waxing lyrical about RPGs), but I set my sights on game programming as a result of that interview and I bought Blitz3D a few months later.

Anyway... my point is that the "Game Programming Gems" books will throw whole new areas of creativity in your path (splines for interpolation, world generation using Rand(seed), neural nets for bot learning, flocking algorithms for emergent behaviour, etc., etc.) that will make you start to think outside the box when dealing with world-building problems.


BerndWill(Posted 2005) [#15]
Hi BlackJumper,

thanks for that nice introduction. So, which of the gems (1...5) is the best / preferable ? Which ones would you buy first, which is last in the list ? And what you think about the "wisdom" gems ?

Regards
Bernd


DH(Posted 2005) [#16]
BerndWill

Get all 5! Read them cover to cover (dont skip chapters).

With what your talking about (doing some sort of MMORPG), you will want a ton of tricks up your sleeve before you even beging a project of that nature, and alone at that.

BlackJumper is very correct, the Gems series is VERY informative. I have 2 of them, and considered the tricks and tip creative and valuable. Even if I don't actively use all the tricks and what not, at least their embedded in my brain for when I am brainstorming the engine structure for game <insert title here>.

To have no way to accomplish something is bad.

To have one way is good, but will limit you when the unforseen approaches

To have many ways to do something will give you options around many unforseens.

Attempting a MMORPG or something similar is a bad idea in my eyes, but everyone to their own I guess.


BlackJumper(Posted 2005) [#17]
@BerndWill:
(from memory) GPGs I is a very good introduction to techniques from a wide variety of game genres. GPGs II and onwards seemed to specialise on specific aspects of these - much more depth but less eclectic than the first one.

Amazon often do bundles and Charles River offer a package of the first three - both good ways to save on multiple volumes... but I would recommend that you get hold of Vol I to see whether the style suits you...