pacai.core.board

  1import copy
  2import os
  3import re
  4import typing
  5
  6import edq.util.dirent
  7import edq.util.json
  8
  9import pacai.core.action
 10import pacai.util.reflection
 11
 12THIS_DIR: str = os.path.join(os.path.dirname(os.path.realpath(__file__)))
 13BOARDS_DIR: str = os.path.join(THIS_DIR, '..', 'resources', 'boards')
 14
 15SEPARATOR_PATTERN: re.Pattern = re.compile(r'^\s*-{3,}\s*$')
 16AGENT_PATTERN: re.Pattern = re.compile(r'^\d$')
 17
 18FILE_EXTENSION = '.board'
 19
 20DEFAULT_BOARD_CLASS: str = 'pacai.core.board.Board'
 21
 22MAX_AGENTS: int = 10
 23
 24MIN_HL_INTENSITY: int = 0
 25MAX_HL_INTENSITY: int = 1000
 26
 27class Marker(str):
 28    """
 29    A marker represents something that can appear on a board.
 30    These are similar to a game pieces in a traditional board game (like the top hat or dog in Monopoly).
 31    Another name for this class could be "Token",
 32    but that term is already overloaded in Computer Science.
 33
 34    Markers are used throughout the life of a game to refer to that component on the board.
 35    Markers may not be how a component is visually represented when the board is rendered
 36    (even when a board is rendered as text),
 37    but it will still be the identifier by which a piece is referenced.
 38    In a standard board, agents use the identifiers 0-9
 39    (and therefore there can be no more than 10 agents on a standard board).
 40    """
 41
 42    def is_empty(self) -> bool:
 43        """ Check if the marker is for an empty location. """
 44
 45        return (self == MARKER_EMPTY)
 46
 47    def is_wall(self) -> bool:
 48        """ Check if the marker is for a wall. """
 49
 50        return (self == MARKER_WALL)
 51
 52    def is_agent(self) -> bool:
 53        """ Check if the marker is for an agent. """
 54
 55        return (self in AGENT_MARKERS)
 56
 57    def get_agent_index(self) -> int:
 58        """
 59        If this marker is an agent, return its index.
 60        Otherwise, return -1.
 61        """
 62
 63        if (not self.is_agent()):
 64            raise ValueError(f"Marker value ('{self}') is not an agent index.")
 65
 66        return int(self)
 67
 68MARKER_EMPTY: Marker = Marker(' ')
 69"""
 70A marker for an empty location.
 71Empty markers are not stored into the board when reading from a string.
 72However, empty markers will be placed in grid representations of a board.
 73"""
 74
 75MARKER_WALL: Marker = Marker('%')
 76MARKER_AGENT_0: Marker = Marker('0')
 77MARKER_AGENT_1: Marker = Marker('1')
 78MARKER_AGENT_2: Marker = Marker('2')
 79MARKER_AGENT_3: Marker = Marker('3')
 80MARKER_AGENT_4: Marker = Marker('4')
 81MARKER_AGENT_5: Marker = Marker('5')
 82MARKER_AGENT_6: Marker = Marker('6')
 83MARKER_AGENT_7: Marker = Marker('7')
 84MARKER_AGENT_8: Marker = Marker('8')
 85MARKER_AGENT_9: Marker = Marker('9')
 86
 87AGENT_MARKERS: set[Marker] = {
 88    MARKER_AGENT_0,
 89    MARKER_AGENT_1,
 90    MARKER_AGENT_2,
 91    MARKER_AGENT_3,
 92    MARKER_AGENT_4,
 93    MARKER_AGENT_5,
 94    MARKER_AGENT_6,
 95    MARKER_AGENT_7,
 96    MARKER_AGENT_8,
 97    MARKER_AGENT_9,
 98}
 99
100BASE_MARKERS: dict[str, Marker] = {
101    MARKER_EMPTY: MARKER_EMPTY,
102    MARKER_WALL: MARKER_WALL,
103}
104
105for agent_marker in AGENT_MARKERS:
106    BASE_MARKERS[agent_marker] = agent_marker
107
108class Position(edq.util.json.DictConverter):
109    """
110    An immutable 2-dimension location
111    representing row/y/height/y-offset and col/x/width/x-offset.
112    """
113
114    ROW_INDEX: int = 0
115    COL_INDEX: int = 1
116
117    MAX_SIZE: int = 1000000
118
119    def __init__(self, row: int, col: int) -> None:
120        if ((abs(row) > Position.MAX_SIZE) or (abs(col) > Position.MAX_SIZE)):
121            raise ValueError(f"Dimensions {(row, col)} is greater than max of {(Position.MAX_SIZE, Position.MAX_SIZE)}.")
122
123        self._row = row
124        """ The row/y/height of this position. """
125
126        self._col = col
127        """ The col/x/width of this position. """
128
129        self._hash: int = (row * Position.MAX_SIZE) + col
130        """
131        Cache the hash value to speed up checks.
132        This hash value is accurate as long as the board dimensions are under one million.
133        """
134
135    @property
136    def row(self) -> int:
137        """ Get this position's row. """
138
139        return self._row
140
141    @property
142    def col(self) -> int:
143        """ Get this position's col. """
144
145        return self._col
146
147    def add(self, other: 'Position') -> 'Position':
148        """
149        Add another position (offset) to this one and return the result.
150        """
151
152        return Position(self._row + other._row, self._col + other._col)
153
154    def apply_action(self, action: pacai.core.action.Action) -> 'Position':
155        """
156        Return a position that represents moving in the cardinal direction indicated by the given action.
157        If the action is not one of the cardinal actions (N/E/S/W),
158        then the same position will be returned.
159        """
160
161        offset = CARDINAL_OFFSETS.get(action, None)
162        if (offset is None):
163            return self
164
165        return self.add(offset)
166
167    def __lt__(self, other: 'Position') -> bool:  # type: ignore[override]
168        return (self._hash < other._hash)
169
170    def __eq__(self, other: object) -> bool:
171        if (not isinstance(other, Position)):
172            return False
173
174        return (self._hash == other._hash)
175
176    def __hash__(self) -> int:
177        return self._hash
178
179    def __str__(self) -> str:
180        return f"({self._row}, {self._col})"
181
182    def __repr__(self) -> str:
183        return str(self)
184
185    def to_dict(self) -> dict[str, typing.Any]:
186        return {
187            'row': self._row,
188            'col': self._col,
189        }
190
191    @classmethod
192    def from_dict(cls, data: dict[str, typing.Any]) -> typing.Any:
193        return Position(row = data['row'], col = data['col'])
194
195CARDINAL_OFFSETS: dict[pacai.core.action.Action, Position] = {
196    pacai.core.action.NORTH: Position(-1, 0),
197    pacai.core.action.EAST: Position(0, 1),
198    pacai.core.action.SOUTH: Position(1, 0),
199    pacai.core.action.WEST: Position(0, -1),
200}
201
202class Highlight(edq.util.json.DictConverter):
203    """
204    A class representing a request to highlight/emphasize a position on the board.
205    """
206
207    def __init__(self,
208            position: Position,
209            intensity: int | float | None,
210            ) -> None:
211        self.position = position
212        """ The position of this highlight. """
213
214        if (isinstance(intensity, float)):
215            if ((intensity < 0.0) or (intensity > 1.0)):
216                raise ValueError(f"Floating point highlight intensity must be in [0.0, 1.0], found: {intensity}.")
217
218            intensity = int(intensity * MAX_HL_INTENSITY)
219
220        if (isinstance(intensity, int)):
221            if ((intensity < MIN_HL_INTENSITY) or (intensity > MAX_HL_INTENSITY)):
222                raise ValueError(f"Integer highlight intensity must be in [MIN_HL_INTENSITY, MAX_HL_INTENSITY], found: {intensity}.")
223
224        self.intensity: int | None = intensity
225        """
226        The highlight intensity associated with this position,
227        or None if this highlight should be cleared.
228        """
229
230    def get_float_intensity(self) -> float | None:
231        """ Get the highlight intensity in [0.0, 1.0]. """
232
233        if (self.intensity is None):
234            return None
235
236        return self.intensity / MAX_HL_INTENSITY
237
238    def to_dict(self) -> dict[str, typing.Any]:
239        return {
240            'position': self.position.to_dict(),
241            'intensity': self.intensity,
242        }
243
244    @classmethod
245    def from_dict(cls, data: dict[str, typing.Any]) -> typing.Any:
246        data = {
247            'position': Position.from_dict(data['position']),
248            'intensity': data['intensity'],
249        }
250        return cls(**data)
251
252class AdjacencyString(str):
253    """
254    A string that indicates which directions have something adjacent.
255    This string is always four characters long,
256    which each character being 'T' for true and 'F' for false.
257    The characters are ordered North, East, South, West (NESW).
258    So, 'TFTF' indicates that there are things to the north and south.
259    """
260
261    TRUE = 'T'
262    FALSE = 'F'
263
264    NORTH_INDEX = 0
265    EAST_INDEX = 1
266    SOUTH_INDEX = 2
267    WEST_INDEX = 3
268
269    def __new__(cls, raw_text: str) -> 'AdjacencyString':
270        text = super().__new__(cls, raw_text.strip().upper())
271
272        if (len(text) != 4):
273            raise ValueError(f"AdjacencyString must have exactly four characters, found {len(text)}.")
274
275        for char in text:
276            if (char not in {AdjacencyString.TRUE, AdjacencyString.FALSE}):
277                raise ValueError(f"AdjacencyString must only have '{AdjacencyString.TRUE}' or '{AdjacencyString.FALSE}', found '{text}'.")
278
279        return text
280
281    def north(self) -> bool:
282        """ Check if there is an adjacency to the north. """
283
284        return (self[AdjacencyString.NORTH_INDEX] == AdjacencyString.TRUE)
285
286    def east(self) -> bool:
287        """ Check if there is an adjacency to the east. """
288
289        return (self[AdjacencyString.EAST_INDEX] == AdjacencyString.TRUE)
290
291    def south(self) -> bool:
292        """ Check if there is an adjacency to the south. """
293
294        return (self[AdjacencyString.SOUTH_INDEX] == AdjacencyString.TRUE)
295
296    def west(self) -> bool:
297        """ Check if there is an adjacency to the west. """
298
299        return (self[AdjacencyString.WEST_INDEX] == AdjacencyString.TRUE)
300
301class Board(edq.util.json.DictConverter):
302    """
303    A board represents the positional components of a game.
304    For example, a board contains the agents, walls and collectable items.
305
306    Most types of games (anything that would subclass pacai.core.game.Game) should probably
307    also subclass this to make their own type of board.
308
309    On disk, boards are represented in files that have two sections (divided by a '---' line).
310    The first section is a JSON object that holds any options for the board.
311    The second section is a textual representation of the board.
312    The specific board class (usually specified by the board options) should know how to interpret the text-based board.
313    Agents on the text-based board are numbered by their index (0-9).
314
315    Walls are treated (and stored) specially,
316    and are not expected to change once a board is created (they are considered fixed).
317
318    Callers should generally stick to the provided methods,
319    as some of the underlying data structures may be optimized for performance.
320    """
321
322    def __init__(self,
323            source: str,
324            board_text: str | None = None,
325            markers: dict[str, Marker] | None = None,
326            additional_markers: list[str] | None = None,
327            strip: bool = True,
328            search_target: Position | dict[str, typing.Any] | None = None,
329            _height: int | None = None,
330            _width: int | None = None,
331            _walls: set[Position] | None = None,
332            _nonwall_objects: dict[Marker, set[Position]] | None = None,
333            _agent_initial_positions: dict[Marker, Position] | None = None,
334            **kwargs: typing.Any) -> None:
335        """
336        Construct a board.
337        The board details will either be parsed from `board_text` is provided,
338        or taken directly from the given underscore arguments.
339        """
340
341        self.source: str = source
342        """ Where this board was loaded from. """
343
344        if (markers is None):
345            markers = BASE_MARKERS.copy()
346
347        self._markers: dict[str, Marker] = markers
348        """ Map the text for a marker to the actual marker. """
349
350        if (additional_markers is not None):
351            for marker in additional_markers:
352                self._markers[marker] = Marker(marker)
353
354        self.height: int = -1
355        """ The height (number of rows, "y") of the board. """
356
357        self.width: int = -1
358        """ The width (number of columns, "x") of the board. """
359
360        self._walls: set[Position] = set()
361        """ The walls for this board. """
362
363        self._neighbor_cache: dict[Position, list[tuple[pacai.core.action.Action, Position]]]  = {}
364        """
365        Keep a cache of all neighbor locations.
366        Note that neighbors only depend on the size of the board and walls.
367        Computing neighbors is a high-throughput activity, and therefore justifies a cache.
368        Neighbors will be shallow copied when a board is copied,
369        therefore all successor boards will share the same cache.
370        """
371
372        self._nonwall_objects: dict[Marker, set[Position]] = {}
373        """ All the non-wall objects that appear on the board. """
374
375        self._agent_initial_positions: dict[Marker, Position] = {}
376        """ Keep track of where each agent started. """
377
378        if (isinstance(search_target, dict)):
379            search_target = Position.from_dict(search_target)
380
381        self.search_target: Position | None = search_target  # type: ignore
382        """ Some boards (especially mazes) will have a specific positional search target. """
383
384        self._is_shallow: bool = False
385        """
386        Keep track of if the variable components of the board have been copied.
387        We will only make a copy of these component on a write.
388        """
389
390        # The board text has been provided, parse the data from it.
391        if (board_text is not None):
392            height, width, all_objects, agents = self._process_text(board_text, strip = strip)
393
394            walls = set()
395            if (MARKER_WALL in all_objects):
396                walls = all_objects[MARKER_WALL]
397                del all_objects[MARKER_WALL]
398
399            self.height = height
400            self.width = width
401            self._walls = walls
402            self._nonwall_objects = all_objects
403            self._agent_initial_positions = agents
404        else:
405            # No board text has been provided, all attributes must be provided.
406            checks = [
407                (_height, 'height'),
408                (_width, 'width'),
409                (_nonwall_objects, 'objects'),
410                (_agent_initial_positions, 'agent initial positions'),
411            ]
412
413            for (value, label) in checks:
414                if (value is None):
415                    raise ValueError(f"Board {label} cannot be empty when the board text is not supplied.")
416
417            self.height = _height  # type: ignore
418            self.width = _width  # type: ignore
419            self._walls = _walls  # type: ignore
420            self._nonwall_objects = _nonwall_objects  # type: ignore
421            self._agent_initial_positions = _agent_initial_positions  # type: ignore
422
423    def copy(self) -> 'Board':
424        """ Get a copy of this board. """
425
426        # Make a shallow copy.
427        new_board = copy.copy(self)
428
429        # Mark both ourself and the copy as shallow.
430        self._is_shallow = True
431        new_board._is_shallow = True
432
433        return new_board
434
435    def _copy_on_write(self) -> None:
436        """ Copy any copy-on-write components if necessary. """
437
438        if (not self._is_shallow):
439            return
440
441        self._nonwall_objects = {marker: positions.copy() for (marker, positions) in self._nonwall_objects.items()}
442        self._is_shallow = False
443
444    def size(self) -> int:
445        """ Get the total number of places in this board. """
446
447        return self.height * self.width
448
449    def get_corners(self, offset: int = 0) -> tuple[Position, Position, Position, Position]:
450        """
451        Get the corner positions of this board (ordered as NE, SE, SW, NW).
452
453        The offset is how much to move diagonally in from each corner.
454        By default, it is zero and will be exactly at each corner position.
455        However many board have a border of walls,
456        in this case an offset of 1 will return those non-border corners.
457        """
458
459        # Add 1 for zero indexing.
460        high_offset = (1 + offset)
461
462        return (
463            Position(offset, self.width - high_offset),
464            Position(self.height - high_offset, self.width - high_offset),
465            Position(self.height - high_offset, offset),
466            Position(offset, offset),
467        )
468
469    def agent_count(self) -> int:
470        """
471        Return the number of agents supported by this board.
472        This counts the number of initial position seen for agents when the board was first parsed.
473        """
474
475        return len(self._agent_initial_positions)
476
477    def agent_indexes(self) -> list[int]:
478        """
479        Get the indexes for all the agents supposed by this board.
480        The reported agents are agents supported by the board, not just agents currently on the board.
481        """
482
483        agent_indexes = []
484        for marker in self._agent_initial_positions:
485            agent_indexes.append(marker.get_agent_index())
486
487        return agent_indexes
488
489    def get(self, position: Position) -> set[Marker]:
490        """
491        Get all non-wall objects at the given position.
492        """
493
494        self._check_bounds(position)
495
496        found_objects: set[Marker] = set()
497        for (marker, objects) in self._nonwall_objects.items():
498            if position in objects:
499                found_objects.add(marker)
500
501        return found_objects
502
503    def get_marker_positions(self, marker: Marker) -> set[Position]:
504        """ Get all the non-wall positions for a specific marker. """
505
506        return self._nonwall_objects.get(marker, set()).copy()
507
508    def get_marker_count(self, marker: Marker) -> int:
509        """ Get a count of the non-wall positions for a specific marker. """
510
511        return len(self._nonwall_objects.get(marker, []))
512
513    def get_walls(self) -> set[Position]:
514        """ Get all the walls. """
515
516        return self._walls
517
518    def remove_agent(self, agent_index: int) -> None:
519        """
520        Remove all traces of an agent from the board,
521        this includes markers and initial positions.
522        The agent's position will be replaces with an empty location.
523        """
524
525        if ((agent_index < 0) or (agent_index >= MAX_AGENTS)):
526            return
527
528        self._copy_on_write()
529
530        marker = Marker(str(agent_index))
531
532        if (marker in self._nonwall_objects):
533            del self._nonwall_objects[marker]
534
535        if (marker in self._agent_initial_positions):
536            del self._agent_initial_positions[marker]
537
538    def remove_marker(self, marker: Marker, position: Position) -> None:
539        """
540        Remove the specified marker from the given position if it exists.
541        """
542
543        self._check_bounds(position)
544        self._copy_on_write()
545
546        markers = self._nonwall_objects.get(marker)
547        if (markers is None):
548            return
549
550        markers.discard(position)
551
552    def place_marker(self, marker: Marker, position: Position) -> None:
553        """
554        Place a marker at the given position.
555        """
556
557        self._check_bounds(position)
558        self._copy_on_write()
559
560        if (marker not in self._nonwall_objects):
561            self._nonwall_objects[marker] = set()
562
563        self._nonwall_objects[marker].add(position)
564
565    def get_neighbors(self, position: Position) -> list[tuple[pacai.core.action.Action, Position]]:
566        """
567        Get positions that are directly touching (via cardinal directions) the given position
568        without being inside a wall,
569        and the action it would take to get there.
570
571        Note that this is a high-throughput piece of code, and may contain optimizations.
572        """
573
574        # Check the neighbor cache.
575        if (position in self._neighbor_cache):
576            return self._neighbor_cache[position]
577
578        neighbors = []
579        for (action, offset) in CARDINAL_OFFSETS.items():
580            neighbor = position.add(offset)
581
582            if (not self._check_bounds(neighbor, throw = False)):
583                continue
584
585            if (self.is_wall(neighbor)):
586                continue
587
588            neighbors.append((action, neighbor))
589
590        # Save to the neighbor cache.
591        self._neighbor_cache[position] = neighbors
592
593        return neighbors
594
595    def get_adjacency(self, position: Position, marker: Marker) -> AdjacencyString:
596        """
597        Look at the neighbors of the specified position to see if the given marker is adjacent in any direction.
598        An out-of-bounds position always counts as non-adjacent.
599        """
600
601        # Get the set of positions to compare against.
602        if (marker == MARKER_WALL):
603            positions = self._walls
604        else:
605            positions = self._nonwall_objects[marker]
606
607        adjacency = []
608        for direction in pacai.core.action.CARDINAL_DIRECTIONS:
609            neighbor = position.apply_action(direction)
610
611            adjacent = 'F'
612            if (neighbor in positions):
613                adjacent = 'T'
614
615            adjacency.append(adjacent)
616
617        return AdjacencyString(''.join(adjacency))
618
619    def get_adjacent_walls(self, position: Position) -> AdjacencyString:
620        """ Shortcut for get_adjacency() with MARKER_WALL. """
621
622        return self.get_adjacency(position, MARKER_WALL)
623
624    def is_empty(self, position: Position) -> bool:
625        """ Check if the given position is empty. """
626
627        for objects in self._nonwall_objects.values():
628            if (position in objects):
629                return False
630
631        return (position not in self._walls)
632
633    def is_marker(self, marker: Marker, position: Position) -> bool:
634        """ Check if the given position is has the target marker. """
635
636        # Get the set of positions to compare against.
637        if (marker == MARKER_WALL):
638            positions = self._walls
639        else:
640            positions = self._nonwall_objects[marker]
641
642        return (position in positions)
643
644    def is_wall(self, position: Position) -> bool:
645        """ Check if the given position is a wall. """
646
647        # Note that we are not using is_marker() for a slight speedup (since this is a common method).
648        return (position in self._walls)
649
650    def get_agent_position(self, agent_index: int) -> Position | None:
651        """
652        Get the position of an agent,
653        or None if the agent is not on the board.
654        """
655
656        marker = Marker(str(agent_index))
657        positions = self._nonwall_objects.get(marker, set())
658
659        if (len(positions) > 1):
660            raise ValueError(f"Found too many agent positions ({len(positions)}) for agent {marker}. There should only be one.")
661
662        for position in positions:
663            return position
664
665        return None
666
667    def get_agent_initial_position(self, agent_index: int) -> Position | None:
668        """
669        Get the initial position of an agent,
670        or None if the agent was never on the board.
671        """
672
673        marker = Marker(str(agent_index))
674        return self._agent_initial_positions.get(marker, None)
675
676    def get_nonwall_string(self) -> str:
677        """
678        Get a string representation of the non-wall objects on the board.
679        This should not be used for any performant code,
680        but provides a consistent way of identifying the "state" of the board.
681        """
682
683        raw_nonwall_objects = []
684        for (marker, positions) in sorted(self._nonwall_objects.items()):
685            raw_nonwall_objects.append(f"{marker}::{','.join([str(position) for position in sorted(positions)])}")
686
687        return '||'.join(raw_nonwall_objects)
688
689    def to_grid(self) -> list[list[Marker]]:
690        """ Convert this board to a 2-d grid. """
691
692        grid = [[MARKER_EMPTY] * self.width for _ in range(self.height)]
693
694        # Place walls first.
695        for position in self._walls:
696            grid[position.row][position.col] = MARKER_WALL
697
698        # Place non-agents.
699        for (marker, positions) in self._nonwall_objects.items():
700            if (marker.is_agent()):
701                continue
702
703            for position in positions:
704                grid[position.row][position.col] = marker
705
706        # Place agents.
707        for (marker, positions) in self._nonwall_objects.items():
708            if (not marker.is_agent()):
709                continue
710
711            for position in positions:
712                grid[position.row][position.col] = marker
713
714        return grid
715
716    def __str__(self) -> str:
717        """ Get a rough string representation of the board. """
718
719        grid = self.to_grid()
720        return "\n".join([''.join(row) for row in grid])
721
722    def _check_bounds(self, position: Position, throw: bool = False) -> bool:
723        """
724        Check if the given position is out-of-bonds for this board.
725        Return True if the position is in bounds, False otherwise.
726        If |throw| is True, then raise an exception.
727        """
728
729        if ((position.row < 0) or (position.col < 0) or (position.row >= self.height) or (position.col >= self.width)):
730            if (throw):
731                raise ValueError(f"Position ('{str(position)}') is out-of-bounds.")
732
733            return False
734
735        return True
736
737    def to_dict(self) -> dict[str, typing.Any]:
738        all_objects = {}
739        for (marker, positions) in sorted(self._nonwall_objects.items()):
740            all_objects[str(marker)] = [position.to_dict() for position in sorted(positions)]
741
742        agent_initial_positions = {}
743        for (marker, position) in sorted(self._agent_initial_positions.items()):
744            agent_initial_positions[str(marker)] = position.to_dict()
745
746        search_target: Position | dict[str, typing.Any] | None = self.search_target
747        if (isinstance(search_target, Position)):
748            search_target = search_target.to_dict()
749
750        return {
751            'source': self.source,
752            'markers': {key: str(marker) for (key, marker) in sorted(self._markers.items())},
753            'height': self.height,
754            'width': self.width,
755            'search_target': search_target,
756            '_walls': [position.to_dict() for position in sorted(self._walls)],
757            '_nonwall_objects': all_objects,
758            '_agent_initial_positions': agent_initial_positions,
759        }
760
761    @classmethod
762    def from_dict(cls, data: dict[str, typing.Any]) -> typing.Any:
763        all_objects: dict[Marker, set[Position]] = {}
764        for (raw_marker, raw_positions) in data['_nonwall_objects'].items():
765            all_objects[Marker(raw_marker)] = {Position.from_dict(raw_position) for raw_position in raw_positions}
766
767        agent_initial_positions = {}
768        for (raw_marker, raw_position) in data['_agent_initial_positions'].items():
769            agent_initial_positions[Marker(raw_marker)] = Position.from_dict(raw_position)
770
771        search_target = data.get('search_target', None)
772        if (search_target is not None):
773            search_target = Position.from_dict(search_target)
774
775        return cls(
776            source = data['source'],
777            markers = {key: Marker(marker) for (key, marker) in data['markers'].items()},
778            search_target = search_target,
779            _height = data['height'],
780            _width = data['width'],
781            _walls = {Position.from_dict(raw_position) for raw_position in data.get('_walls', [])},
782            _nonwall_objects = all_objects,
783            _agent_initial_positions = agent_initial_positions,
784        )
785
786    def _process_text(self,
787            board_text: str,
788            strip: bool = True,
789            ) -> tuple[int, int, dict[Marker, set[Position]], dict[Marker, Position]]:
790        """
791        Parse out a board from text.
792        """
793
794        if (strip):
795            board_text = board_text.strip()
796
797        if (len(board_text) == 0):
798            raise ValueError('A board cannot be empty.')
799
800        lines = board_text.split("\n")
801
802        width: int = -1
803        all_objects: dict[Marker, set[Position]] = {}
804        agents: dict[Marker, Position] = {}
805
806        row_skip_count = 0
807        for (raw_row, line) in enumerate(lines):
808            row = raw_row - row_skip_count
809
810            if (strip):
811                line = line.strip()
812
813            raw_markers = self._split_line(line)
814
815            # Skip empty lines.
816            if (len(raw_markers) == 0):
817                row_skip_count += 1
818                continue
819
820            if (width == -1):
821                width = len(raw_markers)
822
823            if (width != len(raw_markers)):
824                raise ValueError(f"Unexpected width ({len(raw_markers)}) for row at index {row}. Expected {width}.")
825
826            for (col, raw_marker) in enumerate(raw_markers):
827                position = Position(row, col)
828
829                marker = self._translate_marker(raw_marker, position)
830                if (marker is None):
831                    raise ValueError(f"Unknown marker '{raw_marker}' found at position ({row}, {col}).")
832
833                if (marker.is_empty()):
834                    continue
835
836                if (marker not in all_objects):
837                    all_objects[marker] = set()
838
839                all_objects[marker].add(position)
840
841                if (marker.is_agent()):
842                    if (marker in agents):
843                        raise ValueError(f"Duplicate agents ('{marker}') seen on board.")
844
845                    agents[marker] = position
846
847        if (width <= 0):
848            raise ValueError("A board must have at least one column.")
849
850        height: int = len(lines) - row_skip_count
851
852        return height, width, all_objects, agents
853
854    def _split_line(self, line: str) -> list[str]:
855        """
856        Split a line in the text representation of a board.
857        By default, this just splits into characters.
858        """
859
860        return list(line)
861
862    def _translate_marker(self, text: str, position: Position) -> Marker | None:
863        """
864        Translate the given text into the correct marker.
865        By default, this just looks up the text in self._markers.
866        """
867
868        return self._markers.get(text, None)
869
870def load_path(path: str, **kwargs: typing.Any) -> Board:
871    """
872    Load a board from a file.
873    If the given path does not exist,
874    try to prefix the path with the standard board directory and suffix with the standard extension.
875    """
876
877    raw_path = path
878
879    # If the path does not exist, try the boards directory.
880    if (not os.path.exists(path)):
881        path = os.path.join(BOARDS_DIR, path)
882
883        # If this path does not have a good extension, add one.
884        if (os.path.splitext(path)[-1] != FILE_EXTENSION):
885            path = path + FILE_EXTENSION
886
887    if (not os.path.exists(path)):
888        raise ValueError(f"Could not find board, path does not exist: '{raw_path}'.")
889
890    text = edq.util.dirent.read_file(path, strip = False)
891    return load_string(raw_path, text, **kwargs)
892
893def load_string(source: str, text: str, **kwargs: typing.Any) -> Board:
894    """ Load a board from a string. """
895
896    separator_index = -1
897    lines = text.split("\n")
898
899    for (i, line) in enumerate(lines):
900        if (SEPARATOR_PATTERN.match(line)):
901            separator_index = i
902            break
903
904    if (separator_index == -1):
905        # No separator was found.
906        options_text = ''
907        board_text = "\n".join(lines)
908    else:
909        options_text = "\n".join(lines[:separator_index])
910        board_text = "\n".join(lines[(separator_index + 1):])
911
912    options_text = options_text.strip()
913    if (len(options_text) == 0):
914        options = {}
915    else:
916        options = edq.util.json.loads(options_text)
917
918    options.update(kwargs)
919
920    board_class = options.get('class', DEFAULT_BOARD_CLASS)
921    return pacai.util.reflection.new_object(board_class, source, board_text, **options)  # type: ignore[no-any-return]
922
923def create_empty(source: str, height: int, width: int, **kwargs: typing.Any) -> Board:
924    """
925    Create an empty board with the given dimensions.
926    """
927
928    text = ((MARKER_EMPTY * width) + "\n") * height
929    return load_string(source, text, strip = False)