What Algorithm am I looking for?

Evan Meidell — Wed, 18 Oct 2023 03:43:09 +0000

I was playing with my 3 year old today with some toys that he quite likes and it exposed a gap in my understanding. How does track auto completion work in games like Rollercoaster Tycoon? If I wanted to input a collection of track pieces how would you build the algorithm to build a 'valid' track? These Driven toy cars and tracks have up and down roads so assuming we don't include those(remove 3d space) where do you begin?

const track = {
  tileSize: 1,
  type: 'straight',
  avilableConnections: ['male', 'female'],
}

Assuming we only have straight, 90 degree turn, T intersection, and 4 way intersections seems like it shouldn't be too hard.

Place random piece.
From first available connection get random piece that can connect.
Repeat until 'T' or '4-way' intersections are given. Track in state an additional 'available connection'.
Start looping through available connections and random pieces?

This is where I start to break down. As a bootcamp grad I never spent any time learning algorithms. At some point I need to run a 'pathfinding' algorithm to complete the track but how do I run that while expanding the road? I want to use as many of the pieces as I can.

DEV Community: Evan Meidell

What Algorithm am I looking for?