Every now and again, for some reason I can’t explain, my little “flood fill” algorithm from tracing supply links out from the factories manages to miss a spot.
Trying to replicate and then diagnose it, I became dissatisfied with the approach I’d used. I’m pretty sure that the problem arises from my attempt to optimize by reducing the frequency with which I have to do a full repaint.
My first thought was: how about I run each factory on a different CPU core. Unfortunately, my approach is not thread-safe because it tampers with every CP it visits.
I looked at making a version that uses an open and closed list, like A* algorithms, Dijkstra etc. Trouble is, the data is not well organized in memory for this kind of operation: The CPs (towns) are held in one large array in memory, each one not trivial in size. Each contains a std::vector of pointers to the outgoing “link” definitions. A link has a pointer to the depot buildings at either end of the link, the FB on it etc, and there is one for each direction.
So … To connect leftCP to rightCP, you have to do:
Which is numerous hops, skips and jumps around memory. Really, the links need to be allocated with the CP they are leaving, but I was too lazy to use an in-place memory allocator for the std::vector.
The next thing I have to investigate is building a routing table specifically for this. Since link states don’t change all that often, I think the cost of having to modify the table now and again is probably worth the gain I can get in cache performance from having a well-organized, memory-compact dataset. Thought I might have to bite the bullet and not use an STL or boost container for doing it.