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

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.

## No comments:

## Post a Comment