Moving Between Chunks
Home -->
Programming Projects -->
Fractal Block Engine -->
Moving Between Chunks
Overview
The point of this page is to discuss some of the ways
we move the player between different chunks in the
chunk tree.
Teleporting on the Same Level
Suppose the player in located at some chunk C in the tree.
Let L be the level of C.
It is very important that we be able to move the player
to any other chunk on level L
(assuming the target chunk has already been created).
We need this if we want the player to be able to fly or walk
from one chunk to an adjacent one.
When this "same level teleportation" takes place,
all parent / child relationships within the chunk tree
are maintained.
All we need to do is to change the VCP
(Viewer Centric Position) of all chunks in the chunk tree.
Recall that the Viewer Centric Position of a chunk is the
relative position of that chunk from the chunk on the same
level which contains the player.
That is, the VCP of a chunk is the relative position of the chunk
to the "trunk" of the chunk tree.
So when the player changes their chunk, these VCP's must be updated.
However note that only some levels need to be updated.
That is, probably only the several most finest levels need to be updated.
The main engine behind updating all these VCP's is "long addition"
(like "long division" from school).
See here
for code for this algorithm.
The input is the path of the player's chunk together with
the VCP to translate that chunk by.
The output is a list of VCP's which say how much
each level needs to be "shifted".
If a level is shifted by some non-zero VCP (x,y,z),
then we add (x,y,z) to the VCP of every chunk on that level.
The shifting triples come from the "carrying over"
in long addition.
Growing and Shrinking
To make a game with growing and shrinking,
we need to be able to do the following.
First, we need to be able to move the player from
their current chunk to the parent of this chunk.
This corresponds to when the player "grows" in size.
In Fractal Block World, we do not store any chunks
on levels that are finer than the player's level.
So, once the player grows,
we delete all chunks on the old player level
(actually, we delete them gradually over the next
second or so).
To allow the player to shrink,
we must be able to move the player from their
current chunk C to a new child chunk.
The child corresponds to one of the 16x16x16 block
positions of C.
That new child chunk D will be set to have a VCP
of (0,0,0).
During the "exploration" process
(see here),
other chunks on the same level as D will be created.
Trunk Teleportation
It is very important to be able to teleport the player
to any chunk P given a path for that chunk.
This target chunk P need not already exist
(in the active chunk tree).
The simplest way to accomplish this is to simply
delete all chunks (in the active chunk tree)
and then reconstruct the entire chunk tree so that
the player is inside P.
That is, the ancestors of P will constitute the
trunk of the new chunk tree.
However this is slow because we are recreating the
ENTIRE chunk tree.
The reader can figure out the fastest way to teleport the player,
but we propose a method that is usually fast
but is also very easy to implement.
We call this method trunk teleportation.
Here is how it works:
- Let R be the chunk containing the player.
So R represents the trunk of the current chunk tree.
- Let P be the chunk we want to teleport the player to.
- Find C, the chunk that is the "largest common initial segment
of R and P".
That is, R and P are both "inside" C and C is the finest chunk with
this property.
- Delete all chunks that are in levels that are finer than C.
- Create the rest of the (new) chunk tree up to the chunk P.
That is, we are building off of the trunk of the old chunk tree.
In this algorithm, no chunk from the old chunk tree that
survives needs to have its VCP changed.
The green is the (old) active chunk tree.
We delete all chunks below the purple line,
then we continue to build the new active chunk tree
down to P.