Overlapping Objects Creates Lag

May 17, 2012 at 4:04 AM
Edited May 17, 2012 at 4:04 AM

Hey guys, so I've been working on an MMO that uses Farseer for about 8 months now. Posted in here a few times now.

One issue that I'm discovering is that when lots of objects sit on top of each other, the AABB engine still fires off (even when they're set to ignore) and it creates a lot of lag. From my experience, that's what the error is. The more objects that stack, the higher the lag. O(N^2) it feels like.

We use a string for userdata and we trim off the first X characters to get the number associated with the bullet, to set data to destroy it.

This method seems inefficient though. And could be the cause of the lag. How do you guys manage OnCollision and have you noticed this issue before?

BTW we're talking about 600 bullets when we start to lag. Without them touching (mostly) it's around 1400.

image link: http://spacerambles.com/forums/download/file.php?id=338&mode=view

May 17, 2012 at 1:50 PM


Well pretty much what I would expect in terms of performance based on my experience.

IMHO this is one situation where you actually don't need a physics engine to do the physics :) You have one way collisions (bullet vs ship) and no collision response needed. Much easier is to make it work as a particle system. If your bullets can be approximated as point masses (probably they can with the center  of the sprite as center of mass) then do your own motion (using Euler, Verlet or awesome precision Runge-Kutta, won't mattter much comparatively) -> get new position -> cast a ray in Farseer between old and new position -> go boom if the ray hits a fixture of a ship. You can easily get 10k or more bullets like this and the bottleneck will be the graphics engine. 

Also for the userdata - isn't it better to use bitmasks rather than string manipulation (which btw cause huge garbage).

May 17, 2012 at 2:14 PM

Man, you make me feel like a such a noob. I understand what you're talking about because before Farseer we coded our own physics engine. But we didn't use anything like Euler's equations. We just had different speeds that things moved at, no applying forces like in Farseer. That was one of the biggest, "WTF are we doing" when we switched to Farseer, because we were trying to directly set Linear Velocity.

Anyway, how do you cast a ray in Farseer? A ray being a line between two points that checks for collisions, right? Also, what exactly is a point mass? All I think of is an infinitely small point in space. How do you represent a circle or a body in your own methods?

It'd be interesting if you could elaborate a bit on bitmasks. I have no idea what you mean by that. Assuming it's some sort of special data value? How do you use userdata if you want to find a specific object? If I say, "If I collide with a star, bounce, if I collide with a ship, set life to 0" how would I find the object that holds the bullet.body?

Crikey, one more thing. How do you apply a force to an object that's bouncing off something to behave realistically? This is why we gave up on our physics engine. We couldn't figure out a way to do this. And one of our programmers is a physics major, lol. We figured out gravity easily enough, but not bouncing. >.<

With our old simple physics engine I could get about 120k bullets before I started lagging. :D But the amount of bugs was silly, so we dropped it.

If we did write a basic engine, we could make use of OpenCL for some of the calculations. We've been talking about using OpenCL for when we implement authoritative physics. Look at Bullet, it's amazing. I'd hope to be able to do something like that to lower CPU load. Because 60k cubes at 30 fps is ridiculous.

May 17, 2012 at 9:28 PM

Bullet is really absolutely amazing, I agree, and their OpenCL implementation is ultra-cool. I had been looking at OpenTK and Cloo to do some stuff in Farseer but perhaps bullet-sharp when they implement the opencl bindings will be a more solid choice.

About raycasts - really they are nothing special. They still use the standard broadphase. It's, of course, just a line that you shoot between point1 and point2 and you get the intersections in the callback. The method is World.Raycast(). You must decide if your projectiles will actually have a shape that can collide or you can just approximate them as a point and thus be able to check for collisions just with raycasts. Basically the sprite might overlap a bit with the target ship but its center could be outside and will not register a raycast collision. If, instead, you actually you need projectiles with some volume you can cheat - for example for a circle you can cast two rays tangential to the circle and parallel to the velocity vector. Mathematically there are exactly two such lines separated by pi radians. These two rays will create a "bounding path" for the projected movement and if the projectile is smaller than the target then definitely at least one will hit it.  If it's larger you need more rays still parallel but originating from "inside" the circle). Still easy to do. And so on. The objective is to not overburden the engine using the fact that you deal with a specific situation that you can describe better analytically whereas the engine is designed to work in all scenarios equally good (or "bad").

In one of my own simulations I needed a huge complex fluid mechanics thing so I had to do extreme optimization. I used a grid based method. Split the space into a grid and do raycasts as if each cell is a single entity. A grid cell is either full of something or empty. Thus in the real world (well Farseer world) my "raycasts" would actually be thick lines instead of infinitely thin ones. This gives me pretty good performance but it's just one way of doing stuff like that.

About the userdata it's just a pointer - you can put anything in it. You can put a reference to a class that contains all information you need (like the sprite, object descriptor etc.). I'm not sure I understand your question correctly.

As for bouncing you're asking how to do a collision response :) http://en.wikipedia.org/wiki/Collision_response Well I'm just a user of Farseer but this is an interesting and difficult topic especially if you need forces, friction, restitution etc. The point is that a custom physics engine might outperform easily a stock one because it has more knowledge about the scenario and can be optimized skipping non esential stuff. So it's always worth investigating the possibilty. There are several tutorials on the net (check gamedev, gafferongames, amazing fluid engine using vortons by Intel etc.). There is even a tutorial by genbox himself (after all Farseer 2.x was an original engine and not a port of Box2D) - http://ianqvist.blogspot.it/search/label/Physics Unfortunately he didn't get to writing about collision response. 

May 18, 2012 at 4:06 AM

First off, I would just like to say thank you. That's a very helpful bit of information!

So today my Physics colleague and I have been working on these for a few hours now. The raycasts are pretty straight forward. No issues figuring that out so far (fingers crossed). The main thing that's stumping us right now is the userdata. We understand that in C# you can say an Object = Object2 and it creates a pointer. We're trying to figure out how to get access to userdata without casting. In the test bed that comes with Farseer it looks like they cast userdata to an int to get access to the object. So that suggests that there is no better way to do it. How do you do this generally? And if so, do you have any code snippets that you'd be willing to share on the matter?

I'll share more info when I find out more on OpenCL. One of my good friends recently wrote a graphing calculator in OpenCL just for kicks. I'll chat him and see what he thinks about this. I wonder if because Farseer runs in it's own threads and we're calling World.Raycast() that we'd be able to offload much to the GPU. All I can think of is movement of the bullets, but that hardly seems like a big improvement in speed. Atleast without rewriting segments of Farseer to run on the GPU.

May 18, 2012 at 12:04 PM

You need to cast the userdata to a class, no way around that. Or in other words use some OOP pattern like Bridge or Strategy. Actually a classical example for your scenario is the http://en.wikipedia.org/wiki/Double_dispatch

It's similar to how you process input events - an event comes (in your case a collision happens) and we must decide if it's keyboard, mouse etc. and react to it.

But to give a simple example store an int in the userdata as an object descriptor. Then have a big switch block: if intUserData is a ship-type do ship collision, if intUserData is a star-type do star collision etc.

For OpenCL it would be nice if Farseer directly supported it. But since it doesn't what you can do is implement your own broadphase in OpenCL. For example copy the Farseer broadphase tree (the AABBs) at the beginning of each time step to the GPU and do your own raycasting on the GPU together with bullet movement. It's important to figure out where the performance bottleneck is first and whether it's worth it. The GPU can give you immense boost but if it's only to 1% of the runtime it's not worth the extra complexity, not to mention the whole transferring to GPU memory is expensive.