ondrejnepozitek/edgar-dotnet

Configurable procedural layout generator

edgar-dotnet's Issues

Graphs: Planarity check

Input format

Description

It is needed to describe a format that will be used to load rooms and input graphs when using GUI. The format should probably support all the options that can be used through the api.

One way is to distinguish two types of files: one for map description (graph) and another one for room description.

Another open question is the language that should be used for the files. Candidates are for example YAML or JSON.

Room description proposal

name: rectangles
default:
    doors-mode: 
        type: specific-positions
        door-positions:
          -  [[0,0], [0,3]]
rooms:
  - 
    name: 4-square
    shape: [[0,0], [0,4], [4,4], [4,0]]
    doors-mode: 
        type: overlap
        door-length: 1
        minimum-overlap: 1
  - 
    name: 2-4-rectangle
    shape: [[0,0], [0,4], [2,4], [2,0]]

Map description proposal

default-room-shapes:
  - 
    set-name: rectangles
    rotate: true
    probability: 4
    scale: [2,2]
    exclude: [4-square]
  - 
    set-name: rectangles
    room-name: 4-square
    probability: 8
    scale: [2,2]
rooms:
  - name: 1
  - name: 2
  - name: 3
  -
     name: boss-room
     room-shapes:
       -
         set-name: boss-rooms-set
passages:
  - [1,2]
  - [2,3]
  - [3,boss-room]

Steps to reproduce

None.

Actual results

None.

Expected results

None.

Notes for the thesis

None.

Add possibility to choose that no two neighbouring rooms should be same

Configuration spaces: Blocks are connected by passages

GUI: Basic controls

Description

In the first phase, user should be able to configure basic parameters of the algorithm. He should be able to set the number of layouts that should be generated, set the random generator seed. It should be also possible to either choose from already created map description config files or upload a new one.

New button will open after clicking the "Generate" button. It should show the progress of the generation and results.

Steps to reproduce

None.

Actual results

None.

Expected results

None.

Notes for the thesis

None.

Performance: difference checks in SA

Description

Simulated annealing's goal is to generate several layouts that will be used to add more chains and make a final layout. This reports describes what layouts are accepted in an individual run of a simulated annealing.

Motivation

The goal is to not accept every valid layout that is encountered. The motivation behind that is that if one layout fails as a starting point for further extending, we do not want to try it again with a layout that is very similar to the previous one because it would most likely fail, too.

What was tried

The difference check is currently mainly based on a position difference of positions of corresponding configurations in a layout. The difference is computed as a difference of centers of bounding rectangles (we want the computation to be as fast as possible to not slow down the algorithm). The total difference is then normalized to reflect number of rooms and their sizes and the result is compared to all already generated layouts.

Multiple values of a minimal distance were benchmarked.

Result

It seems that values between 0.2 and 1.6 behave in a similar way. More than 80 tries would be probably needed to determine the best option. Too small and too big values did not perform very vell.

Benchmark

Notes for the thesis

None.

Update

Difference computing is currently not invariant to scaling of rooms. It is divided by the average size of rooms but the scale already deformed the computation as the distance is squared before the normalization. See #22

Polygons: computing configuration spaces

Configuration spaces: Blocks can have user-specified door positions

Achieve the speed of the original paper

Description

The program should be at least as fast as the original paper. The problem is that the paper works with real coordinates so it is (in my opinion) easier to generate a valid layout. But it should be enough to show that scaling the rooms up yields similar results as the paper.

Steps to reproduce

1. Prepare all the graphs from the paper
2. Scale the rooms up
3. Run benchmarks

Actual results

Scaling the rooms up sometimes hardly converges (e.g. the graph with 41 vertices).

Expected results

See description.

Notes for the thesis

Generating a layout for a grid is more complicated than using real coordinates. Grid layout is also more general as it can be used even when working with real coordinates but not the other way around.

Notes on performance

Too much backtracking when there is a problem with the earlier chains

It sometimes happens that the way the earlier chains are laid out causes problems in the later stages of the algorithm.

Solution 1: Improve chain decomposition

It should not happen that later chains are connected e.g. to the first chain. But it sometimes happens.

Solution 2: Limit the branching factor of simulated annealing

Currently, the branching factor is set to 5. This may be too much if we have to backtrack really far. From some initial results, it seems like some inputs do not benefit from decreasing the branching factor at all. But if the result is improved decreasing the branching factor, it seems like it benefits the most from branching factor of 2.

branching_results.txt

Chain decomposition improvements

DFS probably better than path components

Start DFS with all neighbors instead of multiple dfs from individual neighbors

Refactor configuration spaces generator

Update config format to reflect new transformations

Commit 8c9c5be added 4 more transformation to existing rotation. However, format of configs was not update to reflect this change. For now, it is only possible to use either all transformations or none. Moreover, the config key is called "rotate", which is obviously wrong.

Diversity of layouts

Description

There could be a switch that would ensure that really different layouts would be outputted. There should also be a matric that would take the total number of rooms into account when deciding whether two layouts are different enough.

What does it mean that layouts are different enough? We are doing a depth-first search with backtracking so it is very likely that all the layouts will be different but also have a few common chains. Is it ok? Or should we start a completely new run of the algorithm to ensure that no two chains are the same? Or is it enough to sometimes perturb a node that is not currently in the last chain? Or should we try to choose a chain at random and perturb it? Will it converge?

Steps to reproduce

None.

Actual results

Layouts have a lot in common.

Expected results

None.

Notes for the thesis

None.

A doorway to the outside?

Silly question - is it possible to mark a room as having a doorway that is not connected to another area.

Use case -
Over-world - for external areas, you use a door - to take you into an interior - at which point you get a new map.
Inside the interior - maps created by your library are used for the interior - but we still need a doorway to mark the place that we entered the map.

This would be a door in a room that does not connect to another room.

Throwing exceptions when trying to get layouts.

When trying to use the DLLs included on the latest release on a new project, it throws a DllNotFoundException (GeneralAlgorithms.Algorithms.Common.BoostWrapper.IsPlanar(Int32[] edges, Int32 edgesCount, Int32 verticesCount) if Boostwrapper isn't found (although the installation tutorial indicates it isn't necessary), and if the DLL is added to the bin folder (since Virtual Studio refuses to add it as a dependency), it throws a NullReferenceException(GeneralAlgorithms.Algorithms.Common.CollectionExtensions.GetWeightedRandom[T](IList1 elements, Func2 weightSelector, Random random), in both cases when trying to call layoutGenerator.GetLayout

Just in case it helps, this is my code:

protected override void Initialize()
        {
            base.Initialize();
            Utils.CenterWindow(this, graphics);
            IsMouseVisible = true;

            var mapDescription = new MapDescription<int>();
            mapDescription.AddRoom(0);
            mapDescription.AddRoom(1);
            mapDescription.AddRoom(2);
            mapDescription.AddRoom(3);

            mapDescription.AddPassage(0, 1);
            mapDescription.AddPassage(0, 3);
            mapDescription.AddPassage(1, 2);
            mapDescription.AddPassage(2, 3);

            var doorMode = new OverlapMode(1, 1);
            var squareRoom = new RoomDescription(GridPolygon.GetSquare(8), doorMode);
            var rectangleRoom = new RoomDescription(GridPolygon.GetRectangle(6, 10), doorMode);
            var corridor = new RoomDescription(GridPolygon.GetSquare(1), new OverlapMode(1, 1));

            mapDescription.AddRoomShapes(squareRoom);
            mapDescription.AddRoomShapes(rectangleRoom);
            mapDescription.AddCorridorShapes(corridor);
            mapDescription.SetWithCorridors(true, new List<int>() { 1 });

            var layoutGenerator = LayoutGeneratorFactory.GetChainBasedGeneratorWithCorridors<int>(new List<int>() { 1 });
            var generatedLayouts = layoutGenerator.GetLayouts(mapDescription, 1);

        }

Allow doors with zero length

It may sound stupid, but there are situations where it's useful to allow doors with zero length. Probably the main usecase for this is if we have to switch from Unity tilemaps to our representation of room shapes. The problem is that when we convert doors from Unity to this library, the length is in fact reduced by 1. And that means, that doors with size 1 in Unity are represented as zero length doors in the library, which is currently not possible.

The main problem when allowing zero length doors is with corner points. We can't deduce in which direction should other rooms be connected because there are two valid possibilities. One possible solution is to either allow connections in both directions or explicitly specify the direction if only one is allowed.

Invariance to scaling

Description

The algorithm should not depend on the scale of the rooms. If both polygons and respective doors are equally scaled, the algorithm should produce similar results with similar speed.

Steps to reproduce

None.

Actual results

The algorithm converges in a similar way with regard to the number of iterations. However, the number of iterations per second decreases as rooms are scaled up. It should be further investigated what part of the algorithms slows it down.

Expected results

Number of iterations and iterations per seconds should not be worse when scaling rooms up.

Notes for the thesis

The reason why scaling up the rooms yields worse results is still unknown.

Update 1

Picking a random intersection now operates in O(1) rather than in O(n) with "n" being the length of a chosen line.

Update 2

Method AddNodeGreedily was changed in a way that it does not search the whole space but rather it tries every i-th point. Where i is chosen in a way that the number of points is left the same. It increases the speed of iterations and has little effect on convergence rate.

ConfigurationSpacesGenerator is currently very slow when scaling up the rooms and must be reworked.

Benchmark

Polygon probabilities normalization

Description

Map description should allow user to normalize polygon probabilities. It would mean that shapes with a lot of rotations do not discrimate for example squares that have only one rotation. Their probabilities are therefore normalized in a way that for example all non-square rectangles have probabilities 1/2 (because there are two rotations). This option therefore makes sense only when polygon rotating is enabled.

Steps to reproduce

None.

Actual results

Rooms with small number of rotations are discriminated and it then looks like they are in the minority.

Expected results

None.

Notes for the thesis

None.

Compile boost only with header files

Description

To build CppCliWrapper, one must have the whole Boost library installed. It should be sufficient to distribute the program with only a few header files. There should be a utility that lets you extract only the header files that you really need.

Steps to reproduce

None.

Actual results

The Wrapper is configured in a way that it finds a boost installation on the disk.

Expected results

None.

Notes for the thesis

None.

Graphs: Straight line planar drawing

Boost 64-bit

I am currently not able to build it in 64 bits.

Performance: lazy evaluation

Description

Simulated annealing can easily generate multiple partial layouts. Straightforward implementation would be to return a list of layouts. However, this could result in generating layouts that are never used. With C#'s yield construct it is quite easy to implement a lazy evaluation that generates a layout only when it is really needed.

Motivation

With lazy evaluation, we can decrease the number of iterations in most of runs. At worst, the number of iterations stays the same because if we needed to generate a "full tree" of layers, both lazy and non-lazy solutions would behave in a same way.

What was tried

Simulated annealing was changed in a way that it uses yield return to fill an IEnumerable. It is then very easy to implement a generator planner that evaluated the problem lazily. In fact, it is now easier to make it lazy because the infrastructure is already prepared. BasicGeneratorPlanner was implemented to showcase the difference between lazy and "classic" evaluation.

Result

When implemented correctly, lazy evaluation is a technique that increases the converge without any side effects.

Benchmark

Notes for the thesis

Some input's convergence is heavily influenced by the lazy evaluation.

Polygons: rotation

Configuration spaces: Let user preselect some rooms' shapes

For boss rooms, etc..

Roadmap

• Make the Unity plugin compatible with the new DungeonGenerator
• Export map descriptions from the Unity plugin
• Forbid individual room templates to repeat in generated levels
• Prepare the evolutionary algorithm to run on the cluster
• Gather statistics about which mutations are often successful
• Generate a detailed report from benchmark result (possibly in the web gui)
• Run benchmark in the Unity plugin

Configuration spaces: Adjacent blocks share a part of a common wall

Output 'points' or json structure to determine position of the rooms on output images?

Use case:
Online roguelike / mud style game - On my overworld (1000x1000 grid) - every 5x5 pixel is a cell- I use this to navigate and draw players position on world map.

I was hoping to use this library for drawing maps for interior areas - such as castles etc.
Instead of drawing a 5x5 pixel of where they are - Now I would simply highlight the room that they are in.
In order to do that- I need to be able to translate Room 1 - into an array of points that correspond with the corners of that room.

Any ideas how to do this with the outputs currently provided?

Different lengths of doors

Description

It is currently possible to pick a valid position for two rooms that have different lengths of doors.

Steps to reproduce

1. Set different door lengths for two shapes

Actual results

None.

Expected results

Configuration spaces should check that the door lengths match. It must also be implemented in the method that post-process layouts to add doors.

Notes for the thesis

None.

Project documentation

Description

Prepare a project documentation with for example https://docusaurus.io/.

Steps to reproduce

None.

Actual results

None.

Expected results

None.

Notes for the thesis

None.

GUI: Center and scale the layout with respect to PictureBox

Performance: simulated annealing parameters

Description

Through generator planner debug logs, it was possible to get a valuable information about where most of the time is spent when the algorithm is stuck. With that information, few changes were proposed.

Motivation

None.

What was tried

Generator planner logs showed that a lot of time was spent on unsuccessful attempts. The simulated annealing ended often after more than 2000 iterations were done. That is quite much. Therefore, the number of iterations per each cycle was decreased in order to use random restarts sooner.

Currently, each simulated annealing run can generate up to 15 layouts. But it was discovered that it is too much. It results in a very wide tree if a layout is bad and most of the generated layouts fail to generate anything. Using this information, the maximum number of generated layout was decreased to 5 layouts.

Result

Proposed changes heavily influenced the convergence rate of the algorithm. Both median and average number of iterations decreased.

Benchmark

Notes for the thesis

None.

Performance: report template

Description

None.

Motivation

None.

What was tried

None.

Result

None.

Notes for the thesis

None.

Update 20.2.2018

 << Breadth first, Lazy, Sigma avg 100, Difference from avg, Perturb inside >> (80 repeats)
---------------------------------------------------------------------------------------------------------
 Name                       | # layouts    | Time first   | Time ten     | Iterations   | Iterations/sec
---------------------------------------------------------------------------------------------------------
 Fig 1 (17 vertices)          .98/1          .20s/.05s      .21s/.05s      8.42k/1.60k    39k/30k        
 Fig 7 top (9 vertices)       1/1            .00s/.00s      .00s/.00s      .09k/.02k      29k/10k        
 Fig 7 bottom (17 vertices)   .68/1          .57s/.36s      .70s/.59s      27.99k/27.66k  40k/47k        
 Fig 8 (41 vertices)          .95/1          3.10s/1.02s    3.62s/1.02s    89.13k/29.82k  24k/29k        
 Fig 9 (15 vertices)          1/1            .69s/.09s      .69s/.09s      22.10k/3.39k   32k/37k        
=========================================================================================================

Performance optimization - evolving generator configurations

The goal of this feature is to improve the performance of the algorithm by observing how it behaves on a given input and then propose improvements of the generator's configuration based on these observations.

Motivation

Currently, there is a single configuration that i used for all inputs. The goal of the bachelor thesis was to make the algorithm usable during runtime so the configuration is already much better than it was in the original paper. However, it is still far from perfect. The problem is that it is quite hard to improve the configuration without seeing how the generator behaves on the input.

So instead of trying to guess how to change the configuration by looking only at the input, I propose to run the algorithm with a given input (e.g. 1000 times), gather statistics and then look at these statistics and propose improvements. The good thing is that we can repeat this process and see whether the performance improved or not.

The resulting optimization technique will be a simple evolutionary algorithm that will start with a single individual (the initial configuration) and then apply mutations (changes to that configuration) with the goal of finding an individual with the best fitness (the configuration with the best performance).

The optimization process will take some time as we need to repeatedly run the algorithm for an extended time to collect enough data. However, it is sufficient to run this optimization once for every input so it can be done for example before releasing a game.

Phase 1

• Implement basic evolutionary algorithm
• Allow early stopping of individual evaluation if it is too bad (otherwise all the bad configurations will slow down the whole process)
• Implement some metric of similarity between generated layouts
• Measure entropy of shapes distribution for individual rooms
• Report how individuals improve/worsen the performance

Mutations

• Merge two neighbouring chains in the chain decomposition
• Change the order of chains
• Change the maximum number of iterations allowed for each chain
• Change the number of cycles and trials per cycle in simulated annealing
• Change the whole chain decomposition strategy

Multithreading support

Description

Running the algorithm on multiple threads could hugely improve overall performance. It can not, however, be implemented before e.g. #17 is resolved as it is not currently clear what part of the algorithm should be done with multiple threads.

One way to do it would be to run the whole algorithm multiple times which would often mean that the running time is equal to time to generate first * number of layouts to generate / number of cores. The problem with this approach is that it could generate very similar layouts without a way to control the process.

Another approach could be to use one or more threads to do the depth-first search and also use one or more threads to plan what layouts should be expanded.

Steps to reproduce

None.

Actual results

None.

Expected results

None.

Notes for the thesis

None.

Performance: chain decomposition

Description

Algorithm to decompose graph into chains is needed.

Steps to reproduce

None.

Actual results

3 different algorithms are currently implemented. The best one yet is the one that uses a breadth first search and tries to minimize the number of chains that have only 1 vertex. The problem is that the reference graph with 17 vertices has a worse convergence rate to using a handmade decomposition.

Benchmark

Expected results

None.

Notes for the thesis

Quality of the chain decomposition plays a crucial role in the convergence speed of the algorithm.

Update 1

Convergence is now better than with the handmade decomposition. However, only 3 inputs were tested. It should be tested at least on all the inputs from the reference paper.

Update 2

All reference inputs are now implemented. Some of them should be further investigated to see if the chain decomposition could be improved.

Update 3

All reference inputs seem to behave well using the best chain decomposition.

Room shape smoothing

The algorithm works best with polygons that are quite simple - having fewer rectangles in the decomposition means cheaper checks if two polygons overlap or not. The goal would be, therefore, to preprocess room shapes to make them simpler while retaining their original door positions.

Phase 1

• Measure the difference in performance between some more complex shapes and manually smoothed shapes

Phase 2

• Implement shape smoothing if the performance difference was significant

Two-stage generation

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

• Remove AddCorridors from SimulatedAnnealingEvolver, replace with calling the second stage logic
• Make chain decomposition compatible with two stages
• Add second graph to the map description (transform the full graph into a stage-one-only graph)
• Add corridors to performance tests
• 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

• Check that all neighbours of a stage-two rooms are stage-one rooms
• Implement map description that will map generic room type to int room type
• Extend map description to support adding corridors between any pair of rooms
• Investigate why using different offsets behaves as in the image below
  • 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.

Graphs: Input format

How should the input look like? Dot language?

GUI: Draw labels on rooms

Connectivity check

Description

It should be somewhere check that to MapDescription desribes a connected graph. The algorithm is not made to handle not connected graphs and it probably doesn't even make sense.

Steps to reproduce

None.

Actual results

Not connected graphs may cause exceptions for example when handling chain decomposition.

Expected results

Notes for the thesis

None.

Performance: random restarts

Description

This report describes how random restarting of the Simulated annealing affects the algorithm. Number of failed iterations is counted and with more failed attempts there is a bigger chance to stop the function and return what has been already generated.

Motivation

Simulated annealing can get stuck so the motivation is to try to evolve the layout from a different starting point when a lot of failed attempts are made.

What was tried

It is important to determine what action results in a successful iteration. Three such places were tried: on valid layout encounter; on valid layout and different enough and at last on an accepted layout (by the simulated annealing). It was also tried to reset the counter when encountering an accepting condition. And at last the probabilities of restarting were scaled.

Results

OnValidAndDifferent dominated all the other place choices so it seems like this is the only option to be further investigated. The performance regarding the scale and resets was pretty similar among the options tried. It also seems like that bigger probabilities of restarting are better.

The main benchmark was done on 50 repeats which may not be enough.

It looks like it is (for now) safe to keep the default setting to be OnValidAndDifferent, without resets, scale one.

Main benchmark

Notes for the thesis

Benchmark showed that having a kind of random restarting definitely helps with the converge of the generator.

Suggestion: Sub-shapes within Rooms

This is a specific idea that would be useful to my game project - but figured it might be re-usable.

In my game I am working on - each room type will have a specific amount of 'slots' where furniture/devices/interact-able objects can go.

At the moment I don't have anything in place to visualise the slots - but I imagine it would be a case of drawing a series of smaller squares inside a room - ideally adjacent to the walls.

The image would then be visualised with a series of grey outlined boxes inside the room shape.
In my game - players could then choose to put objects / devices / technology into those slots.

• While this specific use case is specific to my game.
  Another person might want this feature so they could create table-top dungeon-esq maps that display traps within the room.

Eg: A player who does not have detect trap - gets the original map - minus the trap outlines, but when they 'detect' the trap - the dungeon master reveals the map that has the traps visible.

GUI: Add doors to rooms

Algorithm simplification

The goal of this feature is to simplify the ChainBasedGenerator class. The problem is that the current implementation can generate layouts for different map descriptions without having to create a new instance of the generator. To support that, the generator provides multiple SomethingCreator() classes that are used to set factories for individual components of the algorithm. This makes the algorithm needlessly complex e.g. because it must have additional generic parameters.

The goal is to make the generator simpler. It will possibly mean that users will have to do more of the work themselves (decomposing graphs, creating configuration spaces, etc.). However, even now, we need factory methods to create an instance of the generator so we may implement something similar with the new algorithm.

The new implementation will be probably specialized on a single map description - we will probably have to create a new generator instance for each map description. But that is something that is already being done for example when benchmarking the library, so it is probably not an issue.

Use case 1

Learning parameters for simulated annealing, like when to restart the current run.

Phase 1

• Remove GetLog() from IGeneratorPlanner interface - it can be on the implementation.
• Greedily add nodes to the layout insided SimulatedAnnealingEvolver instead of in the generator itself. Think about who needs to make copies of the layout so that nothing important is overwritten.
• Change IGeneratorPlanner to work directly with ILayoutEvolver instead of LayoutGeneratorFunction.
• Change IGeneratorPlanner to always generate only a single layout.
• Remove IGeneratorContext
• Maybe add more information to event handlers like OnLayoutPerturbed (number of iterations, etc.)

Phase 2

• Remove old interfaces

GUI: Displaying layouts

.NET Standard

Check how hard it would be to convert the libraries into .NET Standard.

Configuration spaces: Let user specify shapes distribution

Rectangles are currently disadvantaged because they have at most 2 rotations whereas other more complex polygons can have up to 4 rotations.

Improve exception messages

There are quite a few exceptions that don't have any message.

Create a benchmark class

Chain decomposition: faces connected by chains

Description

After implementing corridors, a new situation in graph decomposition was revealed. There are graphs where faces are not directly connected to other faces but there is a path or tree that connects them. Previous implementation of chain decomposition was not able to handle this case correctly as it was done in a way that all faces were processed first (and had to be connected to at least one other face) and only then chains were processed.

Steps to reproduce

1. Have a graph where two faces are connected by a path of length at least 2.

Actual results

None.

Expected results

This situation is very usual after adding corridors. Chain decomposition with corridors should be as similar to the decomposition without corridors as possible.

Notes for the thesis

None.