CSSE 413: Uninformed Search Programming Assignment
The aim of this assignment is to understand and implement basic
searching of state spaces. A secondary aim is to learn about the game
environment.
Work on this assignment by yourself.
Problem
The game we ask you to implement is Capture the Flag. We will
implement it in several stages, adding more and more complexity to the
specification and asking you to use the tools that we learn through
out the course. We eventually will hold a tournament in which we will
have your software play against each other. Details will be posted in
due time.
The specifications for this initial version of "Capture the Flag"
are as follows:
- You must use the Java programming language to implement your code.
- There will be a 20 x 20 grid of positions.
- There are three types of objects: you, a single flag with fixed
position, and zero to more walls, which may extend over several grid
positions and are also fixed in position.
- Your software needs to represent the grid.
- It needs to prompt the server to inquire about your initial
position, the position of the flag and the walls.
- Your software needs to implement Breadth-first search in which
duplicate states are removed.
- You need to find an optimal path and once found, send the path
information to the server. An optimal path
in breadth-first search is a path with the least possible moves.
- If no solution can be found, you need to communicate this to the
server.
- You can move up, down, left and right by exactly one position
between states.
- You must make a move, i.e. you cannot simply remain in your
position.
- The goal state is reached if you occupy the same board position as
the flag.
- You may not move outside the boundaries of the board.
- You may not occupy the same position as a wall, i.e. you will need
to move around them.
Testcases
Turnin
Submit your code to the appropriate drop box on Angel by 5pm on Day 6.