A month or so ago I said I would try to optimize Jason Milldrum’s version of Conway’s game of life running in Minecraft-pi. So now I’ve done that and I’ve tried to keep some decent documentation of the process. This post is the summary of that documentation, but if you’re just interested in the results here they are:
The first step was to add checks to find out where things were running slowest. Python has a really useful module for dealing with time, so writing code for that was easy. The code Jason wrote has three main parts – the part where the world is displayed, the part where the world is updated, and the part where the updated world is copied to the displayed world. The big bottleneck was where the world was displayed. This took around 20 seconds a time. Updating took 2 to 3 seconds and the copy was superfast and so negligible.
The display was taking so long because the entire world was being reset every frame – instead of just changing the blocks that are being changed. The first strategy for optimization was to keep a list of cells that were changing from living to dying and cells that were changing from dying to living. Then when the frame is rendered only those cells that have changed state will be set, reducing the amount of work by around a quarter.
Now the rendering runs at around five seconds initially, and as cells die out the rendering time decreases to around two or three seconds. That’s as fast as the rendering can really go. This is still going to be the bottleneck, and there is also an issue in that because the cells die and are born in different phases it’s more difficult to comprehend what is going on because you may be in the middle of a phase. I have an idea for that but in the meantime let’s see what we can do to optimise the update.
Initially I was going to reduce the number of loops by trying to calculate values for adjacent cells at the same time as the current cell, but instead I decided to keep track of the number of live neighbours. Now during each pass I check the cached number of neighbours, and if something lives or dies I increment or decrement the array for the next lot of neighbours. Initially this didn’t seem to make very much difference, then I remembered that a lot of the calculations I was doing were pointless because I has shifted the whole world in an earlier step. It didn’t seem likely to bear fruit, but I removed any calculation that was minus zero. Still no real speed increase, then I realised that I could take away the edge effects and deal with them separately, but a quick test showed that didn’t help either. I was beginning to lose hope, and then I considered the trick I had already used for rendering. What if I returned to the counting approach but kept a list of cells with live neighbours. Then I would expect to see a similar speed up as I did before, with increasing speeds as the numbers of cells with neighbours decreases. By taking this approach, and keeping a rolling track of how many neighbours each cell has the update was reduced from 2 or 3 seconds to a tenth of a second. An added bonus of running the simulation for longer means that as less cells are involved rendering drops to between 0.5 and 1.5 seconds. Nice!
One disadvantage of this approach is that the list of cells that have live neighbours (or are alive themselves) is not in order, and as all the cells dying and being born are dealt with in separate lists this meant that sometimes the simulation looked a little confusing. You couldn’t really see the start or the end, and what was happening was no longer clear. To try to combat this I tried to add some more information by colour coding the different cells before they change, to indicate why they are about to change. Cells that die of overcrowding will be marked red. Cells that die of under-population will be marked magenta, and cells that are about to be born will be marks yellow. So now we have two phases – the change that is about to happen and the change itself. This means that now more work will be done, but hopefully it will give some insight into what is going on. It may seem more responsive, and also might give away clues as to how minecraft-pi updates the screen in sections, and it should certainly be more colourful.
As you know, the results are presented above in a video that was surprisingly easy to put together (thanks for reading this far, by the way!). The entire process now takes just under five seconds – up from about 2 seconds for the non-technicolour version – but then the new visualisation involves double the “rendering” calls to Minecraft-pi.
Whilst it’s not perfect I’m quite pleased with the results. Thanks go to Jason Milldrum for the inspiration, and for the challenge, which I’ve thoroughly enjoyed.
Simon Grey's Blogorama 