Unlike a game its often compared to (factorio), Production Line has intelligent routing. In factorio, things on conveyor belts go in the direction you send them without thought as to if thats the right way. In Production Line, every object has intelligence, and will pick the best route from its current location to its desired location, which allows for some really cool layouts. It is also a performance nightmare.

Obviously every time the game creates a new axle, wheel, airbag or other component, we dont want to calculate a new route along all the overhead conveyors. Thats madness, so we cache a whole bunch of routes. Also, when we decide which resource importer should be assigned with (for example) airbags, we dont want to do a comparison of routes over every possible combination, so we also cache the location of the nearest 2 import bays. Once we have worked out the nearest 2 bays, we never EVER have to recalculate them unless a bay is added, deleted, or a piece of the conveyor network is added or deleted. So thats cool.

The problem is, this happens ALL THE TIME, and its a big part of gameplay. If we have, for example 100 production line slots, and 20 import bays, then we need those 100 slots to check 20 routes each, every time we change anything related to the resource network. Thats 2,000 route calculations per change. if the player is slapping down one every 3 seconds, then thats 600 routes per second, so ten routes a frame, which isn’t *that bad*.

If the map is bigger and we have 200 slots and 40 bays, then suddenly its 40 routes per frame that need calculating. Very quickly you end up with profiling data (multithreaded) like this:

There are multiple solutions that occur to me. One of them is to spread out the re-calculation over more frames, which means that the import location could be sub-optimal for a second or two longer (hardly a catastrophe). Another would be to do some clever code that works out partial routes and re-uses them as well. (If my neighbour is 1 tile away and his routes are optimal, and I have only one possible path from me to him…calculating new routes entirely is madness).

In any case, I have some actual proper bugs relating to routes *not* being calculated, which is obviously the priority, but I need to improve on this system, as it is by far the biggest cause of performance issues. FWIW, it only happens on really super-full large maps, and custom maps, but its still annoying… Eventually I’ll find a really easy fix and feel like an idiot.

Meanwhile Production Line was updated to build 1.38, with loads of cool improvements. Hope you like it.

2 Responses to “The big Production Line performance issue: route-finding”

  1. Alexey says:

    You might want to check Floyd–Warshall algorithm, or its analogues: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

    Building the matrix is O(N^3) on number of graph nodes, but then any pathfinding is just reading the path from that matrix.

    This works better for static or small graphs, obviously, but it still can be useful if you need to look up a lot of paths.

  2. Stephen says:

    Dynamic programming would seem to help here. Each junction could know immediately where to send the item?
    1. consider only junctions, sources & sinks
    2. for each sink, find the nearest junction or source. Store the edge nearest -> sink.
    3. remove all sinks.
    4. consider all junctions found in step 2 as sinks, repeat.

Leave a Reply