Back to the rest of this home page
I hope this will help beginning Java students to understand the process of programming an applet for the first time. This diary outlines all the steps that I, as an experienced programmer in other languages, went through in developing the Pac-Man applet.
When I began this project, I knew how to do some simple Java interface stuff, but I didn't know much about graphics. So first I had to figure out how to display a picture on the screen.
Getting a picture to use was easy. I ran Pac-Man from Microsoft Arcade and took a screen shot. You can do this in Windows by pressing alt-Print Screen. Then I went into a graphics editor and selected "paste". Generally this can be done by either going through the menus, right clicking with the mouse, or pressing the shortcut CTRL-V on a PC. When I pasted the image, a new picture was created. Next I cut out small images of Pac-Man, the red monster, and an energizer. (I used an energizer because a small dot wouldn't be as easily visible. However, the monster doesn't turn blue in this game.)
You can see the images I created here.
I didn't realize this at first, but applets won't display a picture in the Windows bitmap format (.bmp); only in .jpg or .gif formats. So I had a lot of trouble getting my pictures to show up until I wised up and stopped using MS Paintbrush.
Anyway, once I figured out the general idea of drawing pictures I was able to pop my three images up at various places around the screen. Then I created a class definition called "GameObject" which contained, among other things, an x position, a y position, and an Image. This should be familiar to my students, except that they used structs instead of classes, and a letter ("char") instead of an Image.
Now that I had some pictures on the screen, I was ready to write behavior for them. Once you write a "move" function, which can move any object to any place, you have to describe WHERE to move and how fast. In class, most people wrote a "chase" function where one object sizes up the position of another object, then decides which way to move in the old direction. In the old version it looked something like this:
if (chaser.x > victim.x)
newx = chaser.x-1;
else if (chaser.x < victim.x)
newx = victim.x+1;
Well, this was an OK chase function to start with, although I knew it would look pretty crude to have them moving only diagonally or straight. Also, unlike the text version, you are moving pixel by pixel instead of square by square. You don't want to move the objects just "one space", because that would be very slow. Instead, I gave each GameObject a "speed" property which says how many pixels they can move per clock tick.
Another thing I learned at this point is how to make things happen over time (i.e., animation). In Unix, we would draw one frame of animation, then call the "sleep" function to wait one second, then draw another frame and so on as the loop repeated. This is not a nice way to program, because you are hogging all the system resources while your loop proceeds. Remember how you had to hit ctrl-break all the time if your program didn't stop? That's because your program has complete control over your Unix shell while it's in the foreground.
When you use a Java applet inside an internet browser inside a multitasking environment like Windows, you just don't DO that. Instead you create a "Thread" object to do the animation work. A thread is a new system process that you create. What happens is, while your applet just sits there and waits for input, your thread's job is to move the objects, repaint the screen, then wait for a certain amount of time (sleep), then move the objects again and so on. In other words, the thread is doing the exact same animation loop we did in school, only now it does it in the background. It doesn't take over the browser, like our programs would have taken over the Unix shell.
Another thing you should notice is that the Java "sleep" function takes an argument in milliseconds, not seconds. That means if you "sleep (200)", you would be doing something five times per second, not once every 200 seconds.
As I predicted, having the monster and pacman move only on diagonals and straight lines looked extremely stupid. If Pac-Man wants to eat the dot, he should go DIRECTLY towards it on a straight line. How do we do this? Well, unfortunately for people who don't like math, this requires a little bit of knowledge of trigonometry. Not a lot, but some. In fact, we are going to need to use math several times in this program to do all the clever things that we want to. That's the way programming is, especially graphics.
Okay, here goes. Suppose that it is Pac-Man's turn to move. Pac-Man is 10 pixels left of the dot, and 5 spaces above it. Here's what it would look like.
P . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . o
Our old method says he should move 1 pixel to the right and one pixel
down (or 3 pixels to the right and 3 pixels down... whatever his
"speed" variable is, that's how far he should go). Here's what it
would look like if the speed was 3.
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . P . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . o
That looks a little off, because Pac-Man moved too far in a downward
direction and not far enough to the right. Our new method would say
he should move about twice as far to the right as he does downward.
So first of all, we need to find out how much total distance is
between the two objects. (Trust me, we do. You'll see why in a
minute.) Well, the Pythagorean theorem says that distance2 = x2 +
y2. In other words,
distance = sqrt (x*x + y*y);
If Pac-Man had no speed limitation, he would move DIRECTLY to the dot's location. Then we could just say,
chaser.x = victim.x;
chaser.y = victim.y;
What's that you say? You can't move 0.894 pixels to the right because there's no such thing as a fractional pixel? Well, technically that's true, but the physical reality of the screen need not stop us; we are dealing with abstract data here. So we'll just change the declaration of a GameObject so that, instead of declaring x and y as integers, we'll declare them as doubles. (Remember, a "double" is a more precise version of a "float.") When it comes time to DRAW each GameObject, we'll round to the nearest integer, but we'll still store the position as a floating point number all the time.
This process of taking a pair of x and y coordinates, finding the total distance, and then dividing by the length, is a very common process in graphics. So common, in fact, that it has a name: Normalization. I just "normalized" the direction that Pac-Man has to travel, reducing it to a move of one unit (or pixel).
Getting back to our example, we could multiply 0.894 and 0.447 by 3, and the result would be that Pac-Man moves 2.7 pixels to the right, and 1.3 pixels down. When we draw this out, Pac-Man apparently winds up 2 squares right and 1 square down. (Remember, by default all float-to-integer conversions round DOWN. With a little extra effort, you could round them to the nearest integer instead, and get 3 and 1 instead of 2 and 1. Generally it will look okay either way). So our new position looks like this:
. . . . . . . . . . .
. . P . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . o
See, now it looks more like we're moving in a straight line from one location to the other. So now, with this new algorithm, Pac-Man will still move towards the dot, and the monster will still move towards Pac-Man, but now they will do so in a more direct looking way.
So far, our movement algorithm works great. Great for the monster, that is. It doesn't look so good for Pac-Man, because he's still dumb as dirt when it comes to not getting caught by the monster. Pac-Man will walk blindly towards the food, even if the ghost is directly in his path. This happens a little more often than we would like, and the "game" generally ends too quickly to be interesting.
This is where the extra credit part of the assignment came into play. I asked students to (1) make Pac-Man move a little faster than the monster, and (2) give him some "smarts" that dictate behavior which will dodge the ghost while still trying to approach the food. The first part is easy; even easier with this graphical system than with the ASCII graphics. All I have to do is change the "speed" multiplier so that we move farther on each clock tick. The second part is the hard part.
I tinkered with various techniques for making one object avoid another, but eventually I hit on the following pretty good solution. You can see this implemented in the "chaseWhileAvoiding" function. The way I see it, there are two competing influences at work on a character. First there is a desire to move toward its target. Pac-Man wants to "attack" the food, just like the monster wants to "attack" Pac-Man. Second, there is a desire to run away from the pursuer. This is Pac-Man's instinct to run away from the monster.
Another quick mathematical aside... when you have a set of x and y coordinates which represent an arrow pointing in a certain direction, you can refer to it as a "vector". A vector is just an arrow which has direction and length. Both the "toward the food" desire, and the "away from the monster" desire, can be expressed as vectors... arrows pointing in the direction that you want to go. I implemented a vector class to represent this concept. A vector has an x and y coordinate, and it can handle simple functions like adding or subtracting two vectors, multiplying by a constant number, normalizing, etc.
So we have an "attack" vector, and an "escape" vector. Ideally, we would like to satisfy both desires with the same movement, but this is not always possible. For instance, if the monster is right between the food and Pac-Man, there is no way to satisfy both needs at once... you have to decide to either head for the food, run away from the monster, or compromise and move off at an angle.
So what I decided is, assign a priority to each goal. Obviously if the monster is very near, the desire to escape will be much great than the desire to move towards the food. So I created a variable called "fearFactor" which would account for how close the monster is and how "afraid" Pac-Man is of immediately getting caught. The fear factor varies from 0 (no fear at all, monster is so far away) to 1 (completely, 100% fearful). Depending on the fear factor, we might choose to go entirely towards the food, or entirely away from the monster. Of course, by the time the fear factor is one, Pac-Man is probably already dead.
I take the "run away" vector, and multiply it by the fear factor. Then I take the "attack" vector, and multiply it by one minus the fear. The fear factor is always between zero and one, so 1-fearFactor is also between zero and one, and gets smaller as the fear gets bigger. Then I add these two vectors up, normalize the resulting new vector, and now I know which way to go.
It may sound complicated, but it's pretty simple. I will probably add a picture soon to show how the closeness affects fear and direction.
This technique worked out great, even better than I thought... Pac-Man was smart enough to sidle around the monster and still move in the general direction that he wanted to. A new problem came up, though. Sometimes, by chance, the monster would be practically sitting on top of the food as Pac-Man approached. Pac-Man would come close, his fear factor would get high, and he'd move off to the side. The ghost would be moving toward him, so now Pac-Man would still be close, so he'd move off to the side a little more. Suddenly, they'd be trapped in a circle. Pac-Man couldn't get to the food because the ghost was too close, and the ghost wouldn't move away because Pac-Man was too close. The players would wind up sort of "in orbit" around the food, with no way to escape. The program would end up like that almost every time.
This only seemed like a tough thing to counteract. Then I realized: it's just as easy to make the monster avoid the food while he chases Pac-Man, as it is to make Pac-Man avoid the monster while he chases food. I just changed one line of code to call one function instead of the other, and BOOM, it worked again. The rationale can be, ghosts don't eat Pac-Man food, so they can't travel over food at all. It kinda makes sense.
The fear factor technique worked very well, much better than I'd hoped in fact. The only bug that was really blatant now was that neither character was confined by walls. Pac-Man would occasionally run off one side of the screen.
At this point I made a quick design decision which may not have been the correct one, but it did the job anyway. I decided that since I already had the ability to make Pac-Man "fear" the monster and adjust his movements based on how close the enemy was, I could reuse that concept and make him "fear" the wall also. I won't get too detailed on how I applied this concept, but I will point out a few shortcomings of this approach.
If you set the fear factor of the wall too high, it will outweigh the desire to get to the food. This is not good because in some cases where the food is very close to the wall, Pac-Man refuses to eat it and just wobbles in place until the monster arrives. If you set the fear factor too low, fear of the monster may sometimes outweigh fear of the wall anyway, and Pac-Man will wander off the screen anyway. This is not supposed to be allowed under any circumstances. So the fear factor of the wall has to be very high when you are close, but drop off sharply as you move a short distance away.
Now in some cases, Pac-Man gets confused by a combined fear of both the monster and the wall, and doesn't seem clear on which way to go. Sometimes this kills him, and he dies in situations where seems it seems obvious that a human player with half a brain would stay alive. I haven't thought of a good solution to this yet, but I hope someone will suggest one to me.
Back to the rest of this home page
Send me an email