“It’s, well, it’s a minimum spanning tree algorithm - no wait, sorry, that doesn’t help -“
My kids, like many kids are now interested in getting computers to do what they tell them to. In theory I should be well placed to help out, but I’m basically self-taught; I have to rack my brains to work out the best way in. As a result we’re taking quite a scattergun approach to it – some Scratch here, and some html there, and a supportive local Coder Dojo run by Mark Lombardo that’s doing a great job of helping channel some of this energy in a structured way. And, of course, there’s Minecraft.
I want my kids to grow up feeling that they can change the world around them if they want to. With software generally it’s hard because the gap between a polished piece of software and your first html page is so large. Minecraft, however, has s thriving mod community centred mostly on the use of Forge, itself based on decompiled Minecraft sources from the somewhat-mysterious Mod Coder Pack. Here there’s a bridge, and they can see that lots of people are able to change how this thing works. So I said I’d create a mod that spawned a maze to solve. “No, it should have unicorns” my son said. Already with the scope creep.
“It’ll give me an excuse to write some Scala again”, I thought. “Hold on, how do you generate a maze algorithmically?”
Making a minecraft mod
The first question I actually tackled was “Hang on, how do you create a Minecraft mod?”
These days Minecraft has a significant community of fans creating extensions - or mods - that add modify the behaviour of the game in some way. These mods cover a range of sophistication from minor to major, enabling to you do many things from colour coding certain chat messages to playing entirely new game modes online hosted by actual revenue-generating services like Hypixel. I’m not going to discuss creating a mod in detail but suffice to say you need to expend some effort to do it. The Forge website is typically dev in its lack of docs, but there are a number of tutorials out there including this one for Scala and Intellij by nornagon that helped me get started.
After fiddling around for a short while I created a Minecraft mod that gives you a Maze Seed that be used to spawn a randomly generated maze. A chest lies somewhere in the maze, containing a diamond as treasure. It’s standard adventure game fare, but even so it’s a decent workout for a developer.
Generating a maze
Partly it was a workout because algorithmically generating a maze uses some fairly fundamental processes. I used a modified version of Prim’s algorithm to do it. No original thought on my part, it’s a well-known modification: for a square maze the trick is in using the inter-node weights to express the topology of a maze grid, with each cell only having four equidistant neighbours, and choosing one randomly to proceed with at each step.
That makes it sound complicated. It’s not, really, and I think I’ve figured out that I can show the kids how to do it by hand on paper – it must be possible to work through the algorithm by hand and generate a maze with them, and that’s exactly the kind of thing the new computing curriculum is asking them to understand. If that doesn’t end up in Monopoly-scale arguments I might blog it.
At the same time it might be good to teach them an algorithm for exploring a maze as well. The only one I know is to take-every-left-turn – and we can do that in Minecraft, with the mod, or on paper. It struck me that might only work if the maze isn’t changing around you, which leads to an interesting problem in its own right. If you start with a maze where every point can be reached, then add an arbitrary wall, how do you adjust the rest of the maze to make sure that every point can still be reached?
Prim’s algorithm is fairly simple and also easily translated into a functional form, which was interesting to work through in Scala. It feels quite clean – but in truth I don’t think Scala’s the big jump for C# devs that it is for Java devs, as much of it felt very familiar. Feel free to laugh at my Scala code with abandon, naturally. Any constructive comments welcome - but for now, on with the actual mod.
It started with a command (-line interface)
Once you have a basic mod structure in place it’s a matter of either finding tutorials describing what you want to do, finding code that does it already or digging around in the sources for inspiration. Minecraft allows you to create commands that can be issued from the chat window. I found the source for CommandSetBlock and copied it into my own SummonMazeCommand (one of the benefits of Intellij is that it attempts an autoconversion to Scala for you on paste, which helps with the dog-work of interfaces and so on). After cutting it down to the essentials I had it instantiate a PrimsMaze and then display the result in the Minecraft log. I was in business – and this is something the kids could do, but the effect isn’t particularly SO WOW.
The next step was to find some natural way to get this to happen in the Minecraft world. I imagine a Maze Seed that could be used on any given block to cause a maze to grow. Adding an item – actually, technically rendering an item – was a bit frustrating, as it relies on putting in place a few json config files, a texture, and registering the item and its renderer in quite specific places, meaning you need to take a lot of care over filepaths and some varying referencing conventions. I suspect I’m doing the kids a disservice but I suspect that’s the kind of process that would a) be a good learning experience and b) put them off for life. What this thing needs is a DSL that wraps all this stuff up and allows you to easily add a new item and choose from a series of effects. Like Scratch for Minecraft. I wonder if Scratch is open sourced?
So, I had a command and a Maze Seed, both of which could create a maze – but that maze wasn’t yet actually built in the Minecraft world. I had to fight the urge at this point to add configuration options – and how big would you like your maze, sir? – keep the interface minimal and get a maze actually built.
Building the maze in Minecraft
My, was this the exciting bit. Running a command actually results in the command being run on both client and server components (even the solo offline Minecraft internally uses the same architecture). I only figured that out by logging whether the code was executing in a context where world.isRemote == true, and where it was false. And I only guessed that from the fact a log showed the command being called twice. Similarly, set blocks in the world also gets evaluated client and server side. That led to some interesting problems. If I created blocks in both (that is, I didn’t constrain it) then the world would get confused and register blocks in unexpected places – and not render them. When the player reached them it’d be like they met an invisible rubber wall as they jiggled backward and forward while (I’m guessing) the client and server attempted to negotiate what was going on.
That took a short while to guess my way through – but you can output the state of each block, and by doing that in client and server contexts and writing out the results you can see that there are discrepancies between the two world models.
Generating blocks only on the client works, and doesn’t lead to any invisible rubber walls, but as the server didn’t find out about it the changes were never saved down, so all mazes would disappear on reload.
Generating blocks only on the server worked, but there was no guarantee that the client would automatically render them! They appeared on a reload, but that seemed a big ask of the user of a well polished professional mod. Or this one.
I settled on the server-side placement after figuring out I could mark relevant chunks (chunks of the world) dirty after placing the blocks. That caused the client to redraw the dirty chunks, revealing the maze.
In hindsight there’s a shedload of experience and buried context I drew on there that would have made it difficult for anyone without the same experience or a very unambiguous tutorial to achieve the same goal.
And what did we learn?
From a standing start it’s a tall order to get kids to write a mod. They’d need to be familiar with Java at least and likely need a lot of guidance in actually getting anything sophisticated done in the world, although as I say I might be doing them a disservice, and they might wrangle everything into place to get new items and blocks into the game. I’ve sat watching my daughter painstakingly craft html by hand for example, so it might well be doable with a recipe.
Probably the greatest problem and the greatest benefit is that I’ve actually thought about the gap between a complete beginner and someone who’s been coding for a while. There are some activities involved in the process above that a beginner could tackle but they’re buried in a quite complex environment that would mostly likely dishearten someone who didn’t have someone experienced on hand. Even then, much would seem like black magic. Out of it pops a few activities that I’m keen to try though – a by-hand Prim’s maze algorithm for example, or algorithms for exploring a whole maze efficiently. Also adding simple commands, blocks and items to the game. I suspect recipes are also fairly straightforward.
I’ve also got nine-tenths of an algorithm for dynamically adjusting a maze when a wall is added arbitrarily that keeps popping back into mind, demanding to be implemented. But first, I have a few games to play with the kids …