Ray Algorithm

Home --> Programming Projects --> Block Engine --> Ray Algorithm

---

Shooting A Ray Into the World

Suppose the player shoots a gun in the game. We need to determine what the gun will hit. What we need to do is determine where a ray intersects the geometry of the world. The way this is done in Block Arena is with a 3D-version of Bresenham's line algorithm . That is, for each axis (x, y, and z), we step through parallel planes that are each 1 unit away from each other (blocks are 1 unit in width) until we find an intersection. This is a very fast and rhobust technique, and it has the advantage that very few multiplications are performed (only additions).

One way to seed up this technique would be to represent the block world as an oct-tree of blocks, and we step through the nodes of this tree in the appropriate mannor. In small maps, this seedup is not necessary.

Consider now the problem of determining if a ray hits an object in the world that can move around. What we can do is mark all the block positions in the world that intersect the bounding box of the object, and whenever a ray passes through one of these positions, an intersection calculation with the object is performed.

In addition to using the ray algorithm to deal with projectiles, it is used for the computation of shadow maps.