Sign in to follow this  
Win32

2D MMO Physics Simulation Performance

Recommended Posts

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]

Share this post


Link to post
Share on other sites
A celular automata then.

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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[i].x++;
elements[i].y++;
elements[i].z++;
n += (int)elements[i].x;
}
std::cout << timer.elapsed() << std::endl;
std::cout << n << std::endl;
}
This gives me:
Quote:
0.019
2200000
The 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.

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this