Archive for July, 2013


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.

Advertisements

Molly Goes Swimming

Molly’s recovery from her knee surgery is going swimmingly, literally. Her scar is all healed up and she’s bombing round the house probably a bit too much, and yesterday she went for her first hydrotherapy session.

You can see a short video of it here:

Molly did really well, as you can see. Incredibly cute!

TeenTech 2013

Last Thursday I was running a session for Teentech and now, on Monday I’ve just about recovered from it all! Teentech is an event for schools that is held at various locations around the UK to raise teenager’s awareness and interest in careers with STEM skills (Science, Technology, Engineering and Maths). In Hull the event is held at KC Stadium, which is a fantastic venue.

teentech

I was running a session that began with a short talk (that got increasingly shorter) about the games industry followed by an activity to create a character for a top trumps game. Each character was then judged on the quality of the narrative and artwork that the students had produced. Over the summer all of the characters that were created will be drawn up by Platform Expos and Spooky Elephant artist Lewis Jackson to create a playable game.

This was a different type of session to the ones I’m used to and I learnt a lot during the three times I ran it. Although in hindsight there is a lot I would do differently I think the session went well, and could even be regarded as a success. Each school group created a character, with artwork, statistics and a backstory. They were fabulously inventive, which I loved, and some of the artwork, created in just seven minutes was really amazing! Two groups of runners up will receive 6 tickets to Platform Expos in November and the overall winners will get 12 tickets, and an amazing trophy to take back to their school.

Congratulations to staff and students from Winterton!

Congratulations to staff and students from Winterton!

I’d like to thank everyone for their support, from the organizers and staff from teentech to the guys from platform studios who helped me out to the students and staff who attended to David who wrote the demonstration of the game and worked through the judges results to find the winners. Your efforts were all appreciated.

I’ve also had lots of lovely feedback from the schools that did the activity, and met some students who expressed not only and interest in studying programming, but studying programming at Hull. I look forward to seeing you again in about five years time!