Friday Facts #113 - Better rail building

Posted by kovarex on 2015-11-20, all posts

Hello,
0.12 will be stable soon, so is a good time to start making you want things from 0.13 right? :)

0.12.18 is a stable candidate

The 0.12.18 should be out today. It is planned to be declared stable next week as long as no serious problems are reported.

Better rail building

Building of rails, especially curved ones was always quite awkward. We always wanted to make it better, but more urgent things were in the way. Once the work on 0.13 started, I took the liberty of stealing this task as I find it quite interesting.

Before I start the technical part, let me show how it works now:
This is example of the "ghost rail planning", there will be also simplified manual building variant. It will work similarly, but the direction of the end won't be specifiable by rotation and it will just build a few rail pieces close to the player.

How is it done (technical)

The rail plan search works similar as normal A star pathfinding, but the rules are altered.
  • The location on the map is defined by position and direction.
  • Two points on the same position with different directions are unrelated.
  • Extension of a point is always just straight/left/right continuation.
The search is done both from start to goal and from goal to start:

Once the first solution is found(start and goal searches meet with opposite directions), the search continues for a little while, as better solutions might exist. In the next example, the first solution found is not optimal, as the curves can be straightened, so extra steps of the algorithm is needed to find a better solution.

Performance
The collision checking is the most time consuming part of the algorithm, as every step needs to check whether the next rail is buildable. This is especially slow for for curved rails.
The problem is, that in some extreme cases, the search can take up to tens of thousands steps. It is too much to keep the mandatory 60 FPS in that case.
The solution is to not recalculate the path every frame, but to share the search data from frame to frame. The user moves usually moves the cursor in some section, so the big part of the search data can be actually reused.This way, I can limit the path finder to do 200 nodes per tick, so it doesn't slow down the game at all, but the path search still feels responsive enough.
Once the path is selected, it needs to be sent to be processed (locally or over network in multiplayer). I don't wan't to recalculate the path again when other players have to process that action, especially when I had to find it through iterative search, so the whole path data is sent by the network. The rail paths can be pretty long sometimes, and we want to avoid sending big chunks of data over the network, so the path specification is pretty compressed. I use bit buffer, where 0 means straight and 10/11 means left/right, so storing path with 100 rails takes only a few bytes.
Removal of curved rail item
The goal of this task was to simplify the rail building, so instead of having straight rail item and curved rail item, it will be just a rail item from now on. Curved rail entity will be built by 4 rail items (by using the planner), so the player doesn't have to craft both rail item types. Rail item can be still used to build straight lines of rails as before (build and move/drag). The advantage of this approach is, that if we wanted specify other rail shapes (like the S for switching close lanes), we could do it without the need to have many different rail items to be understood by the player.

One last picture of rail search through the forest. It would take me a long time to find this one manually :)


As always, you can comment on the factorio forums.