Game Design, Programming and running a one-man games business…

Speeding up Production Line (large factories)

I thought I might try another of those ‘live blog’ entries where I go through my thought processes as I do some code profiling to speedup the route-finding slowdowns on super-huge Production Line factories. Here is the map I’m analyzing usage on.

I’m loading the map, waiting 20 seconds, then making a change to the resource route layout, then letting it run another 20 seconds, and taking a look at the function level profiling snapshot using aqtime. This save gamne has 8,994 slots in it (which is massive) and uses a custom map.

Here is the function breakdown for the GeneratePath() code which seems to be a major cause of any framerate issues when changing routes:

I probably need a refresher in my mind as to how this code works so… Lets look at when I change a route by (for example) placing down a new conveyor. This makes the following calls:

			SIM_GetResourceConveyors()->RefreshExits();
			SIM_GetResourcesRoutes()->PurgeAllImpossible();
			SIM_GetResourcesRoutes()->InvalidateRoutes();
			SIM_GetResourceObjects()->OnRouteAddition();

RefreshExits is trivial, taking on average 0.002ms, so not a problem, PurgeAllImpossible() doesnt show up in the profiler, but it basically sets a lot of flags to be false, and calls a sub function that also is presumably too quick to show up, so likely not a culprit.

InvalidateRoutes() is likely the culprit. It tells every slot, and every stockpile that it needs to begin verifying its current cached route table in case something has changed.

Finally OnRouteAddition goes through every intransit resource object and tells them they need to verify their route(over the next two seconds) in case a newer route is available, or the current one just got deleted. This is also too quick to show up.

So it looks like all that route invalidation is the slowdown. But why? The actual function takes 0.2ms, which is slowish…but not noticeable when a frame is 16.0 ms. Its the delay over the next few seconds that causes the problems… Basically every slot with a stockpile calls PrepareToVerifyBays()…

void SIM_PlaceableSlot::PrepareToVerifyBays()
{
	BayVerificationPending = true;
	int limit = BAY_VERIFICATION_INTERVAL;
	if (APP_GetPerformance()->DoRoutesLimitFramerate())
	{
		limit *= 2;
	}
	BayVerificationTimer = GRandom::RandomChoice(limit);
}

So in English, this code tells the slot that it needs to verify its nearest import bays, and to do so at some random time over the next 60 frames (1 second). A globally calculated value works out if we have a poor framerate, and if we are verifying bays, and thus notes that given this PC, this map etc…we need to allocate twice as much time as usual (4 seconds) to verify those bays…

Thus we have maybe 4 seconds max (4,000ms) over which to spread the effect of all this route re-calculation. That might mean up to 4 seconds of lag, which may seem a short time, but if you are watching a resource item getting delivered in the game, and it travels down the wrong route for more than four seconds…you would be perplexed, so its a reasonable target. How to make it faster?

Bays are verified every frame. a check happens every frame to see if a verification is pending, and if it is, a function gets called. That function is pretty huge and its called SIM_ProductionSlot::RecalculateNearestBay(). In my profiled sample it was called 2,200 times and on average takes 2.8ms. OH MY GOD. Almost all that time is spent inside SIM_ResourceConveyorManager::GetNearestBays(). This function itself does some fancy multithreading, spinning off taks to a lot of threads (8 on my PC) each of which processes a list of routes, eventually calling SIM_PathFinderManager::FindPath(). This gets complex so lets look at a multithreaded analysis of it in vtune:

This actually looks pretty efficient and packed, so i think that the real answer to speeding this up is not speeding up the actual route-verification, but culling the cases in which I actually even bother verifying a route. For example…Here is a simple map with production slot stockpiles at A and D, and import bays at B,C,E,F…

Both A and D keep a track of the shortest route along conveyor belts to the 2 nearest import bays. Note not every tile is a route, only each one marked with conveyors, so we have the following.

Now lets say I add a new conveyor belt tile to improve the routing from A to its two nearest bays…

Now as mere humans, its pretty clear to us that as soon as possible, we need to get A to recalculate those two routes it has to its nearest bays, because there is now a shorter route from A to B (but actually not C). Its also pretty clear that D’s routes (to E and F) are totally unaffected. Right now… my algorithm is dumb as fuck, because it tells A and D ‘OMG something changed! redo everything!’, which is a massive waste of resources. The problem is…How exactly does a better algorithm look?

This is one of those things that sounds simple but actually is not. If I learned computer science at school I’d likely be better at this, but I’m self taught. Here is my current thought process:

The route from D to E is 4 tiles. The distance from D to the new tile (pointed at by the arrow) is greater than 4. Thus there is NO way that my route from D to E can possibly be affected by this change. Thus I can leave D as a slot that keeps its old fashioned routes.

So an algorithm that made this optimization would be something like:

For Each Slot
bool bcheck = false
int max_dist_bay = GetMaxDistToBay()
For Each changed tile
If CrudeDistanceToTile <= max_dist_bay
bcheck = true

So its worth trying to see if that helps…

…And I tried it! I even wrote some debug output to verify that the number of slots that got verified each time was below 100%. Something I didn’t realize was that obviously for changes taking place right in the middle of a map, the majority of the map ends up being covered by this algorithm, as the distance for slots to the center of the map is often about the same as the distance to the nearest importer. However, when making changes nearer the edges and corners of the map, a way smaller percentage of the slots need verifying, sometimes just 2-4% of them.

Even if I just assume that we average 50% of slots being verified instead of 100%, this represents a 2x speedup in the game during these events, which should be super noticeable. Of course the only way to be sure this feeds through to user experience is to stick the new algorithm on a togglable switch and watch the frame rate counter and…

YES

It boost the framerate a LOT. Obviously its still spread out over the same amount of time, but the total amount of recalculating needed is way lower so… obviously we get a big framerate boost.

This is NOT a perfect optimised way to do it, but you can bet its already roughly twice as fast, which is great. I need a better way to work out what slots are needlessly recalculating, AND I need to ensure I can use similar techniques on situations that cause a recalc by other means, such as when stuff is deleted but…its definite progress.

I’ll probably work on the deletion case tomorrow, do some more extensive testing, then try it out in the 1.80 preview build (unstable beta) on steam.

The political compass in Democracy 4

I’m writing some Democracy 4 code today, and looking at how we display the in-game political compass. This is a graph that shows you how your political position has changed over the course of the current game.

This was in Democracy 3, and definitely back in for D4. This time around I’m stretching it to fill an entire window, as there is no magical reason why both axes have to be the same. For those unfamiliar with the concept of the political compass, it maps a political party or individual or government on 2 axes. The first axes is left-> right (communism to capitalism, or sometimes described as socialism to capitalism) and the other is up-down which is conservative to liberal.

THESE TERMS CAUSE ABSOLUTE CONFUSION EVERYWHERE.

Allow me to expands on this: There are basically TWO axes of politics, not one. In many places, people get this confused and assume liberal == socialism and conservative == capitalism. This is WRONG. There may be countries, societies, communities, and parties that make very strong associations between these two, but other positions very much exist around the world. The biggest confusion is the way US commentators use ‘liberal’ when they mean socialist, mostly because the mcarthyesque history of the US has made socialist an insult in many peoples minds (especially middle aged and older).

For example, its perfectly possible to be a liberal capitalist. I know this because I consider myself to be in that quadrant myself. I am a supporter of a (regulated) free market, a believer in entrepreneurship, and generally a supporter of lower taxes and extremely free trade… NONE of which has anything to do with my positions on..(for example)… same-sex marriage, legalizing cannabis, free-speech, equal pay or religion. Its also perfectly possible to be entirely in the opposite quadrant where you are both conservative and socialist. In fact, a LOT of 1970s British politics was in that quadrant, with very socialist (extremely high marginal taxes, opposition to free trade, very high levels of nationalization) policies mixing freely with the racist, sexist, and deeply conservative attitudes to religion, drugs, same-sex relationships etc that we would now associate with the american right. I grew up in a very strongly pro-union labour-voting community. It was not a liberal paradise.

To put this another way, you can take a far left 1970s british socialist / communist and persuade them to embrace legalizing drugs, same-sex relationships, gender-equality and LGBT issues…and that moves them on one axis but not the other.

Anyway…

The game automatically analyzes every decision you make and plots your government position each turn on the political compass automatically, which is kinda cool to watch. For Democracy 4, I thought it might be interesting to have that compass pre-loaded with the agreed (ha!) positions of a number of historical figures. For example, maybe plot President Kennedy, Nixon, Reagan, Obama and from the UK Thatcher, Blair and David Cameron. Maybe Angela Merkel should be on there? Maybe Trudeau and Trump?

I think this would be cool because it would be funny to to find yourself thinking ‘hmmm I may have gone a bit right wing economically here? and then realize you just swept past Reagan :D.

Of course the HUGE problem here is going to be coming up with locations for these people that don’t get me stoned to death by angry steam forum people. Lets be clear…everyone will; hate me for making this game at all…its pretty much locked-in as being the most divisive game ever made already. I just don’t want to DELIBERATELY annoy people, so I’ll probably do some research, plot some of those figures, then ask for feedback during Early Access :D

Its very tough because to people in the US, Bernie sanders is hugely left wing, but in Europe, I’d say maybe not so much… And to left-wingers in the UK, David Cameron was horribly right wing, but by US standards he was probably a member of the Democratic party. And the problem is…the STRONGER your political views (regardless of axes), the more you get outraged and want to push everyone who disagrees with you to the far extremes of the other side.

I know communities online where people argue that UK labour party deputy-leader tom watson is a ‘dangerously right wing blairite traitor’, despite being frankly hugely left wing by US standards. I’ve seen political compasses that put Hilary Clinton just slightly to the left of Reagan…

Fun times ahead…

Updates for Production Line. DLC coming & more

This is a round-up blog post covering lots of things:

Firstly some meta-stuff. I haven’t been super-frequent in updating this blog recently, and I also have been tweeting a lot less (in fact the wonder of analytics allows me to say my tweets are down 36% in the last month). I also un-followed a lot of accounts, I removed a lot of facebook friends, and I’ve quit some other online stuff. I’m trying to avoid the harsher, more serious, depressing net.

Frankly social media, and much of the internet in general is making me unhappy, and I’m reducing how involved I am with it. I have never been one of the ‘hip’ indies that knows everyone else, and I’m moving more towards being an ‘offline’ kind of person, for my own happiness.

Obviously that doesn’t affect tech support, PR, or blogging/tweeting about what I’m working on, so here we go…

NEW DLC! is coming to Production Line. I have not settled on a final name for it, but its likely ‘Design Variety Pack’ or something like that. Basically every car design in the game gets a duplicate, purely for cosmetic reasons. This is so you can have more variety in the game, and also so that you can more immediately tell which cars are the ‘expensive’ SUVs etc, without having to always resort to selecting a color for each design (Which I tend to do, but it feels a bit of a hack…).

Here is a tiny tiny short video clip of the new sedan.

And here is another tiny one showing we toggling between two designs of the same type.

All the code for this is now DONE, and I am thus just awaiting final artwork before I add this as a new piece of DLC. It has to be DLC because actually the art costs are PRETTY HIGH for this sort of thing, because it basically involves redoing a*all* of the car art for the game, as every new design variant may need a different position for each wheel variant, each seat, and so-on, and thats a LOT of art layers, modeled in 3D and rendered in 2 different directions.

In unrelated news, I’ve been working on some tweaks to the UI for the game, and the latest thing I added is this ability to toggle the showroom view to a ‘summary’ view that shows you how many of each car you have, rather than an endless stream of them. This is togglable with a button, but it auto-guesses which view to show you based on how full the showroom is when you first open that window:

I need to have that toggle in there to support both views because there is some functionality ‘lost’ in the summary view, as you then cannot select an individual car to see its views from customers, its applicable discounts, any defects or missing (uninstalled) features etc. Hopefully its all pretty intuitive and I don’t need any extra tutorial stuff for that? (I do worry about needing an extra tutorial window for that new toggle button for the DLC designs…not sure if its obvious or not…).

Anyway…thats Production Line stuff. I am also starting to help out full-time Democracy 4 programmer Jeff, who is doing great stuff on making the crispest, sharpest GUI for a positech game so far. (Its vector based, so smooth scaling and pixel-perfect UI is here!) I know Democracy 4 seems to be taking a long time, but it will be worth it, and we will have screenshots to show the world pretty soon :D