DEV Community

Evan Meidell
Evan Meidell

Posted on

What Algorithm am I looking for?

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'],
}
Enter fullscreen mode Exit fullscreen mode

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

  1. Place random piece.
  2. From first available connection get random piece that can connect.
  3. Repeat until 'T' or '4-way' intersections are given. Track in state an additional 'available connection'.
  4. 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.

Top comments (3)

Collapse
 
nombrekeff profile image
Keff • Edited

You could take a look at the wave function collapse algorithm. It can be used to generate procedural stuff, it seems pretty simple and efficient.

It's based on a set of rules on how tiles (or tracks pieces in your case) can join together with some randomness.

Collapse
 
syeo66 profile image
Red Ochsenbein (he/him)

What you are describing sounds like a slightly modified depth-first graph traversal.

Collapse
 
matkwa profile image
Mat Kwa

Depending on your set of restrictions different algorithms come into question. Generally a good starting point to understand these is A* search.

en.wikipedia.org/wiki/A*_search_al...