How to calculate where bullet hits

Question

I have been trying to write an FPS in C/X11/OpenGL, but the issue that I have encountered is with calculating where the bullet hits. I have used a horrible technique, and it only sometimes works:

pos size, p;
size.x = 0.1;
size.z = 0.1; // Since the game is technically top-down (but in a 3D perspective)
              // Positions are in X/Z, no Y
float f; // Counter
float d = FIRE_MAX + 1 /* Shortest Distance */, d1 /* Distance being calculated */;
x = 0; // Index of object to hit
for (f = 0.0; f < FIRE_MAX; f += .01) {
    // Go forwards
    p.x = player->pos.x + f * sin(toRadians(player->rot.x));
    p.z = player->pos.z - f * cos(toRadians(player->rot.x));
    // Get all objects that collide with the current position of the bullet
    short* objs = _colDetectGetObjects(p, size, objects);
    for (i = 0; i < MAX_OBJECTS; i++) {
        if (objs[i] == -1) {
            continue;
        }
        // Check the distance between the object and the player
        d1 = sqrt(
                pow((objects[i].pos.x - player->pos.x), 2)
                        + pow((objects[i].pos.z - player->pos.z),
                                2));
        // If it's closer, set it as the object to hit
        if (d1 < d) {
            x = i;
            d = d1;
        }
    }
    // If there was an object, hit it
    if (x > 0) {
        hit(&objects[x], FIRE_DAMAGE, explosions, currtime);
        break;
    }
}

It just works by making a for-loop and calculating any objects that might collide with where the bullet currently is. This, of course, is very slow, and sometimes doesn't even work.

What would be the preferred way to calculate where the bullet hits? I have thought of making a line and seeing if any objects collide with that line, but I have no idea how to do that kind of collision detection.

---

EDIT: I guess my question is this: How do I calculate the nearest object colliding in a line (that might not be a straight 45/90 degree angle)? Or are there any simpler methods of calculating where the bullet hits? The bullet is sort of like a laser, in the sense that gravity does not affect it (writing an old-school game, so I don't want it to be too realistic)

Answer 1

For every object you want to be hit-able, define a bounding object. Simple examples would be a sphere or a box. Then you have to implement a ray-sphere or ray-box intersection.

For exaple have a look at line-sphere intersection. For boxes, you can either test aginast the four bounding lines, but there are algorithms optimsed for axis aligned boxes.

With this, proceed as you already do. For every object in the scene, check for intersection, if intersects, compare distance to previous intersected objects, take the one that is hit first. The intersection algorithems give you the ray parameter as a result (the value t for which hit_position = ray_origin + t * ray_direction) which you can use to compare the distances.

Answer 2

You can organise all scene objects in the BSP tree then hit\collide detection will be pretty easy to implement. Also you can use BSP to detect invisible objects and discard them before rendering.