Bi-directional Tracing

An algorithm called Bi-directional Tracing was developed in this thesis and it's used for area border construction (using Border Tile Set). Its algorithm shows below and the steps for construction shows in Image Gallery.

Step 01: Find a random starting point on the tile plane that is located in a cell with no tile yet placed on it

A valid starting point		An invalid starting point

Step 02: Find the two edges, on which the tile curve goes across this edge, of the starting tile and then mark the two cells next to the two edges as the first step of two paths

A valid starting point

Step 03: Perform the path seeking algorithm (which will be described in following paragraphs) for the path 1, until the path 1 reaches to the border of the tile plane or the starting cell of the path 2. If the path cannot reach to one of the two destinations above, Bi-directional Tracing algorithm will go back to step 1 to find a new starting point; if the path 1 reaches to the starting cell of the path 2, Bi-directional Tracing algorithm is completed for this new path - this path will be recorded and the program will go to step 5.

Path 1 reaches to the border of tile plane		Path 1 reaches to the starting point of path 2		Path 1 failed to reach to the two destinations

Step 04: Perform the path seeking algorithm for the path 2, until the path 2 reaches to the border of tile plane. If the path 2 cannot reach to the border of tile plane, Bi-directional Tracing algorithm has failed to find a valid path with this starting point and the program will go back to step 1; If the algorithm does succeed in finding a valid path, both path 1 and path 2 will be recorded and the program will go to step 5.

Path Seeking Algorithm:

Path seeking algorithm is the most complex part within Bi-directional Tracing algorithm, because the paths to be traced have random starting position, two ending conditions (In the step 3 of Bi-directional Tracing algorithm) and some blocked areas surrounding with the other paths. Hence, the most important task for this algorithm is to avoid the situation that the paths step into “holes” in the tile plane and perform an infinite loop inside the "holes"

A path steps into a “hole” within the tile plane

The pseudo-code for path seeking algorithm is stated below:

FUNCTION PathSeeking
    IF current position is not on the north border of tile plane
        AND the cell on the north of current position is not empty
        THEN north edge colour = south edge colour of north tile
    END IF

    IF current position is not on the south border of tile plane
        AND the cell on the south of current position is not empty
        THEN south edge colour = north edge colour of south tile
    END IF

    IF current position is not on the west border of tile plane
        AND the cell on the west of current position is not empty
        THEN west edge colour = east edge colour of west tile
    END IF

    IF current position is not on the east border of tile plane
        AND the cell on the east of current position is not empty
        THEN east edge colour = west edge colour of east tile
    END IF

    REPEAT
        Choose a tile from border tile set randomly
        IF the tile can match the four edge colours above
            THEN Record the information of current position
            Get the next position by the curve leaving point within the tile
            IF the next position is on the border of tile plane
                OR the next position is the starting point of the other path
                THEN Record this path and finish current path seeking
            ELSE IF the next position is on a filled cell for the other path
                THEN Finish current path seeking
            ELSE perform “PathSeeking” function for the next position
            END IF
        END IF
    UNTIL the program repeats more than a pre-defined number of times

FUNCTION END

---

These are the resulting images constructed with Bi-directional Tracing:

Result of Bi-directional Tracing	Result of Bi-directional Tracing with area colours.