2D MMO Physics Simulation Performance
Author
Hello,
I've devised an approach for physics simulation for a long-standing isometric- MMO(RPG) project of mine and am looking to see how it compares performance-wise to game's with comparable requirements [as follows]:
* World is uniform grid; objects assume a pattern (not necessarily rectangular) of cells which constitutes it's "footprint". Movement is ofcourse at a smaller granularity.
* Simple physics; movement, velocity, acceleration.
* Capable of simulating objects which can advance a maximum of 50cells/s
I'm considering physics simulation to include both state update and collision detection (not resolution). That being said, the method I'm using is capable of simulating ~2,200,000 mobile objects in an absolute worst-case scenario.
[Edited by - Win32 on February 22, 2010 8:45:34 AM]
A celular automata then.
At what rate? One update per hour? Per second? 100 per second?
This is a similar project, which runs at fixed update rate of 22 updates per second (so over half a million entity simulations per second), but can apparently scale upwards from that.
There are none with comparable requirements. Reason being, it is not about updating millions of NPCs, it is about how that information would be sent to players. Another problem is that just seeing millions of drones going about their business is boring - but interactions have above-linear complexity, quadratic in worst case.
This type of simulations is typically used for other, non-MMO purposes, such as disaster simulations. But there the interaction with environment cannot be trivialized, and while a grid-based approach can be used, it is often preferred to simply use a cluster of machines instead and simulate off-line, but with full 3D or vector-based area, semi-accurately simulating interactions between bodies. See also Massive from Weta Digital on how they do it (it's not real-time or interactive, but instead of very high quality).
Main reason why such huge numbers are not all that important is because they tend to be not interesting. Most of designs these days are focusing on small, controlled and fine-tuned content with as few variables as possible.
Quote:capable of simulating ~2,200,000 mobile objects
At what rate? One update per hour? Per second? 100 per second?
This is a similar project, which runs at fixed update rate of 22 updates per second (so over half a million entity simulations per second), but can apparently scale upwards from that.
Quote:MMO(RPG) project of mine and am looking to see how it compares performance-wise to game's with comparable requirements
There are none with comparable requirements. Reason being, it is not about updating millions of NPCs, it is about how that information would be sent to players. Another problem is that just seeing millions of drones going about their business is boring - but interactions have above-linear complexity, quadratic in worst case.
This type of simulations is typically used for other, non-MMO purposes, such as disaster simulations. But there the interaction with environment cannot be trivialized, and while a grid-based approach can be used, it is often preferred to simply use a cluster of machines instead and simulate off-line, but with full 3D or vector-based area, semi-accurately simulating interactions between bodies. See also Massive from Weta Digital on how they do it (it's not real-time or interactive, but instead of very high quality).
Main reason why such huge numbers are not all that important is because they tend to be not interesting. Most of designs these days are focusing on small, controlled and fine-tuned content with as few variables as possible.
As Antheus said, it is hard to say how good it is without context:
- size each cell, size of each object, size of the entire scene?
- density of objects per cell?
Those will hugely affect performance. BTW, this paper might interest you to compare:
http://www.cs.ucf.edu/~hastings/papers/hashing-sim.zip
It is from several years ago, but it reports results for a grid-based system to simultaneously do object-object collision resolution, object-terrain collision resolution, a proximity AI routine, and visibility determination for 10k-20k objects on 2004 hardware.
- size each cell, size of each object, size of the entire scene?
- density of objects per cell?
Those will hugely affect performance. BTW, this paper might interest you to compare:
http://www.cs.ucf.edu/~hastings/papers/hashing-sim.zip
It is from several years ago, but it reports results for a grid-based system to simultaneously do object-object collision resolution, object-terrain collision resolution, a proximity AI routine, and visibility determination for 10k-20k objects on 2004 hardware.
Author
Quote:
At what rate? One update per hour? Per second? 100 per second?
Discrete timesteps of 40ms.
Quote:
There are none with comparable requirements. Reason being, it is not about updating millions of NPCs, it is about how that information would be sent to players. Another problem is that just seeing millions of drones going about their business is boring - but interactions have above-linear complexity, quadratic in worst case.
This type of simulations is typically used for other, non-MMO purposes, such as disaster simulations. But there the interaction with environment cannot be trivialized, and while a grid-based approach can be used, it is often preferred to simply use a cluster of machines instead and simulate off-line, but with full 3D or vector-based area, semi-accurately simulating interactions between bodies. See also Massive from Weta Digital on how they do it (it's not real-time or interactive, but instead of very high quality).
Main reason why such huge numbers are not all that important is because they tend to be not interesting. Most of designs these days are focusing on small, controlled and fine-tuned content with as few variables as possible.
I'm well aware of this, I'm just after a baseline; I intentionally did not mention details for this reason. The propogation of game state along with most other fundamental facets are already designed.
Quote:
As Antheus said, it is hard to say how good it is without context:
- size each cell, size of each object, size of the entire scene?
- density of objects per cell?
I'm not sure how size of each cell would be of interest, but, 16x16px (iso) which in my implementation each "pixel" is further broken down to fractionals of 16 which gives me sufficient enough accuracy for simulating slow-moving objects.
Each object occupies atleast one cell [for the purposes of collision-detection only, ofcourse], the majority of objects (such as player characters and other units) occupy a single cell while terrain and the like can occupy a variable sized pattern of cells.
The world-size currently quoted is 120,000x120,000, although world-size has no impact on my algorithms performance.
Think of Baulder's Gate or Diablo.
Thanks for the link, but I've already read it.
Quote:Original post by Win32
Discrete timesteps of 40ms.
Forgive me for being skeptical, since doing update of 2.2 million objects at 40ms is simply not possible, going beyond trivial for loop.
#include <iostream>#include <vector>#include <boost/timer.hpp>struct Foo { float x, y, z;};int main() { std::vector<Foo> elements(2200000); int n = 0; boost::timer timer; for (size_t i = 0; i < elements.size(); i++) { elements.x++; elements.y++; elements.z++; n += (int)elements.x; } std::cout << timer.elapsed() << std::endl; std::cout << n << std::endl;}Quote:0.019The machine isn't fastest in the world, but still takes 19ms just to run across minimal case scenario. Splitting over the cores would divide this number evenly, but the number would quickly breakdown at anything non-trivial. Technically, the above code is capable of simulating motion of 2.2 million objects, but that is about it. As soon as branching is involved, or any non-local memory access, the time to run that will go up by several orders of magnitude.
2200000
Or perhaps there is some other definition of mobile object, and not all are updated on each step, although that doesn't change much. Then again, it also doesn't mention the hardware used.
Perhaps using something like Barnes-Hut, perhaps even GPU-based simulation, which would indeed push the numbers higher, but drastically limits what can be achieved.
Either way, if you have a demo for download, or some code, or video or anything beyond, many would surely be interested, but as of right now, the basic math simply does not add up.
Author
Skeptisim was expected :)
There's a few things that are making for an incompatible comparison. Indeed I did fail to mention the hardware my tests were run on; Intel i7 920, 1.6GHz DDR3 memory modules.
Most notably, unless you've specified elsewhere, it is likely that the dataset you're operating upon does not reside entirely in physical memory. Afterall, this simple algorithm's bottleneck is memory bandwidth.
Secondly, my algorithm does not invoke the FPU for any calculations; although not a huge impact, with large datasets it does add up.
Additionally, I can't be sure as to whether your code is optimized (that function call sticks out a mile). I've taken the step to write my algorithm in assembly as I'm not 100% satisified with the results generated by various compilers (ofcourse, I've ensured my efforts aren't in vain by comparing the real running times)
You are correct in regards to what I meant by mobile objects (all objects capable of change in position are updated). Due to the very low processing requirements of an invidual object, I do not use a selective process as to only update objects that require attention.
And to add to the skeptisim, my quote also includes collision detection.
I'll see what I can do about a demo.
There's a few things that are making for an incompatible comparison. Indeed I did fail to mention the hardware my tests were run on; Intel i7 920, 1.6GHz DDR3 memory modules.
Most notably, unless you've specified elsewhere, it is likely that the dataset you're operating upon does not reside entirely in physical memory. Afterall, this simple algorithm's bottleneck is memory bandwidth.
Secondly, my algorithm does not invoke the FPU for any calculations; although not a huge impact, with large datasets it does add up.
Additionally, I can't be sure as to whether your code is optimized (that function call sticks out a mile). I've taken the step to write my algorithm in assembly as I'm not 100% satisified with the results generated by various compilers (ofcourse, I've ensured my efforts aren't in vain by comparing the real running times)
You are correct in regards to what I meant by mobile objects (all objects capable of change in position are updated). Due to the very low processing requirements of an invidual object, I do not use a selective process as to only update objects that require attention.
And to add to the skeptisim, my quote also includes collision detection.
I'll see what I can do about a demo.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
