Game Development Reference
In-Depth Information
To clarify this procedure, let's look at an example. We have indices A and B, which are the vertex indices
of the edge the bike is currently on. T is being advanced from 0.95 to 1.1, which means that it passes over
vertex B by 0.1 of the distance between A and B and that the bike should be displayed on the next edge.
The next vertex, C, is located, and we perform the following assignments:
A = B;
B = C;
T = T - 1; // value= 0.1
Notice that this 0.1 actually refers to the tenth of the distance between the A and B we started with. We
now use it, however, as the tenth of the distance between B and C. This approximation works since in the
grid models that I use in the game, the variation between adjacent edges lengths is small. The distance
between A and B is usually very close to the distance between B and C, so the effects of this inaccuracy
are not noticeable to the user.
Finding vertex C depends on the direction that the bike is heading. It's worth delving on how the game
finds this vertex. In the mesh pre-processing stage, for each of the mesh vertices we find and save a list of
its neighboring vertices. Two vertices of the grid are called “neighbors” if an edge passes between them.
When passing over vertex B in game-play time, we know that the next vertex we want to find has to be a
neighbor of B. So we only need to go over B's neighbors and choose the one that is aligned with the bike's
forward direction. The following simple procedure (in pseudo-code) does this.
Given starting vertex B, set of neighboring vertices NB and forward direction F do:
var minDot = -INFINITY;
var chosenC = none;
for each vertex V in NB:
var toV = normalize(V - B);
var neiDot = dot(F, toV);
if (neiDot > minDot)
minDot = neiDot;
chosenC = v;
return chosenC;
The vector “
toV
” is the direction from vector from B to its neighbor V.
The procedure uses the dot product between
F
and
toV
to find which neighbor is best considered in-line
with the forward direction F. It takes advantage of the useful fact that if two vectors of size 1 are pointing in
approximately the same direction, their dot product is close to 1, and if they are pointing in approximately
opposite directions, it is close to -1.
The procedure returns the optimal selection for the next vertex in the most general case where a vertex
has any number of neighbors. In CycleBlob, however, all of the grid meshes are quad meshes and the
great majority of vertices in these meshes have exactly four neighbors. The cube grid of the first level, for
instance, has 1,538 vertices, all of which (except six) have four neighbors; the remaining six vertices are
the ones at the corners of the cube—they have three neighbors.
For vertices that have exactly four neighbors, the game doesn't use this general procedure and instead
does something a lot simpler. When reaching vertex B, the player has only three choices. He can either do
nothing and let the bike continue forward, or he can turn left or turn right. For each of these choices, only
