Subdivision algorithms achieve the results when you want to random split a polygon into smaller polygons.

            *Recursively divided blocks*

Basic BSP Dungeon generation

The result of subdivision algorithm gives random polygons in different width and height which could potentially represent buildings.

For our project, we have a historical map that helps us to think about how a tang city should look like. The following map is the capital of Tang Dynasty, ChangAn. Each square in the map is called Ward, the basic unit of the city.

A standard ward looks like following picture which is divided into smaller blocks for different purpose. Some blocks are used for places such as temple. Based on the house hold social status, people with higher social status owns bigger block.

Implementation

Inspired by an article talking about the 2D subdivision like Mondrian art, the result of divisions looks better than recursively divided blocks.

Algorithm

First, we define a struct called Rect. Rect defines the top-left position, height and width of a rectangle.

struct Rect{
	float x,
	float y,
	float height,
	float width
}

Second, we need to generate a list of points within the rect. Each point has two information: Position and Orientations. Orientations are either horizontal or vertical and decide how rectangle should be sliced. Each point will be repeated in the point list for different orientations.