Repository: ASPP/pelita

Issue:
introduce a database of mazes with descriptive metadata, for example number and length of dead-ends, etc.

Discussion:
@otizonaizit: Looking at #852 , we need to discuss what to store in the layout database. This depends in my opinion on how we plan to use that information. I envision something like this:

```bash
pelita --trapped-food 0.3 bot1.py bot2.py
```

where `--trapped-food` represent the (maximum) proportion of food which is located within dead-ends, tunnels and/or chambers. This would replace the current `--dead-ends` switch.

The way it would work should be the following:

  - if a layout is explicitly specified and the layout contains no food, food is distributed randomly but according to `--trapped-food` in a "soft" way, i.e. if the layout does not have enough trapped squares it won't error our but just do that best it can
  - if layout is explicitly specified and the layout already contains food, a warning is issued and the `--trapped-food ` switch is ignored
  - if layout is **not** explicitly specified, a random layout is selected among those in the database  that allow us to satisfy `--trapped-food` and food is distributed randomly according to `--trapped-food`. For this to work, the layouts will be stored without food in the database.
  
What do you think @Debilski ? If we agree on this use case, we can design the database to make this the privileged and optimized use case. Given that the database is private, I think we can change it later with not too much trouble should the need arise, given that #852 is optimized as hell and tuns in ~10 seconds on 1600 layouts.
@Debilski: Couple of thoughts:

* I suppose this would mean that we also get rid of the mazes with/without dead ends distinction? Mazes can have all the dead ends/chambers that they like, because who cares if we do not put food in them?
* Without the need for this distinction and with an algorithm that finds all chambers in a maze in 1/160 seconds, we might not need a maze database at all (at least not yet). We use the `--trapped-food` (name feels a bit weird) option and the food is arranged according to specification.
* Not having a db will make life a little easier. (Less to think about, fewer moving parts to maintain.)
* The food relocation algorithm will need to be aware of the desired trapped food ratio.
* I think mazes that contain food should (/could) also be reshuffled. For development situations, it could be easier, if the food in a maze does not reshuffle each time one uses it, but this can simply be done by not using the `--trapped-food` flag.
* For a tournament, the food should absolutely be reshuffled. (Although I do not see any problem with *not* reshuffling it. I kind of doubt that there is any real danger in knowing the food locations in advance.)
* I guess we could also decide to use a specific pre-defined, pre-generated set of mazes for the tournament instead of relying on any maze database or live-generation. But live-generation is also fun, so I have nothing against it.
* (This probably goes to far but we could now also vary how much food is on a maze.)

Going forward, my suggestions would then be something like:

* Rename `create_db.py` to `layout_tools.py` or something.
* Make the `find_chambers`, `find_tunnels` methods public api along with a `distribute_food` method. (Public in the sense that `game.py` uses them.)
* Instead of having a database, we could have a script that prints out the stats for each layout, which we could use for our own analyses.
* The tournament should make use of `--trapped-food` or use a new set of mazes that are generated when running tournament setup.@otizonaizit: >     * I suppose this would mean that we also get rid of the mazes with/without dead ends distinction? Mazes can have all the dead ends/chambers that they like, because who cares if we do not put food in them?

this is not strictly necessary, but we can of course re-generate all layouts without using the code that removes dead-ends and chambers
 
>     * Without the need for this distinction and with an algorithm that finds all chambers in a maze in 1/160 seconds, we might not need a maze database at all (at least not yet). We use the `--trapped-food` (name feels a bit weird) option and the food is arranged according to specification.

Well, not really. Imagine I set `--trapped-food 0.33`. This means I want to trap 10 food pellets, i.e. I need to select a maze among those that have at least 10 trapped squares. If I don't have the database I would need to parse all the layouts every time I start a game. With the database, I know which layouts fit my requirements without the need of parsing anything. Given that the algorithm to get the list of trapped squares is fast, this only means that we do not need to store this list in the database, but we need to store the number, so we can select the right mazes and then, once one maze has been chosen at random, with the algorithm we can get the list of relevant squares.

>     * Not having a db will make life a little easier. (Less to think about, fewer moving parts to maintain.)

See above, I don't think we can avoid it.

>     * The food relocation algorithm will need to be aware of the desired trapped food ratio.

I am not sure I agree. A defender may decide to "guard" the entrance of a chamber for too long and then the food will be relocated at random, so it may be relocated _outside_ of the chamber. This is fine in my opinion. The `--trapped-food` thing is in my vision just a starting condition.

>     * I think mazes that contain food should (/could) also be reshuffled. For development situations, it could be easier, if the food in a maze does not reshuffle each time one uses it, but this can simply be done by not using the `--trapped-food` flag.

For development situation, if you want to replay on the same maze with the same food you just use `--seed`. I think that it is a more intuitive API if the food is distributed at random only if not explicitly specified in the layout. If the layout comes with food, I want it to be exactly there. the `--trapped-food` switch is only to make the proportion of trapped food configurable. We could even start without that switch and just hard-code the proportion. The distribution of food at start is a different thing, that we are here doing at the same time, but logically it is a different thing.


>     * For a tournament, the food should absolutely be reshuffled. (Although I do not see any problem with _not_ reshuffling it. I kind of doubt that there is any real danger in knowing the food locations in advance.)

For me it is not about danger, but if we want `--trapped-food` to be configurable, then we need distribution at start, or we may not have enough layouts that match the requirements.
 
>     * I guess we could also decide to use a specific pre-defined, pre-generated set of mazes for the tournament instead of relying on any maze database or live-generation. But live-generation is also fun, so I have nothing against it.
> 
>     * (This probably goes to far but we could now also vary how much food is on a maze.)

OK, OK, but that is something else, we can talk about it later. Note that live **maze** generation is not doable at the moment: it is too slow.
 
> Going forward, my suggestions would then be something like:
> 
>     * Rename `create_db.py` to `layout_tools.py` or something.
> 
>     * Make the `find_chambers`, `find_tunnels` methods public api along with a `distribute_food` method. (Public in the sense that `game.py` uses them.)

Sure.
 
>     * Instead of having a database, we could have a script that prints out the stats for each layout, which we could use for our own analyses.

See above, I don't think this is feasible.
 
>     * The tournament should make use of `--trapped-food` or use a new set of mazes that are generated when running tournament setup.

I don't think it is feasible. Generating the mazes takes too long.@Debilski: I think I have been slightly misunderstood: I never meant to parse and analyse all mazes before a match instead of using a database. No matter how fast the algorithm gets, this would break down on a slow file system. However, my approach assumes that this is not necessarily needed.


> > * I suppose this would mean that we also get rid of the mazes with/without dead ends distinction? Mazes can have all the dead ends/chambers that they like, because who cares if we do not put food in them?
> 
> this is not strictly necessary, but we can of course re-generate all layouts without using the code that removes dead-ends and chambers

> > * Without the need for this distinction and with an algorithm that finds all chambers in a maze in 1/160 seconds, we might not need a maze database at all (at least not yet). We use the `--trapped-food` (name feels a bit weird) option and the food is arranged according to specification.
> 
> Well, not really. Imagine I set `--trapped-food 0.33`. This means I want to trap 10 food pellets, i.e. I need to select a maze among those that have at least 10 trapped squares. If I don't have the database I would need to parse all the layouts every time I start a game. With the database, I know which layouts fit my requirements without the need of parsing anything. Given that the algorithm to get the list of trapped squares is fast, this only means that we do not need to store this list in the database, but we need to store the number, so we can select the right mazes and then, once one maze has been chosen at random, with the algorithm we can get the list of relevant squares.

My approach was: Draw any layout fitting the size from our pre-generated layouts and then place the food according to the requested (or hard-coded) specification. If the maze doesn’t have enough dead-ends or chambers to place food: bad luck. (Or good luck!)
If we want to have `--trapped-food 0`, we can still use mazes with chambers/dead-ends. The important part is that no food is placed in a dead-end, no?

(The only problem would be if this breaks down too often. Then a db could help with pre-selecting.)

Aside: Please let’s not invent something that needs to use a number like 0.33 as a default. That number doesn’t look right. :) Perhaps `--trapped-food 10:30` or so, which also specifies the total food.

> > * Not having a db will make life a little easier. (Less to think about, fewer moving parts to maintain.)
> 
> See above, I don't think we can avoid it.
> 
> > * The food relocation algorithm will need to be aware of the desired trapped food ratio.
> 
> I am not sure I agree. A defender may decide to "guard" the entrance of a chamber for too long and then the food will be relocated at random, so it may be relocated _outside_ of the chamber. This is fine in my opinion. The `--trapped-food` thing is in my vision just a starting condition.

The idea was more: If `--trapped-food` is 0, then relocated food should also not be placed in a chamber.


> > * I think mazes that contain food should (/could) also be reshuffled. For development situations, it could be easier, if the food in a maze does not reshuffle each time one uses it, but this can simply be done by not using the `--trapped-food` flag.
> 
> For development situation, if you want to replay on the same maze with the same food you just use `--seed`. I think that it is a more intuitive API if the food is distributed at random only if not explicitly specified in the layout. If the layout comes with food, I want it to be exactly there. the `--trapped-food` switch is only to make the proportion of trapped food configurable. We could even start without that switch and just hard-code the proportion. The distribution of food at start is a different thing, that we are here doing at the same time, but logically it is a different thing.

But our own selection of mazes would not have the food pre-set? Then I think I misunderstood it.

> > * For a tournament, the food should absolutely be reshuffled. (Although I do not see any problem with _not_ reshuffling it. I kind of doubt that there is any real danger in knowing the food locations in advance.)
> 
> For me it is not about danger, but if we want `--trapped-food` to be configurable, then we need distribution at start, or we may not have enough layouts that match the requirements.

That’s why I am more in favour of a who-cares algorithm that takes any maze and just places the food as good as it can. With the database you now have to figure out a selection algorithm.

> > * I guess we could also decide to use a specific pre-defined, pre-generated set of mazes for the tournament instead of relying on any maze database or live-generation. But live-generation is also fun, so I have nothing against it.
> > 
> > * (This probably goes to far but we could now also vary how much food is on a maze.)
> 
> OK, OK, but that is something else, we can talk about it later. Note that live **maze** generation is not doable at the moment: it is too slow.

Yes, that’s why I meant, pre-generated: They will be generated when the yaml file for the tournament is created, during tournament setup.


> > Going forward, my suggestions would then be something like:
> > * Rename `create_db.py` to `layout_tools.py` or something.
> > 
> > * Make the `find_chambers`, `find_tunnels` methods public api along with a `distribute_food` method. (Public in the sense that `game.py` uses them.)
> 
> Sure.
> 
> > * Instead of having a database, we could have a script that prints out the stats for each layout, which we could use for our own analyses.
> 
> See above, I don't think this is feasible.
> 
> > * The tournament should make use of `--trapped-food` or use a new set of mazes that are generated when running tournament setup.
> 
> I don't think it is feasible. Generating the mazes takes too long.

During tournament setup time it should work.
@otizonaizit: yes, so I think we agree on almost everything. The plan would be this: https://github.com/ASPP/pelita/pull/856#issuecomment-2710143331 . If maze generation is fast enough, we can really get rid completely of the hard coded mazes. @otizonaizit: Fixed by #856 and (when merged) by #867 

Solution patch:
diff --git a/pelita/layout.py b/pelita/layout.py
index 2e6e2750c..51e816a6a 100644
--- a/pelita/layout.py
+++ b/pelita/layout.py
@@ -116,9 +116,12 @@ def get_layout_by_name(layout_name):
         # reraise as ValueError with appropriate error message.
         raise ValueError(f"Layout: '{layout_name}' is not known.") from None
 
-def parse_layout(layout_str, food=None, bots=None):
+def parse_layout(layout_str, food=None, bots=None, strict=True):
     """Parse a layout string.
 
+    If strict is False, the layout string must not be valid and parse_layout will
+    try its best to interpret it. This is useful only during testing.
+
     A valid layout string is enclosed by walls and rectangular:
 
      ########
@@ -178,7 +181,7 @@ def parse_layout(layout_str, food=None, bots=None):
                 # set width of layout
                 width = len(row)
                 # check that width is even
-                if width % 2:
+                if width % 2 and strict:
                     raise ValueError(f"Layout width must be even (found {width})!")
                 rows.append(row)
                 continue
@@ -230,7 +233,7 @@ def parse_layout(layout_str, food=None, bots=None):
     for i, bot in enumerate(lbots):
         if bot is None and BOT_I2N[i] not in bots:
             missing_bots.append(BOT_I2N[i])
-    if missing_bots:
+    if missing_bots and strict:
             raise ValueError(f"Missing bot(s): {missing_bots}")
     lfood.sort()
 
diff --git a/pelita/maze_generator.py b/pelita/maze_generator.py
index c14450d0a..4ed616daa 100644
--- a/pelita/maze_generator.py
+++ b/pelita/maze_generator.py
@@ -1,433 +1,331 @@
 """
-Generate maze layouts for 'pelita', without dead ends.
+Generate mazes for pelita
 
-Algorithm:
-* start with an empty grid
-* draw a wall with gaps, dividing the grid in 2
-* repeat recursively for each sub-grid
-* find dead ends
-* remove a wall at the dead ends
+The algorithm is a form of binary space partitioning:
 
-Players 1,3 always start in the bottom left; 2,4 in the top right
-Food is placed randomly (though not too close to the pacmen starting positions)
+* start with an empty grid enclosed by walls
+* draw a wall with k gaps, dividing the grid in 2 partitions
+* repeat recursively for each sub-partitions, where walls have k/2 gaps
+* pacmen are always in the bottom left and in the top right
+* Food is distributed according to specifications
 
 Notes:
-the final map includes a symmetric, flipped copy
-the first wall has k gaps, the next wall has k/2 gaps, etc. (min=1)
+The final maze includes is created by first generating the left half maze and then
+generating the right half by making mirroring the left half. The resulting maze is
+centrosymmetric.
+
+Definitions:
+Articulation point - a node in the graph that if removed would disconnect the
+    graph in to two subgraphs. Find them with: nx.articulation_points(graph)
+
+Dead-end - nodes in the graph with connectivity 1 -> that node is necessarily
+    connected to an articulation point. Find them with
+    {node for node in graph if graph.degree(node) == 1}
+
+Tunnel: nodes in a sequence of articulation points connecting with a dead-end
+
+Chamber: nodes connected to the main graph by a single articulation point -> it
+    is basically a space with an entrance of a single node
+
 
 Inspired by code by Dan Gillick
 Completely rewritten by Pietro Berkes
 Rewritten again (but not completely) by Tiziano Zito
+Rewritten completely by Jakob Zahn & Tiziano Zito
 """
 
-import numpy as np
 import networkx as nx
 
 from .base_utils import default_rng
+from .team import walls_to_graph
 
 
-north = (0, -1)
-south = (0, 1)
-east = (1, 0)
-west = (-1, 0)
-
+def mirror(nodes, width, height):
+    nodes = set(nodes)
+    other = set((width - 1 - x, height - 1 - y) for x, y in nodes)
+    return nodes | other
 
-# character constants for walls, food, and empty spaces
-W = b'#'
-F = b'.'
-E = b' '
 
+def sample_nodes(nodes, k, rng=None):
+    rng = default_rng(rng)
 
-def empty_maze(height, width):
-    """Return an empty maze with external walls.
+    if k < len(nodes):
+        return set(rng.sample(sorted(nodes), k=k))
+    else:
+        return nodes
 
-    A maze is a 2D array of characters representing walls, food, and agents.
-    An empty maze is made of empty tiles, except for the external walls.
-    """
 
-    maze = np.empty((height, width), dtype='c')
-    maze.fill(E)
+def find_trapped_tiles(graph, width, include_chambers=False):
+    main_chamber = set()
+    chamber_tiles = set()
 
-    # add external walls
-    maze[0, :].fill(W)
-    maze[-1, :].fill(W)
-    maze[:, 0].fill(W)
-    maze[:, -1].fill(W)
+    for chamber in nx.biconnected_components(graph):
+        max_x = max(chamber, key=lambda n: n[0])[0]
+        min_x = min(chamber, key=lambda n: n[0])[0]
+        if min_x < width // 2 <= max_x:
+            # only the main chamber covers both sides
+            # our own mazes should only have one central chamber
+            # but other configurations could have more than one
+            main_chamber.update(chamber)
+            continue
+        else:
+            chamber_tiles.update(set(chamber))
 
-    return maze
+    # remove shared articulation points with the main chamber
+    chamber_tiles -= main_chamber
 
+    # combine connected subgraphs
+    if include_chambers:
+        subgraphs = graph.subgraph(chamber_tiles)
+        chambers = list(nx.connected_components(subgraphs))
+    else:
+        chambers = []
 
-def maze_to_bytes(maze):
-    """Return bytes representation of maze."""
-    lines = [b''.join(maze[i,:])
-             for i in range(maze.shape[0])]
-    return b'\n'.join(lines)
+    return chamber_tiles, chambers
 
-def maze_to_str(maze):
-    """Return a ascii-string representation of maze."""
-    bytes_ = maze_to_bytes(maze)
-    return bytes_.decode('ascii')
 
-def bytes_to_maze(bytes_):
-    """Return a maze numpy bytes array from a bytes representation."""
-    rows = []
-    for line in bytes_.splitlines():
-        line = line.strip()
-        if len(line) == 0:
-            # skip empty lines
-            continue
-        cols = []
-        for idx in range(len(line.strip())):
-            # this crazyness is needed because bytes do not iterate like
-            # strings: see the comments about iterating over bytes in
-            # https://docs.python.org/3/library/stdtypes.html#bytes-objects
-            cols.append(line[idx:idx+1])
-        rows.append(cols)
-
-    maze = np.array(rows, dtype=bytes)
-    return maze
-
-def str_to_maze(str_):
-    """Return a maze numpy bytes array from a ascii string representation."""
-    bytes_maze = str_.encode('ascii')
-    return bytes_to_maze(bytes_maze)
-
-def create_half_maze(maze, ngaps_center, rng=None):
-    """Fill the left half of the maze with random walls.
-
-    The second half can be created by mirroring the left part using
-    the 'complete_maze' function.
-    """
+def distribute_food(all_tiles, chamber_tiles, trapped_food, total_food, rng=None):
     rng = default_rng(rng)
 
-    # first, we need a wall in the middle
+    if trapped_food > total_food:
+        raise ValueError(
+            f"number of trapped food ({trapped_food}) must not exceed total number of food ({total_food})"
+        )
 
-    # the gaps in the central wall have to be chosen such that they can
-    # be mirrored
-    ch = maze.shape[0] - 2
-    candidates = list(range(ch//2))
-    rng.shuffle(candidates)
-    half_gaps_pos = candidates[:ngaps_center // 2]
-    gaps_pos = []
-    for pos in half_gaps_pos:
-        gaps_pos.append(pos)
-        gaps_pos.append(ch - pos - 1)
+    if total_food > len(all_tiles):
+        raise ValueError(
+            f"number of total food ({total_food}) exceeds available tiles in maze ({len(all_tiles)})"
+        )
+
+    free_tiles = all_tiles - chamber_tiles
 
-    # make wall
-    _add_wall_at(maze, (maze.shape[1] - 2) // 2 - 1, ngaps_center,
-                 vertical=True, rng=rng, gaps_pos=gaps_pos)
+    # distribute as much trapped food in chambers as possible
+    tf_pos = sample_nodes(chamber_tiles, trapped_food, rng=rng)
 
-    # then, fill the left half with walls
-    _add_wall(maze[:, :maze.shape[1] // 2], ngaps_center // 2, vertical=False, rng=rng)
+    # distribute remaining food outside of chambers
+    free_food = total_food - len(tf_pos)
 
-def _add_wall_at(maze, pos, ngaps, vertical, rng, gaps_pos=None):
-    """
-    add a wall with gaps
+    ff_pos = sample_nodes(free_tiles, free_food, rng=rng)
 
-    maze -- maze where to place wall, plus a border of one element
-    pos -- position where to put the wall within the center of the maze
-           (border excluded)
-    """
+    # there were not enough tiles to distribute all leftover food
+    leftover_food = total_food - len(ff_pos) - len(tf_pos)
+    if leftover_food > 0:
+        leftover_tiles = chamber_tiles - tf_pos
+        leftover_food_pos = sample_nodes(leftover_tiles, leftover_food, rng=rng)
+    else:
+        leftover_food_pos = set()
 
-    if not vertical:
-        maze = maze.T
+    return tf_pos | ff_pos | leftover_food_pos
 
-    center = maze[1:-1, 1:-1]
-    ch, cw = center.shape
 
-    # place wall
-    center[:, pos].fill(W)
+def add_wall_and_split(partition, walls, ngaps, vertical, rng=None):
+    rng = default_rng(rng)
 
-    # place gaps
+    (xmin, ymin), (xmax, ymax) = partition
+
+    # the size of the maze partition we work on
+    width = xmax - xmin + 1
+    height = ymax - ymin + 1
+
+    # if the partition is too small, stop
+    if height < 3 and width < 3:
+        return set()
+
+    # insert a wall only if there is some space in the around it in the
+    # orthogonal direction, i.e.:
+    # if the wall is vertical, then the relevant length is the width
+    # if the wall is horizontal, then the relevant length is the height
+    partition_length = width if vertical else height
+    if partition_length < rng.randint(3, 5):
+        return set()
+
+    # the raw/column to put the horizontal/vertical wall on
+    # the position is calculated starting from the left/top of the maze partition
+    # and then a random offset is added -> the resulting raw/column must not
+    # exceed the available length
+    pos = xmin if vertical else ymin
+    pos += rng.randint(1, partition_length - 2)
+
+    # the maximum length of the wall is the space we have in the same direction
+    # of the wall in the partition, i.e.
+    # if the wall is vertical, the maximum length is the height
+    # if the wall is horizontal, the maximum length is the width
+    max_length = height if vertical else width
+
+    # We can start with a full wall, but we want to make sure that we do not
+    # block the entrances to this partition. The entrances are
+    # - the tile before the beginning of this wall [entrance] and
+    # - the tile after the end of this wall [exit]
+    # if entrance or exit are _not_ walls, then the wall must leave the neighboring
+    # tiles also empty, i.e. the wall must be shortened accordingly
+    if vertical:
+        entrance_before = (pos, ymin - 1)
+        entrance_after = (pos, ymin + max_length)
+        begin = 0 if entrance_before in walls else 1
+        end = max_length if entrance_after in walls else max_length-1
+        wall = {(pos, ymin+y) for y in range(begin, end)}
+    else:
+        entrance_before = (xmin - 1, pos)
+        entrance_after = (xmin + max_length, pos)
+        begin = 0 if entrance_before in walls else 1
+        end = max_length if entrance_after in walls else max_length-1
+        wall = {(xmin+x, pos) for x in range(begin, end)}
+
+    # place the requested number of gaps in the otherwise full wall
+    # these gaps are indices in the direction of the wall, i.e.
+    # x if horizontal and y if vertical
+    # TODO: when we drop compatibility with numpy, this can be more easily done
+    # by just sampling ngaps out of the full wall set, i.e.
+    # gaps = rng.sample(wall, k=ngaps)
+    # for gap in gaps:
+    #     wall.remove(gap)
     ngaps = max(1, ngaps)
-    # choose position of gaps if necessary
-    if gaps_pos is None:
-        # choose aandom positions
-        gaps_pos = list(range(ch))
-        rng.shuffle(gaps_pos)
-        gaps_pos = gaps_pos[:ngaps]
-        # do not block entrances
-        if maze[0][pos + 1] == E:
-            gaps_pos.insert(0, 0)
-        if maze[-1][pos + 1] == E:
-            gaps_pos.insert(0, ch - 1)
-    for gp in gaps_pos:
-        center[gp, pos] = E
-
-    sub_mazes = [maze[:, :pos + 2], maze[:, pos + 1:]]
-
-    if not vertical:
-        sub_mazes = [sm.T for sm in sub_mazes]
-
-    return sub_mazes
-
-def _add_wall(maze, ngaps, vertical, rng):
-    """Recursively build the walls of the maze.
-
-    grid -- 2D array of characters representing the maze
-    ngaps -- number of empty spaces to leave in the wall
-    vertical -- if True, create a vertical wall, otherwise horizontal
-    """
-
-    h, w = maze.shape
-    center = maze[1:-1, 1:-1]
-    ch, cw = center.shape
-
-    # no space for walls, interrupt recursion
-    if ch < 3 and cw < 3:
-        return
-
-    size = cw if vertical else ch
-    # create a wall only if there is some space in this direction
-    min_size = rng.randint(3, 5)
-    if size >= min_size:
-        # place the wall at random spot
-        pos = rng.randint(1, size-2)
-        sub_mazes = _add_wall_at(maze, pos, ngaps, vertical, rng=rng)
-
-        # recursively add walls
-        for sub_maze in sub_mazes:
-            _add_wall(sub_maze, max(1, ngaps // 2), not vertical, rng=rng)
-
-
-def walls_to_graph(maze):
-    """Transform a maze in a graph.
-
-    The data on the nodes correspond to their coordinates, data on edges is
-    the actions to take to transition to that edge.
-
-    Returns:
-    graph -- a Graph
-    first_node -- the first node in the Graph
-    """
-
-    h, w = maze.shape
-    directions = [west, east, north, south]
-
-    graph = nx.Graph()
-    # define nodes for maze
-    for x in range(w):
-        for y in range(h):
-            if maze[y, x] != W:
-                graph.add_node((x,y))
-                # this is a free position, get its neighbors too
-                for dx, dy in directions:
-                    nbx, nby = (x+dx, y+dy)
-                    # do not go out of bounds
-                    try:
-                        if maze[nby, nbx] == E:
-                            graph.add_edge((x, y), (nbx, nby))
-                    except IndexError:
-                        # this move brought us out of the maze, just ignore it
-                        continue
-    return graph
-
-
-def find_dead_ends(graph, width):
-    """Find dead ends in a graph."""
-
-    dead_ends = []
-    for node in graph.nodes():
-        if graph.degree(node) == 1 and node[0] < width-1:
-            dead_ends.append(node)
-
-    return dead_ends
-
-
-def remove_dead_end(dead_node, maze):
-    """Remove one dead end in a maze."""
-
-    h, w = maze.shape
-
-    # loop through the neighboring positions and remove the first wall we find
-    # as long as it is not on the outer border or in the middle of the maze
-    # not in the central wall x==w//2-1
-    directions = (north, south, east, west)
-    for direction in directions:
-        nbx = dead_node[0]+direction[0]
-        nby = dead_node[1]+direction[1]
-        if nbx not in (0,w-1,w//2-1) and nby not in (0,h-1):
-            neighbor = maze[nby, nbx]
-            if neighbor == W:
-                maze[nby, nbx] = E
-                break
-
-
-def remove_all_dead_ends(maze):
-    height, width = maze.shape
-    while True:
-        maze_graph = walls_to_graph(maze)
-        dead_ends = find_dead_ends(maze_graph, width)
-        if len(dead_ends) == 0:
-            break
-
-        remove_dead_end(dead_ends[0], maze)
-
-def find_chamber(graph):
-    """Detect chambers (rooms with a single square entrance).
-
-    Return (entrance, chamber), where `entrance` is the node representing the
-    entrance to the chamber (None if no chamber is found), and `chamber` is the
-    list of nodes within the chamber (empty list if no nodes are in the chamber).
-
-    The entrance to a chamber is a node that when removed from the graph
-    will result in the graph to be split into two disconnected graphs."""
-    # minimum_node_cut returns a set of nodes of minimum cardinality that
-    # disconnects the graph. This means that we have a chamber if the length
-    # of this set is one, i.e. there is one node that when removed disconnects
-    # the graph
-    cuts = nx.minimum_node_cut(graph)
-    if len(cuts) > 1:
-        # no chambers, yeah!
-        return None, []
-    entrance = cuts.pop()
-    # remove the cut, i.e. put a wall on the entrance
-    lgraph = nx.restricted_view(graph, [entrance],[])
-    # now get the resulting subgraphs
-    subgraphs = sorted(nx.connected_components(lgraph), key=len)
-    # let's get the smallest subgraph: this is going to be a chamber
-    # (other subgraphs are other chambers (if any) and the 'rest' of the graph
-    # return a list of nodes, instead of a set
-    chamber = list(subgraphs[0])
-    return entrance, chamber
-
-def get_neighboring_walls(maze, locs):
-    """Given a list of coordinates in the maze, return all neighboring walls.
-
-    Walls on the outer border are ignored automatically."""
-    height, width = maze.shape
-    walls = []
-    seen = []
-    for nodex, nodey in locs:
-        # if we are already on the border, skip this node
-        if nodex<=0 or nodex>=(width-1) or nodey<=0 or nodey>=(height-1):
-            continue
-        # explore all directions around the current node
-        for dirx, diry in (north, south, east, west):
-            # get coordinates of neighbor in direction (dirx, diry)
-            adjx, adjy = nodex+dirx, nodey+diry
-            if (adjx, adjy) in seen:
-                # we have visited this neighbor already
-                continue
-            else:
-                seen.append((adjx, adjy))
-            # check that we still are inside the maze
-            if adjx<=0 or adjx>=(width-1) or adjy<=0 or adjy>=(height-1):
-                # the neighbor is out of the maze
-                continue
-            if maze[adjy,adjx] == W:
-                # this is a wall, store it
-                walls.append((adjx, adjy))
+    wall_pos = list(range(max_length))
+    rng.shuffle(wall_pos)
+
+    for gap in wall_pos[:ngaps]:
+        if vertical:
+            wall.discard((pos, ymin+gap))
+        else:
+            wall.discard((xmin+gap, pos))
+
+    # collect this wall into the global wall set
+    walls |= wall
+
+    # define the two new partitions of the maze generated by this wall
+    # these are the parts of the maze to the left/right of a vertical wall
+    # or the top/bottom of a horizontal wall
+    if vertical:
+        partitions = [((xmin,  ymin), (pos-1, ymax)),
+                      ((pos+1, ymin), (xmax,  ymax))]
+    else:
+        partitions = [((xmin,  ymin), (xmax, pos-1)),
+                      ((xmin, pos+1), (xmax,  ymax))]
+
+    for partition in partitions:
+        walls |= add_wall_and_split(
+            partition, walls, max(1, ngaps // 2), not vertical, rng=rng
+        )
+
     return walls
 
-def remove_all_chambers(maze, rng=None):
-    rng = default_rng(rng)
 
-    maze_graph = walls_to_graph(maze)
-    # this will find one of the chambers, if there is any
-    entrance, chamber = find_chamber(maze_graph)
-    while entrance is not None:
-        # get all the walls around the chamber
-        walls = get_neighboring_walls(maze, chamber)
-        # choose a wall at random among the neighboring one and get rid of it
-        bad_wall = rng.choice(walls)
-        maze[bad_wall[1], bad_wall[0]] = E
-        # we may have opened a door into this chamber, but there may be more
-        # chambers to get rid of. Or, the wall we picked wasn't good enough and
-        # didn't really open a new door to the chamber. I have no idea how to
-        # distinguish this two cases. If we knew how to, we would spare quite
-        # a few iterations here?
-        # Well, as long as we keep on doing this we will eventually get rid
-        # of all the chambers
-        maze_graph = walls_to_graph(maze)
-        entrance, chamber = find_chamber(maze_graph)
-
-
-def add_food(maze, max_food, rng=None):
-    """Add max_food pellets on the left side of the maze.
-
-    We exclude the pacmen's starting positions and the central dividing border
-    """
+def generate_half_maze(width, height, ngaps_center, bots_pos, rng=None):
+    # use binary space partitioning
     rng = default_rng(rng)
 
-    if max_food == 0:
-        # no food needs to be added, return here
-        return
-    h, w = maze.shape
-    pacmen = [(1,h-2), (1,h-3)]
-    # get all free slots on the left side, excluding the dividing border
-    free_y, free_x = np.where(maze[:,:w//2-1] == E)
-    # convert it to a list of coordinate tuples
-    free = list(zip(free_x, free_y))
-    # remove the pacmen starting coordinates (we have to check that they are
-    # indeed free before try to remove them
-    [free.remove(pacman) for pacman in pacmen if pacman in free]
-    # check if we have any free slots left
-    if len(free) == 0 and max_food > 0:
-        raise ValueError(f'No space left for food in maze')
-    elif max_food > len(free):
-        # check if we can indeed fit so much food in the maze
-        raise ValueError(f'Can not fit {max_food} pellet in {len(free)} free slots')
-    elif max_food < 0:
-        raise ValueError(f'Can not add negative number of food ({max_food} given)')
-
-    # now take max_food random positions out of this list
-    food = rng.sample(free, max_food)
-    # fit it in the maze
-    for col, row in food:
-        maze[row, col] = F
-
-def add_pacmen(maze):
-    ## starting pacmen positions
-    maze[-2, 1] = b'b'
-    maze[-3, 1] = b'a'
-    maze[1, -2] = b'y'
-    maze[2, -2] = b'x'
-
-def create_maze(height, width, nfood, dead_ends=False, rng=None):
-    """Create a new maze in text format.
-
-    The maze is created with a recursive creation algorithm. The maze part of
-    the blue team is a center-mirror version of the one for the red team.
-
-    The function reserves space for 2 PacMan for each team in upper-right
-    and lower-left corners of the maze. Food is added at random.
-
-    Input arguments:
-    height, width -- the size of the maze, including the outer walls
-    nfood -- number of food dots for each team
-    seed -- if not None, the random seed used to generate the maze
-    dead_ends -- if True allow for dead ends and chambers in the maze
-
-    A dead-end is a node with connectivity one.
-    A chamber is a sub-graph such that there is a node in the sub-graph, the
-    entrance to the chamber, that when removed from the graph will result in the
-    graph to be split into two disconnected graphs.
-    """
-    if width%2 != 0:
-        raise ValueError(f'Width must be even ({width} given)')
+    # outer walls are top, bottom, left and right edge
+    walls = {(x, 0) for x in range(width)} | \
+            {(x, height-1) for x in range(width)} | \
+            {(0, y) for y in range(height)} | \
+            {(width-1, y) for y in range(height)}
+
+    # Generate a wall with gaps at the border between the two homezones
+    # in the left side of the maze
+
+    # TODO: when we decide to break backward compatibility with the numpy version
+    # of create maze, this part can be delegated directly to generate_walls and
+    # then we need to rewrite mirror to mirror a set of coordinates around the center
+    # by discarding the lower part of the border
+
+    # Let us start with a full wall at the left side of the border
+    x_wall = width//2 - 1
+    wall = {(x_wall, y) for y in range(1, height - 1)}
+
+    # possible locations for gaps
+    # these gaps need to be symmetric around the center
+    # TODO: when we decide to break compatibility with the numpy version of
+    # create_maze we can rewrite this. See generate_walls for an example
+    ymax = (height - 2) // 2
+    candidates = list(range(ymax))
+    rng.shuffle(candidates)
 
-    rng = default_rng(rng)
+    for gap in candidates[:ngaps_center//2]:
+        wall.remove((x_wall, gap+1))
+        wall.remove((x_wall, ymax*2 - gap))
 
-    maze = empty_maze(height, width)
-    create_half_maze(maze, height // 2, rng=rng)
+    walls |= wall
+    partition = ((1, 1), (x_wall - 1, ymax * 2))
 
-    # make space for pacman (2 pacman each)
-    maze[-2, 1] = E
-    maze[-3, 1] = E
+    walls = add_wall_and_split(
+        partition,
+        walls,
+        ngaps_center // 2,
+        vertical=False,
+        rng=rng,
+    )
 
-    # remove dead ends
-    if not dead_ends:
-        remove_all_dead_ends(maze)
-        remove_all_chambers(maze, rng=rng)
+    # make space for the pacmen:
+    for bot in bots_pos:
+        if bot in walls:
+            walls.remove(bot)
 
-    # add food
-    add_food(maze, nfood, rng=rng)
+    return walls
+
+
+def generate_maze(trapped_food=10, total_food=30, width=32, height=16, rng=None):
+    if width % 2 != 0:
+        raise ValueError(f"Width must be even ({width} given)")
 
-    # complete right part of maze with mirror copy
-    maze[:, width // 2:] = np.flipud(np.fliplr(maze[:, :width // 2]))
+    if width < 4:
+        raise ValueError(f"Width must be at least 4, but {width} was given")
 
-    # add pacman
-    add_pacmen(maze)
+    if height < 4:
+        raise ValueError(f"Height must be at least 4, but {height} was given")
+
+    rng = default_rng(rng)
 
-    return maze_to_str(maze)
+    # generate a full maze, but only the left half is filled with random walls
+    # this allows us to cut the execution time in two, because the following
+    # graph operations are quite expensive
+    pacmen_pos = set([(1, height - 3), (1, height - 2)])
+    walls = generate_half_maze(width, height, height//2, pacmen_pos, rng=rng)
+
+    ### TODO: hide the chamber_finding in another function, create the graph with
+    # a wall on the right border + 1, so that find chambers works reliably and
+    # we can get rid of the  {.... if tile[0] < border} in the following
+    # also, improve find_trapped_tiles so that it does not use x and width, but just
+    # requires two sets of nodes representing the left and the right of the border
+    # and then the main chambers is that one that has a non-empty intersection
+    # with both.
+
+    # transform to graph to find dead ends and chambers for food distribution
+    # IMPORTANT: we have to include one column of the right border in the graph
+    # generation, or our algorithm to find chambers would get confused
+    # Note: this only works because in the right side of the maze we have no walls
+    # except for the surrounding ones.
+    graph = walls_to_graph(walls, shape=(width//2+1, height))
+
+    # the algorithm should actually guarantee this, but just to make sure, let's
+    # fail if the graph is not fully connected
+    if not nx.is_connected(graph):
+        raise ValueError("Generated maze is not fully connected, try a different random seed")
+
+    # this gives us a set of tiles that are "trapped" within chambers, i.e. tunnels
+    # with a dead-end or a section of tiles fully enclosed by walls except for a single
+    # tile entrance
+    chamber_tiles, _ = find_trapped_tiles(graph, width, include_chambers=False)
+
+    # we want to distribute the food only on the left half of the maze
+    # make sure that the tiles available for food distribution do not include
+    # those right on the border of the homezone
+    # also, no food on the initial positions of the pacmen
+    # IMPORTANT: the relevant chamber tiles are only those in the left side of
+    # the maze. By detecting chambers on only half of the maze, we may still have
+    # spurious chambers on the right side
+    border = width//2 - 1
+    chamber_tiles = {tile for tile in chamber_tiles if tile[0] < border} - pacmen_pos
+    all_tiles = {(x, y) for x in range(border) for y in range(height)}
+    free_tiles = all_tiles - walls - pacmen_pos
+    left_food = distribute_food(free_tiles, chamber_tiles, trapped_food, total_food, rng=rng)
+
+    # get the full maze with all walls and food by mirroring the left half
+    food = mirror(left_food, width, height)
+    walls = mirror(walls, width, height)
+    layout = { "walls" : tuple(sorted(walls)),
+               "food"  : sorted(food),
+               "bots"  : [ (1, height - 3), (width - 2, 2),
+                           (1, height - 2), (width - 2, 1) ],
+               "shape" : (width, height) }
+
+    return layout
diff --git a/pelita/ui/tk_sprites.py b/pelita/ui/tk_sprites.py
index 99cd74afe..d5795a1bb 100644
--- a/pelita/ui/tk_sprites.py
+++ b/pelita/ui/tk_sprites.py
@@ -96,7 +96,6 @@ class BotSprite(TkSprite):
     def __init__(self, mesh, team=0, bot_id=0, shadow=False, **kwargs):
         self.bot_id = bot_id
         self.team = team
-        self.width = mesh.mesh_width
 
         self.shadow = shadow
 
@@ -115,9 +114,9 @@ def __init__(self, mesh, team=0, bot_id=0, shadow=False, **kwargs):
 
     def is_harvester_at(self, pos):
         if self.team == 0:
-            return pos[0] >= self.width // 2
+            return pos[0] >= self.mesh.mesh_width // 2
         elif self.team == 1:
-            return pos[0] < self.width // 2
+            return pos[0] < self.mesh.mesh_width // 2
 
     def delete(self, canvas):
         canvas.delete("speak" + self.tag)


Test patch:
diff --git a/test/test_maze_generation.py b/test/test_maze_generation.py
index 4ea2ff010..24e3dbf8b 100644
--- a/test/test_maze_generation.py
+++ b/test/test_maze_generation.py
@@ -1,372 +1,267 @@
-import textwrap
 from random import Random
 
-import networkx as nx
-import numpy as np
 import pytest
 
 import pelita.maze_generator as mg
+import pelita.layout as pl
+import pelita.team as pt
 
 SEED = 103525239
 
-
-def test_maze_bytes_str_conversions():
-    # note that the first empty line is needed!
-    maze_str = """
-                  ##################
-                  #. ... .##.     y#
-                  # # #  .  .### #x#
-                  # # ##.   .      #
-                  #      .   .## # #
-                  #a# ###.  .  # # #
-                  #b     .##. ... .#
-                  ##################"""
-    maze_bytes = bytes(maze_str, 'ascii')
-    maze_clist = [[b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#'],
-                  [b'#',b'.',b' ',b'.',b'.',b'.',b' ',b'.',b'#',b'#',b'.',b' ',b' ',b' ',b' ',b' ',b'y',b'#'],
-                  [b'#',b' ',b'#',b' ',b'#',b' ',b' ',b'.',b' ',b' ',b'.',b'#',b'#',b'#',b' ',b'#',b'x',b'#'],
-                  [b'#',b' ',b'#',b' ',b'#',b'#',b'.',b' ',b' ',b' ',b'.',b' ',b' ',b' ',b' ',b' ',b' ',b'#'],
-                  [b'#',b' ',b' ',b' ',b' ',b' ',b' ',b'.',b' ',b' ',b' ',b'.',b'#',b'#',b' ',b'#',b' ',b'#'],
-                  [b'#',b'a',b'#',b' ',b'#',b'#',b'#',b'.',b' ',b' ',b'.',b' ',b' ',b'#',b' ',b'#',b' ',b'#'],
-                  [b'#',b'b',b' ',b' ',b' ',b' ',b' ',b'.',b'#',b'#',b'.',b' ',b'.',b'.',b'.',b' ',b'.',b'#'],
-                  [b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#',b'#']]
-    maze_arr = np.array(maze_clist, dtype=bytes)
-    assert np.all(mg.bytes_to_maze(maze_bytes) == maze_arr)
-    assert np.all(mg.str_to_maze(maze_str) == maze_arr)
-    # round trip
-    # we must dedent the string and remove the first newline
-    # we have the newline in the first line to have dedent work out of the box
-    maze_str = textwrap.dedent(maze_str[1:])
-    maze_bytes = bytes(maze_str, 'ascii')
-    assert mg.maze_to_bytes(maze_arr) == maze_bytes
-    assert mg.maze_to_str(maze_arr) == maze_str
-
-
-def test_create_half_maze():
-    # this test is not really testing that create_half_maze does a good job
+def layout_str_to_graph(l_str):
+    l_dict = pl.parse_layout(l_str, strict=False)
+    graph = pt.walls_to_graph(l_dict['walls'], shape=l_dict['shape'])
+    shape = l_dict['shape']
+    return graph, shape
+
+maze_103525239 = """
+################################
+#.   .....#....##    .      . y#
+# .# #########      # .    #  x#
+#  # # .     .    # ######    ##
+#  #    .    # ##.         #   #
+#  ####### ###    #.      .# ..#
+# .#     .  ..    ### # ##.#####
+# ### ###### ####  .    #.   . #
+# .   .#    .  #### ###### ### #
+#####.## # ###    ..  .     #. #
+#.. #.      .#    ### #######  #
+#   #         .## #    .    #  #
+##    ###### #    .     . # #  #
+#a  #    . #      ######### #. #
+#b .      .    ##....#.....   .#
+################################
+"""
+
+def test_generate_maze_stability():
     # we only test that we keep in returning the same maze when the random
     # seed is fixed, in case something changes during future porting/refactoring
-    maze_str = """################################
-                  #         #    #               #
-                  #  # #########                 #
-                  #  # #                         #
-                  #  #         # #               #
-                  #  ####### ###                 #
-                  #  #                           #
-                  # ### ###### ###               #
-                  #      #       #               #
-                  ##### ## # ###                 #
-                  #   #        #                 #
-                  #   #          #               #
-                  ##    ###### #                 #
-                  #   #      #                   #
-                  #              #               #
-                  ################################"""
-
-    maze = mg.empty_maze(16,32)
-    mg.create_half_maze(maze, 8, rng=SEED)
-    expected = mg.str_to_maze(maze_str)
-    print(mg.maze_to_str(maze))
-    assert np.all(maze == expected)
-
-def test_conversion_to_nx_graph():
-    maze_str = """##################
-                  #       ##       #
-                  # # #      ### # #
-                  # # ##           #
-                  #           ## # #
-                  # # ###      # # #
-                  #       ##       #
-                  ##################"""
-    maze = mg.str_to_maze(maze_str)
-    graph = mg.walls_to_graph(maze)
-    # now derive a maze from a graph manually
-    # - start with a maze full of walls
-    newmaze = mg.empty_maze(maze.shape[0], maze.shape[1])
-    newmaze.fill(mg.W)
-    # - loop through each node of the graph and remove a wall at the
-    # corresponding coordinate
-    for node in graph.nodes():
-        newmaze[node[1], node[0]] = mg.E
-    assert np.all(maze == newmaze)
-
-def test_find_one_dead_end():
-    # this maze has exactly one dead end at coordinate (1,1)
-    maze_dead = """########
-                   # #    #
-                   #      #
-                   #      #
-                   ########"""
-
-    maze = mg.str_to_maze(maze_dead)
-    graph = mg.walls_to_graph(maze)
-    width = maze.shape[1]
-    dead_ends = mg.find_dead_ends(graph, width)
-    assert len(dead_ends) == 1
-    assert dead_ends[0] == (1,1)
-
-def test_find_multiple_dead_ends():
-    # this maze has exactly three dead ends at coordinates (1,1), (1,5), (3,5)
-    maze_dead = """############
-                   # #        #
-                   #          #
-                   #          #
-                   # # #      #
-                   # # #      #
-                   ############"""
-
-    maze = mg.str_to_maze(maze_dead)
-    graph = mg.walls_to_graph(maze)
-    width = maze.shape[1]
-    dead_ends = mg.find_dead_ends(graph, width)
-    assert len(dead_ends) == 3
-    dead_ends.sort()
-    assert dead_ends[0] == (1,1)
-    assert dead_ends[1] == (1,5)
-    assert dead_ends[2] == (3,5)
-
-def test_find_multiple_dead_ends_on_the_right():
-    # this maze has exactly three dead ends at coordinates (10,1), (10,5), (8,5)
-    maze_dead = """############
-                   #        # #
-                   #          #
-                   #          #
-                   #      # # #
-                   #      # # #
-                   ############"""
-
-    maze = mg.str_to_maze(maze_dead)
-    graph = mg.walls_to_graph(maze)
-    width = maze.shape[1]
-    dead_ends = mg.find_dead_ends(graph, width)
-    assert len(dead_ends) == 3
-    dead_ends.sort()
-    assert dead_ends[2] == (10,5)
-    assert dead_ends[1] == (10,1)
-    assert dead_ends[0] == (8,5)
-
-def test_remove_one_dead_end():
-    # this maze has exactly one dead end at coordinate (1,1)
-    maze_dead = """########
-                   # #    #
-                   #      #
-                   #      #
-                   ########"""
-
-    maze = mg.str_to_maze(maze_dead)
-    mg.remove_dead_end((1,1), maze)
-    assert maze[1,1] == mg.E
-
-def test_remove_multiple_dead_ends():
-    # this maze has exactly three dead ends at coordinates (1,1), (1,5), (3,5)
-    maze_dead = """############
-                   # #        #
-                   #          #
-                   #          #
-                   # # #      #
-                   # # #      #
-                   ############"""
-
-    maze = mg.str_to_maze(maze_dead)
-    mg.remove_all_dead_ends(maze)
-    # There are many ways of getting rid of the two dead ends at the bottom
-    # The one that requires the less work is to remove the left-bottom wall
-    # This one is the solution we get from remove_all_dead_ends, but just
-    # because the order in which we find dead ends is from top to bottom and from
-    # left to right.
-    # In other words, remove the dead ends here actually means getting this maze back
-    expected_maze = """############
-                       #          #
-                       #          #
-                       #          #
-                       # # #      #
-                       #   #      #
-                       ############"""
-    expected_maze = mg.str_to_maze(expected_maze)
-    assert np.all(maze == expected_maze)
-
-def test_find_chamber():
-    # This maze has one single chamber, whose entrance is one of the
-    # nodes (1,2), (1,3) or (1,4)
-    maze_chamber = """############
+    new_layout = mg.generate_maze(rng=SEED)
+    old_layout = pl.parse_layout(maze_103525239)
+    assert old_layout == new_layout
+
+def test_find_trapped_tiles():
+    # This maze has one single chamber
+    one_chamber = """############
+                     #   #      #
+                     #   #      #
+                     # ###      #
+                     #          #
+                     #          #
+                     ############"""
+
+    graph, shape = layout_str_to_graph(one_chamber)
+    one_chamber_tiles, chambers = mg.find_trapped_tiles(graph, shape[0], include_chambers=True)
+    assert len(chambers) == 1
+    tiles_1 = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (3, 1), (3, 2)}
+    assert one_chamber_tiles == tiles_1
+
+    two_chambers = """############
                       #   #      #
                       #   #      #
-                      # ###      #
-                      #          #
-                      #          #
+                      # ###  # ###
+                      #      #   #
+                      #      #   #
+                      #      #   #
+                      #      #   #
                       ############"""
-
-    maze = mg.str_to_maze(maze_chamber)
-    maze_orig = maze.copy()
-    mg.remove_all_dead_ends(maze)
-    # first, check that the chamber is not mistaken for a dead end
-    assert np.all(maze_orig == maze)
-    # now check that we detect it
-    graph = mg.walls_to_graph(maze)
-    # there are actually two nodes that can be considered entrances
-    entrance, chamber = mg.find_chamber(graph)
-    assert entrance in ((1,2), (1,3), (1,4))
-    # check that the chamber contains the right nodes. Convert to set, because
-    # the order is irrelevant
-    if entrance == (1,4):
-        expected_chamber = {(1,1), (1,2), (1,3), (2,1), (2,2), (3,1), (3,2)}
-    elif entrance == (1,3):
-        expected_chamber = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)}
-    else:
-        expected_chamber = {(1,1), (2,1), (2,2), (3,1), (3,2)}
-    assert set(chamber) == expected_chamber
-
-    # now remove the chamber and verify that we don't detect anything
-    # we just remove wall (4,1) manually
-    maze = mg.str_to_maze(maze_chamber)
-    maze[1,4] = mg.E # REMEMBER! Indexing is maze[y,x]!!!
-    graph = mg.walls_to_graph(maze)
-    entrance, chamber = mg.find_chamber(graph)
-    assert entrance is None
-    assert chamber == []
-
-
-
-
-maze_one_chamber = """############
+    graph, shape = layout_str_to_graph(two_chambers)
+    two_chambers_tiles, chambers = mg.find_trapped_tiles(graph, shape[0], include_chambers=True)
+    assert len(chambers) == 2
+    tiles_2 = {(8,3), (8,4), (8,5), (8,6), (8,7), (9,4), (9,5),
+               (9,6), (9,7), (10, 4), (10,5), (10,6), (10, 7) }
+    assert two_chambers_tiles == tiles_1 | tiles_2
+
+def test_distribute_food():
+    maze_chamber = """############
                       #   #      #
                       #   #      #
                       # ###      #
                       #          #
                       #          #
                       ############"""
-maze_two_chambers = """############
-                       #   #      #
-                       #   #      #
-                       # ###  # ###
-                       #      #   #
-                       #      #   #
-                       #      #   #
-                       #      #   #
-                       ############"""
-maze_neighbor_chambers = """####################
-                            #   ##   #         #
-                            #   ##   #         #
-                            # ###### #         #
-                            #                  #
-                            #                  #
-                            #                  #
-                            ####################"""
-maze_chamber_in_chamber = """######################
-                             #                    #
-                             #                    #
-                             #                    #
-                             ##### ####           #
-                             #        #           #
-                             #   #    #           #
-                             ######################"""
-maze_chamber_bonanza = """################################
-                          #   #   #                      #
-                          #   #   #                      #
-                          #   ### #                      #
-                          #                              #
-                          #                              #
-                          ###### ##########              #
-                          #               #              #
-                          #               #              #
-                          # ###########   #              #
-                          #           #                  #
-                          ##### ####  #   #              #
-                          #        #  #   #              #
-                          #   #    #  #   #              #
-                          ################################"""
-
-
-@pytest.mark.parametrize("maze_chamber", (maze_one_chamber,
-                                          maze_two_chambers,
-                                          maze_neighbor_chambers,
-                                          maze_chamber_in_chamber,
-                                          maze_chamber_bonanza,))
-def test_remove_all_chambers(maze_chamber):
-    maze = mg.str_to_maze(maze_chamber)
-    mg.remove_all_chambers(maze)
-    # there are no more chambers if the connectivity of the graph is larger than 1
-    graph = mg.walls_to_graph(maze)
-    assert nx.node_connectivity(graph) > 1
-    #XXX: TODO -> an easy way of getting rid of chambers is to just remove all the
-    # walls. How can we test that this is not what we are doing but that instead
-    # we are removing just a few walls?
-
-@pytest.mark.parametrize('iteration', range(1,11))
-def test_create_maze(iteration):
-    # generate a few mazes and check them for consistency
-    local_seed = 12345 * iteration
-    maze_str = mg.create_maze(8,16,nfood=15,rng=local_seed)
-    maze = mg.str_to_maze(maze_str)
-    height, width = maze.shape
-    # check that the returned maze has all the pacmen
-    for pacman in (b'a',b'x',b'b',b'y'):
-        assert np.any(maze == pacman)
-        # now that we now we have a pacman, check that we have it only once
-        # and remove it by putting an empty space instead
-        row, col = np.nonzero(maze == pacman)
-        assert len(row) == 1
-        assert len(col) == 1
-        maze[row,col] = mg.E
-
-    # check that we have in total twice nfood in the maze
-    assert (maze == mg.F).sum() == 15*2
-    # remove the food for computing dead ends and chambers
-    maze[maze == mg.F] = mg.E
-
-    # check that the returned maze is center-mirror symmetric
-    left_maze = np.flipud(np.fliplr(maze[:,width//2:]))
-    assert np.all(left_maze == maze[:,:width//2])
-
-    # check that we don't have any dead ends
-    # no node in the graph should have only one connection
-    graph = mg.walls_to_graph(maze)
-    for node, degree in graph.degree():
-        assert degree > 1
-
-    # now check that we don't have chambers, i.e. the connectivity of the
-    # graph is > 1
-    assert nx.node_connectivity(graph) > 1
-
-def test_odd_width():
+
+    graph, shape = layout_str_to_graph(maze_chamber)
+    all_tiles = set(graph.nodes)
+    chamber_tiles, _ = mg.find_trapped_tiles(graph, shape[0], include_chambers=False)
+
+    # expected exceptions
     with pytest.raises(ValueError):
-        mg.create_maze(2,3,1)
-
-def test_add_food():
-    mini = """########
-              #      #
-              #      #
-              ########"""
-    maze = mg.str_to_maze(mini)
-    # We have 12 empty squares in total, so 6 on the left side.
-    # -> 2 slots are taken by the dividing border, so we have 4 left
-    # -> 2 are reserved for pacmen, so we have only 2 slots for food
-    # - check that we can indeed accommodate 2 pellets in the maze
-    lmaze = maze.copy()
-    mg.add_food(lmaze, 2)
-    assert (lmaze == mg.F).sum() == 2
-    # - check that if we add a wall in a free spot that is not reserved by the
-    #   pacmen we can only accommodate 1 pellet
-    lmaze = maze.copy()
-    lmaze[1,2] = mg.W
-    mg.add_food(lmaze, 1)
-    assert (lmaze == mg.F).sum() == 1
-    # - if we try to add more food, we complain
-    lmaze = maze.copy()
-    lmaze[1,2] = mg.W
+        mg.distribute_food(all_tiles, chamber_tiles, 0, len(all_tiles) + 1)
+
     with pytest.raises(ValueError):
-        mg.add_food(lmaze, 2)
-    # - check that if no space is left we complain
-    lmaze = maze.copy()
-    lmaze[1,2], lmaze[2,2] = mg.W, mg.W
+        mg.distribute_food(all_tiles, chamber_tiles, 10, 8)
+
+    # no intersection of food positions and chamber_tiles
+    trapped_food = 0
+    total_food = 10
+    food = mg.distribute_food(all_tiles, chamber_tiles, trapped_food, total_food)
+    assert len(set(food) & chamber_tiles) == trapped_food
+
+    # trapped food is placed in chamber as requested
+    # all food is placed as requested
+    trapped_food = 3
+    food = mg.distribute_food(all_tiles, chamber_tiles, trapped_food, total_food)
+    assert len(food & chamber_tiles) == trapped_food
+    assert len(food) == total_food
+
+    # food is completely contained in chamber
+    total_food = trapped_food = 3
+    food = mg.distribute_food(all_tiles, chamber_tiles, trapped_food, total_food)
+    assert food.issubset(chamber_tiles)
+    assert len(food) == total_food
+
+    # best effort placement of trapped food
+    trapped_food = 10  # > 7 chamber_tiles
+    total_food = 20
+    food = mg.distribute_food(all_tiles, chamber_tiles, trapped_food, total_food)
+    assert len(food & chamber_tiles) == len(chamber_tiles)
+    assert len(food) == total_food
+
+    # distribute only leftover food in chambers, fill non-chambers first
+    trapped_food = 1
+    free_tiles = all_tiles - chamber_tiles
+    n_free_tiles = len(free_tiles)
+    leftover_food = 2
+    total_food = n_free_tiles + trapped_food + leftover_food
+    food = mg.distribute_food(all_tiles, chamber_tiles, trapped_food, total_food)
+    assert len(food) == total_food
+    assert (food & free_tiles) == free_tiles
+    assert len(food & chamber_tiles) == trapped_food + leftover_food
+
+    # edge case, no food at all
+    food = mg.distribute_food(all_tiles, chamber_tiles, 0, 0)
+    assert len(food) == 0
+
+
+np_maze_generator_86523 = """
+################################
+# #  ..  ..  # ##    # ..  #  y#
+# # . .           .. ## ####  x#
+#       .. . #     . #   . ## ##
+#.#### #######    ####.#. .#   #
+#. .  .        ## .# # #       #
+#.#  ## ######     #  .### #####
+#     ....   . ## ## #      #  #
+#  #      # ## ## .   ....     #
+##### ###.  #     ###### ##  #.#
+#       # # #. ##        .  . .#
+#   #. .#.####    ####### ####.#
+## ## .   # .     # . ..       #
+#a  #### ## ..           . . # #
+#b  #  .. #    ## #  ..  ..  # #
+################################
+"""
+
+@pytest.mark.parametrize('iteration', range(100))
+def test_generate_maze(iteration):
+    local_seed = SEED * iteration
+    rng = Random(local_seed)
+
+    # edge cases
+    # width not even
     with pytest.raises(ValueError):
-        mg.add_food(lmaze, 1)
-    # - check that we fail if we get passed unreasonable amounts of food
-    lmaze = maze.copy()
+        mg.generate_maze(0, 0, 9, 10, rng=rng)
+
+    # width too small
     with pytest.raises(ValueError):
-        mg.add_food(lmaze, -1)
-    # - check that we can cope with no food to add
-    lmaze = maze.copy()
-    mg.add_food(lmaze, 0)
-    assert np.all(lmaze == maze)
+        mg.generate_maze(0, 0, 2, 10, rng=rng)
 
+    # height too small
+    with pytest.raises(ValueError):
+        mg.generate_maze(0, 0, 10, 2, rng=rng)
+
+
+    width = rng.choice(range(16, 65, 2))
+    height = rng.randint(8, 32)
+    total_food = int(0.15 * width * height / 2)
+    trapped_food = int(total_food / 3)
+
+    ld = mg.generate_maze(trapped_food, total_food, width, height, rng=rng)
+
+    walls = set(ld["walls"])
+
+    border = set()
+    for x in range(width):
+        border.add((x, 0))
+        border.add((x, height - 1))
+
+    for y in range(height):
+        border.add((0, y))
+        border.add((width - 1, y))
+
+    def split(nodes, width):
+        left = [node for node in nodes if node[0] < width // 2]
+        right = [node for node in nodes if node[0] >= width // 2]
+        return left, right
+
+    def is_full_mirror(left, right, width, height):
+        right_copy = right[:]
+
+        for x, y in left:
+            mirrored = (width - 1 - x, height - 1 - y)
+            if mirrored not in right:
+                return False
+            else:
+                right_copy.remove(mirrored)
+
+        if len(right_copy) > 0:
+            return False
+
+        return True
+
+    # check that the maze is mirrored around the center
+    left_walls, right_walls = split(ld["walls"], width)
+    left_food, right_food = split(ld["food"], width)
+    assert is_full_mirror(left_walls, right_walls, width, height)
+    assert is_full_mirror(left_food, right_food, width, height)
+
+    # check that the maze is completely enclosed by walls
+    assert border.issubset(set(ld["walls"]))
+
+    # check that there is enough food
+    assert len(ld["food"]) == 2 * total_food
+
+    # check that the bots are where they are supposed to be
+    assert ld["bots"] == [
+        (1, height - 3),
+        (width - 2, 2),
+        (1, height - 2),
+        (width - 2, 1),
+    ]
+
+    # verify shape
+    assert min(ld["walls"]) == (0, 0)
+    assert max(ld["walls"]) == (width - 1, height - 1)
+
+    # verify that the types in the dictionary are as expected
+    def is_seq_of_tuples(seq_type, thing):
+        assert type(thing) is seq_type
+        for item in thing:
+            assert type(item) is tuple
+
+    is_seq_of_tuples(tuple, ld["walls"])
+    is_seq_of_tuples(list, ld["food"])
+    is_seq_of_tuples(list, ld["bots"])
+    assert type(ld["shape"]) is tuple
+
+    # verify that we generate exactly the same maze if started with the same seed
+    seed = rng.randint(1,100000)
+    l1 = mg.generate_maze(trapped_food, total_food, width, height, rng=seed)
+    l2 = mg.generate_maze(trapped_food, total_food, width, height, rng=seed)
+    assert l1 == l2
+
+@pytest.mark.parametrize('iteration', range(100))
+def test_generate_maze_food(iteration):
+    local_seed = SEED + iteration
+    rng = Random(local_seed)
+
+    width = 10
+    height = 5
+    total_food = 10
+    trapped_food = 0
+    ld = mg.generate_maze(trapped_food, total_food, width, height, rng=rng)
+    # check that we never place food on the border
+    x_food = {x for (x, y) in ld['food']}
+    assert width//2 not in x_food
+    assert width//2 - 1 not in x_food