## Monday, September 19, 2011

### Linear Maze

Different maze-generation algorithms can produce drastically different results. Up until now, in SpaceRL I've been using an algorithm that picks a random potential connection and adds it if it is joining two disjoint areas of the maze. Here is a version that does a depth-first traversal instead. It maintains a stack of potential connections to visit. Starting at the entrance, it pushes all potential outgoing edges onto the stack (in random order), then pops edges off until it finds one that goes to an unvisited room. After adding that edge it then pushes on all the unused exits from that room, and so forth until the stack is empty. The result is a maze with a much longer, more linear main path. I'm not sure whether this is good or not, but it's different.

## Monday, September 12, 2011

Uploaded a new version of SpaceRL.

Changes:
• Once player sees a location, it stays permanently visible.
• Door construction revamped to included barricaded and broken doors.
• Single outside hatch on symmetry axis.
• Player always starts out floating toward the entrance hatch.
• Limit ship's spread away from symmetry axis.

The general algorithm for connecting the rooms is as follows:
1. Come up with a set of all potential adjacencies (rooms sharing a wall)
2. Connect all of the adjacent space rooms together (you can't see them in the final product)
3. Connect the ship's rooms together with “original” doors. These may or may not be passable in the final level but represent how the ship was originally constructed. The ship's interior is minimally connected, plus about 50% of the remaining adjacencies.
4. Doors between the inside and the enclosed outside areas are added. This is the same process as the previous step, but doing it afterward ensures that the ship's original layout would not have relied on going outside to traverse it.
5. Create the door to surrounding outer space. It's on the symmetry axis at the moment.
6. Choose from the set of “original” doors to construct a simply-connected maze through the rooms. This will be the expected traversal. These become regular doors. Note that this path may require passage through enclosed exterior areas.
7. Compute each room's depth from the entrance hatch when traversing via the maze.
8. Turn the remaining original doors into broken or barricaded doors: broken, if the traversal depth is the same on either side, and barricaded (so they can only be opened from the deeper side) otherwise.

A couple other things:
• The window size is expanded from 80x25 to 120x40. It really needs to be resizable but that's been a low priority.
• The number of rooms in the ship is greater: 10-100.
• If you just want to look at ship layouts, use the undocumented Ctrl-A hotkey to toggle visibility of everything.