Task 1: Map Implementation

Your first task is to complete the implementation of the Map ADT in Map.c, which agents will use to get information about cities and roads.

Task 2: Agent Implementation

In this task, you must implement various strategies that the agents can use to try and catch the thief in Agent.c. This will require you to modify existing functions and add new fields to the agent struct (to enable agents to remember things), so make sure you understand the existing code first.

Stage 0: RANDOM strategy

In stage 0, all agents use the random strategy. In the random strategy, each agent randomly selects an adjacent city that they have the required stamina to move to and move to it. If the agent does not have sufficient stamina to move to any city, they must remain in their current city for another cycle, which will completely replenish their stamina.

The random strategy has already been implemented, so you are not required to do anything to complete this stage. You should not alter the logic of the random strategy in Agent.c. You should also not use any random number generation in your implementation of the other strategies.

Stage 1: CHEAPEST_LEAST_VISITED strategy

If a detective is assigned this strategy, it means that at every opportunity they have to move, they must move to the city they have visited the least number of times, out of the legal options that are available. This means the detective must work out what cities are actually adjacent to the current city that they have sufficient stamina to move to and pick from those the one that has been visited the least. If there is more than one city with the same number of visits, the city which requires the least stamina among those should be chosen. If there is more than one city with the same number of visits and that requires the least stamina, the city with the lowest ID among those should be chosen.

Note that at the beginning of the game, a detective is considered to have visited its starting city once. Also, if a detective must remain in their current city, this counts as an additional visit, even though the detective did not move.

Stage 2: DFS strategy

In this stage a DFS strategy must be implemented. When following this strategy, the agent maps out an entire route that will take them through every city on the map using the DFS algorithm. If the DFS has a choice between multiple cities, it must prioritise the city with the lowest ID. At every cycle, the agent attempts to move to the next city on the plan. If the agent does not have enough stamina they must wait in the same city to recover. When the agent has visited all cities at least once, a new DFS path from the final location is mapped out and is followed.

For example, consider the following arrangement of cities and roads:

If an agent using the DFS strategy starts at city 5, then they should devise the following route: 5 → 0 → 1 → 0 → 6 → 7 → 3 → 4 → 9 → 4 → 3 → 7 → 8 → 2. The route ends at city 2 because once the agent reaches city 2, they will have visited all the cities, and the next DFS would begin at city 2.

You can assume that all detectives using the DFS strategy have enough maximum stamina to traverse every road, and so no detective using the DFS strategy will be stuck forever at some city while trying to complete their route.

Stage 3: Least Turns Path

In this stage we will test your implementation using city data with informants. If a detective starts at, or moves to a city where there is an informant, they will discover where the thief is currently located. The detective must then find the path to that location that will take the least number of turns and then follow this path. Of course, the thief may be gone by the time the detective gets there, in which case the detective must restart their original strategy from their new location. Any cities the detective passes through on the shortest path are counted as being visited if the detective returns to the CHEAPEST_LEAST_VISITED strategy. The detective may also pass through a city with another informant in which the detective would find a new least turns path from the current location.

You must take into account the stamina of the agent. For example, if one path requires the agent to travel through 3 cities, but would have to rest twice (5 turns), that is more turns that an agent travelling through 4 cities but not having to rest (4 turns). If there are multiple paths that would take the least number of turns, the path that results in the agent having the most stamina at the end should be chosen. If there are multiple paths that would take the least number of turns and would also result in the agent having the same stamina, either path is valid.

You can assume that all detectives will be able to reach every city from every other city. That is, for every pair of cities, there exists a route between them such that each detective will have sufficient maximum stamina to take that route.

Information