Chris Conlan

Financial Data Scientist

  • About
  • Blog
    • Business Management
    • Programming with Python
    • Programming with R
    • Automated Trading
    • 3D Technology and Virtual Reality
  • Books
    • The Financial Data Playbook
    • Fast Python
    • Algorithmic Trading with Python
    • The Blender Python API
    • Automated Trading with R
  • Snippets

Procedurally Generating a Maze in Blender Python

July 23, 2017 By Chris Conlan 1 Comment

Everyone knows I am a fan of Blender Python. It’s really fun. This post will discuss a brief script for procedurally generating a maze in Blender Python. This may be the boilerplate code for a larger routine that produces massive randomly-generated landscapes.

In this brief code, we will run into some fairly advanced concepts in Blender Python, particularly 3D data structures. For those interested in a more involved discussion, refer to Chapters 3 and 7 of my new book, The Blender Python API.

Outline

We will generate a maze in Blender Python using the following steps…

  1. Create a large plane, partitioned in NxN squares at Z=0
  2. Set our starting point to the bottom left corner of the plane
  3. Move in a random direction, forward, backward, left, or right
  4. If the tile we are “standing” on is at Z=0, depress it (or extrude it down) by H units
  5. Repeat steps 3 and 4 until we have cut a path through the plane and are “standing” B units away from the maze

With the right parameters, this should leave us with a cool maze. It will help to add another parameter that specifies the probability of a forward step versus a backward step, as we will see. Flipping some parameters around, we should be able to adjust it to make catwalks and multi-level structures.

Tell me this wouldn’t make a good video game map for 1v1’s.

Important Functions

We will discuss some of the important Blender functions and custom utilities we will use in this code.

Selection by Location

This is a feature I believe should be native to Blender. It involves selecting vertices, edges, or faces of a Blender objects according to their location in 3D space. The version we will discuss here is for selecting faces. Writing this algorithm requires a good understanding of Blender’s internal data structures.

import bpy
import bmesh

# Check if an (X, Y, Z) coordinate is within a rectangular prism
# defined by its lowest and highest corners
def in_bbox(lbound, ubound, v, buffer = 0.0001):
    return all([lbound[i] - buffer <= v[i] <= ubound[i] + buffer for i in range(3)])

# Select faces that are within the bounding box
def select_by_loc(lbound = (0, 0, 0), ubound = (0, 0, 0), additive = False):
    
    # Set selection mode to FACE
    bpy.ops.mesh.select_mode(type = 'FACE')   
    
    # Grab the transformation matrix
    world = bpy.context.object.matrix_world
    
    # Instantiate a bmesh object and ensure lookup table
    bm = bmesh.from_edit_mesh(bpy.context.object.data)
    bm.faces.ensure_lookup_table()
    
    # Initialize list of vertices and list of parts to be selected
    verts_by_face = []
    to_select = []
    
    # Organize sets of verticies by the face that contains them
    for face in bm.faces:
        this_faces_verts = []
        for vert in face.verts:
            this_faces_verts.append((world * vert.co).to_tuple())
        verts_by_face.append(this_faces_verts)
            
    # Check if the faces is bounded by the bounding box
    # The face is bounded if all of its vertices are
    for this_faces_verts in verts_by_face:
        are_bounded = []
        for vert in this_faces_verts:
            are_bounded.append(in_bbox(lbound, ubound, vert))
        to_select.append(all(are_bounded))
    
    # Select all faces that are bounded, retaining previously selections
    for faceObj, select in zip(bm.faces, to_select):
        faceObj.select |= select  

The above select_by_loc() function can be significantly shortened using list comprehensions like so…

def select_by_loc(lbound = (0, 0, 0), ubound = (0, 0, 0), additive = False):
    
    # Set selection mode to FACE
    bpy.ops.mesh.select_mode(type = 'FACE')   
    
    # Grab the transformation matrix
    world = bpy.context.object.matrix_world
    
    # Instantiate a bmesh object and ensure lookup table
    bm = bmesh.from_edit_mesh(bpy.context.object.data)
    bm.faces.ensure_lookup_table()
    
    # Initialize list of vertices and list of parts to be selected
    verts_by_face = []
    to_select = []
    
    [verts_by_face.append([(world * v.co).to_tuple() for v in f.verts]) for f in bm.faces]        
    [to_select.append(all(in_bbox(lbound, ubound, v) for v in f)) for f in verts_by_face] 

    # Select all faces that are bounded, retaining previously selections
    for faceObj, select in zip(bm.faces, to_select):
        faceObj.select |= select  

The lbound and ubound parameters specify a rectangular prism in 3D space, in which all of the faces will be selected. For example, a cube of length 2 with center at (0, 0, 0) would be specified as lbound=(-1, -1, -1) and ubound=(1, 1, 1). This function will only select, not deselect faces. Faces can be deselected first by setting all faceObj.select to False before the last loop.

Extrusion

Extrusion is Blender’s word for pulling a vertex, edge, or face outward while keeping it attached to the object. Extrusion can normally be accessed as an Edit Mode function, but we will access through Blender Python with the bpy.ops.mesh.extrude_region_move() function.

Subdivision

Blender has a handy function for splitting up planes with an arbitrary number of sides into more similarly-shaped planes. This does not change the shape of the plane, but allows us to create a grid out of plane consisting of a single face. We will access this through the bpy.ops.mesh.subdivide() function.

Create the Maze

Using the above functions and outline, we can create mazes and catwalks with the following code…

import bpy
import bmesh

if __name__ == '__main__':
    
    import random
    
    N = maze_size = 25
    H = maze_height = 2.5
    B = buffer = 5
    FP = forward_probability = 0.6
    
    
    bpy.ops.mesh.primitive_plane_add(radius = maze_size/2, location = (0, 0, 0))
    
    bpy.ops.object.mode_set(mode = 'EDIT')
    bpy.ops.mesh.subdivide(number_cuts = maze_size - 1)
    bpy.ops.mesh.select_all(action = 'DESELECT')
    
    v = standing_location = [-maze_size/2, -maze_size/2]
    b = boundary = [-maze_size/2 - buffer, maze_size/2 + buffer]

    while b[0] <= v[0] <= b[1] and b[0] <= v[1] <= b[1]:
        
        # Select a face if we are "standing on it"
        select_by_loc( lbound = (v[0] - 0.5, v[1] - 0.5, -0.1),
                       ubound = (v[0] + 1.5, v[1] + 1.5, 0.1) )
                     
        # Returns 0 or 1 corresponding to X and Y  
        r_index = random.randint(0,1)
        
        # Returns -1 or 1 corresponding to forward and backward
        r_direction = (int(random.random() > 1 - FP) * 2) - 1
        
        # Adjust standing locaiton
        v[r_index] += r_direction
        
    # Finally, pull all the selected faces down
    bpy.ops.mesh.select_all(action='INVERT')
    bpy.ops.mesh.extrude_region_move(TRANSFORM_OT_translate=
        {"value":(0,0,H),
         "constraint_axis":(False,False,True)}
        )

Make sure the above declaration of in_bbox() and select_by_loc() are in the file or loaded through a separate module.

Messing with the Paramters

Setting the forward probability closer to 0.50 creates dense areas.
Setting H as negative and removing the “invert selection” step generates catwalks.
Repeating the script without the plane-creation step can produce cool results.

Filed Under: 3D Technology and Virtual Reality, Programming with Python

Comments

  1. Shawn Irwin says

    January 6, 2019 at 10:24 pm

    The thought occurred to me that it may be more efficient to extrude horizontally, rather than vertically, as you would have less geometry to deal with . . . . I guess the biggest trick would be coming up with the algorithm that would handle both passageways and rooms, although I would like to go even further than that . . . . I’d like to create bridges over bottomless pits, and round rooms with semi-circles at the top. I have done a level creator before, but it was pretty simple, and not very efficient. Generally, it created the passageways, dropped a marker while doing so to add rooms. While extruding horizontally may be a bit more complex, I think it would be more efficient.

    Reply

Leave a Reply Cancel reply

Fast Python: Master the Basics to Write Faster Code

Fast Python: Master the Basics to Write Faster Code

Available for purchase at Amazon.com.

Featured Posts: Python Programming

Pulling All Sorts of Financial Data in Python [Updated for 2021]

When to Use Heap Sort to Speed Up your Python Code

Fastest Way to Flatten a List in Python

Topics

  • 3D Technology and Virtual Reality (8)
  • Automated Trading (9)
  • Business Management (9)
  • Chris Conlan Blog (5)
  • Computer Vision (2)
  • Programming with Python (16)
  • Programming with R (6)
  • Snippets (8)
  • Email
  • LinkedIn
  • RSS
  • YouTube

Copyright © 2022 · Enterprise Pro Theme On Log in