Hacking Roller Coaster Tycoon

Kevin Burke

@derivativeburke

Jobs

12 Year Old Me

Goal - Build cool coasters via computer program

Might be tractable!

What is a cool coaster?

High Excitement/Low Sickness

How do you interface with the game?

How do you interface with the game?

Tracks are stored separately

TD6 format

Source

Run Length Encoding

Read a byte (x)
If x < 0: Read next byte and copy it -1*x times.
If x > 0: Read x bytes

Go Interfaces

func (z *Reader) Read(data []byte) (int, error) {
  // Read one byte...
}
func (z *Writer) Write(ride []byte) (int, error) {
  // Peek at upcoming bytes...
}

Plan of action:

Generate tracks outside of the game
Save to the RCT track format
Load them in the game
...
Profit

How to represent the track pieces?

Track Data (cont'd)

What is x86 assembler?

What is assembler cont'd

a = 3
a = a + 4
b = 6
if a > b:
  a++
else:
  b++

CPU registers + instructions

1  MOV $3,CX   ; a = 3
2  ADD $4,CX   ; a = a + 4
3  MOV $6,AX   ; b = 6
4  CMP CX,AX   ; a > b ?
5  JLE 9
6  INC CX      ; a++
7  NOP
8  RET         ; return
9  9:          ; else (label)
10   INC AX    ; b++

RCT Source Code

4,862,557 instructions
~1,289,635 bytes of data
No labels/symbols!
Poor program flow (GOTOs, etc)

How do you find what you are looking for?

Link

OpenRCT2

Cross platform support! (via SDL2)
Better game AI!
Cheats!
Twitch integration!
Languages (CN, FR, NL, ES, PO, HU, more)
~~Janitor unionization~~

Coming to a Platform Near You

NB: you still need the game assets

How do you test as you go?

How can you test as you go?

CPU starts execution at an entry point specified by ABI
Compile game, C into shared DLL
Modify game's rct2.exe to point to the C entry point
Distribute new .exe

Call x86 subroutines

static void sub_68B2B7(int x, int y)
{
	RCT2_CALLPROC_X(0x0068B2B7, x, 0, y, 0, 0, 0, 0);
}

Finding Game Data - 2 Objectives

Find the track data
Find the excitement/nausea ratings

IDA Pro

IDA (cont'd)

Where Is Anything

Track Data Has Consistent Order

Track Formula

    baseTrackPointer +
    width * trackPieceNo +
    dataOffset

Good enough to make guesses

Guessing Track Data

f, err := os.Open("~/code/OpenRCT2/openrct2.exe")
var WIDTH = 0x12
b := make([]byte, 100*WIDTH)
addr := 0x0057E3A8
f.ReadAt([100]byte{}, int64(addr))

Guessing Track Data (cont'd)

for i := 0; i < len(rct.TRACKNAMES); i++ {
  fmt.Printf("\t%d,\t", b[i*WIDTH])
  fmt.Printf("// %02x ", i)
  fmt.Printf("%s\n", rct.TRACKNAMES[i])
}

Guessing Track Data (cont'd)

A Good Guess

A Good Guess

>>> hex(878)
'0x36e'

A Good Guess (cont'd)

A Good Guess

sub_6C511D:
  mov word_141E9A, 36Eh

A Good Guess (cont'd)

Rating Data

A Good Guess

>>> hex(215)
'0x0d7'

Rating Data

sub_65C4D4 proc near
  or      dword ptr [edi+1D0h], 2
  or      dword ptr [edi+1D0h], 8
  mov     byte ptr [edi+198h], 5
  call    sub_655FD6
  mov     ebx, 0D7h       ; 215
  mov     ecx, 3Eh        ; 62
  mov     ebp, 22h        ; 34
  call    sub_65E7A3
  call    sub_65E7FB
retn

Rating Jump Table

dd offset sub_655FEF ; Mini Coaster
dd offset sub_65628D ; Bumper Boats
dd offset sub_656504 ; Canoes
dd offset sub_65679E ; Rowing boats
dd offset sub_656A27 ; Wooden Mine Ride
dd offset sub_656CA0 ; Wild Mouse

So what is "excitement"?

Excitement

Initial ride constants
+ Length
- (Too short penalty)
+ Duration
+ Max Speed
- (Too low max speed)
+ Average Speed

Excitement (cont'd)

+ # of Drops
- Too low max drop height
+ G Forces
- Too high max negative G's
- Too intense

Intensity

excitement += min(numDrops, 9) * 700
intensity += numDrops * 930

Okay! Time to build an algorithm.

Pump the brakes

Track needs to be a complete circuit!

Source

Track can't collide with itself

This is a search problem

Analog = Protein Folding

Hard Math

100 track pieces on average
~13 average branch factor
~13^100 possible track designs
roughly 2.47e+111
Chess: 1e+120

Trim the problem space!

No Loops
No Diagonal Pieces
No Brakes/Boosters

Using a genetic algorithm

Reproduction Strategies

Selection
Mutation
Crossover

Genetic algorithm cont'd

Goal: "Hello"

Starting Points

"Lr2Kl"
"JqLuy"
"qq7Xh"
"377Ph"
"L4YgS"

Evaluate Fitness

fitness("Lr2Kl")

How many characters would have to change?

"Lr2Kl" "Hello"

fitness("HerKo")

How many characters would have to change?

"HerKo" "Hello"

Smaller distance from a "good" solution == better fitness

The fitness function is the most expensive part!

Algorithm

Generate a random pool of strings
Evaluate fitness
Let the best ones "reproduce" & form next generation
Repeat at (1)

Use track pieces instead of strings

Book - David Goldberg

Selection

var weightedTotal float64 = 0
totals := make([]float64, len(p.Members))
for i := 0; i < len(p.Members); i++ {
  weightedTotal += p.Members[i].Fitness
  totals[i] = weightedTotal
}
return totals[rand.Float64()*weightedTotal]

Mutation

Generate random number for each track piece
If random # < MUTATION_PROBABILITY
Replace the piece with a different piece

Mutation (2)

Generate random number for each track piece
If random # < MUTATION_PROBABILITY
Insert a new piece

Crossover

Choose 2 parents via Select()
Choose crossover point at random
Return TrackA[0] + Track B[1]
Return Track B[0] + Track A[1]

Crossover (2)

Occasionally, let the parents survive

Let's see it!

Generated Coaster 1

Partial coasters don't load

Lessons Learned

Data inconsistencies will kill you

Observance: Table driven tests

Table Driven Tests

func TestCompatibility(t *testing.T) {
  for _, tt := range cases {
    c := tracks.Compatible(tt.first, tt.second)
    if c != tt.expected {
        t.Errorf("Compatible(%s, %s) => %q, want %q")
    }
  }
}

Table Driven Tests (cont'd)

testCases := []struct {
  first      Element
  second     Element
  compatible bool
}{
  {FLAT, LEFT_TURN, false},
  {LEFT_TURN, LEFT_BANK, false},
}

Lessons Learned

Data inconsistencies will kill you
Write tests for 2D code
Fitness function complexity is hard to predict
Make the problem as small as possible
Do the dumbest thing

Future Work

Excitement/Intensity/Nausea
Genetic Algorithm for fitness costs
Dynamically weight mutated/chosen track piece
CGo - call into OpenRCT2
Integrate with given landscape/layout
In-browser coaster viewer

Thanks to Kyle Conroy

Thanks!

Kevin Burke

github.com/kevinburke/rct

kev.inburke.com

kev@inburke.com

@derivativeburke

These slides are available at: