Random Floorplan Generation
Original Publication Date: 2002-Oct-11
Included in the Prior Art Database: 2003-Jun-21
Disclosed is an algorithm which can be used to extend the life of computer games by generating random floorplans for buildings or other areas of play. Most random maps in games are constructed by randomly placing a small set of fixed-sized, fixed-content tiles in a regular grid. Use of these tiles typically requires a fixed placement of entry and exit points on each tile to allow the tiles to be connected. This is a more robust algorithm which greatly enhances the randomness of the floorplans with a minimal increase of complexity for the game designer. The algorithm uses a set of stretchable rectangular tiles, or rooms, which can be can be entered and exited from any location around the perimeter of each room that is not occupied by blocking terrain. The algorithm begins from a single room and expands by attaching tiles to randomly selected points on the perimeter of the current set of rooms. Each new room is first stretched to a randomly selected size, possibly limited by available space, then moved to a randomly selected orientation relative to the selected attachment point. Stretching consists of adding empty rows or columns to a room definition. An example of a room orientation is that a 3x3 room attached to the north side of an existing room could be placed in any of the three positions where the attachment point is one of the 3 locations in the southern most row of the new room. Stretching of any room can be enabled or disabled for any direction to allow specific interior features to be generated along interior walls. Connectivity to other rooms is guaranteed by simply requiring that all non-blocked locations within a room are accessible from all other non-blocked locations. Thus, the algorithm guarantees that all interior locations are accessible from all other interior locations by exactly one sequence of rooms.