Skip to content

Basic Tutorial

Jump to bottom
Lord of Galaxy edited this page Aug 13, 2022 · 4 revisions

Over the course of this tutorial, you will learn about the basic features of the API and understand the simple mining agent supplied with the dev-kit (v1.1). You will need to have downloaded and installed the dev-kit, and verified that it works properly.

Basic Structure of the Code

The player.py file contains a basic mining agent via a class named Player. It is required to inherit from Agent, and implement a constructor and a move method. Your own agents must also be present in a file named player.py, and include a class named Player that inherits from Agent. This Player class forms the main component of your agent.

The Constructor

The constructor for the Player class must have a positional argument player (which is 1 if your agent will be player 1 and 2 if your agent will be player 2 for the game), along with any subset of the following keyword-only arguments:

  • game_params: This is an instance of the GameParams class, which gives you all the necessary information about the (current instance) of the game. You are recommended to check out the class definition in params.py for more details.
  • time_limits: This is an instance of the TimeLimits class, which gives important information about the time limits for your agent, including the total time (TimeLimits.MAIN) and increment (TimeLimits.INCREMENT), similar to chess.
  • map_w: The width of the game map (an integer).
  • map_h: The height of the game map (an integer).
  • game_map: The initial state of the game's map. The game map is a 2D numpy array of size (map_w, map_h) (with dtype=object). Each element of the array corresponds to a single tile in the game map, and is either None or has type Entity or ResourceDeposit. We will go over the game map in greater detail later.
    Other keyword-only arguments may be added later, so ensure that you have a **kwargs as well to capture those parameters that you don't use.

The supplied agent simply stores the game parameters, time limits, and map width and height for later use. It also creates a few variables to store information regarding the "goals" system, and the pathfinding. We will explain this later.

The move Function

The move function has exactly 4 parameters (not including self):

  1. time: The move number (an integer).
  2. game_map: The game map again, which we shall go over later.
  3. p1_inv: The inventory for player 1. We will go over the Inventory class later.
  4. p2_inv: The inventory for player 2.

The close Function

The close function is optional and takes no parameters. This is called after the end of the game and should be used to safely close any resources your agent consumes. The supplied agent uses it to print out some debug information, but this is not the intended purpose of close as anything printed by your agent is simply discarded.

A Very Simple Agent

This first agent does almost nothing, but will get your started and teach you about the fundamentals of building an agent. We will go over the supplied agent after this one.

The Code

class Player(Agent):
    def __init__(self, player: int, **kwargs):
        super().__init__(player, **kwargs)

    def move(self, time: int, game_map: npt.NDArray[object], p1_inv: Inventory, p2_inv: Inventory) -> list[Action]:
        moves: dict[int, Action] = {}  # maps ids to actions
        p_inv = p1_inv if self.player == 1 else p2_inv
        d1: Direction = Direction.RIGHT if self.player == 1 else Direction.LEFT
        d2: Direction = Direction.RIGHT if self.player == 2 else Direction.LEFT

        miners = p_inv.miners  # get a list of all miners
        if len(miners) == 0:
            return []
        m = miners[0]  # get the first miner
        d = d1 if len(m.cargo) < m.cargo_space else d2
        rp = m.pos + d.vec  # get the position of the miner's next tile
        if isinstance(game_map[rp], ResourceDeposit):
            moves[m.id] = Action(m).mine(d)  # mine
        elif isinstance(game_map[m.pos], Base) and len(m.cargo) == m.cargo_space:
            moves[m.id] = Action(m).cargo([])  # if the miner is at a base, deposit its cargo
        else:
            moves[m.id] = Action(m).move(d)  # move the miner
        return list(moves.values())

Understanding the Code

The constructor for this simple agent does nothing except pass on the parameters to the Agent class. Note that the Agent class already stores the which player the agent is in Agent.player, so you can access it with self.player in Player without setting it yourself.

The move function does very little. First, it creates a moves dictionary mapping Entity IDs to Actions.

The Entity class is the base class for all the player (or enemy) controllable objects on the game map. The concrete subclasses of this type include both the ship types (Miner and Fighter) and both the main building types (Base and Turret).

The Action class is what will be used to specify an action for the entities that the player owns. Its constructor takes the Entity itself as the sole argument. It then supplies various functions that allow you to command the entity to take various actions.

The next line gets the player's inventory, after which we have basic direction determination logic to ensure the miners move towards the center to find resources and back to the base to deposit them. We then fetch the list of player-owned miners, and find the first one (if it exists). If the player owns no miners, we simply do nothing on the turn.

Once we have a miner, we determine if it needs to mine or deposit resources. Accordingly, we either mine resources (with Action.mine), deposit resources (with Action.cargo) or move in the required direction (with Action.move). We hope that this section of the code is mostly self-explanatory.

The Basic Agent

Now we are ready to go over the basic agent supplied with the dev-kit. We shall first briefly go over the path-finding system used before diving into the main agent code.

Path-Finding

Fast and effective path-finding is critical to success in this game, as it involves moving a large number of agents around, preferably without wasting too many moves. To achieve, we shall be using an algorithm called Space-Time A-Star, based on the famous A-Star algorithm. A proper explanation of the two algorithms is outside the scope of this tutorial, and interested readers are recommended to check out the links above to learn more.

The API in path_finding.py consists of the functions space_time_astar, cleanup_reservations and clear_reservations. cleanup_reservations is used to ensure that the reservation table does no grow too large, while clear_reservations is used to clear reservations for an agent in order to, say, modify its goal or recomptute its path. Thus, we shall focus our attention upon space_time_astar. This function takes a long list of parameters:

  1. agent_id: The (integer) ID of the agent for which we must compute a path.
  2. start: The starting position for the agent.
  3. target: The target we wish to find a path to.
  4. time: The starting time (move number).
  5. maze: A proper representation of the map within which we must path-find. It is a 2D numpy array (with dtype=np.integer) of size (width, height) where width and height are the width and height of the map (respectively). Every entry in it is an integer that represents the maximum number of (player-owned) ships that can occupy that position at any given time. Thus, an entry of 0 represents an obstacle, while an entry larger than 1 represents a building that can hold multiple ships.
  6. reserved: A reservation table, used by the algorithm to (mostly) prevent ship collisions. It maps the time (move number) to a dictionary that itself maps positions to lists of agent IDs, which represents the list of agents occupying that position at that time.
  7. depth: The depth to which to make reservations (in the reservation table) for the path found.
  8. pause: The amount of time for which the agent will pause at it's target after getting there.

The function then returns a path (a list of positions) starting at start and ending at target (if it finds one), and makes the necessary reservations in the reservation table. Additionally, cleanup_reservations(reserved, time) removes all reservations made for time time, while clear_reservations(reserved, agent_id) removes all reservations for the agent with ID agent_id.

Exception Handling and Performance Measuring

We shift the actual agent code to a protected function _move and instead use move for handling any exceptions and logging the time taken per move for debugging purposes. This can be removed in your submission as it will have no effect as long as your agent functions correctly. The time taken will later be printed using the close function, again for debugging purposes.

Core Agent Logic

Similar to the simpler agent, we start by creating the moves dict and getting the player inventory. Next, we create an action for every single Ship (both Miners and Fighters) that we own. This is followed by checking if every one of these ships has a goal and assigning goals to those that do not. Next, we compute paths and moves for all the ships as needed. Finally, we add any auxillary actions, specifically the building of new Miners any time we have fewer than 20, and return the list of all actions.

The Goals System

We now return our attention to the list of variables we defined in the constructor, specifically:

self.all_goals: set[vec2] = set()  # a set of all goals currently being targeted
self.goals: dict[int, tuple[vec2, int]] = {}  # maps ship ids to (goal, pause)
self.reached_goal: dict[int, int] = {}  # maps ship ids to the time they reached their goals
self.next_reset: dict[int, int] = {}  # maps ship id to the time when their path needs to be re-computed
self.reserved: dict[int, dict[vec2, list[int]]] = {}  # this is a reservation table for path finding purposes
self.paths: dict[int, dict[int, vec2]] = {}  # maps ship ids to paths, where a path maps time to position

The first variable is a set of all positions that are currently the target of some ship. The second maps ship IDs to their goals, where a goal is a tuple consisting of a target position along with a integer indicating the number of turns the ship should pause for once it reaches its target in order to achieve its goal (for instance, mining requires 4 turns to complete). The third variable is a dictionary that is used to keep track of when any particular ship reached its goal, which is used to determine when a new goal must be allotted to it. The fifth variable is the reservation table used by the path-finding described above. The last variable maps ship's ID to the path that has been computed for the ship, which is cached for performance purposes (without it, the paths would have to be recomputed every turn, which is extremely inefficient).

These variables together are used for the goals system, which allots a unique goal to each ship owned by the player to try and make good use of all available ships. It is strongly recommended that you replace this with a more sophisticated system, perhaps one that follows basic OOP principles.

Handling and Allotting Goals

handle_goal is used to complete the goals (for instance, mining or depositing) after the ship has already reached its target. It first checks how long the ship has already been at the target for, and then either determines that the goal has been completed, or takes the necessary action.

allot_goal is used to allot a goal to any ship that currently lacks a goal - only Miners are supported right now. Specifically, it either gives the Miner a mining goal (if it still has space in its cargo hold), or gives it a deposit goal to deposit mined resources at a base (if its cargo hold is full). find_mining_goal is used to find nearby unoccupied spots from where the Miner can mine resources.

Computing Paths and Moves

To compute paths, we must first pre-process the map to generate the maze used by the path-finding API, so we use process_map. Note that this ignores enemy ships, so additional work may be necessary to handle complications arising from the presence of enemy ships.

After this, we compute the paths for every ships that requires a new path to be compute. We keep track of the time at which a new path must be computed for every ship. Currently, we recompute paths for ships at least every DEPTH/2 turns, where DEPTH is the depth of path-finding reservations. In addition, paths must be computed for any ships that have just been allotted a new goal. Once a path has been found, we cache the path for performance reasons so that we do not need to compute the path for that ship again until either a new goal is allotted or DEPTH/2 turns are over. Finally, we compute the direction every ship needs to move to follow its computed path.

This is followed by some cleanup code that handles destroyed ships by destroying their goals, ensuring no paths are computed for them, and deleting their cached paths. At the end, we remove all reservations for the current move as they will not be used anymore.

Clone this wiki locally