Procedural content generation: map construction via binary space partitioning (a.k.a. building a Rogue-like map)

There are times that I question my market value and future job prospects as a life science Ph.D. (or whether I'll be able to finish the Ph.D. at all). When the Llama feels like this, she studies for Actuarial exams. I pursue something equally lucrative.

Video games.

These past few weeks have been spent preparing for our preliminary exams. The concomitant feelings of inadequacy led me to want to procedurally generate video game content. Seeing as I don't know the first thing about procedural content generation (PCG), I figured I'd make some maps. And make some maps I did.

Who wants to adventure through these bad boys!?

The method I used is based on binary space partitioning, and all I really did was implement the algorithm described by this book in chapter 3 (link to .pdf).

I implemented it in Python because I figured it'd be faster to prototype in than C++. I'm not sure that this was actually the case. I couldn't find a tree data structure and ended up implementing one (...and it's a bit of a mess). I also really wanted to declare a static variable to keep track of things during the recursive tree searches, but I don't think such a thing exists in Python; I end up passing lists around to get around this which seems pretty weird, but evidently lists are mutable in this case and booleans or integers are not? Anywho, it works for the most part. The function that controls the overall flow is below, and you can find the entire script on my GitHub here. I'm pretty sure there are some bugs crawling around still, but it seems to work.

def generateBSPMap():
    # 1: start with the entire area (root node of the BSP tree)
    rootNodeBox = Box((0, 0), 256, 256) #The dimensions should be evenly divisible by 2
    rootNode = AreaNode("root", defaultdict(AreaNode), rootNodeBox)
    tree = AreaTree(rootNode)
    firstPartitionNames = ("A", "B")
    # 2: divide the area along a horizontal or vertical line
    tree.partitionNode("root", firstPartitionNames)
    currentArea = rootNodeBox.getArea()
    currentPartitionNames = firstPartitionNames
    MAGICMINIMUMAREA = (0.03125) * 256 * 256
    #MAGICMINIMUMAREA = (0.10) * 256 * 256
    
    while (currentArea > MAGICMINIMUMAREA):
        # 3: select one of the two new partition cells
        chosenIndex = random.choice([0, 1])
        chosenPartition = currentPartitionNames[chosenIndex]    
        if (chosenIndex == 0):    
            otherPartition = currentPartitionNames[1]
        else:
            otherPartition = currentPartitionNames[0]
        
        #4: if this cell is bigger than the minimal acceptable size:
        print("Chosen partition " + chosenPartition + " has node area " + str(tree.getNodeArea(chosenPartition)))

        if (tree.getNodeArea(chosenPartition) > MAGICMINIMUMAREA):
            #5: go to step 2 (using this cell as the area to be divided)
            newPartitionNames = (chosenPartition + "_0", chosenPartition + "_1")
            tree.partitionNode(chosenPartition, newPartitionNames)
        
        #6: select the other partition cell, and go to step 4
        if (tree.getNodeArea(otherPartition) > MAGICMINIMUMAREA):
            newPartitionNames = (otherPartition + "_0", otherPartition + "_1")
            tree.partitionNode(otherPartition, newPartitionNames)
        
        currentArea = min([tree.getNodeArea(chosenPartition), tree.getNodeArea(otherPartition)])

        partitionNameList = []
        tree.getListOfLeafPairs(partitionNameList)
        currentPartitionNames = random.choice(partitionNameList)
        
    #7: for every partition cell:
    #8: create a room within the cell by randomly
    #   choosing two points (top left and bottom right)
    #   within its boundaries
    li_areasAreConnected = []
    terminationIterator = 0
    while (li_areasAreConnected == [False] or li_areasAreConnected == []):     
        tree.resetSubAreas()        
        tree.constructSubAreas()

        #9: starting from the lowest layers, draw corridors to connect
        #   rooms in the nodes of the BSP tree with children of the same
        #   parent
        #10:repeat 9 until the children of the root node are connected
        li_areasAreConnected = []
        tree.connectSubAreas(li_areasAreConnected)
        terminationIterator += 1
        if (terminationIterator > 50):
            print("Attempted too many iterations. Terminating.")
            print(li_areasAreConnected)
            break

    if (li_areasAreConnected == [True]):
        print(tree)
        tree.showAreaTree()

Run that thing and booooooooom.

I also used an agent-based approach in part 2 here.