Starbeamrainbowlabs

Stardust
Blog


Archive


Mailing List Articles Atom Feed Comments Atom Feed Twitter Reddit Facebook

Tag Cloud

3d 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blog bookmarklet booting bug hunting c sharp c++ challenge chrome os cluster code codepen coding conundrums coding conundrums evolved command line compilers compiling compression containerisation css dailyprogrammer data analysis debugging demystification distributed computing documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs learning library linux lora low level lua maintenance manjaro network networking nibriboard node.js operating systems own your code pepperminty wiki performance phd photos php pixelbot portable privacy problem solving programming problems project projects prolog protocol protocols pseudo 3d python reddit redis reference releases rendering resource review rust searching secrets security series list server software sorting source code control statistics storage svg talks technical terminal textures thoughts three thing game three.js tool tutorial twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 xmpp xslt

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.

An awesome render of a 3D maze done in Blender - see below for an explanation.

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).

A screenshot of OpenSCAD showing a generated maze.

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.

A divider made up of orange renders of a small 7x7x7 maze rotating

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 with 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

The Lua logo

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.

Art by Mythdael