Two-stage generation

[OndrejNepozitek]

The goal of this feature is to generate each room chain in two distinct stages. In the first stage, only a subset of rooms is laid out, ignoring all the others rooms. In the second stage, all the other rooms are laid out and after this step succeeds, the next chain can be generated.

Use case 1 - Corridors

The main motivation of this feature is the generalization of corridors. Currently, there are special implementations of some parts of the generator that allow corridors to be generated (LayoutOperationsWithCorridors, CorridorsData, ConfigurationSpacesGenerator). With the two-stage generation, corridors could be treated as another room type that is alwys handled in the second stage of the generation process. It would also mean that we would be able to exactly which rooms should be connected by corridors.

Phase 1

• [x] Remove AddCorridors from SimulatedAnnealingEvolver, replace with calling the second stage logic
• [x] Make chain decomposition compatible with two stages
• [x] Add second graph to the map description (transform the full graph into a stage-one-only graph)
• [x] Add corridors to performance tests
• [x] Handle all stage-two rooms greedily - in a similar way to how are currently corridors handled

Open questions

Should we allow multiple stage-two rooms neighbouring with one another?

It would probably not be very practical because we would have to implement configuration spaces that can handle case where two or more stage-two rooms are missing between two stage-one rooms.

Solution: It will not be supported for now

Phase 2

Being implemented in the dev-corridor-configuration-spaces branch

• [x] Check that all neighbours of a stage-two rooms are stage-one rooms
• [x] Implement map description that will map generic room type to int room type
• [x] Extend map description to support adding corridors between any pair of rooms
• [x] Investigate why using different offsets behaves as in the image below
  • [x] Check if the probability of the second stage not succeeding increases with more offsets - This is exactly the reason. It also sometimes happens that the previous chain does not allow any valid positions of the next chain. The solution is to limit the maximum number of failed attempts of the second stage.
• [ ] Rewrite configuration spaces generator so that it handlers corridors correctly and does not use offsets
  • [ ] Implement configuration spaces over a set of room templates
  • [ ] Implement mapping from position to used corridor and its position to speedup the lookup
• [ ] Handle stage-two rooms differently based on their type

Open questions

How to handle corridor configuration spaces?

Option 1 Save complete mapping of which position of two non-corridor rooms corresponds to which positions and shapes of corridors.

Pros: Should be fast during runtime if memory requirements are not too high. Cons: Does not scale very well because we have to compute individual points and not just work with lines. That will results in higher computational cost when computing these configuration spaces. Could be solved by precomputing configuration spaces.

Option 2 Do not save any mapping.

Pros: Fast computation of configuration spaces. Cons: Probably not that much slower during runtime. When trying to choose a corridor shape, we do not know which shape to pick. So we pick a random one and check whether the intersection of configuration space of the two non-corridor rooms is empty or not. If it is empty we try another shape. That means that we can eliminate a given shape after computing one configuration spaces intersection.

Option 3 Mixed approach. Save only some information.