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.
The specifications for this initial version of "Capture the Flag"
are as follows:
- The playing field consists of a 10 x 10 grid of positions.
- There are three types of objects:
- A person (you)
- A single flag with fixed position
- Zero or more walls, which may extend over several grid positions
and are also fixed in position.
- 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.
The specifications for your software are as follows:
- You must use the Java programming language to implement your code.
Your software must:
- Interact with the server we provide.
- Prompt the server to inquire about the persons initial position, the
position of the flag and positions of the walls.
- Needs to represent the grid.
- Needs to implement Breadth-first search in which duplicate states
are discovered and removed.
- Find an optimal path and once found, send the path information to
the server. An optimal path is a path with the least number of moves.
- Communicate to the server, if no solution can be found.
Complete specs
Here is a DRAFT of what we believe will be the final specifications.
Testcases
The Game Server
The game server
Turnin
Submit your code to the appropriate drop box on Angel by 5pm on Day 6.