Exploring procedural generation

One of my long term goals has been to produce a piece of software which can produce completely random yet somehow natural terrains. Whilst I know software to produce this already exists it's something that has interested in for a while and I think it would be an interesting challenge encompassing a wide variety of disciplines.


VORONOI DIAGRAMS

At its core the application will use a Voronoi diagram for generating the general layout and areas of the terrain. A Voronoi diagram is a partitioning of a plane into regions based on the distance between points. Say we are given a finite set of points {P1, P2, ..., Pn} in this case each site, Pk is simply a point, and its corresponding Voronoi cells Rk consists of every point in the plane whose distance to Pk is less than or equal to any other Pk. The line segments of the Voronoi diagram are all points on the plane that are equidistant to the two nearest sites. The Voronoi vertices are equidistant to three (or more) sites.

We could try and use a plane sweep algorithm but that presents a problem as the Voronoi diagram above the sweep line may be affected by sites below the line. The best way to get around this problem is to maintain two sets of lines, the sweep line and a new line, the beach line. The beach line is not a line but a series of parabolas. This line separates the known and unknown parts of the Voronoi diagram, it is the minimum of parabolas defined by sites above the sweep line and the sweep line itself. As the sweep line moves down the plane the each parabola within the beach line changes. The intersection between between the parabolas in the beach line represent the edges within the Voronoi diagram. As the sweep line moves down these intersections trace out the position of the beach lines.

The Voronoi diagram will be produced using Steven Fortunes sweepline algorithm. This diagram mains a sweep line and a beach line as it passes through a plane of points. In my application all points above the sweep line have been processed and incorporated into the diagram. Following behind this is the beach line, this is not a line but a collection of parabolas. Everything above the parabola has been fully processed, everything above this line requires no further computation - the voronoi diagram above this line is complete.

FORTUNES ALGORITHM

Pseudocode description of Fortune's sweep line algorithm:

01 let P1, P2, P3...Pn be the set of sites ordered by Y coordinate
02 let T be the beach line
03 let Rp be the region covered by site P
04 let Cpq be the boundary ray between sites P and Q
05 let P1, P2, P3, ..., Pm be the sites ordered by Y coordinate
06 Q <-- P1, P2, P3, ..., Pm
07 WHILE NOT isEmpty(Q) DO
08 P <-- Q.pop
09 IF P = Site Event THEN
10 find the occurence of region *Rq in T containing P,
11 bracketed by Crq on the left and Cqs on the right
12 create new boundary rays Cpq- and Cpq+ with bases P
13 replace *Rq with *Rq, Cpq-, *Rp, Cpq+, *Rq in T
14 delete from Q any intersection between Crq and Cqs
15 insert into Q any intersection between Crq and Cpq-
16 insert into Q any intersection between Cpq+ and Cqs
17 ELSE
18 let P be the intersection of Cqr on the left and Crs on the right
19 let Cuq be the left neighbour of Cqr and
20 let Csv be the right neighbour of Crs in T
21 create a new boundary ray Cqs0 if Q.x = S.x,
22 or create Cqs+ if P is right of the higher of q and s,
23 otherwise create Cqs-
24 replace Cqr, *Rr, Crs with newly created Cqs in T
25 delete from Q any intersection between Cuq and Cqr
26 delete from Q any intersection between Crs and Csv
27 insert into Q any intersection between Cuq and Csv
28 insert into Q any intersection between Cqs and Csv
29 record P as the summit of Cqr and Crs and the base Cqs
30 output boundary segments Cqr and Crs
31 END WHILE
32 output the remaining boundary rays in T


FORTUNES ALGORITHM EXPLAINED

As we can see in the algorithm above, the only time the beach line is changed is when one of two events occur:

  1. Site Event: occurs when the sweep line encounters a new site and a new parabola is added to the beach line.
  2. Circle Event: occurs when a parabola needs to be removed from a beach line, indicating a Voronoi vertex needs to be added to the diagram. They occur when three sites lie on the edge of a circle and the sweep line passes below the bottom of that circle.

Therefore all we need to do is store a list of site events and possible circle events, this will be stored in a priority queue - sorted by Y coordinate with the highest value at the top of the queue. Circle events will be added to the queue based on their Y value at the base of the circle as this is when they are triggered. Not all circle events added to the queue will be triggered, there must also be a way to remove these once they have been added.

When a site event occurs a new parabola forms; this means two new break points occur and a new Voronoi edge is found between these.

When a circle event occurs a parabola disappears from the beach line; two break points come together, a new Voronoi vertex is discovered and a new break part starts to be traced. These obviously only occur between adjacent parabolas on the beach line. As mentioned earlier, not all circle events will trigger, this may occur if a new site is added to diagram and sits in the middle of the previously empty circle; that is, the previously consecutive arcs are no longer consecutive. It may also be that one of the arcs forming the circle event is removed before the event is triggered.


SITE EVENTS

Following the algorithm we need to do the following steps during a site event:


CIRCLE EVENTS

Following the algorithm we need to do the following steps during a circle event: