Background COMP2521 23T2
In this assignment, you are the police! You will control four detectives as they travel through a
network of cities trying to catch a thief.
The police are aiming for any of the four detectives to catch the thief before the thief escapes to
the getaway city, and before the time runs out... and the aim of the thief is to reach the getaway
city before they are caught.
The detectives have a map, but do not know where the thief is or where they are trying to get to.
The thief also has a map but unfortunately they didn't take COMP2521, so they don't really know
how to use it and they wander randomly through the cities trying to reach the getaway city. The
detectives may employ different strategies depending on what they have been assigned to.
Game Rules
In this game, all the people (the four detectives and the thief) are known as agents, and the game
consists of a series of turns, known as cycles.
Each agent starts in a city, determined by user configuration. Every cycle, each agent may move
from their current city to an adjacent city by road. The goal of the detectives is to end up in the
same city as the thief, which would allow them to catch the thief, while the goal of the thief is to
reach the getaway city.
Each agent begins with some stamina, also determined by user configuration. Whenever an agent
moves from one city to another, they lose stamina equal to the length of the road between them.
Agents cannot travel along a road if they do not have the required level of stamina. This means it
is possible for an agent to have no legal moves. If an agent has no legal moves due to not having
enough stamina, they must remain in their current city for another cycle. Remaining in the same
city for a turn resets the agent's stamina back to its initial level.
Each detective uses a set strategy to navigate the cities, determined by user configuration.
Meanwhile, the thief always moves randomly.
The game ends if one of the following conditions is met:
If a detective starts in the same city as the thief, the thief is caught immediately and the
detectives win.
If a detective is in the same city as the thief at the end of a turn, the thief is caught and the
detectives win.
If the thief is in the getaway city at the end of a turn and there are no detectives there, the thief
escapes, so the thief wins.
If the time has run out, regardless of whether the thief was able to reach the getaway city, the
trail has gone cold, so the thief wins.
cities*.data files Sample city data files to use as a starting point for your testing. Some
COMP2521 23T2
data files will have small numbers of cities, some will have more; some
have informants, some don't… but you should also create your own data
files.
agentsS*.data files Sample agent data files that you can use once you have completed the
different stages of the assignment. agentsS1.data can be used if you
have implemented stage 1 and above, agentsS2.data can be used if
you have implemented stage 2 and above, and so on. Note that stage 3
must be tested by using one of the city data files with informants. And, of
course, you should create your own agents*.data files for testing.
Note that you are permitted to create supporting files for Task 2. To ensure that these files are
actually included in the compilation, you will need to edit the Makefile; the provided Makefile
contains instructions on how to do this. Supporting files are not permitted for Task 1.
The Client Program
Inputs
Command-Line Arguments
The client program should be invoked as follows:
./game <city data file> <agent data file> <cycles> [seed]
The program requires 3 command-line arguments with an optional fourth. The command-line
arguments are
1. the name of the city data file
2. the name of the agent data file
3. the maximum number of cycles in the game
4. (optional) a seed value for the random number generator; by using the same seed, you can
produce the same ordering of 'random' moves and repeat exactly the same situation.
City Data
The first line contains a single integer which is the number of cities. Then, for every city there will
be a line of data. Each line begins with the ID of the city, which will always be between 0 and (the
number of cities - 1), followed by pairs of integers indicating a road to another city of a certain
length. After the roads are listed each line will contain either an 'n' or 'i'. An 'i' indicates that the
city has an informant, while an 'n' indicates that it doesn't. At the end of each line is the name of
the city.
Once the client program has started the initial state of the game will be displayed and the user
will be prompted for input. The available commands are as follows: COMP2521 23T2
Command Description
run This will run an entire simulation, printing out a trace of the agents' locations for
each cycle of the game. It will print out how the game finished, i.e., with the thief
being caught, getting away, or time running out.
step This runs just one cycle of the game, printing out the new location of the agents for
the next cycle. If the game finished in that cycle, it will also print out how the game
finished. This allows the user to step through the game one cycle at a time.
stats This prints out the status of each agent. This includes the name of the agents'
current location and the agents' stamina.
display This displays the current locations of all agents.
map This prints out the map in a textual format, including the ID/name of each city, and
the roads from each city and their length.
quit Quits the game!
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.
The interface functions of the Map ADT are as follows:
Function Description Assumptions
MapNew Creates a new map with the given number of The given number of
cities and no roads cities is positive
MapFree Frees all memory allocated to the given map
MapNumCities Returns the number of cities on the given map
MapNumRoads Returns the number of roads on the given map
MapSetName Sets the name of the given city. If the city's name The given city and name
has already been set, renames it to the given are valid
name.
MapGetName Returns the name of the given city, or "unnamed" The given city is valid
if the city's name has not been set (via
MapSetName)
least number of visits and that requires the least stamina, the city with the lowest ID among those
should be chosen. COMP2521 23T2
Note that at the beginning of the game, a detective is considered to have visited their 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 detective
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 detective attempts to move to the next city on the plan. If the detective
does not have enough stamina, they must wait in the same city to recover. As soon as the
detective 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 a detective 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 detective reaches city 2, they will have visited all the cities, and the next DFS would begin at
city 2.
You can assume that the maximum stamina of each detective using the DFS strategy is greater
than or equal to the length of the longest road, 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 (this is achieved by the AgentTipOff function being called). 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
D4 is at [1] perth with 500 stamina
COMP2521 23T2
Enter command: step
Hour 1
T D1 D2 D3 D4
2 0 0 0 0
Enter command: stats
Hour 1
T is at [2] darwin with 970 stamina
D1 is at [0] melbourne with 99959 stamina
D2 is at [0] melbourne with 4959 stamina
D3 is at [0] melbourne with 9 stamina
D4 is at [0] melbourne with 459 stamina
Enter command: step
Hour 2
T D1 D2 D3 D4
3 1 2 0 1
Enter command: stats
Hour 2
T is at [3] california with 940 stamina
D1 is at [1] perth with 99918 stamina
D2 is at [2] darwin with 4059 stamina
D3 is at [0] melbourne with 50 stamina
D4 is at [1] perth with 418 stamina
Enter command: display
Hour 2
T D1 D2 D3 D4
3 1 2 0 1
Enter command: run
Hour 3
T D1 D2 D3 D4
2 0 3 1 0
Hour 4
T D1 D2 D3 D4
0 1 2 1 1
T got away to melbourne (0)
GAME OVER: YOU LOSE - THIEF GOT TO GETAWAY
Stage 1
In this example, all detectives are using the CHEAPEST_LEAST_VISITED strategy.
continue on the set path. (This happens even if there were other options they did have the
stamina for.) COMP2521 23T2
Detectives 1 and 2 are still following the CHEAPEST_LEAST_VISITED strategy and the thief is of
course using the RANDOM strategy.
$ ./game data/citiesMedium.data data/agentsS2.data 10 2
DETECTIVE ACADEMY 2521
Red alert! A thief is on the run.
Detectives, to your cars. You have 10 hours.
Hour 0
T D1 D2 D3 D4
9 2 8 1 2
Enter command: run
Hour 1
T D1 D2 D3 D4
4 1 0 0 1
Hour 2
T D1 D2 D3 D4
9 5 5 5 0
Hour 3
T D1 D2 D3 D4
4 6 6 3 0
Hour 4
T D1 D2 D3 D4
9 5 5 4 5
Hour 5
T D1 D2 D3 D4
4 5 1 9 3
Hour 6
T D1 D2 D3 D4
4 0 2 4 4
D3 caught the thief in darwin (4)
YOU WIN - THIEF CAUGHT!
Stage 3
In this example, detectives 1 and 2 start with the CHEAPEST_LEAST_VISITED strategy and
detectives 3 and 4 start with the DFS strategy. However detectives 1 and 4 start off in a city with
D1 caught the thief in darwin (4)
YOU WIN - THIEF CAUGHT! COMP2521 23T2
Testing
Task 1
Task 1 can be tested in isolation using the testMap.c program.
To run these tests, first run make, which compiles your code and creates an executable called
testMap, and then run ./testMap. The program contains assert-based tests, which means that
the program will exit as soon as a test fails.
As given, the testMap.c program contains very basic tests - it is recommended that you add
more extensive tests. You can add more tests by creating additional functions in testMap.c and
then calling them from the main function.
Task 2
Task 2 can be tested using the ./game program.
To find out how to run the program, see "The Client Program" section of the spec. There are also
example runs of the program in the "Example" section.
You can devise more test cases by creating new city data files and agent data files. It is
recommended that you first draw out a map on paper (to double check that it actually tests the
scenario that you want to test) and then create the corresponding city and agent data files.
A reference implementation is also available at:
/web/cs2521/23T2/ass/ass2/reference/game
Note that the ./game program uses random number generation (for the RANDOM strategy), so to
properly compare your program with the reference implementation, you must run your program
on CSE machines.
If the reference implementation fails (e.g., segmentation fault, bus error, etc.) or behaves
incorrectly according to the specification, please email cs2521@cse.unsw.edu.au and attach
the test file or a description of the input that caused the failure/bug.
Debugging
Debugging is an important and inevitable aspect of programming. We expect everyone to have an
understanding of basic debugging methods, including using print statements, knowing basic GDB
commands and running Valgrind. In the forum and in help sessions, tutors will expect you to have
WARNING:
COMP2521 23T2
After you submit, you must check that your submission was successful by going to your
submissions page. Check that the timestamp and files are correct. If your submission does not
appear under Last Submission or the timestamp is not correct, then resubmit.
Compilation
You must ensure that your final submission compiles on CSE machines. Submitting non-compiling
code leads to extra administrative overhead and will result in a 10% penalty.
Every time you make a submission, a dryrun test will be run on your code to check that it
compiles. Please ensure that your final submission successfully compiles, even for parts that you
have not completed.
Assessment Criteria
This assignment will contribute 20% to your final mark.
Correctness
80% of the marks for this assignment will be based on the correctness of your code, and will be
based on autotesting. Marks for correctness will be distributed as follows:
Task Weight
Map Implementation 15%
Agent Implementation Stage 1 20%
Stage 2 25%
Stage 3 20%
There are no formal time complexity requirements. However, each test will still be run under time
constraints, and solutions that are slower than O(n ), where n is the number of cities, will risk
4
timing out.
Memory errors/leaks
You must ensure that your code does not contain memory errors or leaks, as code that contains
memory errors is unsafe and it is bad practice to leave memory leaks in your program.
Our tests will include a memory error/leak test for each part of the assignment. If a memory
error/leak arises from your code, you will receive a penalty which is 10% of the marks for that part.
For example, the penalty for causing a memory error/leak in Stage 1 will be 2%. Note that our
tests will always call MapFree at the end of the test (and AgentFree if appropriate) to free all
memory allocated to the map and agent.
work to another person for any reason, and work derived from it is submitted, then you may be
COMP2521
penalised, even if the work was submitted without your knowledge or consent. 23T2
This may apply
even if your work is submitted by a third party unknown to you.
COMP2521 23T2: Data Structures and Algorithms is brought to you by
the School of Computer Science and Engineering
at the University of New South Wales, Sydney.
For all enquiries, please email the class account at cs2521@cse.unsw.edu.au
CRICOS Provider 00098G
