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.
Top comments (3)
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.
What you are describing sounds like a slightly modified depth-first graph traversal.
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...