---

Translated from fr 2000 3d tile_algorithm.doc

A tile is a 128*128 image to be displayed on a grid. The neighbour of a tile is one of its four adjacent tiles. The relative orientation of a tile to its neighbour is the rotation in the trigonometric meaning which the tile must undergo in order to be oriented like its neighbour. The neighbouring type of a tile is defined by a neighbour attached to it. The type is defined by the type of the neighbouring tile and the relative orientation between the tile and its neighbour. A transition tile allows you to make a tile with 2 or 3 types of neighbours around it. It is comprised of 4 corners. A transition tile corner is specified as a texture tileset with a relative rotation. A normal tile is not a transition tile. A tile border is a tileset of corner textures. For a normal tile, all 4 corners are equal. For a transition tile, the pairing may be different but there should be only 3 types of neighbours on the tile in total. An extraordinary point is a point from which any number of edges other than 4 starts.

Placing a tile of type A with the current rotation, and cyclic or not:

While there are tiles on which A must be placed:

• Backup the state of the tile.
• Add the tile to the list of already visited tiles.
• Place a 128 sized tile, selected either cyclic if in cyclic mode or random, with the current rotation.
• For each of its neighbouring tiles:
• Propagate the borders, with A, of the tile, and current rotation + relative rotation between the tile and the neighbor.
• Remove the tile from the list to traverse.

Placing a tile of type A with the current rotation coming from the list and not cyclic: Propagating the borders:

• If already visited, end
• If empty, end

Backup the state of the tile. Add the tile to the list of already visited tiles. Find the state of the borders of neighbours already visited by their current tile. Force the common borders of the neighbours already visited into the tile: copy the type of tile from both 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 corners cannot be compatible with one of the neighbours' corners, this is an extraordinary point. Choose the type of tile with the better relative rotation for the corner.