---

Translated from "fr 2000 3d tile_algorithm" — the algorithm used for placing and propagating tile textures across 3D patches in the Ryzom landscape system. This document is referenced by the 3D Engine Specification and the tile bank documentation. {.is-info}

• A tile is a 128x128 image to be placed on a grid.
• The neighbor of a tile is one of its four adjacent tiles.
• The relative orientation of a tile with its neighbor is the counterclockwise rotation that the tile must undergo to be oriented like its neighbor.
• The neighbor type of a tile characterizes a neighbor attached to it. The type is characterized by the tile type of the neighbor and the relative orientation between the tile and its neighbor.
• A transition tile is used to create a tile that bonds with 2 or 3 neighbor types around it. It is composed of 4 corners.
• A transition tile corner is a (tile type, relative rotation) pair.
• A normal tile is not a transition tile.
• A tile border is a pair of corners.
• For a normal tile, all 4 corners are equal. For a transition tile, the pairs can be different but there must be at most 3 different neighbor types on the tile.
• An extraordinary point is a point from which a number of edges different from 4 originates.

Place_a_tile_of_type_A with a current rotation, cyclic or not:

While there are tiles on which A must be placed:

1. Back up the tile state.
2. Add the tile to the already-visited list.
3. Place a 128 tile chosen either cyclically if in cyclic mode, or randomly, with the current rotation.

For all neighboring tiles:

4. Propagate_borders from the tile with A and the current rotation + relative rotation between the tile and the neighbor.
5. Remove the tile from the list to traverse.

Place_a_tile_of_type_A with the current rotation from the list, non-cyclic.

1. If already visited, end.
2. If empty, end.

Back up the tile state.

Add the tile to the already-visited list.

Retrieve the border state of already-visited neighbors using their current tile.

Force into the tile the border shared with already-visited neighbors: copy the tile type of the two corners and the rotation + the relative rotation between the two tiles. Mark borders where a corner has changed. Keep the other borders unchanged.

If the last corner cannot be compatible with one of the neighbor's corners, it is an extraordinary point. Choose the tile type with the higher relative rotation for the corner.

• If there are ultimately 4 tiles, cancel. The tile cannot be placed. Restore the tile states, then quit.
• If two corners of the tile use the same materials but with a relative rotation of 2, the tile cannot be placed. Restore the tile states, then quit.
• If the neighbor is invalid (diagonal neighbor type), the tile cannot be placed. Restore the tile states, then quit.

Find the tile that satisfies the corner constraints.

If all four corners are identical, choose a tile at random.

If it is a transition:

For each modified transition border:

• If a corner of the border does not tile with the neighbor's corner due to an extraordinary point, it is then necessary to use a 1/4 transition on this corner for this border to avoid it being too visible.
• Otherwise, if the tile has three colors, and if the border has a sister border in the patch linked by this border, choose a 3/4 border type and force the neighbor's border if it is 1/4. Otherwise, choose a 1/4 border type.
• Otherwise, either the neighbor has been visited and its border must be copied, or it has not been visited and a 1/4 or 3/4 border must be chosen at random.

For transition tiles, arrange the layers in ascending order of tile type. In a layer of a transition tile, a corner is empty only if there is nothing above it. If the tiles are of the same type but not the same relative rotation, sort them by relative rotation.

For all unvisited neighboring tiles on a border with a corner that has changed:

Propagate_borders from the tile.