July 20–24, 2015
Portland, OR

Hacking "Roller Coaster Tycoon" with genetic algorithms and Go

Kevin Burke (burke.services)
10:40am–11:20am Wednesday, 07/22/2015
Solve E147/148
Average rating: ****.
(4.00, 10 ratings)
Slides:   external link

Prerequisite Knowledge

A basic understanding of programming concepts would be useful, but I'm going to try to make the talk as accessible as possible, including a walkthrough of how assembly language works and how to read assembly data into your own program.

Description

I was 12 and wanted to build the perfect coaster in Roller Coaster Tycoon. And now at 26, I have the tools to write the code to do it. So I did. The talk will cover various parts of the project.

1) Reading and writing ride data
Ride data is stored in a custom data format where each byte means something different – one byte controls the ride color, one controls the entrance location, etc. This data is then encoded using a custom ride length encoding. The first step of the project was to write Go encoders and decoders to serialize saved rides into Go structs, and vice versa.

2) Getting info about track pieces
There are about 120 different track pieces – sharp turns, corkscrews, straightaways, and more. Instead of encoding this information by hand, I found where it was located in the ~600,000 lines of x86 code making up the game, and read these into Go structs. You’ll learn how to read basic x86 and how to parse this data with Go.

3) Viewing rides
It’s hard to look at a sequence of track pieces and determine whether it’s a cool roller coaster or not. I used the Go ‘image’ library to create crude drawings of a given coaster design, without needing to load it in-game.

4) Generating a fitness function
To evolve coasters, you need a way to determine whether a given coaster is better than another. At the beginning, you can evaluate coasters based on how close they are to forming a complete loop, and not colliding with themselves. Then you can use the game’s excitement, intensity, and nausea ratings (which required another dive into the x86 codebase).

5) Evolving coasters to find a good one
We’ll discuss some strategies for mutating roller coasters, how many coasters to choose, in the context of helping you find the right genetic algorithm to solve your own problem.

6) Conclusion
We’ll look at some pictures of the finished coasters, and reflect on how Go is perfect for this task:

  • Reading byte data from an exe
  • Allowing you to write custom encoding/decoding functions/enforce types on the decoded data
  • Drawing pictures of coasters
  • Having great performance when asked to generate a large number of mutated coasters across multiple rounds, detect track collisions, and more.
Photo of Kevin Burke

Kevin Burke

burke.services

Kevin Burke is an engineer at Shyp, where he writes reliable code and designs great experiences. Kevin once accidentally left Waiting for Godot during the intermission.