Procedurally generating closed-circuit racetracks

In this week’s talk we had another 3rd year student, Jamie, explain his project to us and why he chose to spend his time on this subject.

Jamie started out by giving some examples of procedurally generated content. The example he used was Minecraft and how 2D Perlin Noise was used for the terrain generation. However, he explained that different methods are used in procedural generation depending on the required properties of the result. He illustrated this by explaining that Perlin Worms are used to generate the caves in Minecraft in order to increase the connectivity of the caves.

image.CN0VCY

He then went on by briefly touching upon the uses of procedural generation in audio, L-systems and city layout generation (as seen above), before going on to the main part of his talk: “Procedurally generating closed-circuit racetracks”.

Jamie started out by giving us some definitions that were necessary to understand the process. Firstly, he needed to define a racetrack, which was required to be a closed circuit and needed to have a start and a finish. Then, he talked about the different constraints one could put on the racetracks. He chose to have a number of “hard constraints”, which were properties the generated racetrack had to have, and also a number of “soft constraints”, which were properties which would be preferable but not necessary. The “hard constraints” were represented by a set of (in)equality constraints, so they had to have a certain exact values. Each “soft constraint” was represented by an Energy Function, which gave a certain racetrack a value based on its properties regarding the constraint. The total “value” of a racetrack was then found by summing all the Energy Functions.

In order to write his code and generate racetracks, he needed a way of representing the racetracks, which he did by using an ordered list of “d quadratic bezier curves”, which are a way of representing a piece of the racetrack, where each bezier curve can at most have one type of curvature.  The racetracks themselves were generated by using something called Voronoi Diagrams (as seen below).

image.0NATCY

Voronoi diagrams are represented by a group of points, with the edges being defined as the locus of points where the distances to each of the 2 closest points are equal. Jamie then created racetracks from these by selecting a collection of these edges. Each racetrack is first checked to conform with the “hard constraints” and is then optimised by minimising the sum of the energy functions of the “soft constraints” using gradient descent, which works a bit like rolling a ball down a slope (see picture below).

image.V0KZCY

Jamie finished his presentation by giving us a demo of his code and explaining that, to finish off his project, he would do a user study to see if the racetracks he generated are truly as good or maybe even better than the content that is available so far.

Advertisements