Routing and finding the front line

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.

Leave a Reply

Name and email address are required. Your email address will not be published.

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <s> <strike> <strong> 

%d bloggers like this: