Ray Algorithm
Home -->
Programming Projects -->
Fractal Block Engine -->
Ray Algorithm
The Goal
A common task is "shooting a ray" into the world.
We register callback functions to the algorithm
which are called when a "collision is made".
For example, suppose the ray hits an ment (moving entity).
A callback function is called to
"process the collision".
That callback function will return whether or not
the hit "is terminal".
The function can also have side effects, such as "damaging" the block.
Terminal means the ray will stop at that point.
Certain collisions are always terminal, such as hitting a solid block.
Thus the callback functions need to be called in order
in which the ray hits the corresponding objects.
One could imagine a different system where there are two types of
callback functions: one which simply returns if the collision would be terminal,
and the second which processes the effects of a collision.
Because the callback functions need to be called in the correct
order, what we do is first find all "potential" collisions
(intersections of the ray with objects in the world).
We then sort them by their distance to the start of the ray.
We then call the callback functions
for each of these objects in order.
Multiple Levels
Something interesting about the Fractal Block Engine is that there are
multiple levels of detail at any given time.
When a ray is shot into the world, the caller specifies the
number of levels that are involved (1 through 5).
Call these the interacting levels.
That is, certain projectiles only interact with objects
on their same level, whereas other objects
interact with multiple levels.
We actually do not shoot a ray, we shoot a "line segment".
We could process all the interacting levels simultaneously.
Someone clever could figure out how to do that.
However Fractal Block World processes each interacting level
separately, starting from the finest and making the way
to the coarsest.
For each interacting level, we form a list of all
objects with which the ray collides.
Once we have processed all interacting levels like this,
we sort all the ray collisions and then call the
callback functions in order until we find a terminal collision.
A clever trick
There is a reason why we process the finest interacting level first.
There are certain collisions which we know in advance will
be terminal (such as colliding with a solid block).
So if on the finest level the ray collides with a solid block,
then when we process another interacting level,
we only need to use the line segment which is the
original line segment clipped to that solid block collision.
So if the player is in a room and shoots the wall, we do not have to
compute the intersection of the line segment of the bullet
with distant planets.
Processing a single level
Here is how we process one of the "interacting levels"
to get a list of all collisions of the ray (actually line segment)
with objects on that level.
First, we intersect the line segment with the bounding
box of the level (the bounding box of the set of all chunks in the level).
The main engine we use is Bresenham's line algorithm.
We do this using "block positions".
For each block position, we have to query which chunk it is in.
Someone clever can figure out how to make a chunk based
version of the algorithm.
However by caching the chunk pointer, our version is pretty fast anyway.
So we do Bresenham's line algorithm to get
"block type" collisions.
An output of our version of the Bresenham's line algorithm
is a list of the chunks which the line segment intersects
(up until the first terminal collision, if there is one).
We then use this list of chunks to figure out if
the line segment intersects any objects in those chunks.
But actually that last part is not totally simple,
because ments (moving entities) might be centered in one
chunk but spill over into another chunk.
For this reason, there is a system to track which chunks
each ment intersects.
Care must be taken for this
(we don't want a single ment intersecting hundreds of chunks).
The solution is that for the sake of locating an ment
based on which chunks it intersects, we store an ment
on its index level.
That is the finest level in which the radius of the ment
is less than the chunk width.