PC Game Programming techniques
A 3D game engine consists of many parts, in the following list I mention the most important, and I'll give an explanation about the things that are in my opinion important:
1. Initialisation hardware and software
(under contruction: Initialize videocard (VGA,VESA,other like 3Dfx), initialize timer, keyboard,mouse and other input device routines, loading data (graphics, sound and other game information), building efficient data structures.)
1.1 Graphics: VGA, SVGA (VESA) and 3Dfx
1.2 Keyboard, Timer
1.3 Datastructures: 3D BSP tree
2. Player interface and movement
(under construction, but on request, here are some lines about COLLISION DETECTION, and COLLISION HANDLING)
2.1 3D Collision detection and handling
Collision detection is an important part in a (3D) game engine. Without collision detection the player wouldn't be able to move properly through the world or have interaction with it (like shooting things for example). It is not an easy topic in a 3D environment where many objects are moving, and the world is complex. Even commercial games like Tombraider and (I hate to say it but...) QUAKE have problems in detecting and handling collisions well. In many games you get stuck on places where you shouldn't, and/or have problems when doors are opening in front of you. Good implemented collision detection can add realism and feeling to the world you are playing in.
Before going into more detail, I assume the movement of the player is done in intervals: each time span (of timelength T) the player is moved from the current position (call this CURPOSITION) to the next position (NEXTPOSITION). Furthermore I assume this movement is linear each time so the destination can be calculated by taking the current position and adding the movement to it. This means the velocity (call it V) in such time span is constant, and the formula to calculate the next position is : NEXTPOSITION = CURPOSITION + V * T. The player has a certain volume, call this VOLUME.
Okay, rests to state the collision detection problem: given the player, and object and desired motions, decide whether those come into collision over the given time span.
There are many algorithms to solve this problem, most of them fall in one of these classes:
[more information about solutions, and many references on articles about collision detection can be found in the article 'Collision Detection by Four-Dimensional Intersection Testing' IEEE Transactions on Robotics and Automation, VOL. 6, No.3, June 1990 (page 291)]
Here I will give my own solution (which doesn't falls in one of those classes) I used in the demo. The player is assumed to have a bounding SPHERE as the VOLUME, and there is no collision when the player is in CURPOSITION. In my case collision detection can be better called collision aviodance because I exactly calculate the shortest distance of how far the player is allowed to move until there will be a collision. When I have calculated this shortest distance (call it SHORTDIST), I check if the desired moving agains this distance. If the distance is less, the player can move without problem, else the player can move SHORTDIST, and then the movement must be altered (not only the shortest distance is needed but also the object that is responsible for this 'first collision'). The latter is called collision handling.
Here follows an explanation for how the shortest distance (SHORTDIST) can be calculated between a (moving) player, and a static world polygon:
Take the normalvector of the polygon, and project the midpoint of the sphere onto the surface of the sphere, in opposite direction of that normalvector. If the sphere will fully collide with the polygon, this point will be the collisionpoint on the sphere. Now calculate the intersection of the vector with this collisionpoint as startpoint and movingdirection as direction, and the plane of the polygon. If the vector and the plane are parallel there will be no intersection, else there will be a distance (SHORTDIST). If this intersectionpoint (yellow dot in picture above) lies within the polygonboundaries we are finished for this polygon, and the distance between player and other polygons can be calculated. If this intersection point is outside the polygonboundaries, the sphere may hit the polygon on the boundaries. In this case: for each polygonedge, create a plane formed by this edge and the movement direction vector, and intersect the sphere with this plane. If there is no intersection with any of these planes, then there is no collision (so SHORTDIST is infinite for this polygon).Else the distance is easily calculated (if anyone asks me howto, I'll put it here).
To avoid the 'many pairs problem' (all the collision tests between the player and EVERY polygon in the world), the worldspace can be devided into an OCTREE structure, and then only the polygons that are in the octreecells that are visited along the direction the sphere moves, have to be taken into account.
After there has been detected a collision, there must be a form of collision handling (else all detecting work is useless). The handling depends on how we want the player or object interact with the world. When a player walks for example against a wall there are several ways to handle it's movement. One way is to disable further moving of the player, so the only thing the player can do is to turn and walk into another direction. This is not a good solution in most 3d environments where the player has to move quickly and fluid. Even more important is that the difference between the floor and a wall is hard to determine in many cases. (For example in Tombraider when Lara is walking in a rocky environment). Another solution is to let the player strafe along the polygon in the projected moving direction (projected on that polygon).
The resulting direction can be calculated by projecting the desired movement onto the normalvector of the polygon, and adding this to projection to the desired movement. When you want the player (or a ball, like in my demo) to bounce against a polygon, just add the projection TWICE.
One of the problems I encountered in implementing this collision detection and handling was the floating point inprecision in the calculation of the SHORTDIST. Many times, the player just walk THROUGH a polygon wall after a bit strafing and turning against that polygon. My first workaround for the floating point inprecision was to keep any objects at a little distance from the nearest polygon by subtracting a small DELTA from SHORTDIST. This didn't work out well, because when a player turns, another polygon can become closest, and even closer then this DELTA. So I searched for another solution, and I tried altering the RADIUS of the bounding SPHERE of the player. First I calculate SHORTDIST with the original RADIUS, and then with a smaller RADIUS (RADIUS- DELTA). If the result of the first calculation is larger then the second, there must have been a floating point inprecision, and no further moving in that direction is allowed. This is the way collision detection was implemented in the demo.
[will be continued]
3.Game logic, and object control
(under construction)
4.Building and displaying view
(under contruction)
Main | Introduction | What's NEW | Download | Links | About author