A downloadable tool

The Map Generator using binary space partitioning to divide up a map. After making a collection of rooms, it then chooses an entrance and places doors so that certain rooms act as nodes to the rooms around it. The source files are all in the zip and can be executing through either the .jar file or the nodeBasedSpacePartition.java file.

Arguments can be passes into either file in the format int int boolean. The first number will be the map width, second number will be the height, and the boolean (if true) will display the nodes and endpoints in different colors. Defaults are 25 25 false.

Minimum room size, size of each square, and the connection chances can be changed in Room.java, MapJPanel.java, and nodeBasedSpacePartition.java respectively.

////////////////////////////////////////////////////////////////////////////////////////////////////////////

The following is an extremely detailed description of how this generator chooses to place doors in the fashion that it does. It is really not necessary to read in order to use the tool.

////////////////////////////////////////////////////////////////////////////////////////////////////////////

Binary Space Partitioning

The map starts as a single room that spans the entire map as Room 000.

This room is then cut up vertically into Rooms 000, and 001.

The map will then cut up rooms into two rooms, neither which will be smaller than the required minimum room width or height. If any doors have been placed, a wall will not appear and isolate that door. This process continues until a random number of cuts have been completed. Given a minimum width and height of 3, a final result appears as such:

////////////////////////////////////////////////////////////////////////////////////////////////////////////

Placing Doors

First, a random border room is choosen as the entrance, which is marked in red. All nearby rooms to the entrance immediately become nodes, marked in blue. Then each node will randomly connect or not to the nearby rooms. In the following image, Room 022 has been choosen as the entrance and connected to Rooms 016, 017, 019, and 023; Room 016 has connected to Room 006 and a door has been placed between any connecting rooms.

Each room around a node has a chance to become a node or an endpoint depending on a random number and a chance multipled to the area of the room so that larger rooms are more likely to become nodes. In the following image, Rooms 017, 016, 019, and 023 have connected to all surrounding rooms but Room 015 has be selected to be another node.

This process continues until the nodes eventually close themselves off like in the following image.

In this case, the generator chooses a random unset room that is next to the one of the endpoints, marked in gray. In the following image, Room 004 has been choosen as a new node.

The previous process continues until all rooms in a map have been set and the map is completed.

This is also a chance of nodes to connect to nearby endpoints in order to reduce the amount of backtracking that a player would be forced to do. Furthermore, a number of doors maybe be added the end to further redure the backtracking. In the following image, Rooms 001 and 005 have connected.

These doors are far more useful on larger maps. There are a few more random chances that are not displayed in the previous example but appear on larger maps.

For instance, there is a chance that a node will not connect to a nearby room. In the following image. Room 265 and Room 255 are not connected.

As mentioned eariler a number of doors are placed at the end, in order to reduce the amount of backtracking. In the following images, a door has been placed between Rooms 403 and 419 - without that door a player would have to travel roughly around the given images to get to the other side.

Before:

After:

////////////////////////////////////////////////////////////////////////////////////////////////////////////

Notes

This generator has great variance in terms of the quality of the generated content. Beyond backtracking (Note: Backtracking evaluation planned), some nodes come out really well and in other cases, very poor. When evaluation is complete, there will be more notes about the variance of quality.

Good: