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.
Step 05: If the number of attempts exceeds a pre-defined value, blank cells within the tile plane will be filled using filling tile set and the process of Bi-directional Tracing will terminate. On the contrary, the program will go back to step 1 and try to find the next path
.
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. |
|