Wall Performance

Member
Posts: 196
Joined: 2002.04
Post: #1
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
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
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 north-facing walls and check the south-facing ones. If they're moving east, you can ignore the east-facing walls and check the west-facing 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.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #3
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 line-circle tests for the end position of the objects. If if did move farther than it's radius you'd need an extra line-line test. If you're doing non-circular 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 Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
Member
Posts: 196
Joined: 2002.04
Post: #4
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.
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
                }
            }
        }  
    }
}
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
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #5
Try this:

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...
Quote this message in a reply
Member
Posts: 196
Joined: 2002.04
Post: #6
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
Quote this message in a reply
Member
Posts: 196
Joined: 2002.04
Post: #7
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?

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
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #8
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.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #9
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 Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
Member
Posts: 196
Joined: 2002.04
Post: #10
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:
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
Quote this message in a reply
Member
Posts: 304
Joined: 2002.04
Post: #11
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 one-dimentional array, while medium rocks are in a two-dimentional array and small rocks are in a three-dimentional 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 multi-dimentional arrays when you really need one-dimentional 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
Quote this message in a reply
Member
Posts: 196
Joined: 2002.04
Post: #12
Sorry. Yeah I just read it again and I realized I forgot how to addGrin. Ok it's 240 small rocks not 180. Here's an example:
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
Quote this message in a reply
Post Reply