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'],
}

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.

Comments

[Keff]

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.

[Red Ochsenbein (he/him)]

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

[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...