This article illustrates how the Distribution Algorithm and Braid Algorithm by Ioannidis (2016) are improved in PacMaze.

Readers should know about the PacMaze project before reading this article.
读者在阅读本文前，应当先了解 PacMaze 项目。

Improvements to the Distribution Algorithm

The original Distribution Algorithm is simply an algorithm that combines random numbers with probability judgement logic. In order to achieve the desired effect of the optimisation, it is necessary to understand what kind of wall layout provides better game experience than random generation.

Figure 1 shows the “classic” map that comes with the PacMaze game. This is the map that is created by default when the player creates a new map in the “Edit Maps” page (the player can then modify the map based on it). The wall layout design of this map takes some inspiration from the famous Pac-Man game (Namco, 1980) map. It has been tested to some extent and has playability and some challenge.

figure-1

Figure 1 The classic map in PacMaze

Figure 2 shows the number of neighbours for every tile in this classic map. Different numbers of neighbours are marked in different colours to improve intuition.

figure-2

Figure 2 Number of neighbours of every tile in the classic map

From Figure 2, it is possible to detect a certain degree of regularity in the wall layouts that are more suitable for being used as PacMaze game maps. It can be concluded by the following four patterns:

  1. The outermost ring should have a fairly small number of tiles with 3 neighbours and the vast majority of tiles should have only 2 neighbours. This is because the outermost ring should play less of a “traffic hub” role and more of a role in giving the player the pleasure of eating a large number of dots in a straight line in quick succession. At the same time, this also means challenge, as fewer 3-neighbour tiles in the outermost ring means fewer exits from it, which means that if two Ghostrons are blocking Pacboy from both ends at the same time, the chances of escaping will be very slim.
  2. Overall, the probability of occurrence of a tile with 3 neighbours increases as its distance from the centre point decreases. This is because locations closer to the centre point on the map have relatively more complex traffic.
  3. A tile with 3 neighbours is more likely to be adjacent to another tile with 3 neighbours at the same time. There are only a few such tiles that appear alone. This is because two adjacent tiles with 3 neighbours ensure better accessibility in all directions on the map. This also ensures that the player has a good view of the map (especially in First Person View), so that they can quickly observe and choose a safe escape route if the Pacboy is being chased by Ghostrons.
  4. Only the centre part will have 2 adjacent tiles with 4 neighbours. This is supposed to be serving Ghostron spawn points (of course, it is okay for the player to not set any Ghostron Spawn Point here in the Map Editor).

Therefore, based on this regularity, a better Distribution Algorithm logic can be designed. The idea of the improved Distribution Algorithm will be described in relation to each of these four patterns.

For Pattern 1

The algorithm should constrain the number of neighbours of tiles in the outermost ring. It should contain mostly tiles with 2 neighbours, with at most four non-adjacent tiles having 3 neighbours.

To achieve this in the improved Distribution Algorithm, we impose explicit constraints on the distribution of walls at the edges of the map. First, all tiles in the outermost ring (i.e. tiles with either x-coordinate or y-coordinate equal to 1 or 11) are obtained. We first shuffle the order of all these tiles, and try to find out one by one whether it satisfies the condition “no 3-neighbour tiles in the neighbourhood”; if it does, there is a 10% chance that this tile will become a 3-neighbour tile. When the 3-neighbour tile count reaches the upper limit, all the remaining tiles will be forced to be labelled as 2-neighbour.

The pseudocode for Pattern 1 is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Pattern 1
function determine_tiles_in_outermost_ring(map_tile_neighbours):
    // Find all the tiles in the outermost ring first
    outer_tiles = empty_set()
    for x in 0 to 10 do
        for y in 0 to 10 do
            if x == 0 or x == 10 or y == 0 or y == 10 then
                outer_tiles.add(x, y)
            end if
        end for
    end for
    
    // Shuffle the order
    shuffle(outer_tiles)
    
    count_3_neighbour_tiles = 0

    for x, y in outer_tiles do
        // If there are already four 3-neighbour tiles, all the remaining should be 2-neighbour
        if count_3_neighbour_tiles >= 4 then
            map_tile_neighbours[x][y] = 2
            continue
        end if
        
        // Check that the tile has no adjacent 3-neighbour tiles
        // If so, it has a probability to be 3-neighbour
        if has_adjacent_3_neighbour_tiles(x, y) == False and random_number() < 0.1 then
            map_tile_neighbours[x][y] = 3
            count_3_neighbour_tiles += 1
        else
            map_tile_neighbours[x][y] = 2
        end if
    end for

For Pattern 2

The algorithm should ensure that the frequency of occurrence of 3-neighbour tiles increases as their distance from the centre point decreases.

So, a simplified discrete distance decay model can be used here. To calculate the probability of a tile, its Manhattan distance from the centre point is calculated. This distance value is subsequently applied to a generative probability function: p = 0.75 - 0.12 * distance.

The pseudocode for Pattern 2 is as follows.

1
2
3
4
5
6
7
// Pattern 2
function weighted_3_neighbour_prob(x, y):
    // Calculate the Manhattan distance
    distance = max(abs(x - 5), abs(y - 5))
    
    // Return the probability
    return min(0.9, max(0.1, 0.75 - 0.12 * distance))

For Pattern 3

The algorithm should ensure that tiles with 3 neighbours are more likely to be adjacent to other tiles with 3 neighbours.

To implement that, a local propagation mechanism is introduced. When a tile is assigned to be 3-neighbour, there is a 50% chance that one of its adjacent tiles will also be become 3-neighbour.

The propagation is done cautiously. After a tile (x, y) is assigned as 3-neighbour, the algorithm shuffles the four cardinal directions and tries them in random order. It then checks each neighbouring tile to see if it is still unassigned (with neighbour value 0). Upon finding one, it is immediately marked as 3-neighbour, and no further spreading is done.

The pseudocode for Pattern 3 is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Pattern 3
function determine_inner_tiles(map_tile_neighbours):
    for x in 1 to 9 do
        for y in 1 to 9 do
            if map_tile_neighbours[x][y] != 0 then
                continue
            end if

            // Obtain the 3-neighbour probability of the current tile
            random_chance = weighted_3_neighbour_prob(x, y)
            
            if random_number() <= random_chance then
                map_tile_neighbours[x][y] = 3

                // Local propagation mechanism
                if random_number() <= 0.5 then
                    random_dirs = shuffle([(0,1), (1,0), (-1,0), (0,-1)])
                    for dx, dy in random_dirs do
                        nx, ny = x + dx, y + dy
                        if map_tile_neighbours[nx][ny] == 0 then
                            map_tile_neighbours[nx][ny] = 3
                            break
                        end if
                    end for
                end if
            else
                map_tile_neighbours[x][y] = 2
            end if
        end for
    end for

For Pattern 4

The algorithm should generate two adjacent 4-neighbour tiles in the central area, ensuring that the centremost area is relatively wide.

According to the design, we allow only the central part of the map to contain two adjacent tiles with 4 neighbours. To enforce this constraint, the algorithm scans the 3×3 square at the centre of the map, that is, all tiles where both x and y range from 4 to 6 inclusive. It then shuffles these tiles and tries each as a candidate starting point for an adjacent pair. For each selected tile (x, y), it attempts to form a valid adjacent pair either to the right or downward.

Once a valid pair of adjacent tiles is found within the central block, they are both assigned as a 4-neighbour tile. The process is then terminated immediately, ensuring that there is exactly one such pair in the entire map.

The pseudocode for Pattern 4 is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Pattern 4
function place_adjacent_4_neighbour_tiles_in_centre(map_tile_neighbours):
    // Find all the centre tiles first
    centre_tiles = empty_set()
    for x in 4 to 6 do
        for y in 4 to 6 do
            centre_tiles.add(x, y)
        end for
    end for
    
    // Shuffle the order
    shuffle(centre_tiles)
    
    // Randomly set two adjacent tiles as 4-neighbour
    for x, y in centre_tiles do
        random_dirs = shuffle([(0,1), (1,0)])
        for dx, dy in random_dirs do
            nx, ny = x + dx, y + dy
            if nx, ny in centre_tiles then
                map_tile_neighbours[x][y] = 4
                map_tile_neighbours[nx][ny] = 4
                return
            end if
        end for
    end for

In summary, the whole logic of the improved Distribution Algorithm can be pseudo-coded as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function improved_distribution_algorithm():
    // Initialise an empty map_tile_neighbours array, size 11×11, default value 0
    map_tile_neighbours = new 11x11 array filled with 0

    // Pattern 1
    determine_tiles_in_outermost_ring(map_tile_neighbours)

    // Pattern 2 & 3
    determine_inner_tiles(map_tile_neighbours)

    // Pattern 4
    place_adjacent_4_neighbour_tiles_in_centre(map_tile_neighbours)

    // Return the final distributed tile neighbour data
    return map_tile_neighbours

Figure 3 illustrates the neighbour distribution matrix result of six attempts to apply the improved Distribution Algorithm for generation. As can be seen, all the four patterns identified are present.

figure-3

Figure 3 Neighbour distribution matrices generated by six attempts

Improvements to the Braid Algorithm

In the original Braid Algorithm, the direction in which each iterated tile determines its neighbours is completely random. In order to achieve a better gameplay experience, it is also necessary to analyse the wall layout suitable for use as a PacMaze game map.

During the improvement of the Distribution Algorithm, Pattern 3 is discovered and summarised as “A tile with 3 neighbours is more likely to be adjacent to another tile with 3 neighbours at the same time.” By further observation of the classical map in Figure 1, a phenomenon based on this can be identified. That is, when a 3-neighbour tile has some adjacent 3-neighbour tiles, it has a big probability to actually become neighbours with these tiles. Therefore, the improvement idea that the Braid Algorithm can have when dealing with 3-neighbour tiles is, to favour the adjacent 3-neighbour tiles more, rather than depending on pure randomness.

Based on this idea, we can now design the logic that handles all 3-neighbour tiles in the improved Braid Algorithm. We first find all the 3-neighbour tiles from the list of all tiles on the map (shuffled). When processing each 3-neighbour tile, all adjacent tiles of that tile are stored, shuffled, and iterated one by one. Every time an adjacent tile is iterated:

  • If it is a 2-neighbour tile, disconnect it with the current tile.
  • If it is a 3- or 4-neighbour tile, it has a 90% probability to remain being neighbours with the current 3-neighbour tile. That is, it only has a 10% probability to be disconnected from the current tile.

The pseudocode of processing 3-neighbour tiles is as follows. Where the disconnect(), connect() and flood() methods are as defined in the original Braid Algorithm pseudocode by Ioannidis (2016). Note: the pseudocode in the original Braid Algorithm may be confusing disconnect() with connect(), since the logic of the algorithm should try to “build” a wall between two tiles first, and then “break” it if it is found that this is not fine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
function handle_tiles_with_3_neighbours(all_tiles, current_neighbour_counts, distributed_neighbour_nums):
    // Find all the 3-neighbour tiles first
    all_3_neighbour_tiles = empty_set()
    for tile in all_tiles do
        if distributed_neighbour_nums[tile] == 3 then
            all_3_neighbour_tiles.add(tile)
        end if
    end for
    
    for 3_neighbour_tile in all_3_neighbour_tiles do
        // Obtain all adjacent tiles and shuffle them
        adjacent_tile_lists = adjacent_tiles(3_neighbour_tile)
        shuffle(adjacent_tile_lists)
        
        for adjacent_tile in adjacent_tile_lists do
            // Stop if neighbour num is already down to the distributed value
            if current_neighbour_counts[3_neighbour_tile] <= distributed_neighbour_nums[3_neighbour_tile] then
                break
            end if
            
            if distributed_neighbour_nums[adjacent_tile] == 2 then
                // Case: the iterated adjacent tile is 2-neighbour
                // Ignore if this adjacent tile cannot lose any more neighbour
                if current_neighbour_counts[adjacent_tile] <= distributed_neighbour_nums[adjacent_tile] then
                    continue
                end if
                
                // Valid 2-neighbour adjacent tiles will be disconnected
                disconnect(3_neighbour_tile, adjacent_tile)
                current_neighbour_counts[3_neighbour_tile] -= 1
                current_neighbour_counts[adjacent_tile] -= 1
                
                // Check the connectivity of the map
                if flood(all_tiles) == False then
                    // If this disconnection affects the connectivity, undo it
                    connect(3_neighbour_tile, adjacent_tile)
                    current_neighbour_counts[3_neighbour_tile] += 1
                    current_neighbour_counts[adjacent_tile] += 1
                end if
            else
                // Case: the iterated adjacent tile is 3- or 4-neighbour
                // Ignore if this adjacent tile cannot lose any more neighbour
                if current_neighbour_counts[adjacent_tile] <= distributed_neighbour_nums[adjacent_tile] then
                    continue
                end if
                
                // Valid adjacent 3-neighbour tiles have only a small probability of not being neighbours
                if random_number() <= 0.1 then
                    // Disconnect the two tile
                    disconnect(3_neighbour_tile, adjacent_tile)
                    current_neighbour_counts[3_neighbour_tile] -= 1
                    current_neighbour_counts[adjacent_tile] -= 1
                
                    // Check the connectivity of the map
                    if flood(all_tiles) == False then
                        // If this disconnection affects the connectivity, undo it
                        connect(3_neighbour_tile, adjacent_tile)
                        current_neighbour_counts[3_neighbour_tile] += 1
                        current_neighbour_counts[adjacent_tile] += 1
                    end if
                end if
            end if
        end for
    end for

In addition to this, another interesting phenomenon can be found by looking at the wall layout in Figure 1: the classic map has an apparent one-ring-over-one-ring phenomenon. Despite the fact that there are more 3-neighbour tiles in the inner rings, the presence of the rings can still be clearly observed. This makes the map visually more layered and makes it somewhat more difficult for Pacboy to avoid Ghostrons.

To ensure that the random map wall layouts generated by the improved Braid Algorithm follows this trend, some adjustment can be made to the neighbourhood preferences of all the 2-neighbour tiles in the map except for the central area, to help the generated map better present the one-ring-over-one-ring phenomenon. Figure 4 illustrates the most desirable neighbourhood scenarios for all 2-neighbour tiles of the map, except for the 3×3 area in the centre. For each tile location, its two arrows point to the directions in which its two neighbours would ideally be located.

figure-4

Figure 4 Direction of ideal neighbours for each 2-neighbour tile in the PacMaze map (except for the central 3×3 area)

Based on this idea, we can now design the logic that handles all 2-neighbour tiles not in the central 3×3 area, in the improved Braid Algorithm. We first find all the 2-neighbour tiles from the list of all tiles on the map (shuffled), that is not in the central 3×3 area. When processing each 2-neighbour tile, its neighbours are obtained and their order is shuffled. For each of all neighbours but two ideal neighbours of the current tile, it has a 85% probability to be disconnected the current 2-neighbour tile. That is, it only has a 15% probability to remain being neighbours with the current tile. If the number of neighbours of the current tile is still greater than its distributed value after traversing all non-ideal neighbours, its ideal neighbours are sacrificed.

The pseudocode of processing 2-neighbour tiles (not in the central 3×3 area) is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
function handle_non_centre_tiles_with_2_neighbours(all_tiles, current_neighbour_counts, distributed_neighbour_nums):
    // Find all the 2-neighbour tiles that is not in the centre first
    all_non_centre_2_neighbour_tiles = empty_set()
    for tile in all_tiles do
        if distributed_neighbour_nums[tile] == 2 then
            if tile.x < 4 or tile.x > 6 and tile.y < 4 or tile.y > 6 then
                all_non_centre_2_neighbour_tiles.add(tile)
            end if
        end if
    end for
    
    for 2_neighbour_tile in all_non_centre_2_neighbour_tiles do
        // Obtain all adjacent tiles and shuffle them
        adjacent_tile_lists = adjacent_tiles(2_neighbour_tile)
        shuffle(adjacent_tile_lists)
        
        for adjacent_tile in adjacent_tile_lists do
            // Stop if neighbour num is already down to the distributed value
            if current_neighbour_counts[2_neighbour_tile] <= distributed_neighbour_nums[2_neighbour_tile] then
                break
            end if
            
            if preferred_neighbours[2_neighbour_tile].contains(adjacent_tile) == False then
                // Case: the iterated adjacent tile is not the ideal neighbour
                // Ignore if this adjacent tile cannot lose any more neighbour
                if current_neighbour_counts[adjacent_tile] <= distributed_neighbour_nums[adjacent_tile] then
                    continue
                end if
                
                // Valid adjacent non-ideal tiles have a big probability of not being neighbours
                if random_number() <= 0.75 then
                    // Disconnect the two tile
                    disconnect(2_neighbour_tile, adjacent_tile)
                    current_neighbour_counts[2_neighbour_tile] -= 1
                    current_neighbour_counts[adjacent_tile] -= 1
                
                    // Check the connectivity of the map
                    if flood(all_tiles) == False then
                        // If this disconnection affects the connectivity, undo it
                        connect(2_neighbour_tile, adjacent_tile)
                        current_neighbour_counts[2_neighbour_tile] += 1
                        current_neighbour_counts[adjacent_tile] += 1
                    end if
                end if
            end if
        end for
        
        if current_neighbour_counts[2_neighbour_tile] > distributed_neighbour_nums[2_neighbour_tile] then
            // If the current number is still more than its distributed num, sacrifice ideal neighbours
            for adjacent_tile in adjacent_tile_lists do
                // Stop if neighbour num is already down to the distributed value
                if current_neighbour_counts[2_neighbour_tile] <= distributed_neighbour_nums[2_neighbour_tile] then
                    break
                end if
                
                // Find ideal neighbours
                if preferred_neighbours[2_neighbour_tile].contains(adjacent_tile) == True then
                    // Ignore if this adjacent tile cannot lose any more neighbour
                    if current_neighbour_counts[adjacent_tile] <= distributed_neighbour_nums[adjacent_tile] then
                        continue
                    end if
                    
                    // Disconnect the two tile
                    disconnect(2_neighbour_tile, adjacent_tile)
                    current_neighbour_counts[2_neighbour_tile] -= 1
                    current_neighbour_counts[adjacent_tile] -= 1
                    
                    // Check the connectivity of the map
                    if flood(all_tiles) == False then
                        // If this disconnection affects the connectivity, undo it
                        connect(2_neighbour_tile, adjacent_tile)
                        current_neighbour_counts[2_neighbour_tile] += 1
                        current_neighbour_counts[adjacent_tile] += 1
                    end if
                end if
            end for
        end if
    end for

Finally, we can deal with all the tiles in the central 3×3 area that are still not processed. Here, the same stochastic logic as in the original Braid Algorithm will be taken, so no pseudocode will be shown for this logic.

In summary, the whole logic of the improved Braid Algorithm is pseudo-coded as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function improved_braid_algorithm():
    // Obtain the neighbour distribution matrix for all tiles
    distributed_neighbour_nums = improved_distribution_algorithm()
    
    // Initialise the current neighbour counts for all tiles
    for tile in all_tiles do
        current_neighbour_counts[tile] = adjacent_tiles(tile).count
    end for
    
    // Shuffle the order of all the tiles
    shuffle(all_tiles)
    
    // Step 1: Handle 3-neighbour tiles
    handle_tiles_with_3_neighbours(all_tiles, current_neighbour_counts, distributed_neighbour_nums)
    
    // Step 2: Handle 2-neighbour tiles that are not in the centre
    handle_non_centre_tiles_with_2_neighbours(all_tiles, current_neighbour_counts, distributed_neighbour_nums)
    
    // Step 3: Handle unprocessed tiles in the centre (pseudocode omitted)
    handle_unprocessed_centre_tiles(all_tiles, current_neighbour_counts, distributed_neighbour_nums)

Figure 5 shows the result of six attempts to generate a map wall layout, applying the overall improved algorithm scheme.

figure-5

Figure 5 Six wall layout generation attempts using the overall algorithm scheme in PacMaze

References

This reference list is in Harvard style.
本引用列表采用 Harvard 风格。

Ioannidis P.L. (2016) Procedural Maze Generation. Bachelor Thesis. National and Kapodistrian University of Athens. Available at: https://pergamos.lib.uoa.gr/uoa/dl/object/1324569/file.pdf (Accessed: 6 May 2025).

Namco. (1980) Pac-Man [Video game]. Bandai Namco Entertainment, Arcade.

The graphic resources used in Figure 1 & 5:
图 1 以及图 5 中使用的图形资源：

https://assetstore.unity.com/packages/templates/tutorials/chomp-man-3d-game-kit-tutorial-174982