CSE 2010, HW6
Due Tue Apr 21 at the start of your lab section; Submit
Server: class = cse2010, assignment = hw6SxIndividual
Due Tue Apr 21 at the end of your lab section; Submit
Server: class = cse2010, assignment = hw6SxGroupHelp
=== Extra Credit 1 - 3 ===
Due Tue Apr 28 at the start of your lab section; Submit
Server: class = cse2010, assignment = hw6extraSxIndividual
Due Tue Apr 28 at the end of your lab section; Submit
Server: class = cse2010, assignment = hw6extraSxGroupHelp
x is 14, 23, j—section number or j for java submissions.
In the subgame of I/O Tower in the game of Tron, the player
moves Tron in a maze so that Tron can get to the I/O Tower
quickly. To prevent Tron from reaching his goal, grid bugs
roam around trying to destroy Tron. How would you design
the bugs such that they can reach Tron quickly?
HW6 explores graph algorithms to simulate a simpler ver-
sion of the Tron game. Given a starting position in a 2D grid
world, a player’s goal is to move Tron to reach the I/O Tower
without running into a bug. At each step, the player can move
Tron up, down, left, or right to an adjacent empty cell. Sim-
ilarly, at each step, bugs can move in those four directions to
an adjacent cell that is empty or occupied by Tron. For sim-
plicity, the bugs move at the same speed as Tron. The game
ends when Tron reaches the tower or a bug reaches Tron.
The player moves Tron first, then each bug (in alphabeti-
cal order) will move. Trying to reach Tron quickly, each bug
decides which direction to move based on the shortest path
from its cell to Tron’s cell. The distance from one cell to an
adjacent cell is 1. For easier debugging and testing, during
Breadth-First Search for the path, consider the valid adjacent
cells in this order: up, down, left, and right. Each cell can be
empty or can have Tron, a bug, or an obstacle.
HW6: one round of the first move from Tron and the first
move from the bugs.
HW6 Extra Credit 1 (via hw6extra1.c) [10 points]: multiple
rounds of moves to the end of the game.
HW6 Extra Credit 2 (via hw6Extra2.c) [10 points]: Smarter
bugs know that Tron is likely to use the shortest path to the
I/O Tower so that he can get there quickly. Hence, the bugs
would prefer their paths to cross Tron’s shortest path to the
I/O Tower. One approach is to increase the “distance” be-
tween adjacent cells that are not on Tron’s shortest path. For
Extra Credit 2, the distance between two adjacent cells is:
• 1 if both cells are on Tron’s shortest path
• 2 if one of the two cells is on Tron’s shortest path
• 3 if both cells are not on Tron’s shortest path
To find the shortest path for a smarter bug, use Dijkstra’s
algorithm. One round of the first move from the player and
the first move from the bugs.
HW6 Extra Credit 3 (via hw6extra3.c) [10 points]: same as
Extra Credit 2, but multiple rounds of moves to the end of the
game.
Input: Command-line argument for hw6.c is a filename of
the 2D grid world—the first line has number of rows and
columns of the world, the following lines have the initial world
represented by these characters:
• T represents Tron
• I represents the I/O Tower
• a, b, c, d, ... represent bugs
• # represents a stationary obstacle
• a space represents empty
During the game, via the keyboard, the player can input u,
d, l, and r to indicate moving up, down, left, and right to an
adjacent cell. If the input is invalid (incorrect letter or the
adjacent cell is not empty), prompt the player to re-enter.
Output: Output goes to the standard output (screen):
1. the world with row numbers on the top and column num-
bers on the left
2. Please enter your move [u(p), d(own), l(elf), or r(ight)]:
3. the world with row numbers on the top and column num-
bers on the left
4. For each bug (in alphabetical order), display its move
(u/d/l/r), length of its shortest path to Tron, and cells
on the shortest path starting with the bug cell before the
move and ends with Tron’s cell:
Bug a: move shortestPathLength (row1,col1)
(row2,col2) ...
...
Bug b: move shortestPathLength (row1,col1)
(row2,col2) ...
Row 0 is at the top and column 0 is on the left. Sample output
(with player keyboard input) is on the course website.
For extra credit, the program repeatedly displays the output
above and terminates after:
1. Tron reaches I/O Tower: the program displays the final
world and “Tron reaches I/O Tower”, or
2. one of the bugs at Tron’s cell: the program displays the
final world and “A bug is not hungry any more!”
Sample input files and output are on the course website.
Submission: Submit hw6.c that has the main method
and other program files. Submissions for Individual and
GroupHelp have the same guidelines as HW1.
For extra Credit 1, 2, and/or 3, submit hw6extra1.c,
hw6extra2.c, and/or hw6extra3.c that have/has the main
method and other program files. GroupHelp and late sub-
missions are not applicable.
Note the late penalty on the syllabus if you submit after the
due date and time as specified at the top of the assignment.