GDMC 2018 Competition - a participant's perspective

Post date: Nov 16, 2018 1:44:59 AM

2018 has been a crazy year for Minecraft projects. Microsoft and Mojang seem to have hit their groove, and waves of gaming platform integration and feature releases are washing through the map making and player community.

Unexpectedly, at the start of the year, New York University burst on the scene with a community challenge to create a practical village in Minecraft worlds through the use of procedural generation or artificial intelligence methods. "GDMC" stands for "Generative Design in MineCraft", in case you were wondering. You can read all about the challenge here: http://gendesignmc.engineering.nyu.edu/

My response to this was: "this is great! I want in!"

I have been an avid follower of all things computer-generative ever since I first picked up James Gleick's excellent book "Chaos!" as a teenager. The prospect for computing to create new stuff that's never been seen before is exciting, and the tools and techniques to do it are fascinating to study. The other major influence in my interest is a quirky novel about 'computer contact with a 2D world' called "The Planiverse" by A. K. Dewdney. In this story, a species of flatworld creatures exists and we join one of them on their journey through their world and beyond.

I thought about approaches for pretty much the entire competition time, then jumped in to write some code just as the deadline approached (FYI this wasn't the best approach). In my defense, there's a lot of projects underway all the time so prioritisation of the fun stuff (like this competition) suffers.

Here is a short description of what I did up until the point of submission (spoiler: I made it on time). If you're interested in procedural methods, Minecraft content creation, and Python programming then read on. If you just want to see how things worked out, check out the GDMC wrap-up presentation, and my final submission.

Thoughts on approach

From my reading of the competition, the challenge was to respond to an arbitrary section of landscape with an in-game village that has in-game playability characteristics. The framework provided was a custom version of the popular MCEdit Unified tool which I often liken to a CAD package for Minecraft worlds. It has scripting support for batch-style jobs that modify the Minecraft world. It also has an interactive interface for touch-ups and real-time ad-hoc editing.

MCEdit has a good capability for working with the 1 metre x 1 metre blocks that make up a world. It has low-level APIs for working with the hidden meta-data, called NBT, that describes chests and their contents, as well as ingame characters like Villagers. MCEdit also provides a way to work with aggregates of blocks and NBT through the use of 'schematics'. Schematics are pre-build structures that can be placed around the landscape in an editing session.

The structure of a Minecraft world, adapted from the Minecon Earth 2018 MCEdit Community Panel

The core problem in this challenge is attaining a holistic understanding of the world so that decisions can be made about designing where to place things. The supplied framework for the first challenge leaves it up to the participant to build an appropriate framework to respond to the challenge. The evaluation is based on the results, however, so whatever ideas I had as to how to apply holistic thinking to the problem were not really important to the competition ranking. Still - that's where my interest lies, so that's what I'm going to write about in this article.

Artificial Intelligence is a field that involves a lot of choice of methods to get machines acting in a way where decisions can be made. Not all methods are appropriate for all tasks. Consider Machine Learning, which is the discipline of generating statistical models that support the evaluation and production of assets by examining features of things that are 'like' what we're after while also avoiding features that are not. Choosing a machine learning approach can be complicated by a lack of available large and good training sets, for example. You can see some of the problems with machine learning against small training sets in this example using Minecraft's skin system here:

Machine learning with Minecraft skins

Traditional approaches to design problems in computing involve evaluating criteria and then responding with a procedure that takes input to create a result. Some systems are iterative and involve repeated application of 'rules' to generate an outcome. My work on this challenge was 'procedural' and not-iterative in nature, and not statistical/learning based. My approach was to evaluate the landscape and then build something in response to what was found.

The first pass: "Find places to build out"

I decided that regardless of whatever I would eventually build, it would be important to have an understanding of the characteristics of the landscape at different scales so I could make decisions about how to respond to it. If there was a lake of lava then I'd be well-placed to steer clear of it with a flammable wooden house.

To do this, I established a height map by scanning from the sky to the surface of the landscape and then used a set of grid systems across the heightmap to work out what the 'roughness' of the terrain was, among other things like what materials were present.

The height map is a 2D row/column structure of height values generated through a brute-force looping process as shown:

def getMyHeightMap(level, box, options):

'''

Iterate through space and explore it

'''

print "INFO: Starting to getMyHeightMap()"

HM = [] # A set of rows

for z in xrange(box.minz,box.maxz):

COL = []

for x in xrange(box.minx,box.maxx):

(theBlock,theBlockData) = (-1,-1)

heightHere = -1 # default to 'invalid'/void

y = box.maxy

while y >= box.miny: # Examine each 1x1 line, top down

y -= 1

theBlock = level.blockAt(x,y,z)

if theBlock not in NONSURFACE:

theBlockData = level.blockDataAt(x,y,z)

heightHere = y

y = box.miny-1 # or... break

COL.append((heightHere,(theBlock,theBlockData)))

HM.append(COL) # Adding the current column of values to the set

if DEBUG: print "Height Map:\n",HM

print "INFO: Completed getMyHeightMap()"

return HM

Once the landscape height was profiled, a series of doubling grids from size 4x4 and up were applied to it and each cell was examined to determine the roughness and the materials present on the surface:

def generateAggregateHeightMaps(HM):

'''

Gathers a set of info about regions together

'''

print "INFO: Starting to generateAggregateHeightMaps()"

DEPTH = len(HM)

# print HM

WIDTH = len(HM[0])

AHM = []

DIM = 4

keepGoing = True

while keepGoing:

if DIM > DEPTH or DIM > WIDTH:

keepGoing = False

else:

CZ = 0

ROWS = []

while (CZ+DIM) <= DEPTH:

COL = []

CX = 0

while (CX+DIM) <= WIDTH:

heightSum = 0

heightMin = 999999  # Invalid

heightMax = -999999 # Invalid

analyseBlocks = {} # Analyse Block types

for dz in xrange(0,DIM):

for dx in xrange(0,DIM):

HMRow = HM[CZ+dz]

(heightHere,(bID,bData)) = HMRow[CX+dx]

if (bID,bData) in analyseBlocks: # Analyse Block types

analyseBlocks[(bID,bData)] = analyseBlocks[(bID,bData)]+1 # Analyse Block types

else: # Analyse Block types

analyseBlocks[(bID,bData)] = 1 # Analyse Block types

heightSum += heightHere

if heightHere < heightMin: heightMin = heightHere

if heightHere > heightMax: heightMax = heightHere

heightAvg = heightSum/(DIM**2)

COL.append(((CX,CZ),(heightAvg,heightSum,heightMin,heightMax,heightMax-heightMin),analyseBlocks)) # Sample tuple - including variance

#print COL

CX += DIM

ROWS.append(COL)

CZ += DIM

AHM.append((DIM,ROWS))

DIM += 1 # DIM*2 # Or otherwise double it

if DEBUG: print "Aggregate Height Maps:\n",AHM

print "INFO: Completed generateAggregateHeightMaps()"

return AHM

Once there was some landscape information to examine in the cells, placement of structures to conform to the landscape properties was (in theory) a matching exercise of generating candidate locations and selecting one for each building.

This approach supports individual structure placement, but does not deal with what the structure should be and how it should participate in the village as a whole. This approach was explored by placing 'marker tape' box outlines on the plots that would be selected to build on based on the 'flatness' of the terrain cell, as determined by the max and min heights within the cell.

Terrain profiles as cells at different scales

The code for this is in abode_v2.py.

The drawback of this approach is that it doesn't offer any clues as to whether the terrain between selected plots is passable (or can be easily adjusted to be passable) for roads and pathways, making it unclear whether the resultant village would 'look' right. At a high level, my plan for generating a village was:

• 1. generate networks representing buildings in the settlement.

  2. the nodes are areas/rooms, each with a local generator

  3. merge the networks into a settlement network

  4. position the nodes on the landscape, using rules for how close areas should be

  5. Render.

Note that in thinking item 4 was the more difficult and interesting task, I focussed exclusively on understanding it and solving it first.

Ultimately I did not leave enough time to fully explore this idea, except it did drive the next revised approach.

The second pass: "Gently sloping pathways"

If I was going to tease out information from the landscape about how areas were connected, I figured the height map was probably a good place to start because by examining the way that block heights differ I could work out if the slope of the terrain was too aggressive to walk and build across. The other useful thing about a height map is that it is two-dimensional and so, in theory, the connectivity between points on the map can be determined using standard well-understood pathing methods. I used PyGame as the library to work with image representations of the landscape because MCEdit Unified, which is the supplied framework, bundles it in for its own use:

Height map (left) and derived edge map (right) showing connected areas of gentle sloped terrain

Edge detection was done simply by calculating whether the difference between two heights was excessive, which for a Minecraft player is the unjumpable height difference of 2 blocks, and also by projecting this difference out far enough that there is sufficient area marked as 'near the edges' that would allow a building to be safely placed anywhere there was a 'flat' pixel in the edge map:

def findEdges(img):

width = img.get_width()

height = img.get_height()

delta = 2 # This is the number to change to adjust the sensitivity of edge detection. Decrease to increase the possible plot locations to flatter zones.

deltaHalf = delta >> 1

imgB = pygame.Surface((width-delta, height-delta),0,8)

pix = pygame.PixelArray(img)

pixB = pygame.PixelArray(imgB)

for x in xrange(deltaHalf,width-deltaHalf):

for y in xrange(deltaHalf,height-deltaHalf):

avgDelta = 0

vr = pix[x,y]

count = 0

for dx in xrange(-deltaHalf,deltaHalf+1):

for dy in xrange(-deltaHalf,deltaHalf+1):

count += 1

if not (dx == 0 and dy == 0):

nr = pix[x+dx,y+dy]

# print vr,nr

avgDelta = avgDelta + int(abs(vr-nr))

avgDelta = avgDelta / count

# pixB[x-1,y-1] = avgDelta

if avgDelta != 0:

pixB[x-delta,y-delta] = 255

img.unlock()

imgB.unlock()

return imgB

As for buildings, finding a candidate place to build on the edge map then became a problem of looking for areas of the required size that did not have an edge marked as running through it. This was simplified by marking areas close to to edge as being non-flat so they would not be selected as the origin of a build location.

To simplify selection of building sites (black, right), the edge detection (white, right) is expanded to prevent the building dimensions falling close to an edge

(Note: The submitted code for building placement incorrectly places buildings from the corner. In subsequent code revisions the selected build location should be the centre of the building plot)

The mad rush to finish

By this time I was quite please with the ideas and simplicity of implementation, particularly since image processing methods are a mainstay of 'real' AI projects. I felt this was a reasonably good way to find legal places to place buildings.

With scant hours until submission time I made the call that I'd be back for round 2, so solving this placement problem would be good enough for the first competition. I turned to a building generator I had lying around from earlier work with the Blockworks team on creating the greater London of the past and re-used my building generator by plugging it in once a suitable plot for building on was selected.

Houses are randomly generated

As a result my submission was limited to buildings placed according to the flatness of the terrain within the supplied landscape area. This is suggestive of a village in that there's more than one dwelling, but if I lived there I'd be looking for a bit more supporting infrastructure!

What came next

The competition has become a catalyst for developing a few of the ideas further. In particular, the theme of generation at different scales is an area I have continued to explore using a variety of techniques to generate large scale structures:

Modular procedurally generated houses

Modern city hierarchical procedural generation by the author in Minecraft (Building and project by @NitricConcepts)

Hierarchical procedural generation framework adapted for space diorama

Hierarchical procedural generation framework adapted for clouds

Final thoughts

I am grateful to the GDMC team for hosting and co-ordinating this competition as good governance and community management is always the hardest part of any project.

I believe that the next round of participants will benefit from being able to select from already existing frameworks that solve some of the more time-consuming problems. If a competition participant can select from a library of functions and then string them together to do the tedious grunt work then they can focus on solving the challenge in new and creative ways!