Wall Performance
I've been having a lot of trouble with my wall collision engine. I'm using only the 90.0, 180.0, 270.0, and 360.0/0.0 angles for the walls, and then loading them into an array for each angle. How can I throw away the collision walls that are too far away and aren't used? I have 54 walls total so its really slowing the game down.
Thanks,
Iceman
Thanks,
Iceman
Is that really your performance problem? It seems to me it would be quite difficult to write a wall collision routine that was that slow for only 54 walls... Have you done a profile to see?
Assuming it is:
I could suggest all sorts of horrifically complicated things...
You can throw away half your walls each time  if that player is moving north, you can ignore the northfacing walls and check the southfacing ones. If they're moving east, you can ignore the eastfacing walls and check the westfacing ones, &c.
Also, if you have a vertical wall, you know its top & bottom, and you don't need to test against that wall if the player's y coordinate is higher than the top or lower than the bottom (give or take a radius). Similarly for horizontal.
Assuming it is:
I could suggest all sorts of horrifically complicated things...
You can throw away half your walls each time  if that player is moving north, you can ignore the northfacing walls and check the southfacing ones. If they're moving east, you can ignore the eastfacing walls and check the westfacing ones, &c.
Also, if you have a vertical wall, you know its top & bottom, and you don't need to test against that wall if the player's y coordinate is higher than the top or lower than the bottom (give or take a radius). Similarly for horizontal.
Hmm...
How are you testing collision right now? Unless you have several thousand objects, doing 54 collision tests for even a thousand objects shouldn't be a major speed hit unless you're doing the tests in a bad way. As far as the actual collision test process, the best way I can think of is:
If an object didn't move more than half it's radius, do one linecircle tests for the end position of the objects. If if did move farther than it's radius you'd need an extra lineline test. If you're doing noncircular objects you can use a bounding circle and then do the finer test only if it passes.
As for the collision tests themselves, you're probably best off storing walls as a normal vector and distance from the origin. This lets you do an initial tests that will (on average) eliminate all but log(n) lines in a few multiplies, some adds and subtracts, one absolute value, and one compare each. After that you can test whether it actually hit with a few more multiplies and subtracts, and maybe one divide. If anyone is interested in the math of how I'd do this, let me know.
As for optimizing which tests you do, here's some options:
BSP the walls. This is a fairly simple algorithm and gives you O(log(n)) time collision tests (or thereabouts). If anyone wants a more detailed explanation of why BSP is simple compared to the rest, and how I'd do the BSP, let me know.
Grid map. Divide your map into a (finite) grid. For every tile store a list of all walls that either intersect it, come within the maximum object radius of any of the corners, or who's endpoints are within the maximum object radius of it.
Quad Tree. Probably pointless for this, not going into details.
angular array binary search trees. Not sure if this would work actually. But I read a cool PDF about using it for fast BSP generation so I felt I should mention it.
How are you testing collision right now? Unless you have several thousand objects, doing 54 collision tests for even a thousand objects shouldn't be a major speed hit unless you're doing the tests in a bad way. As far as the actual collision test process, the best way I can think of is:
If an object didn't move more than half it's radius, do one linecircle tests for the end position of the objects. If if did move farther than it's radius you'd need an extra lineline test. If you're doing noncircular objects you can use a bounding circle and then do the finer test only if it passes.
As for the collision tests themselves, you're probably best off storing walls as a normal vector and distance from the origin. This lets you do an initial tests that will (on average) eliminate all but log(n) lines in a few multiplies, some adds and subtracts, one absolute value, and one compare each. After that you can test whether it actually hit with a few more multiplies and subtracts, and maybe one divide. If anyone is interested in the math of how I'd do this, let me know.
As for optimizing which tests you do, here's some options:
BSP the walls. This is a fairly simple algorithm and gives you O(log(n)) time collision tests (or thereabouts). If anyone wants a more detailed explanation of why BSP is simple compared to the rest, and how I'd do the BSP, let me know.
Grid map. Divide your map into a (finite) grid. For every tile store a list of all walls that either intersect it, come within the maximum object radius of any of the corners, or who's endpoints are within the maximum object radius of it.
Quad Tree. Probably pointless for this, not going into details.
angular array binary search trees. Not sure if this would work actually. But I read a cool PDF about using it for fast BSP generation so I felt I should mention it.
"He who breaks a thing to find out what it is, has left the path of wisdom."
 Gandalf the GrayHat
Bring Alistair Cooke's America to DVD!
The different *Bounce0* and *Bounce90* stand for 0 and 90 degrees etc. The xBounce** and yBounce** equal the x and y coordinates that are the end points of the collision walls. Also x and yTrans are the x and y map coordinates (the negative sign outside of the x and yBounce should really be xTrans and yTrans but I did it before I realized my mistake). Finally the x and yVect are the vectors for x and yTrans.
Is there a better way to make this run a lot faster? And if so is there a tutorial with some example code in it?
Thanks,
Iceman
Code:
for (i = 0 ; i < 12; i++) {
for (p = 0 ; p < 14; p++) {
for (q = 0 ; q < 15; q++) {
for (o = 0 ; o < 13; o++) {
if(yTrans > (yBounce0[i]50) // the 50 is because the wall slopes at an angle but I still
have to use this for the tiles on the map thus the offset.
&& xTrans > (xBounce0[i]+53)
&& xTrans < (xBounce01[i]53) // the *Bounce01 stands for the other end point.
&& yTrans < (yBounce0[i]58)) {
yTrans = (yBounce0[i]50); // this is so the object doesn't get stuck in the wall.
yVect = yVect; // 0 degrees
}
if(xTrans < (xBounce90[p]+50) && yTrans > (yBounce90[p]+53)
&& yTrans < (yBounce901[p]53) && xTrans > (xBounce90[p]+58)) {
xTrans = (xBounce90[p]+50);
xVect = xVect; // 90 degrees
}
if(yTrans < (yBounce180[q]+50) && xTrans < (xBounce180[q]53)
&& xTrans > (xBounce1801[q]+53) && yTrans > (yBounce180[q]+58)) {
yTrans = (yBounce180[q]+50);
yVect = yVect; // 180 degrees
}
if(xTrans > (xBounce270[o]50) && yTrans < (yBounce270[o]53)
&& yTrans > (yBounce2701[o]+53) && xTrans < (xBounce270[o]58)) {
xTrans = (xBounce270[o]50);
xVect = xVect; // 270 degrees
}
}
}
}
}
Thanks,
Iceman
Try this:
The code you posted was checking every combination of walls, instead of just every wall. I'm a little surprised it worked at all...
Code:
for (int r = 0; r < 12; ++r) {
if (yTrans > (yBounce0[r]50)
&& xTrans > (xBounce0[r]+53)
&& xTrans < (xBounce01[r]53)
&& yTrans < (yBounce0[r]58)) {
yTrans = (yBounce0[r]50);
yVect = yVect;
}
}
for (int p = 0; p < 14; ++p) {
if( xTrans < (xBounce90[p]+50)
&& yTrans > (yBounce90[p]+53)
&& yTrans < (yBounce901[p]53)
&& xTrans > (xBounce90[p]+58)) {
xTrans = (xBounce90[p]+50);
xVect = xVect; // 90 degrees
}
}
for (int q = 0; q < 15; ++q) {
if (yTrans < (yBounce180[q]+50)
&& xTrans < (xBounce180[q]53)
&& xTrans > (xBounce1801[q]+53)
&& yTrans > (yBounce180[q]+58)) {
yTrans = (yBounce180[q]+50);
yVect = yVect; // 180 degrees
}
}
for (int o = 0; o < 13; ++o) {
if (xTrans > (xBounce270[o]50)
&& yTrans < (yBounce270[o]53)
&& yTrans > (yBounce2701[o]+53)
&& xTrans < (xBounce270[o]58)) {
xTrans = (xBounce270[o]50);
xVect = xVect; // 270 degrees
}
}
The code you posted was checking every combination of walls, instead of just every wall. I'm a little surprised it worked at all...
Thanks so much it runs 100 times faster! Before all I got was that beach ball thingy and a white screen. Also I realized I had done the same horrible mistake with another part of the game code.
Thanks again,
Iceman
Thanks again,
Iceman
I've been having some trouble with performance issues on my wall collision again. I think it has something to do with how I'm loading the functions. Which one is correct?
or should it be like this:
Are these both wrong?
Thanks,
Iceman
Code:
 (void) collision {
for (j = 0; j < 10; j++) {
for (i = 0; i < 10; i++) {
if (something1[i]) {
// something goes here
}
if (something2[i] && something3[i][j]) {
// something goes here
}
}
for (k = 0; k < 10; k++) {
if (something4[k]) {
// something goes here
}
if (something5[k] && something6[k][j]) {
// something goes here
}
}
}
}
or should it be like this:
Code:
 (void) collision {
for (i = 0; i < 10; i++) {
if (something1[i]) {
// something goes here
}
for (j = 0; j < 10; j++) {
if (something2[i] && something3[i][j]) {
// something goes here
}
}
}
for (k = 0; k < 10; k++) {
if (something4[k]) {
// something goes here
}
for (j = 0; j < 10; j++) {
if (something5[k] && something6[k][j]) {
// something goes here
}
}
}
}
Are these both wrong?
Thanks,
Iceman
I don't know whether they're wrong or right, but they look to be equivalent, except for the order in which you look at your items.
Assuming the ifs you moved out of the inner loops don't care if they're repeated or not, the second form is equivelant. The fastest version would be loops like this:
Code:
for (i = 0; i < 10; i++) {
if (something1[i]) {
// something goes here
}
if (something2[i]) {
for (j = 0; j < 10; j++) {
if (something3[i][j]) {
// something goes here
}
}
}
}
"He who breaks a thing to find out what it is, has left the path of wisdom."
 Gandalf the GrayHat
Bring Alistair Cooke's America to DVD!
Thanks; although, it still seems to be running very slow. I think this should explain it better here's some actual code from my game:
First the rocks start out as a rock(x/y)1[*], then split into rock(x/y)2[*][*], and finally break up into rock(x/y)3[*][*][*]. rock(x/y)1[*] stands for the large rocks x and y coords, rock(x/y)2[*][*] stands for the medium rocks, and rock(x/y)3[*] [*][*] stands for the small rocks. Also the rock*v* stands for the vector. Additionally The rockRandL[k] and rockRandM[k][l] can be a random number between 1 and 3. Thus I can have 180 small rocks bouncing at one time. What is it that's causing such a slow down?
Thanks again,
Iceman
Code:
define# ROCKS 20;
for(i = 0; i < WALL; i++) {
for(k = 0; k < ROCKS; k++) {
// The Large Rocks 20 & +20 for the edges
if(rocky1[k] < (yBounce0[i]30)
&& rockx1[k] < (xBounce0[i]+73)
&& rockx1[k] > (xBounce01[i]73)
&& rocky1[k] > (yBounce0[i]33)) {
rocky1[k] = (yBounce0[i]30);
rockyv1[k] = rockyv1[k]; // 0 degrees
}
for(l = 0; l < rockRandL[k]; l++) {
// The Medium Rocks 10 & +10 for the edges
if(rocky2[k][l] < (yBounce0[i]40)
&& rockx2[k][l] < (xBounce0[i]+63)
&& rockx2[k][l] > (xBounce01[i]63)
&& rocky2[k][l] > (yBounce0[i]43)) {
rocky2[k][l] = (yBounce0[i]40);
rockyv2[k][l] = rockyv2[k][l]; // 0 degrees
}
for(m = 0; m < rockRandM[k][l]; m++) {
// The Small Rocks 0 & +0 for the edges
if(rocky3[k][l][m] < (yBounce0[i]50)
&& rockx3[k][l][m] < (xBounce0[i]+53)
&& rockx3[k][l][m] > (xBounce01[i]53)
&& rocky3[k][l][m] > (yBounce0[i]53)) {
rocky3[k][l][m] = (yBounce0[i]50);
rockyv3[k][l][m] = rockyv3[k][l][m]; // 0 degrees
}
}
}
}
}
for(p = 0; p < OTHERWALL; p++) {
for(k = 0; k < ROCKS; k++) {
if(rockx1[k] > (xBounce90[p]+30)
&& rocky1[k] < (yBounce90[p]+73)
&& rocky1[k] > (yBounce901[p]73)
&& rockx1[k] < (xBounce90[p]+33)) {
rockx1[k] = (xBounce90[p]+30);
rockxv1[k] = rockxv1[k]; // 90 degrees
}
for(l = 0; l < rockRandL[k]; l++) {
if(rockx2[k][l] > (xBounce90[p]+40)
&& rocky2[k][l] < (yBounce90[p]+63)
&& rocky2[k][l] > (yBounce901[p]63)
&& rockx2[k][l] < (xBounce90[p]+43)) {
rockx2[k][l] = (xBounce90[p]+40);
rockxv2[k][l] = rockxv2[k][l]; // 90 degrees
}
for(m = 0; m < rockRandM[k][l]; m++) {
if(rockx3[k][l][m] > (xBounce90[p]+50)
&& rocky3[k][l][m] < (yBounce90[p]+53)
&& rocky3[k][l][m] > (yBounce901[p]53)
&& rockx3[k][l][m] < (xBounce90[p]+53)) {
rockx3[k][l][m] = (xBounce90[p]+50);
rockxv3[k][l][m] = rockxv3[k][l][m]; // 90 degrees
}
}
}
}
}
First the rocks start out as a rock(x/y)1[*], then split into rock(x/y)2[*][*], and finally break up into rock(x/y)3[*][*][*]. rock(x/y)1[*] stands for the large rocks x and y coords, rock(x/y)2[*][*] stands for the medium rocks, and rock(x/y)3[*] [*][*] stands for the small rocks. Also the rock*v* stands for the vector. Additionally The rockRandL[k] and rockRandM[k][l] can be a random number between 1 and 3. Thus I can have 180 small rocks bouncing at one time. What is it that's causing such a slow down?
Thanks again,
Iceman
I cant make much heads or tails of your code. But I know its wrong. Your indenting makes it look at first glance that in your i and p loops you are doing three loops one after another  but you are really doing three *nested* loops.
Also why are large rocks in a onedimentional array, while medium rocks are in a twodimentional array and small rocks are in a threedimentional array??
Get a c/c++ book and study up on loops and arrays. You tend to make nested loops when you really need sequential loops  and you tend to make multidimentional arrays when you really need onedimentional arrays. Remember  every time you nest another loop  or add another dimention to an array you *exponentially* take up more time and memory.
here is a suggestion. Simplify! Do something like:
hth,
Codemattic
Also why are large rocks in a onedimentional array, while medium rocks are in a twodimentional array and small rocks are in a threedimentional array??
Get a c/c++ book and study up on loops and arrays. You tend to make nested loops when you really need sequential loops  and you tend to make multidimentional arrays when you really need onedimentional arrays. Remember  every time you nest another loop  or add another dimention to an array you *exponentially* take up more time and memory.
here is a suggestion. Simplify! Do something like:
Code:
define# kNumRocks 20;
define# kNumWalls 20;
typedef struct {
float x, y, radius; //radius = 20.0 for big, 10.0 for medium, 2.0 for small
} rocksStruct;
typedef struct {
float left, right, top, bottom;
//in a horizontal wall top=bottom
//in a vertical wall left=right
} wallsStruct;
rocksStruct rock[kNumRocks];
wallsStruct wall[kNumWalls];
for(i = 0; i < kNumRocks; i++) {
for(k = 0; k < kNumWalls; k++) {
//compare rock[i] and wall[k] and take action
}
}
hth,
Codemattic
Sorry. Yeah I just read it again and I realized I forgot how to add. Ok it's 240 small rocks not 180. Here's an example:
Thanks,
Iceman
Code:
O are the rocks
O Rocks (there are 20 of these at the beginning they split into the lower levels once hit)

O O O rockRandL(this is a random number of rocks between 1 and 3; three are shown)
  
O O O O O O O O O rockRandM(each group of three works just as rockRandL)
Thanks,
Iceman