WorldEditAdditions: The story of the //convolve command

Sometimes, one finds a fascinating new use for an algorithm in a completely unrelated field to its original application. Such is the case with the algorithm behind the //convolve command in WorldEditAdditions which I recently blogged about. At the time, I had tried out the //smooth command provided by we_env, but The //smooth command smooths out rough edges in the terrain inside the defined WorldEdit region, but I was less than satisfied with it's flexibility, configurability, and performance.

To this end, I set about devising a solution. My breakthrough in solving the problem occurred when I realised that the problem of terrain smoothing is much easier when you consider it as a 2D heightmap, which is itself suspiciously like a greyscale image. Image editors such as GIMP already have support for smoothing with their various blur filters, the most interesting of which for my use case was the gaussian blur filter. By applying a gaussian blur to the terrain heightmap, it would have the effect of smoothing the terrain - and thus //convolve was born.

If you're looking for a detailed explanation on how to use this command, you're probably in the wrong place - this post is more of a developer commentary on how it is implemented. For an explanation on how to use the command, please refer to the chat command reference.

The gaussian blur effect is applied by performing an operation called a convolution over the input 2D array. This function is not specific to image editor (it can be found in AI too), and it calculates the new value for each pixel by taking a weighted sum of it's existing value and all of it's neighbours. It's perhaps best explained with a diagram:

All the weights in the kernel (sometimes called a filter) are floating-point numbers and should add up to 1. Since we look at each pixels neighbours, we can't operate on the pixels around the edge of the image. Different implementations have different approaches to solving this problem:

1. Drop them in the output image (i.e. the output image is slightly smaller than the input) - a CNN in AI does this by default in most frameworks
2. Ignore the pixel and pass it straight through
3. Take only a portion of the kernel and remap the weights to that we can use that instead
4. Wrap around to the other side of the image

For my implementation of the //convolve command, the heightmap in my case is essentially infinite in all directions (although I obviously request a small subset thereof), so I chose option 2 here. I calculate the boundary given the size of the kernel and request an area with an extra border around it so I can operate on all the pixels inside the defined region.

Let's look at the maths more specifically here:

Given an input image, for each pixel we take a multiply the kernel by each pixel and it's neighbours, and for each resulting matrix we sum all the values therein to get the new pixel value.

The specific weightings are of course configurable, and are represented by a rectangular (often square) 2D array. By manipulating these weightings, one can perform different kinds of operations. All of the following operations can be performed using this method:

• Blur, of varying different descriptions
• Edge detection
• Sharpen
• Emboss
• And others I'm sure

Currently, WorldEditAdditions supports 3 different kernels in the //convolve command:

• Box blur - frequently has artefacts
• Gaussian Blur (additional parameter: sigma, which controls the 'blurriness') - the default, and also most complicated to implement
• Pascal - A unique variant I derived from Pascal's Triangle. Works out as slightly sharper than Gaussian Blur without having artifacts like box blur.

After implementing the core convolution engine, writing functions to generate kernels of defined size for the above kernels was a relatively simple matter. If you know of another kernel that you think would be useful to have in WorldEditAdditions, I'm definitely open to implementing it.

For the curious, the core convolutional filter can be found in convolve.lua. It takes 4 arguments:

1. The heightmap - a flat ZERO indexed array of values. Think of a flat array containing image data like the HTML5 Canvas getImageData() function.
2. The size of the heightmap in the form { x = width, z = height }
3. The kernel (internally called a matrix), in the same form as the heightmap
4. The size of the kernel in the same form as the size of the heightmap.

Reflecting on the implementation, I'm pretty happy with it within the restrictions of the environment within which it runs. As you might have suspected based on my explanation above, convolutionally-based operations are highly parallelisable (there's a reason they are used in AI), and so there's a ton of scope for at using multiple threads, SIMD, and more - but unfortunately the Lua (5.1! It's so frustrating since 5.4 is out now) environment in Minetest doesn't allow for threading or other optimisations to be made.

The other thing I might do something about soon is the syntax of the command. Currently it looks like this:

//convolve <kernel> [<width>[,<height>]] [<sigma>]

Given the way I've used this command in-the-field, I've found myself specifying the kernel width and the sigma value more often than I have found myself changing the kernel. With this observation in hand, it would be nice to figure out a better syntax here that reduces the amount of typing for everyday use-cases.

In a future post about WorldEditAdditions, I want to talk about a number of topics, such as the snowballs algorithm in the //erode. I also potentially may post about the new //noise2d command I've working on, but that might take a while (I'm still working on implementing a decent noise function for that, since at the time of typing the Perlin noise implementation I've ported is less than perfect).

WorldEditAdditions: More WorldEdit commands for Minetest

Personally, I see enormous creative potential in games such as Minetest. For those who aren't in the know, Minetest is a voxel sandbox game rather like the popular Minecraft. Being open-source though, it has a solid Lua Modding API that allows players with a bit of Lua knowledge to script their own mods with little difficulty (though Lua doesn't come with batteries included, but that's a topic for another day). Given the ease of making mods, Minetest puts much more emphasis on installing and using mods - in fact most content is obtained this way.

Personally I find creative building in Minetest a relaxing activity, and one of the mods I have found most useful for this is WorldEdit. Those familiar with Minecraft may already be aware of WorldEdit for Minecraft - Minetest has it's own equivalent too. WorldEdit in both games provides an array of commands one can type into the chat window to perform various functions to manipulate the world - for example fill an area with blocks, create shapes such as spheres and pyramids, or replace 1 type of node with another.

Unfortunately though, WorldEdit for Minetest (henceforth simply WorldEdit) doesn't have quite the same feature set that WorldEdit for Minecraft does - so I decided to do something about it. Initially, I contributed a pull request to node weighting support to the //mix command, but I quickly realised that the scale of the plans I had in mind weren't exactly compatible with WorldEdit's codebase (as of the time of typing WorldEdit for Minetest's codebase consists of a relatively small number of very long files).

(Above: The WorldEditAdditions logo, kindly created by @VorTechnix with Blender 2.9)

To this end, I decided to create my own project in which I could build out the codebase in my own way, without waiting for lots of pull requests to be merged (which would probably put strain on the maintainers of WorldEdit).

The result of this is a new mod for Minetest which I've called WorldEditAdditions. Currently, it has over 35 additional commands (though by the time you read this that number has almost certainly grown!) and 2 handheld tools that extend the core feature set provided by WorldEdit, adding commands to do things like:

• Plant instant forests (//forest)
• Generate torus (i.e. doughnut) shapes (//torus)
• Simulate erosion (currently experimental, as I'm still tweaking the parameters) (//erode)
• Smooth terrain out (//convolve)
• Generate 2d and 3d mazes (//maze, //maze3d) - also responsible for my 3D mazes with Lua, OpenSCAD, and Blender blog post
• Scale regions up and down - even at the same time! (//scale)
• Run commands on areas that won't fit into memory all at the same time (//subdivide)

These are just a few of my favourites - I've implemented many more beyond those in this list. VorTechnix has also contributed a raft of improvements, from improvements to //torus to an entire suite of selection commands (//srect, //scol, //scube, and more), which has been an amazing experience to collaborate on an open-source project with someone on another continent (open-source is so cool like that).

A fundamental difference I decided on at the beginning when working of WorldEditAdditions was to split my new codebase into lots of loosely connected files, and have each file have a single purpose. If a files gets over 150 lines, then it's a candidate for being split up - for example every command has a backend (which sometimes itself spans multiple files, as in the case of //convolve and //erode) that actually manipulates the Minetest world and a front-end that handles the chat command parsing (this way we also get an API for free! Still working on documenting that properly though - if anyone knows of something like documentation for Lua please comment below). By doing this, I enable the codebase to scale in a way that the original WorldEdit codebase does not.

I've had a ton of fun so far implementing different commands and subsequently using them (it's so satisfying to see a new command finally working!), and they have already proved very useful in creative building. Evidently others think so too, as we've already had over 4800 downloads on ContentDB:

Given the enormous amount of work I and others have put into WorldEditAdditions and the level of polish it is now achieving (on par with my other big project Pepperminty Wiki, which I've blogged about before), recently I also built a website for it:

You can visit it here: https://worldeditadditions.mooncarrot.space/

I built the website with Eleventy, as I did with the Pepperminty Wiki website (blog post). My experience with Eleventy this time around was much more positive than last time - more on this in future blog post. For the observant, I did lift the fancy button code on the new WorldEditAdditions website from the Pepperminty Wiki website :D

The website has the number of functions:

• Explaining what WorldEditAdditions is
• Instructing people on how to install it
• Showing people how to use it
• Providing a central reference of commands

I think I covered all of these bases fairly well, but only time will tell how actual users find it (please comment below! It gives me a huge amount of motivation to continue working on stuff like this).

Several components of the WorldEditAdditions codebase deserve their own blog posts that have not yet got one - especially //erode and //convolve, so do look out for those at some point in the future.

Moving forwards with WorldEditAdditions, I want to bring it up to feature parity with Worldedit for Minecraft. I also have a number of cool and unique commands in mind I'm working on such as //noise (apply an arbitrary 2d noise function to the height of the terrain), //mathapply (execute another command, but only apply changes to the nodes whose coordinates result in a number greater than 0.5 when pushed through a given arbitrary mathematical expression - I've already started implementing a mathematical expression parser in Lua with a recursive-descent parser, but have run into difficulties with operator precedence), and exporting Minetest regions to obj files that can then be imported into Blender (a collaboration with @VorTechnix).

If WorldEditAdditions has caught your interest, you can get started by visiting the WorldEditAdditions website: https://worldeditadditions.mooncarrot.space/.

If you find it useful, please consider starring it on GitHub and leaving a review on ContentDB! If you run into difficulties, please open an issue and I'll help you out.

Lua in Review 2

Back in 2015, I reviewed the programming language Lua. A few months ago I rediscovered the maze generation implementation I ported as part of that post, and since then I've been writing quite a bit of Lua - so I thought I'd return to the thoughts in that original post and write another language review now that I've had some more experience with the language.

For those not in the know, Lua is a lightweight scripting language. You can find out more here: https://www.lua.org/

In the last post, I mentioned that Lua is very lightweight. I still feel this is true today - and it has significant advantages in that the language is relatively simple to understand and get started in - and feels very predictable in how it functions.

It is often said that Lua is designed to be embedded in other programs (such as to provide a modding interface to a game, for example) - and this certainly seems to hold true. Lua definitely seems to be well-suited for this kind of use-case.

The lightweightness comes at a cost though. The first of these is the standard library. Compared to other languages such as C♯ and even Javascript, the standard library sucks. At least half of the time you find yourself reimplementing some algorithm that should have been packaged with the language itself:

• Testing if a string starts with a given substring
• Rounding a number to the nearest integer
• Making a shallow copy of a table

Do you want to do any of these? Too bad, you'll have to implement them yourself in Lua. While these really aren't a big deal, my point here is that with functions like these it can be all too easy to make a mistake when implementing them, and then your code has a bug in it. If you find and fix an obscure edge case for example, that fix will only apply to your code and not the hundreds of other ad-hoc implementations other developers have had to cook up to get things done, leading to duplicated and wasted effort.

A related issue I'm increasingly finding is that of the module system and the lack of reusable packages. In Lua, if you want to import code from another file as a self-contained module, you use the require function, like this:

local foo = require("foo")

The above will import code from a file named foo.lua. However, this module import here is done relative to the entrypoint of your program, and not the file that's requesting the import, leading to a number of issues:

• If you want to move a self-contained subsection of a codebase around, suddenly you have to rewrite all the imports of not only the rest of the codebase (as normal), but also of all the files in the subdirectory you've just moved
• You can't have a self-contained 'package' of code that, say, you have in a git submodule - because the code in the submodule can't predict the path to the original entrypoint of your program relative to itself

While LuaRocks attempts to alleviate this issue to some extent (and I admit I haven't yet investigated it in any great detail), as far as I can tell it installs packages globally, which doesn't help if you're writing some Lua that is going to be embedded inside another program, as the global package may or may not be available. Even if it is available, it's debatable as to whether you'd be allowed to import it anyway, since many embedded environments have restrictions in place here for security purposes.

Despite these problems, I've found Lua to be quite a nice language to use (if a little on the verbose side, due to syntactical structure and the lack of a switch statement). Although it's not great at getting out of your way and letting you get on with your day (Javascript is better at this I find), it does have some particularly nice features - such as returning multiple values from a single function (which mostly makes up for the lack of exceptions), and some cute table definition syntax.

It's not the kind of language you want to use for your next big project, but it's certainly worth experimenting with to broaden your horizons and learn a new language that forces you to program in a significantly different style than you would perhaps use normally.

3D mazes with Lua, OpenSCAD, and Blender

Way back in 2015, I posted a language review about Lua. In that post, I ported an even older 2D maze generator I implemented in Python when I was in secondary school on a Raspberry Pi (this was one of the first experiences I had with the Raspberry Pi). I talked about how Lua was easy to get started with, but difficult do anything serious because everything starts from 1, not 0 - and that immutable strings are awkward.

Since then, I've gained lots more experience with the language. As an aside, I discovered a nice paradigm for building strings:

local function string_example()
    local parts = {} -- Create a table
    table.insert(parts, "This is ") -- Add some strings
    table.insert(parts, "a ")
    table.insert(parts, "string")
    return table.concat(result, "") -- Concatenate them all at once and return
end

Anyway, before I get too distracted, I think the best way to continue this post is with a picture:

Fair warning: This blog post is pretty media heavy. If you are viewing on your mobile device with a limited data connection, you might want to continue reading on another device later.

Pretty cool, right? Perhaps I should explain a little about how I got here. A month or two ago, I rediscovered the above blog post and the Lua port of my Python 2d maze generator. It outputs mazes like this:

#################
#   #     #     #
### ##### ##### #
# #   #       # #
# # # # # ##### #
# # #   #       #
# ### # ### #####
#     #   #     #
#################

(I can't believe I didn't include example output in my previous blog post!)

My first thought was that I could upgrade it to support 3d mazes as well. One thing led to another, and I ended up with a 3D maze generator that output something like this:

#################
#################
#################
#################
#################
#################
#################
#################
#################

#################
#   #   #       #
# ### ###########
#           # # #
# ####### ### # #
#       #   # # #
# ### ####### # #
#   #       # # #
#################

#################
##### ### #######
#################
############### #
#################
############# # #
#################
# ########### ###
#################

#################
#               #
# ### ###########
#   #         # #
# ###############
#               #
##### # ####### #
#   # #     # # #
#################

#################
#################
#################
#################
#################
#################
#################
#################
#################

Each block of hash (#) symbols is a layer of the maze. It's a bit hard to visualise though, so I decided to do something about it. For my masters project, I used OpenSCAD to design a housing for an Internet of Things project I did. Since it's essentially a programming language for expressing 3D models, I realised that it would be perfect for representing my 3D mazes - and since said mazes use a grid, I can simply generate an OpenSCAD file full of cubes for all the locations at which I have a hash symbol in the output (the data itself is stored in a nested table setup, which I then process).

This is much better. We can clearly see the maze now and navigate around it. OpenSCAD's preview controls are really quite easy to pick up. What you see in the above screenshot is an 'inverted' version of the maze - i.e. instead of carving out a solid block, the algorithm walks around an empty space inside a defined region.

The algorithm that generates the maze itself is pretty much the same as the original algorithm I devised myself in Python (which I've now lost, sadly - as I didn't use Git back then).

It starts in the top left corner, and then does a random walk around the defined area. It keeps track of where it has been in a node list (basically a list of coordinates), and every time it takes a step forwards, there's a chance it will jump back to a previous position in the nodes list. Once it can't jump anywhere from a position, that position is considered complete and is removed from the nodes list. Once the node list is empty, the maze is considered complete and it returns the output.

As soon as I saw the STL export function though, I knew I could do better. I've used Blender before a little bit - it's a production-grade free open-source rendering program. You can model things in it and apply textures to them, and then render the result. It is using a program like this that many CGI pictures (and films!) are created.

Crucially for my case, I found the STL import function. With that, I could import the STL I exported from OpenSCAD, and then have some fun playing around with the settings to get some cool renders of some mazes:

(Above: Some renders of some of the outputs of the maze generator. See the full size image [3 MiB])

The sizes of the above are as follows, in grid squares as generated by the Lua 3d maze generator:

• Blue: 15 x 15 x 15
• Orange: 7 x 7 x 7
• Purple: 17 x 15 x 11, with a path length of 4 (i.e. the generator jumps forwards by 4 spaces instead of 2 during the random walk)
• Green: 21 x 21 x 7

Somehow it's quite satisfying to watch it render, with the little squares gradually spiralling their way out from the centre in a hilbert curve - so I looked into how to create a glass texture, and how to setup volumetric rendering. It was not actually too difficult to do (the most challenging part was getting the lights in the right place with the right strength). Here's a trio of renders that show the iterative process to getting to the final image you see at the top of this post:

(Above: Some renders of some of the blue 15x15x15 above in the previous image with a glass texture. See the full size image [3.4 MiB])

From left to right:

1. My initial attempt using clear glass
2. Frosting the glass made it look better
3. Adding volumetric lighting makes it look way cooler!

I guess that you could give the same treatment to any STL file you like.

Anyway, the code for my maze generator can be found here on my private git server: sbrl/multimaze

The repository README contains instructions on how to use it. I won't duplicate that here, because it will probably change over time, and then this blog post would be out of date.

Before I go, I'll leave you with some animations of some mazes rotating. This whole experience of generating and rendering mazes has been really fun - it's quite far outside what I've been doing recently. I think I'd like to do some more of this in the future!

Update: I've re-rendered a new version at a lower quality. This should help mobile devices! The high-quality version can still be accessed via the links below.

(High-quality version: webm - vp9, ogv - ogg theora, mp4 - h264)

Language Review: Lua

I have recently tried writing a bit of Lua. I ported an implementation of a maze generation algorithm I came up with from Python to try it out:

-------------------------------------
-- Maze generation script
-------------------------------------
-- A test by @Starbeamrainbowlabs

---------------------------------------------
-- Intelligent table printing function
---------------------------------------------
-- From http://coronalabs.com/blog/2014/09/02/tutorial-printing-table-contents/

function print_r ( t )
    local print_r_cache={}
    local function sub_print_r(t,indent)
        if (print_r_cache[tostring(t)]) then
            print(indent.."*"..tostring(t))
        else
            print_r_cache[tostring(t)]=true
            if (type(t)=="table") then
                for pos,val in pairs(t) do
                    if (type(val)=="table") then
                        print(indent.."["..pos.."] => "..tostring(t).." {")
                        sub_print_r(val,indent..string.rep(" ",string.len(pos)+8))
                        print(indent..string.rep(" ",string.len(pos)+6).."}")
                    elseif (type(val)=="string") then
                        print(indent.."["..pos..'] => "'..val..'"')
                    else
                        print(indent.."["..pos.."] => "..tostring(val))
                    end
                end
            else
                print(indent..tostring(t))
            end
        end
    end
    if (type(t)=="table") then
        print(tostring(t).." {")
        sub_print_r(t,"  ")
        print("}")
    else
        sub_print_r(t,"  ")
    end
    print()
end

if arg[1] ~= nil then
        width = tonumber(arg[1])
else
        width = 36
end
if arg[2] ~= nil then
        height = tonumber(arg[2])
else
        height = 16
end

----------------------------------
-- function to print out the world
----------------------------------
function printspace(space, w, h)
        for y = 0, h, 1 do
                local line = ""
                for x = 0, w, 1 do
                        line = line .. space[y][x]
                end
                print(line)
        end
end

-- Initialise the world
start_time = os.clock()
math.randomseed(os.time()) -- seed the random number generator with the system clock
world = {}
for y = 0, height, 1 do
        world[y] = {}
        for x = 0, width, 1 do
                world[y][x] = "#"
        end
end

-- do a random walk to create pathways
nodes = {} -- the nodes left that we haven't investigated
curnode = 1 -- the node we are currently operating on
cx, cy = 1, 1 -- our current position
table.insert(nodes, { x = cx, y = cy })

world[cy][cx] = " "
while #nodes > 0 do
        io.write("Nodes left: " .. curnode .. "\r")
        --print("Nodes left: " .. #nodes)
        --print("Currently at (" .. cx .. ", " .. cy .. ")")

        local directions = "" -- the different directions we can move
        if cy - 2 > 0 and world[cy - 2][cx] == "#" then
                directions = directions .. "u"
        end
        if cy + 2 < height and world[cy + 2][cx] == "#" then
                directions = directions .. "d"
        end
        if cx - 2 > 0 and world[cy][cx - 2] == "#" then
                directions = directions .. "l"
        end
        if cx + 2 < width and world[cy][cx + 2] == "#" then
                directions = directions .. "r"
        end
        --print("radar output: '" .. directions .. "' (length: " .. #directions .. "), curnode: " .. curnode)
        if #directions > 0 then
                -- we still have somewhere that we can go
                --print("This node is not a dead end yet.")
                -- Everything starts at 1 in Lua...... ewwwwwwww
                local curdirnum = math.random(1, #directions)
                local curdir = string.sub(directions, curdirnum, curdirnum)
                if curdir == "u" then
                        world[cy - 1][cx] = " "
                        world[cy - 2][cx] = " "
                        cy = cy - 2
                elseif curdir == "d" then
                        world[cy + 1][cx] = " "
                        world[cy + 2][cx] = " "
                        cy = cy + 2
                elseif curdir == "l" then
                        world[cy][cx - 1] = " "
                        world[cy][cx - 2] = " "
                        cx = cx - 2
                elseif curdir == "r" then
                        world[cy][cx + 1] = " "
                        world[cy][cx + 2] = " "
                        cx = cx + 2
                end

                table.insert(nodes, { x = cx, y = cy })
        else
                --print("The node at " .. curnode .. " is a dead end.")
                table.remove(nodes, curnode)
                if #nodes > 0 then
                        --print("performing teleport.");
                        curnode = math.random(1, #nodes)
                        --print("New node: " .. curnode)
                        -- print("Nodes table: ")
                        -- print_r(nodes)
                        cx = nodes[curnode]["x"]
                        cy = nodes[curnode]["y"]
                else
                        --print("Maze generation complete, no teleportation necessary.")
                end
        end
        --printspace(world, width, height)
end

printspace(world, width, height)
end_time = os.clock()
print("Generation completed in " .. (end_time - start_time) .. "s.")

I originally wrote it in Python 3 (I might post about the game it is part of at some point). After trying Lua for a bit I thought it would be a good idea to write up a language review about it.

Firstly, it is really easy to get started with. I was able to compile Lua from source using my MinGW on my Windows 7 machine. Lua is also really lightweight (500kb in total!).

The problems begin when you start looking at Lua's equivalent of arrays: tables. I found that they feel clunky and outdated as there appears to be a lack of manipulation functions. Those that do exist (table.insert() and table.remove() use a lot more characters to use than the equivalent in other languages, such as Javascript (e.g. table.insert(tablename, "somestring") is 40 characters, compared to Javascript's tablename.push("somestring"), which is only 28 characters - a 30% saving!)

Lua's tables also start indexing from 1, not 0 - I found this to be a source of much confusion when I was experimenting with it.

The other thing I found annoying is that strings in Lua are immutable - which means that you can't change them once you have declared them. This can lead to lots of nasty performance issues in programs that do a lot of string manipulation if you are not very careful since every time you re-set a string variable's contents, you are creating more work for the garbage collector.

All in all, Lua looks like an interesting language to learn for fun - you should definitely check it out, if only to see how odd a language it is. I love how lightweight it is. I also managed to build the Lua interpreter from source too, which is always a plus. I can't see myself using it for any real project any time soon though - it just feels too clunky to work with for my purposes, although this is probably more down to my lack of experience and the other languages that I know than the design of the language itself.

Edit April 2020: Fixed a small bug in the code, so it should be slightly faster now.