Implementing a PRT-style system in Minetest
The PRT is a lost form of public transport which is basically taxis on a rail network. Just like light rail, you go to a special station to use the system. But like a taxi, you tell the system where you wish to go, wait for a small car to come pick up you and other travellers going to the same place, then the car brings you directly to your destination, navigating the grid of intersections and never stopping along the way. PRTs were thought to be the future of transport, but the high cost and complexity means it never caught on.
Fast forward to myself, who was playing around with rail networks in Minetest's advtrains mod. At the time, the mod has rails that turn in 30-degree(ish) increments, a lifelike fixed-block signalling and interlocking system, and station rails that makes the train stop at stations. Then, I found out about the PRT architecture, which immediately interested me. A forgotten form of rail transport is a prime target! My efforts to reimplement the ideas of the PRT in Minetest evolved into this project.
How to use it?
Let me show you the final product, I'll travel from Estercroft to Armya in the Gen 2 world.
We start at little Estercroft station. I like designing stations to be small so they won't clutter the world, especially in the Gen 1 world where stations are as close as 150m apart.
Instead of hopping onto a train line, I punch in my destination, Armya...
...and asked the system to get me a train that goes there.
Here it comes! The train is only 1 car long, becuase only a few families at most would be cramming themselves into this.
The train navigates junctions along the network to get me to Armya with minimal distance. I have to record the time of each leg anyway, so I displayed it on the train as well.
There's a station in the way...
...which we can duck under and continue forward without slowing down.
And we're here!
The train now leaves the station and goes on to serve other passengers.
Tools of the trade
I know I wrote "Minecraft" above, but I actually used Minetest, an open-source, mod-focused reimagination of it. The trains are powered by the advtrains mod, which provides the rails and trains, an excellent fixed-block interlocking and signalling mechanism, and route setting based on codes put in trains. This means that you can set up a realistic metro system that even shares tracks between lines, all without touching a line of code.
Unfortunately, a PRT system isn't available for me to deploy. Luckily, advtrains allows me to program the system's behaviour in the very same language as itself - the famous game scripting language, Lua. Instead of using what is given to me, I can reimplement much of the functionalities with custom code. Even better, a shared
array table is available to all components, so I can do CTC without running cables everywhere if I wanted to.
advtrains gives each train a unique ID, which can be used to index the shared table. In addition, each train carries two fields,
LN ("Line") and
RC ("Routing Code"). These fields are used by the pre-made components, and are deleted along with the train. There isn't a way to directly detect a destroyed train, and I would have to manually garbage-collect the shared table if I destroy one.
Now that you have the necessary background knowledge, let's move on to how the system works. Many design decisions are based on the quirks of advtrains.
What do we have to do?
Here's a list of what the system has to do:
- A train needs to come to the station and stop at the departure platform.
- The train has to be told where it's going to.
- The train has to navigate the network, taking the correct path at junctions, and going through stations along the way.
- The train has to enter the destination station and stop at the arrival platform to let the passengers off.
Let's go through everything step by step.
1a: Making sure a train comes
The main inspiration behind the mtPRT project is the Morgantown PRT, which parks empty trains at various points along the network, waiting for a passenger to call a train. This requires the network to keep track of where each train is, and pick out a particular train.
Luckily, because operating a train in Minetest does not use electricity or add wear and tear, I can keep the trains running. My solution is to let the trains flowing in an uninterrupted loop through the network, and when a train comes across a station that has a passenger waiting, that train simply changes course and enters the station. Essentially, if each train is a taxi, their taxis wait for Grab to pick a passenger for them, while my taxis roam around looking for passengers. It looks funny, but it works.
To finish the proof, we also have to make sure that every single station (in fact, both sides of every station, since for simplicity's sake each side has its own platform) will come across a train regularly. One might notice that this is simply a formulation of the travelling salesman problem, where we have to find the shortest closed loop that visits every single station once. Right now, I solve the problem manually, and can manually check that, indeed, all stations are served.
In the Gen 2 system, because we need the length of every leg, I programmed the junctions to keep sending trains down every possible path. (More accurately, I always send empty trains down the least recently visited option.) Every station is on a possible path, so every station is necessarily visited.
1b: Entering the station
How do we know that a train needs to enter the station? There are many ways to do this - I'll include how it works on the Gen 1 system as well (simply because it's super ingenious) and move on to the more straightforward Gen 2 method.
Back when Gen 1 was designed, it's impossible to run custom code when a train is approaching a programmable rail, only when a train is going over one. Because the train has to start braking way before the station, only signals and "station rails" can be used. The behaviour of both of them can only be changed by the train's LN or RC fields.
I reserved the LN field for the train's destination, and used the RC field for a list of stations that need a train. Then, when a train approaches a station, the signal simply sends the train into the station if and only if the train has the station's code in the LN or RC fields. This is synchronised with the big global table at the end of the station.
Gen 2 used a much more straightforward system, as rails now have limited influence over the train while they are approaching a programmable rail.
When you reserve a train, the station rail (which is used as the main computer of sorts) first notifies the guard rail in front of the station zone that a train is needed. Going back to the taxi analogy, this turns on the "Need a taxi" light at the front of the alley. When a train approaches the guard rail, it checks whether the platform needs a train, and sends it down the appropriate path.
The trains still run around the network, but this system solves a couple of edge cases. For example, if two trains travel towards a platform at the same time, the second train might enter the platform area unnecessarily - at the time its RC is updated, the platform still needs a train, but when it actually arrives, the platform doesn't need one anymore.
2: Telling the destination
As mentioned earlier, the train's destination is stored within the LN field of the train. It's stored when the train reaches the station rail at the departure platform.
3: Navigating the network
In the Gen 1 system, trains are routed at the junctions based on their LN fields. This is a well-functioning system, but it has one issue: Whenever I add a new station, I have to add the new station to every single junction entrance's signal, and that requires flying to the actual junction and addding the new entry one by one. This doesn't scale, and solving that issue is one of the main motivations of Gen 2.
In Gen 2, the path that the train needs to take (including every single junction) is calculated by the station and stored in the RC field. The field can only store text, so I essentially wrote a queue abstract datatype for this purpose. This means that I can program the junction with only the next node, and the train will still know where to go. I could've used the built-in routing in advtrains for this, but I decided to reimplement it on my own so that I can include some features such as the empty train algorithm and the time remaining display.
The best route is actually precalculated using Dijkstra's algorithm on every starting station, and the results are cached in a vector of spanning trees. The station rail simply reads the route from the tree, which I think is cheap enough.
Firstly, the station reads the LN field to see if the train is bound for this station. If so, it will bring the train into the station. If not (and no one's waiting at the departure platform), the train is sent to the bypass route so it can zoom past the station.
There's a built-in type of rail in advtrains which automatically slows down, stops, and restarts trains, and you can make it do its job only on trains with certain values in its LN or RC fields. I used this type of rail for the arrival platform, and set it to only stop trains bound for this station (of course, by checking the LN field). The LN and RC fields are cleared by the station rail.
Nitty-gritty: Block sections
My system uses advtrains's built-in fixed block signalling. For all of you who don't know what this means, let me explain.
The entire rail network is divided into "blocks", and only one train can (or rather, should) be in a block section at a time. This is so that trains are always at a safe distance from another. In order for a train to move, the blocks that the train will move through will also have to be cleared and kept clear. This means that all paths that can be operated independently must each be in separate block sections. Here's a quick primer of the same concept being used on rollercoasters.
There's a section break between the arrival and departure platforms so that the two platforms are used independently during busy usage. It turns out, however, that the train frequency is so low that the first train would've been leaving the platform when the other one arrives, so the improvement would be marginal at best. Oh well, future proofing!