pacai.capture.board

  1import argparse
  2import logging
  3import random
  4import sys
  5import typing
  6
  7import pacai.core.board
  8import pacai.core.log
  9import pacai.pacman.board
 10import pacai.util.reflection
 11
 12MIN_SIZE: int = 10
 13
 14MAX_RANDOM_SIZE: int = 24
 15""" The maximum size for a maze with unspecified size. """
 16
 17MIN_MAZE_AXIS_WIDTH: int = 1
 18
 19DEFAULT_GAPS: int = 3
 20
 21DEFAULT_GAP_FACTOR: float = 0.50
 22MAX_GAP_FACTOR: float = 0.65
 23GAP_FACTOR_STDEV: float = 0.1
 24
 25MAX_PRISON_WIDTH: int = 3
 26
 27MIN_PELLETS: int = 1
 28MAX_PELLETS: int = 100
 29
 30MIN_CAPSULES: int = 0
 31MAX_CAPSULES: int = 4
 32
 33DEFAULT_NUM_AGENTS: int = 2
 34
 35class Maze:
 36    """
 37    A recursive definition of a maze.
 38
 39    Each maze has an "anchor", which is the position of its top-left (northwest) corner in it's parent.
 40    There is only one collection of markers that backs all mazes in a tree.
 41    """
 42
 43    def __init__(self,
 44            height: int, width: int,
 45            anchor: pacai.core.board.Position | None = None, root: typing.Union['Maze', None] = None,
 46            prison_width: int = 0,
 47            ) -> None:
 48        self.height: int = height
 49        """ The height of this submaze. """
 50
 51        self.width: int = width
 52        """ The width of this submaze. """
 53
 54        if (anchor is None):
 55            anchor = pacai.core.board.Position(0, 0)
 56
 57        self.anchor: pacai.core.board.Position = anchor
 58        """ The position that this maze lives at according to the root/parent maze. """
 59
 60        grid = None
 61
 62        if (root is None):
 63            root = self
 64        else:
 65            grid = root.grid
 66
 67        self.root: 'Maze' = root
 68        """
 69        The parent of this maze (the maze that this (sub)maze lives inside).
 70        The true root will have itself as a parent.
 71        """
 72
 73        if (grid is None):
 74            grid = [[pacai.core.board.MARKER_EMPTY for col in range(width)] for row in range(height)]
 75
 76        self.grid: list[list[pacai.core.board.Marker]] = grid
 77        """
 78        A 2-dimensional representation of all the markers in this maze.
 79        All mazes in this tree will share the same grid.
 80        """
 81
 82        if (len(self.grid) == 0):
 83            raise ValueError("Grid cannot have a zero height.")
 84
 85        self.submazes: list['Maze'] = []
 86        """ The submazes/children in this maze. """
 87
 88        self.prison_width: int = prison_width
 89        """
 90        The number of columns used by the "prisons".
 91        Prisons are the starting areas for each agent.
 92        This number does not include walls.
 93        """
 94
 95    def place_relative(self, row: int, col: int, marker: pacai.core.board.Marker) -> None:
 96        """ Place a marker in the grid according to the relative coordinates of this submaze. """
 97
 98        self.grid[self.anchor.row + row][self.anchor.col + col] = marker
 99
100    def is_marker_relative(self, row: int, col: int, marker: pacai.core.board.Marker) -> bool:
101        """ Check if the given marker exists at the relative coordinates of this submaze. """
102
103        true_row = self.anchor.row + row
104        true_col = self.anchor.col + col
105
106        # No markers are out-of-bounds.
107        if ((true_row < 0) or (true_row >= len(self.grid)) or (true_col < 0) or (true_col >= len(self.grid[0]))):
108            return False
109
110        return (self.grid[true_row][true_col] == marker)
111
112    def to_board(self, source: str) -> pacai.core.board.Board:
113        """
114        Create a pacai capture board from this maze.
115        This will add a border (of walls), add a mirrored copy (for the other team), and properly set agent indexes.
116        """
117
118        # Make a new grid that is big enough to include the opposing side (mirrored) and a border (wall) around the entire board.
119        # Initialize with wall markers for the boarder.
120        new_grid = [[pacai.core.board.MARKER_WALL for col in range((self.width * 2) + 2)] for row in range(self.height + 2)]
121
122        for base_row in range(self.height):
123            for base_col in range(self.width):
124                # Offset for the boarder.
125                row = base_row + 1
126                col = base_col + 1
127
128                # Copy the left side, and mirror around both axes for the right side.
129
130                copy_marker = self.grid[base_row][base_col]
131                mirror_marker = self.grid[self.height - base_row - 1][self.width - base_col - 1]
132
133                # If either marker is an agent, adjust the indexes.
134                # Even (including 0) are on the left, and odds are on the right.
135
136                if (copy_marker.is_agent()):
137                    copy_marker = pacai.core.board.Marker(str(copy_marker.get_agent_index() * 2))
138
139                if (mirror_marker.is_agent()):
140                    mirror_marker = pacai.core.board.Marker(str((mirror_marker.get_agent_index() * 2) + 1))
141
142                # Place the final markers.
143                new_grid[row][col] = copy_marker
144                new_grid[row][col + self.width] = mirror_marker
145
146        board_text = "\n".join([''.join(row) for row in new_grid])
147
148        kwargs = {
149            'strip': False,
150            'class': pacai.util.reflection.get_qualified_name(pacai.pacman.board.Board),
151        }
152
153        return pacai.core.board.load_string(source, board_text, **kwargs)
154
155    def _add_wall(self, rng: random.Random, wall_index: int, gaps: float = 1.0, vertical: bool = True) -> bool:
156        """
157        Try to add a vertical wall with gaps at the given location.
158        Return True if a wall was added, False otherwise.
159        """
160
161        if (vertical):
162            return self._add_vertical_wall(rng, wall_index, gaps = gaps)
163
164        return self._add_horizontal_wall(rng, wall_index, gaps = gaps)
165
166    def _add_vertical_wall(self, rng: random.Random, col: int, gaps: float = 1.0) -> bool:
167        """
168        Try to add a vertical wall with gaps at the given col.
169        Return True if a wall was added, False otherwise.
170        """
171
172        # Choose the specific number of gaps we are expecting.
173        gaps = int(round(min(self.height, gaps)))
174
175        # The places (rows) that we may put a wall.
176        slots = list(range(self.height))
177
178        # If there are empty spaces directly above or below our proposed wall,
179        # then don't put a wall marker directly in front of those respective spaces.
180        # This prevents us blocking entrances into our submaze.
181
182        if (self.is_marker_relative(-1, col, pacai.core.board.MARKER_EMPTY)):
183            slots.remove(0)
184
185        if (len(slots) == 0):
186            return False
187
188        if (self.is_marker_relative(self.height, col, pacai.core.board.MARKER_EMPTY)):
189            slots.remove(self.height - 1)
190
191        # If we cannot provided the requested number of gaps, then don't put down the wall.
192        if (len(slots) <= gaps):
193            return False
194
195        # Randomize where we will put our walls.
196        rng.shuffle(slots)
197
198        # Skip the first slots (these are gaps), and place the rest.
199        for row in slots[gaps:]:
200            self.place_relative(row, col, pacai.core.board.MARKER_WALL)
201
202        # By placing a wall, we have created two new submazes (on each side of the wall).
203
204        # One submaze to the left.
205        self.submazes.append(Maze(self.height, col, anchor = self.anchor, root = self.root))
206
207        # One submaze to the right.
208        anchor_offset = pacai.core.board.Position(0, col + 1)
209        self.submazes.append(Maze(self.height, (self.width - col - 1), self.anchor.add(anchor_offset), self.root))
210
211        return True
212
213    def _add_horizontal_wall(self, rng: random.Random, row: int, gaps: float = 1.0) -> bool:
214        """
215        Try to add a horizontal wall with gaps at the given row.
216        Return True if a wall was added, False otherwise.
217        """
218
219        # Choose the specific number of gaps we are expecting.
220        discrete_gaps = int(round(min(self.width, gaps)))
221
222        # The places (cols) that we may put a wall.
223        slots = list(range(self.width))
224
225        # If there are empty spaces directly to the left/right of our proposed wall,
226        # then don't put a wall marker directly in front of those respective spaces.
227        # This prevents us blocking entrances into our submaze.
228
229        if (self.is_marker_relative(row, -1, pacai.core.board.MARKER_EMPTY)):
230            slots.remove(0)
231
232        if (len(slots) == 0):
233            return False
234
235        if (self.is_marker_relative(row, self.width, pacai.core.board.MARKER_EMPTY)):
236            slots.remove(self.width - 1)
237
238        # If we cannot provided the requested number of gaps, then don't put down the wall.
239        if (len(slots) <= discrete_gaps):
240            return False
241
242        # Randomize where we will put our walls.
243        rng.shuffle(slots)
244
245        # Skip the first slots (these are gaps), and place the rest.
246        for col in slots[discrete_gaps:]:
247            self.place_relative(row, col, pacai.core.board.MARKER_WALL)
248
249        # By placing a wall, we have created two new submazes (on each side of the wall).
250
251        # One submaze above.
252        self.submazes.append(Maze(row, self.width, anchor = self.anchor, root = self.root))
253
254        # One submaze below.
255        anchor_offset = pacai.core.board.Position(row + 1, 0)
256        self.submazes.append(Maze((self.height - row - 1), self.width, self.anchor.add(anchor_offset), self.root))
257
258        return True
259
260    def build(self,
261            rng: random.Random,
262            gaps: float = DEFAULT_GAPS, gap_factor: float = DEFAULT_GAP_FACTOR,
263            vertical: bool = True,
264            max_pellets: int = MAX_PELLETS, max_capsules: int = MAX_CAPSULES,
265            num_agents: int = DEFAULT_NUM_AGENTS,
266            ) -> None:
267        """
268        Build a full maze into this maze.
269        This happens in several parts:
270         - Building a "prison" which is the starting places for a team.
271         - Building the rest of the maze in the non-prison area.
272         - Filling the non-prison area with capture objects (food, capsules).
273         - Placing agents on the board prioritizing the left columns.
274        """
275
276        self.prison_width = rng.randint(0, MAX_PRISON_WIDTH)
277
278        for prison_col in range(self.prison_width):
279            # Compute the actual column the wall for this prison column is on.
280            wall_col = (2 * (prison_col + 1)) - 1
281
282            # Mark a full vertical of walls.
283            for row in range(self.height):
284                self.place_relative(row, wall_col, pacai.core.board.MARKER_WALL)
285
286            # Make an opening at either the top or bottom.
287            if (prison_col % 2 == 0):
288                self.place_relative(0, wall_col, pacai.core.board.MARKER_EMPTY)
289            else:
290                self.place_relative(self.height - 1, wall_col, pacai.core.board.MARKER_EMPTY)
291
292        # Everything outside the prison is now a submaze.
293        # We will not make a submaze for the prison, since we don't want to edit that.
294        anchor_offset = pacai.core.board.Position(0, 2 * self.prison_width)
295        non_prison_submaze = Maze(self.height, self.width - (2 * self.prison_width), self.anchor.add(anchor_offset), self.root)
296        self.submazes.append(non_prison_submaze)
297
298        # Build the rest of the maze.
299        for submaze in self.submazes:
300            submaze._build_submaze(rng, gaps = gaps, gap_factor = gap_factor, vertical = vertical)
301
302        # Place agents.
303        self._place_agents(rng, num_agents = num_agents)
304
305        # Place capture objects.
306        non_prison_submaze._place_capture_markers(rng, max_pellets = max_pellets, max_capsules = max_capsules)
307
308    def _build_submaze(self,
309            rng: random.Random,
310            gaps: float = DEFAULT_GAPS, gap_factor: float = DEFAULT_GAP_FACTOR,
311            vertical: bool = True) -> None:
312        """
313        Recursively build a maze by making a wall (which will create 0 or two submazes),
314        and then building a maze with a different orientation in the submaze.
315        """
316
317        # Stop when there is no more room in either orientation.
318        if ((self.height <= MIN_MAZE_AXIS_WIDTH) and (self.width <= MIN_MAZE_AXIS_WIDTH)):
319            return
320
321        # Decide between vertical and horizontal walls by seeing how much space is left across the primary axis
322        # (width if vertical, height if horizontal).
323        if (vertical):
324            axis_width = self.width
325        else:
326            axis_width = self.height
327
328        # If there is not enough room on this axis, flip the orientation.
329        if (axis_width < (MIN_MAZE_AXIS_WIDTH + 2)):
330            vertical = not vertical
331            if vertical:
332                axis_width = self.width
333            else:
334                axis_width = self.height
335
336        # Add a wall to the current maze
337        wall_slots = range(1, axis_width - 1)
338
339        if (len(wall_slots) == 0):
340            return
341
342        wall_index = rng.choice(wall_slots)
343        wall_added = self._add_wall(rng, wall_index, gaps = gaps, vertical = vertical)
344
345        # If we did not add a wall, then stop.
346        if (not wall_added):
347            return
348
349        # Recursively build submazes in the opposite orientation.
350        for submaze in self.submazes:
351            submaze._build_submaze(rng,
352                    gaps = max(1, gaps * gap_factor), gap_factor = gap_factor,
353                    vertical = (not vertical))
354
355    def _place_capture_markers(self, rng: random.Random,
356            min_pellets: int = MIN_PELLETS, max_pellets: int = MAX_PELLETS,
357            min_capsules: int = MIN_CAPSULES, max_capsules: int = MAX_CAPSULES,
358            ) -> None:
359        """
360        Place capture markers/objects on the board.
361        This includes pellets and capsules, but not agents.
362        """
363
364        # Choose a number of pellets and capsules to place, and randomize the placement order.
365        num_pellets = rng.randint(min_pellets, max_pellets)
366        num_capsules = rng.randint(min_capsules, max_capsules)
367
368        markers = ([pacai.pacman.board.MARKER_PELLET] * num_pellets) + ([pacai.pacman.board.MARKER_CAPSULE] * num_capsules)
369        rng.shuffle(markers)
370
371        # Collect all the empty locations, separated into dead-ends and non-dead-ends.
372        dead_ends = []
373        non_dead_ends = []
374
375        for row in range(self.height):
376            for col in range(self.width):
377                if (not self.is_marker_relative(row, col, pacai.core.board.MARKER_EMPTY)):
378                    continue
379
380                dead_end = True
381                for offset in pacai.core.board.CARDINAL_OFFSETS.values():
382                    if (not self.is_marker_relative(row + offset.row, col + offset.col, pacai.core.board.MARKER_EMPTY)):
383                        dead_end = False
384                        break
385
386                if (dead_end):
387                    dead_ends.append((row, col))
388                else:
389                    non_dead_ends.append((row, col))
390
391        # Shuffle the filling order, making sure that dead-ends get priority.
392        rng.shuffle(dead_ends)
393        rng.shuffle(non_dead_ends)
394        locations = dead_ends + non_dead_ends
395
396        # Keep filling until we run out of objects or locations.
397        for marker in markers:
398            (row, col) = locations.pop(0)
399            self.place_relative(row, col, marker)
400
401            if (len(locations) == 0):
402                break
403
404    def _place_agents(self, rng: random.Random, num_agents: int = DEFAULT_NUM_AGENTS) -> None:
405        """
406        Place agent in this maze.
407        Start on the far left column and randomly choose empty locations.
408        If there are not enough locations for agents, move to the next column.
409        Will raise an error if not all agents can be placed.
410        """
411
412        agent_indexes = list(range(num_agents))
413
414        for col in range(self.width):
415            empty_rows = [row for row in range(self.height) if self.is_marker_relative(row, col, pacai.core.board.MARKER_EMPTY)]
416            rng.shuffle(empty_rows)
417
418            for row in empty_rows:
419                marker = pacai.core.board.Marker(str(agent_indexes.pop(0)))
420                self.place_relative(row, col, marker)
421
422                if (len(agent_indexes) == 0):
423                    return
424
425        raise ValueError("Unable to find enough empty locations to place all agents.")
426
427def generate(
428        seed: int | None = None,
429        size: int | None = None,
430        gaps: float = DEFAULT_GAPS, gap_factor: float | None = None,
431        max_pellets: int = MAX_PELLETS, max_capsules: int = MAX_CAPSULES,
432        num_agents: int = DEFAULT_NUM_AGENTS,
433        ) -> pacai.core.board.Board:
434    """
435    Generate a random capture board.
436
437    General Procedure:
438     - Create a maze for just one team.
439       - Create a starting area ("prison") for the team.
440       - Recursively create a maze in the rest of the area be making a wall and then making a maze in each new "room" created by the wall.
441     - Place agents on the maze, prioritizing the starting area.
442     - Place pellets and capsules randomly, ensuring that dead-ends are filled first.
443     - Created a mirrored (on both axes) copy of the maze to create the other team's half of the board.
444       - Re-index all agents so that evens (and zero) are on the left and odds on the right.
445
446    This process was originally created by Dan Gillick and Jie Tang as a part of
447    UC Berkley's CS188 AI project:
448    https://ai.berkeley.edu/project_overview.html
449    """
450
451    if (seed is None):
452        seed = random.randint(0, 2**64)
453
454    rng = random.Random(seed)
455
456    if (size is None):
457        size = rng.choice(range(MIN_SIZE, MAX_RANDOM_SIZE + 1, 2))
458
459    if ((size < MIN_SIZE) or (size % 2 != 0)):
460        raise ValueError(f"Found disallowed random board size of {size}. Size must be an even number >= {MIN_SIZE}.")
461
462    logging.debug("Generating a Capture board with seed %d and size %d.", seed, size)
463
464    if (gap_factor is None):
465        gap_factor = min(MAX_GAP_FACTOR, rng.gauss(DEFAULT_GAP_FACTOR, GAP_FACTOR_STDEV))
466
467    maze = Maze(size, size)
468    maze.build(rng, gaps = gaps, gap_factor = gap_factor)
469    board = maze.to_board(f"random-{seed}")
470
471    return board
472
473def main() -> int:
474    """ Randomly generate a capture board and then print it. """
475
476    parser = argparse.ArgumentParser(description = "Randomly generate a capture board.")
477    parser = pacai.core.log.set_cli_args(parser)
478
479    parser.add_argument('--seed', dest = 'seed',
480            action = 'store', type = int, default = None,
481            help = 'The random seed for this board.')
482
483    parser.add_argument('--size', dest = 'size',
484            action = 'store', type = int, default = None,
485            help = ('The size for this board.'
486                    + f" Must be even and >= {MIN_SIZE}."
487                    + f" If not specified, a random number between {MIN_SIZE} and {MAX_RANDOM_SIZE} will be chosen."))
488
489    args = parser.parse_args()
490    args = pacai.core.log.init_from_args(parser, args)
491
492    board = generate(args.seed, args.size)
493    print(board)
494
495    return 0
496
497if __name__ == '__main__':
498    sys.exit(main())