# Help choosing a collision prediction method?

This takes a little backstory, bear with me.

This is also a very general question, and I'm aware that without greater specifics the best answer might be "it depends."

So the context is that we're doing a real-time two-player iPhone game, with one iPhone acting as host and the other as client.

One of the things that's happening in the game, that needs to sync properly across devices, is similar to a Break-Out style situation: multiple rows of bricks at the top of the screen and a ball that bounces up and destroys them.

The wrinkle is that the projectile is more like a bullet than a ball. It takes out all the bricks in its path.

So to sync this across devices, what we're doing is calculating all the bricks that will be hit as soon as the bullet launches along a given trajectory. We have to do this because due to the physics model we're using, if we just launch the bullet at the identical angle and identical velocity on each of the two devices, the bullet ends up taking out slightly different bricks on each device.

So that's the task at hand: we need a calculation of all the bricks that will be taken out by a given bullet. Once we have that, we can send that array to the client, and then (ideally) the clients knows what bricks to take out before the bullet actually hits them, and the games sync infinitely better than if the collisions were reported in real time.

The last important element to consider is that there can be lots of bullets shooting at once. Anywhere from 4-40+ of these arrays need to be calculated as rapidly as possible.

So what's the best way to do it? We've thought of two ways:

1) Drawing an imaginary line along the path of the bullet and detecting all the bricks it intersects.

2) Shooting a separate invisible bullet along the normal bullet's path at something like 20x faster velocity. This "phantom bullet" doesn't cause any reaction upon contact with the bricks, it just passes right through them. But when it passes through a brick, that brick gets added to an array, and it ends up creating the array we need.

I should note that we've actually implemented option 1, and it works really well. The only problem is that when we get upwards of ten or twenty bullets it seems to cause massive slowdown. We're considering option 2 to try to boost framerate because we think it would be easier on the processor.

So, we're looking for a way to figure out if that's true.

I know that different physics simulators are different, and everything is different and difference is different and etc. etc. different, but I guess I was wondering if anyone has a general idea whether or not, in general, one of these methods should perform better than the other.

I'm hoping there's some knowledgeable individual here that can provide insight--or even suggest a simple test we could do to find out for ourselves.

• Share a ray between the two games. With the ray you should be able to easily do ray/rectangle intersection tests. Alternatively, just sync an array that lists each of the rectangles that will be removed. Option 2 isn't going to be faster than option 1. You're likely just doing option 1 in a poorly implemented way. – MichaelHouse Sep 10 '13 at 18:17
• @Byte56, is there a reason people prefer to leave answers as comments rather than, you know, as answers? That's a good idea and I'm interested in asking you about it, but why not leave it as an answer? – Le Mot Juiced Sep 10 '13 at 18:40
• Mostly because I think it's just my opinion. I didn't want to put the full work into a fully fleshed out answer, but had a suggestion for you and wanted to share it. It's just my guess of what would work. I think the question is a bit broad, and maybe opinion based. Since most of the answers you'd get would be different but all of them would be equally valid. – MichaelHouse Sep 10 '13 at 18:46

## 2 Answers

Before implementing a new solution you should make profiling tests to identify the bottleneck of your application. I think it must be either the data transfer latency between host and client or the processor capabilities of devices. Just make simple stress tests in both cases and profile the results.

For example, if the results show that you have problems with transfer latency you must minimize data transfer. A solution could be to send the ray description over network and make the two devices calculate the entire collision in parallel. As a prerequisite you must have a way to offset the angle or velocity error to achieve the same trajectory in the host. You could make a test to see if this error is predictable.

If sending data over network is not the bottleneck you could divide the processing among host and client by letting each one check collisions for one half of the trajectory, for example. As a prerequisite the client must have the capability to send data to the host for sync.

create a grid for your playing field

each brick is composed of one or more grid spaces

when you shoot a bullet it goes at a certain angle from perpendicular take the tangent (tan) of that and you can do the following:

double y=starty;
for(int i=0;i<maxX;i++){

if(tan>0){
for (int ytmp=floor(y);ytmp<=floor(tan+y);ytmp++){
GridBlock gr = grid[i][floor(y)];
if(containsBrick(gr)){
//remove brick
}
}
}else{
for (int ytmp=floor(y);ytmp>=floor(tan+y);ytmp--){
GridBlock gr = grid[i][floor(y)];
if(containsBrick(gr)){
//remove brick
}
}
}
y+=tan;
}


the main speedup I introduce here is not looping over all bricks but instead going over a grid and checking for each cell whether there is a brick that needs to be removed and you don't have to muck about with line-line intersections

just transmit the tan and starty with as much accuracy as possible

note I didn't account for wall bouncing