The bugs are back.
With a knowledge of arrays and structs, you can solve many complex problems. The issue that arises for many problems is "representation": choosing data structures so that the problem can be modeled naturally but still be convenient and efficient to implement.
Computers are frequently used for simulations, that is, to simulate or imitate the steps of a real-life activity, in order to investigate how that activity operates without the messiness of actually carrying it out, which might be especially desirable if the activity is expensive, dangerous, or impractical. The computer program becomes a "model" of reality, and so the programmer has to choose a "representation" of the real world. Often this means throwing away unnecessary details to concentrate on what is essential.
In this project, you will write a program to simulate playing a
game of tag where a bunch of bugs chase a person across a gameboard.
key concepts
In addition to concepts with which you should be comfortable by this point, this your chance to become familiar with the following:
The characters in the game are a person, represented in the sample program by a smiley-face, and the bugs, represented by a small version of the bugs from homework 4. A complete working version of the game is available (see link in the files section, below). To make sure you understand exactly what these rules mean, you can play the game repeatedly to experiment.
The game is played on a rectangular board divided into small squares. Each player occupies one square.
A game consists of one or more rounds, each of which consists of a sequence of moves. At the beginning of a round, the person and some number of bugs are positioned randomly on the board.
In each move (or time step), the person moves first. The person can either stay where he is, or move to any adjacent square that is not already occupied. "Adjacent" means immediately above, below, or diagonally touching the current location. No player (person or bug) is able to leave the world of the grid.
Once the person moves (or stays put), the bugs should automatically move closer to the person, but they can move only one square at a time. Their motion is completely determined by where the person moves. In fact, since they're not paying any attention to each other, it's possible that two bugs might collide. If this happens, they both turn into a pile of rubble, and are thus effectively eliminated from the game. Any bugs which later blunder into an existing pile simply join the pile and are eliminated.
A bug collision is good news for the person. In fact, the person's strategy should be to try to trick the bugs into colliding with each other or a rubble pile.
Winning and losing: the person wins a round when it has tricked every bug into colliding. The person loses if a bug ever captures him by landing on the same square.
Once a round is over, a new round of the game starts. If the person won the previous round, more bugs appear in the next round. If the bugs won (captured the person), then the same number of bugs as in the initial round appear. If the person keeps winning, eventually the whole board will fill with bugs at the beginning of the game.
Scoring: The person gets 100 points for each bug that is eliminated, either by a collision or by using the RaidTM bug spray (an optional feature; see below). If the person is captured, the score returns to 0. After each move, the updated score should be displayed at the top of the window.
There are two further optional tricks the person can use. Once per round, and only once, the person can use a can of RaidTM bug spray to disintegrate every bug that is at that moment adjacent to him. Also whenever desired, the person can teleport from his current location to some unoccupied square on the board. The teleporter is quite random---the person might land in any unoccupied square. It might be adjacent, it might be all the way across the board, or it might even be back in the original location. Both the RaidTM and teleporter moves are optional. You are not required to implement them, but you can receive some extra credit if you do.
data structures: representing the game world
A key decision in designing a program like this is to pick suitable data structures to represent the various objects in the game. Another key decision is to pick the operations that should be packaged as functions in the program. The starter program for this assignment has several plausable data structures and operations, along with useful constants, that you might want to use. Most of these are just suggestions (i.e. feel free to do something different).
You are required, however, to use at least one struct and a two-dimensional array in your program. The starter program suggests a possible struct to contain information about the person moving around the game board. You should almost certainly use this data structure (possibly with some additions or modifications as needed by the rest of your code).
The starter program contains enough code to draw the grid and randomly place the person and some bugs on it when the program is executed. It also contains additional code that you can use as building blocks for your code (or not, as you prefer). You should examine it carefully to understand what's there and figure out what you will need to modify.
There are many possible ways to represent the game world. The most natural is probably using a two-dimensional array to represent the grid. Each location in the grid needs to store information about the status of the square: either occupied by the person, by a bug, by a pile of rubble, or empty. In the starter program, we suggest a representation of the world as a 2-D array where columns are numbered left-to-right starting from 0 (as usual), but rows are numbered from bottom-to-top starting from 0 at the bottom. So, for example, if map[i][j] contains the value HAS_BUG, then that means there is a bug in horizontal position (column) i and row j. This numbering scheme may take a bit of getting used to, but it has the advantage that it is much easier to convert between screen graphics coordinates and grid column/row coordinates if we think of the grid this way.
moving the person
To implement a move, you need to wait for a GP142 mouse-click event, read the mouse coordinates, and react accordingly. The mouse coordinates need to be converted to the corresponding column and row numbers on the grid. Then, if that square of the grid is adjacent to the person's current position and is empty, the person should move there. If the mouse is clicked in the same square the person currently occupies, the person should stay put. If the mouse is clicked on a grid square that contains a bug or pile, or if the click is off the game board entirely, it should be ignored.
moving the bugs
Once the person has moved in response to a mouse click, all of the bugs should move one square closer to the person's new position either up, down, or diagonally (if possible), whichever brings the bug closest to the person. In other words, if the bug is not in the same column as the person, it should move one square horizontally toward the person's position. If the bug is not in the same row as the person, it should move one square vertically toward the person's position. If a bug can move closer to the person by moving one square both horizontally and vertically (i.e. diagonally), it should do so.
The process of moving all of the bugs is a bit tricky, because what happens to a bug depends on the old positions of nearby bugs. If you just traverse the array and move bugs as you find them, then you can get incorrect results if you move a bug before considering all of its neighbors in the old position. There are at least a couple of ways to handle this. The basic idea is to store two pieces of information about each grid cell---its "old" contents, and its new contents after all the bugs move. Then to move the bugs, you first make a pass through the grid to calculate the new contents without moving anything. After figuring what the new board will look like, go back and update the actual board.
It is more important than ever that you start early and get the program working bit by bit so you can make steady progress and not have a large mass (mess?) of code to debug at the last minute. Here is a suggested order in which to get the parts of the game to work.
Get started early and make steady progress, making sure your program compiles without warnings and errors at each step and making backup copies of your work.. The labs are usually jammed towards the end of the quarter, so you will have a problem if you wait until the last minute.
Once you have the basic game working and have turned in a working copy in case something goes wrong later, feel free to add to the game and submit an improved, working version. A modest amount of extra credit will be awarded for significant additions to the program. Here are a few suggestions.
Use your imagination and have fun.
This information is repeated from the assignment 4 handout as a convenience. GP142 has not been changed.
You will find the GP142 User's Guide (also linked on the main Homework page) useful as a reference as you read and write graphics code in this homework.
If you are using Windows, we strongly advise that you compile and modify the program ONLY via the .dsw file that will be supplied in the self-extracting archive. Here's why: GP142 programs differ from previous projects in some important ways. First, they have multiple .c files (gp142.c in addition to your own). Second, they use a special .h file that must be available to the compiler. Third, they are built as "Windows Applications" rather than "Console Applications." All of this means that you cannot create a "default project workspace" to compile and run your program in. If you double-click on the .dsw file we give you (.dsp for users of some older versions of MSVC), all of these special settings are taken care of.
If you really need to know how to create your own project, look at the MSVC tips page, which is also linked on the course home page.
We recommend that you work on a Windows PC to work on this homework, but the GP142 User's Guide page also includes information for Macintosh and X Windows (UNIX) users.
As always, be sure to read the homework submission guidelines, linked on the course home page in the Announcements section. You will have to submit your work (1) via the web using the page linked below and (2) on paper (a printout of the web turn-in receipt page).
self-extracting archive, including starter C file
If any clarifications or changes need to be made for this homework, they will be posted to the cse142-announce email list and linked here.
Save paper: Read documents on the web when you can and, if you print, print two-sided. Remember to reuse or recycle this paper when you're done.