Snake Realtime Geometry Generator Algorithm

Developed for Project Largo by

Rolv Seehuus

Ståle Furset

Torbjørn Vik

[ Introduction ]

Any reader of this document should be experienced with C++-programming and vocabulary. A brief understanding of three dimensional mathematics and 3D-programming principles is also needed.

[ Problem ]

The problem is to generate a geometry model describing a snake. The input data is based on the players choices of direction. The player’s actions on the keyboard will be transformed into a 4x4 matrix describing the new position/orientation of the snake’s head. This 4x4 matrix is the actual input to this algorithm. As the snake’s body and tail follow in the head’s path, it will create an illusion of movement.

To understand the rest of this description, an extensive study of the classdiagram is required:

A vectorobject is built up of a collection of vertices and faces. The class Vector contains a table of vertices, each vertice representing a coordinate in three dimensional space as X,Y,Z-coordinates. The class also contains a table of faces, each face (triangle) having three vertex-indexes, pointing to which vertices in the vertex-table to use for the triangle. These two tables describes any models appearance, at any time.

[ Solution ]

The algorithm developed by the project group includes the introduction of an intermediate data abstraction layer in addition to the Vector-class described above. Instead of forcing the geometry updating algorithm to work directly on the vertex/face-arrays, the implemention of an extra data layer would simplify both the algorithm and implementation. The two new structures VertexRing and FaceRing contain all data necessary to describe a certain ring in the snake’s geometry. The figure on the right illustrates how the snake is built up; a VertexRing describes a section of vertices (8 in the figure), a FaceRing describes a ring of faces (16 in the figure) and connects two vertexrings. The snake will contain both an array of VertexRings and an array of FaceRings.

The original idea was to update all of the vertices each frame, moving them a certain distance along the path of the snake each frame. This would include traversing through a huge memoryblock, moving the coordinates. Processing such huge amounts of data would slow down the game significantly. A better idea would be to move the first and the last vertexring, processing approximately 1000 bytes of data instead of 500.000. To make the model describe the snake’s curves accurate, the distance between two vertexrings (along the path) should not exceed a certain size. As the first ring moves forward (and the second does not), the distance between the two first rings will at some point exceed this number. A new ring is created at the maximum distance from the second ring, and a new ”first” ring is created. This ring will move forward until the distance to the second ring exceeds the maximum distance...etc.etc. In general, this means adding new rings in front of the snake and removing rings on the other end. To do this effectively, a circual databuffer is required for storage of Vertices, Faces, VertexRings and FaceRings (see figure).

The grey block illustrates the total memoryblock allocated for the snake. The pink/red small block illustrates the actual memory block used by the snake. As new rings are added to the front of the geometry and rings are removed at the tail, the memory used for the snake will move through the total buffer from left to right. As the head ring reaches the end of the allocated memorybuffer, it loops back to the start of the total memoryblock and reuses this memory. Of course, this limits the snake to a certain maximum size.

Along with each VertexRing, a matrix is stored to save the orientation/position of this particular ring. As the tail moves forward, it uses this matrices to obtain the right position.

As only the front and back ring of the geometry moves, a little trick is needed to create an illusion of movement. The snake will be so called ”texturemapped”, a picture is wrapped around the snake’s body, making it look more like a real snake. This texturemap may also be used to create movement by dragging it along the geometry; the geometry doesn’t move, only the map does.

Torbjørn Vik, 13.02.2000