Procedural Racetrack Generation

栏目: IT技术 · 发布时间: 3年前

内容简介:This post explains my personal take (in Python) of the work done byI have been thinking for some time to develop a game that mimics the mechanics ofI mainly wanted to achieve two things:

This post explains my personal take (in Python) of the work done by Gustavo Maciel and explained in this article .

Introduction

I have been thinking for some time to develop a game that mimics the mechanics of vector racer (nothing new here). When I finally started to work on it , I thought it would also be a good opportunity to give a try at procedurally generating racetracks.

I mainly wanted to achieve two things:

  1. Procedurally generate racetrack layouts
  2. Implement a drawing system generic enough that could draw recognisable racetracks from the layouts obtained in 1.
Procedural Racetrack Generation

Figure 1: Procedurally generated racetracks. (Clickbait: As you may notice, some corners do not have kerbs… Keep reading to find out why!)

A quick search led me to Gustavo’s article, linked above, and after skimming through it decided to give it a go.

Racetrack Generation

The track generation algorithm is well explained in Gustavo’s article . I will just present the general idea, but if you want to dive into the details of the algorithm I suggest reading the original post. The image below shows some of the obtained layouts obtained from my implementation.

Procedural Racetrack Generation

Figure 2: Layouts of some of the procedurally generated racetracks.

The main steps followed to obtain the track layout are:

  1. Generate a set of random points ( white dots in Figure 1).
  2. Get their convex hull ( red lines in Figure 1).
  3. Compute the midpoint of each pair of points in the convex hull and displace it by a random amount.
  4. Given both a minimum angle and a minimum distance threshold, push apart the set of points resulting from 2 and 3 to try to guarantee that: a) there are not two adjacent points whose distance is less than the minimum distance threshold and b) there is no set of three adjacent points where the angle of the vectors that connect them is less than the minimum angle threshold. ( blue lines in Figure 1).
  5. Obtain the final layout by interpolating all the points obtained after step 4 with splines forcing them to pass through all the input points ( black curve  in Figure 1).

There are quite a few parameters (more than I would like) that can be modified and tuned to alter the results, and after playing a bit with them I was quite happy with the obtained layouts. Some of them are presented in Figure 2.

Drawing the Racetrack

Since tracks are procedurally generated, the track rendering system has to be generic enough to be able to handle a wide variety of layouts. This made the rendering interesting pretty quickly, and ended up being harder than expected. My results are far from ideal, but anyway, here’s what I came up with. Any suggestions on how to improve it are more than welcome!

Growing the Track

This is the easiest part. To obtain something that begins to look like a racetrack we can simply get a predefined number of evenly spaced points (I chose 1000 points) from the curve obtained at the end of the previous section. Then, at the position of each of these points we simply draw a circle of a given radius (20 pixels in my case).

If the points are close enough there will be no sign of the individual circles and we will have a constant-width racetrack with smooth corners. The result does indeed already look like a racetrack (at least, that is what I like to think). Some results after this stage are presented in the Figure below.

Procedural Racetrack Generation

Figure 2: Partial racetrack drawing.

Placing Kerbs

This is where it began to get interesting. My approach is probably not the optimal one, so I am open to give a try at any suggestions on how to improve it.

The first thing we have to do is to detect where the corners of the racetrack are. A solution that balances complexity and good results is to use the set of points from which the splines were computed (points connected with blue lines in Figures 1 and 3)  to roughly estimate where the corners of the track are.

Given three consecutive points we can compute the angle between the two vectors that connect the point in the middle with both extremes. If this angle is inside a range, we add it to the list of corners requiring kerbs. We can play with this range to increase or reduce the amount of kerbs that will be placed in the track. Figures 3 and 4 show results obtained for different angle ranges. One drawback of this approach is that we will miss any corner in the spline which does not satisfy the detection method.

Procedural Racetrack Generation

Figure 3: Complete racetrack with kerbs. Note that all the dots connected with blue lines have resulted in a corner with a kerb in the final racetrack.

After this step we will have the list of single points, representing a corner in the track, that require kerbs. We have the location of the corner but, before drawing anything, we should know the length of the corner (where does it start and where does it end). To simplify, I decided to set a fixed offset that represents the length of the corner and assume that the points indicating the corner location are the center of the corner. With this approach all the corners will be assumed to have the same length, which is not true but will make our lifes easier.

Now, since we have the guarantee that the points selected in the previous step are part of the spline, we can find their index in the set of points that we used to draw the circles that resulted in the basic racetracks shown in Figure 2. Once having this indices we can, for each corner, build the list of points from the spline that represent the full corner. This list is made by the points inside the range [ corner center – offset, corner center + offset ]. I had to play a bit with the offset value, but I ended finding a value I was satisfied with.

Procedural Racetrack Generation
Figure 4: Complete racetrack with kerbs. Note that, in this case, not all the dots connected with blue lines have resulted in a corner with a kerb in the final racetrack.

We now have, for each corner, a list of points that indicate its location and length. It is time to draw the kerbs. The main restriction here is that kerbs should outline the corners and be located at the limits of the track.  I thought that the best approach would be to draw a simple building block and place it several times along the corner. After a bit of trial and error I ended up with the following tile (althoug it cannot be seen, there is another white stripe at the right):

Now we just need a position and orientation to place them in the track. Getting the orientation is as simple as computing the angle between the vector obtained from two consecutive points in the corner and the horizontal axis. Instead of two consecutive points I defined yet another offset n and, for each point in the corner, computed the angle between ( i, i+n ) and the horizontal axis.

As for the location, first we should compute the unitary vector perpendicular to the vector used to determine the orientation. Multiplying this vector by the radius of the circles used to draw the track gives us the displacement from the track center to the place where the kerb should be drawn. With this values we are set to draw the kerb.

To prevent the tiles from ovelapping I repated this process for every 4th (another parameter to be adjusted) point in the list of corner points.

I did the same for the indicator of the track start, but this time placing it in the middle of the track and perpendicular to the track direction. The tile I used is shown below.

Results and Code

The images below show some example racetracks obtained with the algorithm explained above. The code (a bit messy) can be found here .

Results showing the underlying process

Procedural Racetrack Generation

Procedural Racetrack Generation

Procedural Racetrack Generation

Final Racetracks

Procedural Racetrack Generation

Procedural Racetrack Generation

Procedural Racetrack Generation

If you have any doubts or suggestions, do not hesitate to leave a comment below!


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

测试驱动开发的艺术

测试驱动开发的艺术

Lasse Koskela / 李贝 / 人民邮电出版社 / 20101023 / 59.00元

在传统的软件开发中,开发人员对于代码是否正确心中无底,一切依赖于后期的测试环节。极限编程反其道而行之,主张采用测试驱动开发(TDD)的方法,即通过测试定义所要开发的功能的接口,然后实现功能的开发过程。TDD通过不断地测试推动代码的开发,既简化了代码,又保证了软件质量。 本书采用“手把手”的教学方式,通过大量实例来解释TDD,还专门用几章的篇幅来讲解如何为难于测试的技术编写单元测试。全书内容循......一起来看看 《测试驱动开发的艺术》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换