Procedural Building Placement Design

Introduction

Given Atlantis is supposed to be a glorious pre-existing city, it was important to do it justice when placing buildings procedurally. Procedural placement was chosen over static placement, to continue the theme of variability between different playthroughs - as the map and resource collection are procedurally generated. This will hopefully give the game some replayability, and require the player to be more adaptive between subsequent games. Although the placement of the buildings is dynamic, the number to place, and the types of buildings are static, to allow the game to be balanced (as having 5 barracks in one game, and one in another would be unfair)

Motivation

The algorithm required to generate the layout of the city was required to be quite rigid, as just spawning buildings randomly all over the place to fit would be too chaotic and unordered for a city with the pedigree of Atlantis. It was deemed essential that while building placement would be different across each game, the player would still feel as if they were being presented with an ordered city, and not just a haphazard collection of buildings. These constraints informed the construction of both the algorithm and the supporting classes for the BuildingGenerator (the class which handles the procedural placement of buildings).

Helper classes

Building

This is a simple class containing the basic information of a building as it is to be placed in game. It includes the name, width, height and tile that the building is placed at.

CityRow

A city row represents a row of buildings within the city (so that the city can be arranged into a grid formation - as would be expected from an ordered city). A CityRow features a list of buildings, which are placed into ordered positions relative to the city row. It provides functions to centre the buildings within a row (run at the end of generation), and tracks how much space is left, to know whether or not a building may fit.

BuildingSpecification

This class tracks the number of buildings of each building type need to be placed, and how many have been placed. It interfaces with the BuildingGenerator to inform it when to stop placing buildings of a given type

Algorithm

1. The BuildingGenerator loads in a list of BuildingSpecification from configs/buildingSpecification.json, to know how many buildings to place of each building type
2. A list of CityRows are allocated, the number of which is based on the height of the tallest building, to have the worst case (all buildings of same height, which is the max height) accounted for
3. Randomly choose a BuildingSpecification from the list - this building is to be placed
4. Attempt to place the Building in the CityRow with the lowest capacity (if there is a tie, it will choose deterministically in order of index)
5. If no placements could be found, re-start generation if it has tried less than 5 times, or throw an exception if no placement could be found in 5 generations
6. If a placement is found, update the coordinate placement of that building
7. If this was the last building required of that building type, remove this BuildingSpecification from the BuildingSpecification list
8. Repeat 3-7 until no buildings remain in the BuildingSpecification list

Testing

A two-pronged approach to testing was executed, as unit tests could not fully cover the breadth of the algorithm and its process

Unit Testing

Unit tests that were devised for BuildingGenerator and its helper classes cover the following:

• Each class returns valid output (i.e. getter/setter functions)
• Specific functions (such as clearing a city row, or reducing the number of buildings in a BuildingSpecification) are validated
• BuildingGenerator, when run through significant iterations (50 in this revision), will consistently place buildings within valid locations within the city

This demonstrates that all classes are performing their intended functionality, and it is exceedingly unlikely that any case in the random generation isn't caught where the buildings cannot be adequately placed

Experimental Testing

The function's output was also experimentally tested, through the implementation of a visual debugging code, which produces the following output: