Map Generation

[CromulentEntity]

Currently the map is static. The intention is to have it generate a random layout each time.

[CromulentEntity]

My original plan for this was to make use of a Maze Generation Algorithm in order to generate a random map. After giving it some more thought, this clashes with the current design philosophy of the Map object.

Currently, the map is a 2d array. Each point in the array, which I call a tile, is either a Room or a Rock. Rooms allow traversal to and from any other adjacent room, as long as both are unlocked. Rocks completely block player movement.

The Maze Generation Algorithms seem to make more sense as follows. Every single tile is a Room. Each Room has 4 Doors or Walls. For the entire map, all walls start in-tact/doors start locked. As the algorithm carves out paths, we mark walls as demolished or doors as unlocked. In doing this, each room will end up with a random combination of ways the player can enter and leave.

If we were to try and place Rocks between the rooms where the algorithm has deemed there to be walls/locked doors, we would end up with a maze that is bigger than the dimensions supplied by the user. That's not acceptable.

[CromulentEntity]

I built a map/maze generator years ago through trial and error, without researching an algorithm to base it on. From what I remember, that algorithm would not fill the entire X*Y grid with rooms. There would be many empty "tiles" that were functionally the same as the "Rocks" I have defined now. It may also have given each room 4 doors, and unlocked those along the paths generated by the algorithm. Kind of a hybrid between the currently implemented approach in this game, and the approach which I theorized in the above comment to be the proper way to implement maze generation in a tile system.

[CromulentEntity]

My intent is to dig out the old algorithm, pick apart how it worked, and then decide how I would like to proceed here. That may be redesigning the tile system in the game, or it may be finding a different sort of algorithm to adopt to the current tile system.

[CromulentEntity]

For future reference, good articles on Maze Generation algorithms:

• General Overview
• Recursive Backtracking
• Hunt & Kill
• Growing Tree

[CromulentEntity]

Very large generation example from old map generator.

[CromulentEntity]

This old generator worked as follows:

1. Initialized a 2D String array with textural representations of various rooms. S for Start, placed at 0, 0. F for Finish, placed at X length, Y length. All other points were set to void space, represented above by "■" symbols.
2. A Linked List is initialized containing int[] arrays, which are X, Y coordinate pairs. Coordinates 0, 0 are added as the start of the path.
3. While the algorithm has not found the finish room, if the generator has not found new valid coordinate set for the next room in the path in a while, back up one room.
4. Otherwise, if there have been over X number of failed attempts to find the finish line since generation began, start the whole process over.
5. Otherwise, chose a random direction out of North, South, East, and West, and check to see if the coordinates in that direction are either A) off the map, B) neighbored by more cells than the one you are coming from (to prevent circles, though they are still present in the above image??), C) the finish room. If none of the above are true, place a new room. If A or B are true, increment the failure count and try again. If C is true, you have found the finish line and generation is complete.

It would then take the following optional steps:

6. Generate side paths. These paths ultimately do not lead to the finish line, and instead just prevent the map from being a linear corridor. The program will make a total of 25 attempts at creating new rooms when it decides to create a side path, meaning each side path is 25 rooms or less in length. It looks like each point on the original path has a 1 in 5 chance of spawning a branching path off of it, but the image above appears to show far fewer branches in practice. Note: I think something in this section of the code is broken and creating the circular paths we see above.
7. Replicate the path in a 2D array of Room items. The Room array is initialized to have the same dimensions as the map. The starting room, finish room, and all rooms in the path are created at their appropriate coordinates in the grid. Each Room contains Door objects which themselves contain references to its neighboring Rooms.
8. Indexes in the 2D Room array that are not initialized as part of a path are left as whatever the default value of array objects in Java might be. (void?)

Implementation Notes:

An important note about this implementation. For whatever reason, there are 3 separate "copies" of the map involved in this process. There is the 2D String array, mentioned in step one. There is the Linked List of int[] x,y pairs from step two. And finally, there is a 2D array of Room objects from step 7. Why it is this way I cannot fathom.

The 2D String Array is updated whenever a new room is created, and is used to check if a potential new room has too many neighbors. If more than one of the cells immediately above or to the side of the queried cell is set to a character that represents a room, the new room is not created.

The int[] Linked List is used to establish easy back and forth movement along the path when creating new rooms and removing those that result in dead ends.

The 2D Room array is actually used by the game for most functions outside of printing the map, for which it uses the String array representation instead. Movement is based entirely on what doors each room contains from the generation process. These doors reference other Room objects. The int[] linked list is effectively discarded after the map is generated.

Side paths are generated the same way the main one is, although the implementation looks bugged.

Improvements: If I were to implement something similar to this, the 3 map representations could be squished down to 1. A 2D array of rooms, each containing a "String icon" field which can be accessed to get the textual representation of that room. Each room would then reference the next and previous Room objects in the main path, as well as any offshoot paths that are added after the fact. I guess this would make each room double as a node in a linked list kind of? Need a little more thought for that part.

There are also parts of the code that are very much important for the map generation which actually take place inside of the Room objects instead. This functionality should be lifted into the Map class.

[CromulentEntity]

Looking at that old generator was pretty neat. I'll need some time to digest the pros and cons of going in that direction versus using/tweaking an established maze generation algorithm. Will come back to this.