Category: programming

I recently got sent a HUGE factory in a savegame for Production Line. It has over 600 production slots and 24 resource importers, and its MASSIVE. Here are some screenshots:

Despite its awesomeness it was MASSIVELY slow. Not only did loading it take forever, but whenever you changed any of the resource conveyors the game would hang for about 20 seconds. hardly ideal, especially given that I have an 8core i7 PC. So I set to work trying to optimize the code. I did some fairly small optimisations first, which boosted processing by 12% but I needed more fundamental re-design.  After chatting to a fellow indie coder, I agreed that my currents system of always calculating the optimum route to everywhere, for everyone, when something changed, was clearly not viable. I switched over to a new system of ‘lazy’ computation. Basically when I change a route somewhere, it now sets a flag on every production slot saying ‘you should recalculate your nearest slot soon’. That flag gets checked every frame, and sometime in the next 120 frames 92 seconds) each slot will calculate the route from its location to all the importers, and store the nearest two. It needs this so slots seem to import from a sensible location, as opposed to an importer that is miles away.

This was good, and sped things up a LOT. Now instead of hanging, the game would stutter for about 10 seconds. better but nowhere near good enough. I then realised I was doing something seriously dumb. I was going through all those routes I calculated, and picking the nearest, THEN doing it again, to pick the second nearest. doh! This sped things up, but in retrospect, it was trivial, it just alerted me (alongside my profiler) to the fact that when I tried to get (for example0 15,000 routes, I actually calculated 30,000. How come?

It turns out that the code that multithreaded all of the ‘calc the routes’ code, was not storing any of the results, so the code that came after it which then went through the (not saved) routes to pick the nearest ones was having to recalculate them anyway. I was essentially doing everything twice.l Worse…this second bit of code was single threaded, meaning all my multithreaded time was wasted and all the work happened in a single thread. What a dork.

A nice simple change to the code to make sure those multithreaded route calcs are actually stored *doh* means that not only did the processing time half, it now gets split over potentially 8 cores instead of 1, so on my PC its now running 16x faster. Combine that with the earlier speed-ups and its likely 18x faster, and because of the frame-spanning over 120 frames, it *feels* fluid as hell, even on insane maps.

Here is the concurrency visualiser showing the loading of the insanely big map.

And here it is zoomed in showing the multithreaded bits.

Those gaps are because each slot makes a single-threaded call to evaluate all of the import bays (each colored block is the code to get a route from one import bay to one production slot), and that call (in the main thread), then spreads it over the worker threads. Ideally I’d find time to eliminate that single thread blocking. Also I have some gaps in there because the end of each threads Calc() has to use a critical section lock to deposit its new routes safely in the main thread. Ideally I’d bunch them up inside a thread structure and dump them at the end.

Anyway, enough tech bollocks, the upshot is that massive factories will now be uber-fast :D.

I thought it might be interesting to just brain dump my thoughts as I do them for a Production Line bug.

The bug is an error message which I get triggering thus:

GERROR(“No room to TrashLowPriorityResource from stockpile”);

Which is handy, as I know exactly WHAT is happening, and where in the code. Thats 95% of the work done already. Amen to asserts! I know that inside the function SIM_ResourceStockpile::TrashLowPriorityResource(), I am not able to actually do what the function needs to do. So firstly what does this function do anyway? I can’t remember… Thankfully there is a comment:

//if we find a resource not needed by current task, destroy it (only one)

Which is pretty handy. So this is a stockpile at a production task (working on a vehicle) and it needs room for a new resource presumably. The code goes through all of the objects currently in the stockpile to check we really need them. here is the code:

    iter it;
    for (it = Objects.begin(); it != Objects.end(); ++it)
    {
        SIM_ResourceObject* pobject = *it;

        //is this object needed?
        bool bneeded = false;
        SIM_ProductionTask::iter rit;
        for (int c = 0; c < SIM_ProductionSlot::MAX_RESOURCE_QUANTITIES; c++)
        {
            SIM_ResourceQuantity req = PSlot->CurrentResources[c];
            if (req.Quantity <= 0)
            {
                continue;
            }
            if (req.PResource == pobject->GetResource())
            {
                if (GetQuantity(req.PResource) > req.Quantity)
                {
                    bneeded = false;
                }
                else
                {
                    bneeded = true;
                }
            }
        }
        if (!bneeded)
        {
            RemoveObject(pobject->GetResource());
            return;
        }
    }

Thats the first half of the function, it then tries to do a simialr thing with requests, rather thanm objects. However I think I see an issue already. That GetQuantity() is checking the total quantity, not for this single object. Nope…thjat makes sense. I guess I really need to trigger the error and step through it, so time to fire up a save game from a player and run it in *slooooow* debug mode. Ok… an immediate crash from a save game..where we have 16 requests and no objects. So there seems to be a bug in the latter code:

    //ok we need to destroy a request instead of a current object.
    reqit qit;

    for (qit = Requests.begin(); qit != Requests.end(); qit++)
    {
        SIM_ResourceRequest* preq = *qit;
        //is this object needed?
        bool bneeded = false;
        for (int c = 0; c < SIM_ProductionSlot::MAX_RESOURCE_QUANTITIES; c++)
        {
            SIM_ResourceQuantity req = PSlot->CurrentResources[c];
            if (req.Quantity <= 0)
            {
                continue;
            }
            if (req.PResource == preq->PObject->GetResource())
            {
                //sure we ordered it, but do we actually have enough for this task, when com,bining requests with objects?
                int stock_and_ordered = GetStockAndOrdered(req.PResource);
                if (stock_and_ordered >= req.Quantity)
                {
                    Requests.remove(preq);
                    preq->PObject->Trash();
                    return;
                }
                bneeded = true;
            }
        }
        if (!bneeded)
        {
            Requests.remove(preq);
            preq->PObject->Trash();
            return;
        }
    }

So what could be wrong here? Ok…well hang on a darned minute. This code is just saying ‘do we really need resources of this type right now???’ rather than ‘do we need ALL of these right now?’  which is more of a problem. We are clearly somehow ‘over-ordering’. The slot in question is ‘fit trunk’. presumably it only needs trunks… They do all indeed appear to be the same type. 4 are ‘intransit’ the rest are queued up at some resource importer or a supply stockpile or component stockpile somewhere.

So the ‘solution’ is easy. First kill off (delete) a request that is not in transit yet, to make room, or if that is not possible, kill one that actually is in transit. This then frees up the required place in our stockpile. But hold on? this is just patching over the wound? how on earth did this happen? The calling code is requesting new resources, when clearly 16 are already on the way! in fact its requesting a servo…

AHAHAHAHA!

what a beautiful bug. The player obviously upgraded to a powered tailgate, which means a servo is needed for every trunk, and yet 16 trunks were already on order. Error! error! I have special code that handles when an upgrade makes an existing resource requirement obsolete (climate control replaces aircon), but not code to handle this case, where additional stuff is needed. This is FINE, I can implement the above mentioned code without worrying how it happened.

That actually wasn’t too bad at all :D

A mixed bag of stuff this week. I’m crunching away boih at bugs, and balance issues, which make for a poor video, but also luckily we now have lot-expansion plus some zoom-out UI shininess to look at, plus I fire up nvidia nsight to give you a quick preview of how a frame gets rendered in the game. (FWIW I use my own engine, based on directx9 which means I need to worry about draw calls when changing textures. One day I’ll switch to a newer directx version, but I feel no pressing urge to do so yet :D.

Enjoy:

This is the short ‘story so far’ on animation compression for Production Line, my next game. I use my own engine that runs on directx9,a nd the game is isometyric in style, so uses a lot of spritesheet-style animation frames. In short, this is about how I enable animations like the one below (excuse the crappy gif compression, actual image is less pixelated in the real game), to fit into tiny amounts of video memory. (The disk version of that anim is 4MB, compressed for download its 355k). This is an ‘idle’ anim of a marketing manager in the game checking his phone to make all-important marketing related phonecalls…

You might think that cannot possibly be a 4MB animation, but you would be dead wrong. The actual source graphic is 128 wide by 256 high, after cropping, meaning that a frame of it gets delivered from the artist looking like this:

Thats no problem, but a complete animation cycle is 300 frames long, and I need two versions, one to look towards, one away (I can flip in X axis for the others). 128 x 256 x 300 is 9.8 million pixels, or a 4096 x 2,400 pixel sprite sheet, which takes up 39MB of VRAM. Assume both directions are in use = 80MB, 3 different characters is 240MB. Thats with one skin color and one gender. Ouch. So obviously we need to compress it.

I rolled my own compression system for fun, and to give me total control over how it works. The first step is to cut out any dead space and remove any duplicates. When our little dude is on the phone, the image doesn’t change, so we have a lot of duplication in that colossal theoretical sprite sheet. How did I approach this?

I decided upon a 64 chunk ‘grid’ for any image that would be animated, dividing it into 8 sections horizontally and vertically. With the raw image I get given, that gives me this:

Actually this is annoying because his hair only just clips into another row, which is inefficient… never mind. The most obvious thing here is that a lot of the animation frame is just empty space. In order to kill both the ’empty space’ and the ‘same as last frame’ problems in one go, I work out a CRC (basically a unique signature) for each of those grid squares, for each frame, and store it in a great big list of data as a pre-processing step.

With all that data in memory, I then go through each chunk of each frame, and look for previous frame chunks with the same CRC. If I don’t find any, I mark it as a ‘used’ chunk. if I do, I just make a note of which earlier chunk to use, and increment the use count on the old chunk. Once this is done, I can go through all the chunks and discard the ones that have a zero use count (or are blank).
Stage two is to create a whacking great spritesheet of all of the chunks that I actually *do* use, which looks like a weird mashup of imagery like this:

(It also has an alpha channel). I can then go through all of those ‘used’ chunks and make a note of the UV values for each of them in my new spritesheet. Now, the final stage is to go through every frame of the animation, and make a note of which chunks actually get drawn, and the index into my list of ‘used’ chunks. This means I now have a big text file for the animation that tells me which of the 64 maximum chunks of the spritesheet I need to draw in each frame. In the case of this phone-dude, that shrinks the actual texture memory usage by 95%, meaning I can easily have a bunch of different animations.

Thats where I am right now, and its pretty fluid, and works without bugs. The next step will be optimizing the code, rather than the source. An optimisation I managed today was to actually successfully only draw the non transparent chunks when I do the rendering of each frame, which reduces the number of polys and draw calls. The next obvious optimization is to spot when a chunks ‘source id’ is the same as the previous frame, and then not bother updating it at all. Right now, I redo the UV lookup and apply the values every frame for this dudes legs, even though they don’t move during the whole animation. Thats a bit too much processing for my liking.

I’m sure middleware *does* exist that does this, but I like to code stuff myself so I know 100% how it works, 100% how fast/slow it is, and can ensure compatibility with all the rest of my code and workflow. I’ve probably spent a week doing this, maybe a bit more, but I have a pretty cool system now that lets me knock up a 30 secon text file when I get a new bunch of animation source files, then hit the launch button and the game will do all the preprocessing and give me the compressed data automatically. Yay.

This also means that with only 4MB+4MB of VRAM for an animation for a character, I could double the characters, and have both genders without running out of VRAM. This also makes the game more usable on low end PCs. Now the limit is my art budget, rather than the hardware :D Anyway here is a reminder of the final video, and also that this is for my car factory game: Production Line