Joey's Code Lab

HUAIDONG WANG wrote:
> Dear John Carmack:
>
> I don't know if you can get this email or not, I have been following 
> your work for a long time, but I was in China, cannot be there at 
> Quakecon, now that I am in Penn State, I can come to Quakecon this year.
>
> For this quakecon, can you talk a little about how far have you been 
> on the unified rendering architecture? that you mentioned in a couple 
> of quakecon, you said you are close to build a architecture for 
> rendering like Renderman did.
The short answer is that I backed away from that.  When targeting a 60hz 
game on current gen consoles, it is still necessary to think like a game 
engine.  You could make a commercial game with a truly general 
architecture, but it wouldn't be at the AAA level currently due to the 
compromises.

John Carmack

I finally figured out a proper way to achieve collision detection.

so far I have tried 4 ways of doing it, but it turns out that the last one is the most realistic one.

first let me describe what I want to do:

I want to do a decent collision detection between two rectangles (one is the car, the other is the wall). In my case ,the walls are axis-aligned. I used a 2 dimentional array to generate the wall.

since my map is generated by a 2d array, so it's easy to determine whether one point is in the wall or not.
using
             int m=(-y)/side_length_of_each_tile;
             int n=x/side_length_of_each_tile;
              if (map[m][n]=="The tile number you set as a wall")
                  then  this point is in the wall
the hard part is to determine which side of the wall is the car colliding, so that I can figure out if the car is gonna turn clockwise or counterclockwise.

before I explain,  there is one thing, my map is generated to the 2nd quadrant. that means map[0][0] is at (0,0), map[m][n] is at (MAP_W,-MAP_H)

let me go over the method that I think is the best so far:

1. vertices test
    for each collision test cycle, I test all 4 or the vertices of my car, and determine if one of them is in the wall, and then calculate this point's distance to the middle points of the four sides of the
wall tile to figure out which side is the car colliding, so that we can find out the normals, and to determine the turning direction.

let me explain here in detail:  let's say the tile is map[m][n], the the upperleft corner's coordinates is (n,-m), upperright corner's is (n+1,-m), and so on.

then calculate the mid points of all four sides, and find the smallest distance, and that one is the side that the car is colliding.

but there is one problem with this, when I was using integer m and n to find the map tile, and if I take into account the refreshing rate, it's possible that when we try to locate the point, the point is already in the wall, so there is a possibility that the smallest distance is not bewteen the point and the colliding wall.

moreover, this method requires the computer to calculate the min value every time, it's a little bit expensive.

2. improved vertices test

when I think about this problem again, I figured since all the wall tiles are axis aligned, why can't I do some optimization?

then I tried to list all the situations of collision, I thought it would be a lot, but it's not.

let's lable the upperleft corner No.1, upperright corner No.2, lowerleft corner No.3, lowerright corner No.4.

here I simplify the situation to that "if there is a collision on No.3, and No.4, the car doesn't rotate"

so , if No.1 collides:

           a) No.3 and No.4 are in the map tile map[m+1][], the normal is 270 degrees

           b) No.3 and No.4 are in the map tile map[][n+1], the normal is 180 degrees.

           c) No.3 and No.4 are in the map tile map[m-1][], the normal is 90 degrees.

           d) No.3 and No.4 are in the map tile map[][n-1], the normal is 0 degrees.

 if No.2, No.3 and No.4 collide, the situation is the same as No.1.

in this way, there is no problem of finding the min value of the distances and the error when the distances are wrong, and can find all the normals correctly.

but there is also an optimization we can do, that is , if we already know that No.1 is colliding, the car is got to be turning clockwise, we don't even have to know the normals. likewise, if No.2 is colliding, the car is gonna rotate counterclockwise. this will make life a lot simpler.

but there is another problem, this problem is still the one I raised in Method 1, when No.1 is in the wall, it's possible that No.2 is also in the wall, this will cause the car to jitter, sometimes real badly. This will lead to the next improved solution.

3. collision timer

the reason why the object jittered is that the time difference is too small, and they just go back and forth a thousands of times, that means thousands of collisions per second. So to get rid of this, I set up a timer, if the collision time is smaller than 12 millisec, no typical collision reaction.

conclusion:

for a axis aligned wall collides with a rotating rectangle situation:

1. use vertex test

2. no need to generate normals

3. setup a timer to avoid jittering.

now that the collision detection is done, the rest of the work is to simulate the bounce reaction.this will be up to you, you can do a cheesy simulation, just rotate and stuff, or you can use momentum and angluar speed and angular acceleration to do a realistic simulation, that's all up to you now.

"FS: You have a special focus, an inspiration - how you can improve an algorithm or something. How often do these epiphanies come to you?

John: Well, I think a lot of people put too much emphasis on the epiphanies. Epiphanies are there, you do get them where you see clearly into something and all that. But it really is true that most great works aren't a result of epiphanies, they're the result of lots of hard labor. That is a trap that a lot of people fall into where you think that the epiphany is the important thing. Sometimes it is, but in 95% of cases it's just a matter of smooth, calm integration of everything you know.

It's not the one brilliant decision, it's the 500 smart decisions that really make things good. It's more a matter of being able to keep making smart decisions. Making one brilliant decision and a whole bunch of mediocre ones isn't as good as making a whole bunch of generally smart decisions throughout the whole process. And there's so many of them that have to be made.

Even at the end of Quake 3, I had a to-do list of a thousand things that could potentially be improved on. So it's a matter of going through and knowing all these things that could be done, and prioritizing what the "sweet spots" are. Like "This amount of effort would get this batch of things done and it would have this side effect." Or "it would take all day to do this thing but it would probably destablize something else, so I'm not going to do it."

I definitely enjoy the epiphanies when they come - when I can be working on something and just realize that there's a much better way of doing it. That's very rewarding but I can't say that those happen every day. To a lesser degree, there's some insight where I can actually come home and tell Anna, "I figured something new out today!" That happens fairly often, and that's good.

"

1>main.obj : error LNK2019: unresolved external symbol _gluOrtho2D@32 referenced in function "void __cdecl init(void)" (?init@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glMatrixMode@4 referenced in function "void __cdecl init(void)" (?init@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glClearColor@16 referenced in function "void __cdecl init(void)" (?init@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glFlush@0 referenced in function "void __cdecl lineSegment(void)" (?lineSegment@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glEnd@0 referenced in function "void __cdecl lineSegment(void)" (?lineSegment@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glVertex2i@8 referenced in function "void __cdecl lineSegment(void)" (?lineSegment@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glBegin@4 referenced in function "void __cdecl lineSegment(void)" (?lineSegment@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glColor3f@12 referenced in function "void __cdecl lineSegment(void)" (?lineSegment@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol __imp__glClear@4 referenced in function "void __cdecl lineSegment(void)" (?lineSegment@@YAXXZ)
1>main.obj : error LNK2019: unresolved external symbol _glutMainLoop@0 referenced in function _main
1>main.obj : error LNK2019: unresolved external symbol _glutDisplayFunc@4 referenced in function _main
1>main.obj : error LNK2019: unresolved external symbol _glutCreateWindow@4 referenced in function _main
1>main.obj : error LNK2019: unresolved external symbol _glutInitWindowSize@8 referenced in function _main
1>main.obj : error LNK2019: unresolved external symbol _glutInitWindowPosition@8 referenced in function _main
1>main.obj : error LNK2019: unresolved external symbol _glutInitDisplayMode@4 referenced in function _main
1>main.obj : error LNK2019: unresolved external symbol _glutInit@8 referenced in function _main