snippetMinor
How to devise an algorithm to generate a random but valid train track layout?
Viewed 0 times
randomtrackbutlayoutalgorithmgeneratetrainvalidhowdevise
Problem
I am wondering if I have quantity C of curved tracks and quantity S of straight tracks, how I could devise an algorithm, (computer assisted or not), to design a "random" layout using all of those tracks, such that the following rules are satisfied:
1) The tracks, when all connected, form a closed (continuous) loop for the train to go around.
2) Ramps, bending of tracks, bumping of tracks, crossing of tracks are all not allowed.
3) C and S will both be even numbers. An example would be C=20 and S=10. Note that it takes 12 curves in the same orientation to make a complete circle of 360 degrees so at least 12 of those curves need to be oriented the same way to complete the 360 degrees. The others can "zigzag" as long as the net result is 360 degrees so the train has a complete loop.
Straight tracks are about 10 inches (25.4 cm) long and curved tracks are about 12.4 inches (31.6 cm) long (down the center, following the curve) and curve 30 degrees. The "ties" on the tracks have a maximum width of 3 5/8 inches (9.2 cm). I placed a straight and curved track on top of each other and measured that the 12.4" (31.6 cm) curve has 12" (30.5 cm) of linear length (in the same direction as the straight), and 3" (7.6 cm) of bend (in the perpendicular direction of the straight). A 12C circle has diameter of 47.5" (120.6 cm) from center to center of the tracks on opposite sides.
All measurements are approximate.
UPDATE
I re-measured the tracks using many more of them to help eliminate errors and somewhat to my surprise, the length of the straights are NOT 10 inches, they appear to be about 9.78 inches. This has a significant impact on the matching of zigzag curves to straights. Originally I thought 4 zigzag curves = 5 straights but that is not quite correct. 4 curves has about 47" of linear distance so 5 straights at 9.78" each would be 48.9", almost 2 inches longer. So the trick it to find the LCM (Least Common Multiple) of 47 and 9.78. It turns out to be 235. 235
1) The tracks, when all connected, form a closed (continuous) loop for the train to go around.
2) Ramps, bending of tracks, bumping of tracks, crossing of tracks are all not allowed.
3) C and S will both be even numbers. An example would be C=20 and S=10. Note that it takes 12 curves in the same orientation to make a complete circle of 360 degrees so at least 12 of those curves need to be oriented the same way to complete the 360 degrees. The others can "zigzag" as long as the net result is 360 degrees so the train has a complete loop.
Straight tracks are about 10 inches (25.4 cm) long and curved tracks are about 12.4 inches (31.6 cm) long (down the center, following the curve) and curve 30 degrees. The "ties" on the tracks have a maximum width of 3 5/8 inches (9.2 cm). I placed a straight and curved track on top of each other and measured that the 12.4" (31.6 cm) curve has 12" (30.5 cm) of linear length (in the same direction as the straight), and 3" (7.6 cm) of bend (in the perpendicular direction of the straight). A 12C circle has diameter of 47.5" (120.6 cm) from center to center of the tracks on opposite sides.
All measurements are approximate.
UPDATE
I re-measured the tracks using many more of them to help eliminate errors and somewhat to my surprise, the length of the straights are NOT 10 inches, they appear to be about 9.78 inches. This has a significant impact on the matching of zigzag curves to straights. Originally I thought 4 zigzag curves = 5 straights but that is not quite correct. 4 curves has about 47" of linear distance so 5 straights at 9.78" each would be 48.9", almost 2 inches longer. So the trick it to find the LCM (Least Common Multiple) of 47 and 9.78. It turns out to be 235. 235
Solution
One possible solution to make this as simple as possible to quickly get a working algorithm would be as follows. The simplest layout is of course 12C (12 curved tracks all with the same orientation (relative to each other), and forming a simple circle. This will be the basis upon which we can build on.
So the basic algorithm will be to maintain the 360 degree continuous loop layout at every step when adding tracks. We can do this by examining how many curved tracks we have remaining, and adding them to the layout in groups such that the 360 degree property is maintained. For example, start with our 12C layout (a simple circle). We know we have 20C total so we have 8C remaining. The simplest addition of some of those that would maintain the 360 degree property would be to add a reverse orientation curve and a same orientation curve (same as the main circle we started with). We would then to do the same to the opposite side of the layout. In this simple example, we would have added 4 more curves to the circle layout so 12C would become 16C (with 4C leftover). We would continue placing curves until all 20 (in this example) are properly placed. Note that this layout consisting of all curves is a valid closed loop layout. The train can use this layout, however, it consists of all curved tracks so we are not yet done.
The straight tracks would then be inserted the same way except those can be added in pairs (2 tracks) since they are not changing the 360 degree property. They can be inserted anywhere so I think it would be best to first place ALL of the curved tracks, then go back and make a 2nd pass to place the straights randomly (but symmetrically).
This is the simplest algorithm I can think of for now. It is guaranteed to produce a 360 degree closed loop, a symmetrical track, and assuming the # of curves is a multiple of 4, and the # of straights is a multiple of 2, it will use each and every track.
One thing to consider though (when using this algorithm either on a computer or just in your mind as you are building the layout), is, there may be space restrictions more so in one direction than the other. For example, on a patio that is long, but not so wide. When using the algorithm, it should be biased more towards the long dimension of where the layout will be assembled.
If someone can figure out an algorithm to form an asymmetric layout using all of the tracks, that would be even more impressive.
The difference in complexity between the simplest solution and the most complicated is staggering. Starting with a circle (12C) is about as simple as it gets for this problem and is reasonable for kids, however it is very interesting to analyze a generic solution that can produce ANY valid layout (including asymmetric ones).
In reality, a non computer algorithm would be to just add some "cool" shapes to the layout and get it close to connecting, then go back and fine tune it so that it does indeed connect (for a closed loop). With 70 track pieces total (44C and 26S), a huge layout is possible. I calculated a total of about 67 feet of track which is about 20 meters. The train should take about 1 minute to loop that entire layout once.
Another candidate solution would be to take the actual measurements of each track and remember the rightmost edge of the layout. When building the layout, you can start with a straight track or with a left curve (counterclockwise), accumulating how far away the last added track is from that rightmost edge, and then when adding other tracks, never allowing a combination of tracks that will bump or cross that rightmost edge or maybe not even get close. So for example, start with a straight track (no 12C initial circle on this candidate solution), then randomly pick another track piece. Notice from the start we would NOT allow a right (clockwise) turn, since that would break the rule of "crossing" the rightmost edge. After the first straight track, our only options are another straight or a left (counterclockwise) curve. Another rule to enforce would be after a straight, we are not allowed to add more than 9 same orientation curves in a row, otherwise it will be likely to bump/cross some other tracks already in place. That limit could even be reduced to 8 for more clearance, and if that occurs, the next track MUST be a reverse oriented curve (since a straight may cause problems).
This algorithm would need some help to get it to come back and connect to the other side of that first added track piece. We can do that by insisting that counterclockwise curves count as +1 and clockwise curves count as -1, and those must add up to 12 on the last added curve. We can help this out by biasing the CC (counterclockwise) curves at a 4:1 ratio with clockwise curves, so that chances are we get 16 CC and 4 clockwise, which will effectively net a 360 degree circle. If the algorithm attempts to add a CC curve but bumps existing tracks, we have 2 options at that point, t
So the basic algorithm will be to maintain the 360 degree continuous loop layout at every step when adding tracks. We can do this by examining how many curved tracks we have remaining, and adding them to the layout in groups such that the 360 degree property is maintained. For example, start with our 12C layout (a simple circle). We know we have 20C total so we have 8C remaining. The simplest addition of some of those that would maintain the 360 degree property would be to add a reverse orientation curve and a same orientation curve (same as the main circle we started with). We would then to do the same to the opposite side of the layout. In this simple example, we would have added 4 more curves to the circle layout so 12C would become 16C (with 4C leftover). We would continue placing curves until all 20 (in this example) are properly placed. Note that this layout consisting of all curves is a valid closed loop layout. The train can use this layout, however, it consists of all curved tracks so we are not yet done.
The straight tracks would then be inserted the same way except those can be added in pairs (2 tracks) since they are not changing the 360 degree property. They can be inserted anywhere so I think it would be best to first place ALL of the curved tracks, then go back and make a 2nd pass to place the straights randomly (but symmetrically).
This is the simplest algorithm I can think of for now. It is guaranteed to produce a 360 degree closed loop, a symmetrical track, and assuming the # of curves is a multiple of 4, and the # of straights is a multiple of 2, it will use each and every track.
One thing to consider though (when using this algorithm either on a computer or just in your mind as you are building the layout), is, there may be space restrictions more so in one direction than the other. For example, on a patio that is long, but not so wide. When using the algorithm, it should be biased more towards the long dimension of where the layout will be assembled.
If someone can figure out an algorithm to form an asymmetric layout using all of the tracks, that would be even more impressive.
The difference in complexity between the simplest solution and the most complicated is staggering. Starting with a circle (12C) is about as simple as it gets for this problem and is reasonable for kids, however it is very interesting to analyze a generic solution that can produce ANY valid layout (including asymmetric ones).
In reality, a non computer algorithm would be to just add some "cool" shapes to the layout and get it close to connecting, then go back and fine tune it so that it does indeed connect (for a closed loop). With 70 track pieces total (44C and 26S), a huge layout is possible. I calculated a total of about 67 feet of track which is about 20 meters. The train should take about 1 minute to loop that entire layout once.
Another candidate solution would be to take the actual measurements of each track and remember the rightmost edge of the layout. When building the layout, you can start with a straight track or with a left curve (counterclockwise), accumulating how far away the last added track is from that rightmost edge, and then when adding other tracks, never allowing a combination of tracks that will bump or cross that rightmost edge or maybe not even get close. So for example, start with a straight track (no 12C initial circle on this candidate solution), then randomly pick another track piece. Notice from the start we would NOT allow a right (clockwise) turn, since that would break the rule of "crossing" the rightmost edge. After the first straight track, our only options are another straight or a left (counterclockwise) curve. Another rule to enforce would be after a straight, we are not allowed to add more than 9 same orientation curves in a row, otherwise it will be likely to bump/cross some other tracks already in place. That limit could even be reduced to 8 for more clearance, and if that occurs, the next track MUST be a reverse oriented curve (since a straight may cause problems).
This algorithm would need some help to get it to come back and connect to the other side of that first added track piece. We can do that by insisting that counterclockwise curves count as +1 and clockwise curves count as -1, and those must add up to 12 on the last added curve. We can help this out by biasing the CC (counterclockwise) curves at a 4:1 ratio with clockwise curves, so that chances are we get 16 CC and 4 clockwise, which will effectively net a 360 degree circle. If the algorithm attempts to add a CC curve but bumps existing tracks, we have 2 options at that point, t
Context
StackExchange Computer Science Q#117972, answer score: 4
Revisions (0)
No revisions yet.