CEP Breaking News, Articles, Feature Stories and Blog Posts

CEP on Ulitzer

Subscribe to CEP on Ulitzer: eMailAlertsEmail Alerts newslettersWeekly Newsletters
Get CEP on Ulitzer: homepageHomepage mobileMobile rssRSS facebookFacebook twitterTwitter linkedinLinkedIn


cep Authors: Tony Shan, Liz McMillan, Bob Gourley, Charles Rich, AppDynamics Blog

Related Topics: Java Developer Magazine, CEP on Ulitzer

Java Developer : Article

Cover Story: Java Gaming - Understanding the Basic Concepts

PART 1

At JavaOne 2004 we gave a presentation on Java game development that included general framework information and tips and tricks on using the media APIs effectively. We also showed an application named "Ping" that demonstrated some of the ideas we discussed (see Figure 1).

Working code is a great way to illustrate an API, and we have posted the source code that accompanied our presentation on http://ping.dev.java.net. This article fully explains the ideas behind our JavaOne presentation as well as the elements of interest in the Ping application.

This two-part article is divided into three main sections:

  1. Game framework
  2. 2D rendering specifics
  3. Ping: the demo
We will cover the first topic here and save the rest for Part 2.

Game Framework
Usually a game will want to spin off a separate thread to handle all of the main work of the per-frame game loop. This doesn't mean that all processing for the entire application happens on this thread (some things, like events, are inherently processed on different threads), but that one single thread will be used to synchronize and serialize all of the actions that must occur in every frame.

For example, a simple game loop might be:


public class GameLoop implements Runnable {
    public void run() {
        while (true) {
            syncFrameRate();
				gatherInput();
				updateObjects();
				render();
        }
    }
}

This Runnable could be used when spawning a dedicated thread:


Thread t = new Thread(new GameLoop());
t.start();

...and you're off and running. Now you just have to implement the methods in run() and you're all done. Right?

Although the loop above is pretty simplistic, it covers the basics for many types of games and it's what we'll use for the purposes of our discussion. Let's see what the details are in the methods called inside that game loop.

syncFrameRate()
At the start of any frame, you should figure out the timing information. Many games have been written that assume some kind of constant frame rate, or constant movement per frame. If you actually have a constant frame rate this may work fine, but in this world of arbitrarily fast or slow computers, different performance - based on machine configuration and load and per-frame variability in terms of scene complexity and rendering time - makes it suicidal to count on a constant frame rate. Instead, your game should figure out the per-frame movement based on how much time has actually passed. For example, don't assume that your characters move one unit per frame, but rather one unit per time unit; then no matter how much time passes between one frame and the next, the movement will look constant to the user of your program.

syncFrameRate() is an attempt to boil down this idea into some simple code that does two things:

  1. Tries to regulate the frame rate to some configurable speed.
  2. Calculates the actual time passed since the last frame. This elapsed time will be used later in object movement calculations.
Frame Rate Consistency
Of course you could always run flat-out as fast as you can and just use the elapsed frame times to make sure the object movement is realistic. However, you may then end up spending way too much effort just getting through your game loop at that speed and not leaving enough CPU cycles for other things that your application (or your machine) might want to do instead. For example, if events are getting processed asynchronously, you want to make sure that the thread that processes those events gets enough time to actually run effectively. Also, your game may use extra cycles in a different thread to run the AI engine, the physics engine, the audio, or a host of other things. It's far better to determine a "good" or "good enough" frame rate and try to match that than to just run as fast as you can.

Another reason for consistency is that you don't want disturbing artifacts if your game runs like a demon for several frames and then crawls for a frame or two because some other thread is playing catch up. Far better to set a consistent rate lower than the peak so that the game can run smoothly at all times.

One simple way to get a consistent frame rate is to figure out what rate you would like to run at (based on preset values, user input, or timing tests before or during the game) and to throttle the game loop down to that speed during syncFrameRate().

Elapsed Frame Time
Once you've throttled the frame rate to some reasonable level, you also want to measure the exact time that has passed since the last frame. This is what you should use to calculate things like object movement - you may be close to some ideal time value by trying to set a consistent frame rate but chances are you'll usually vary slightly from that ideal (and you may occasionally vary widely due to some hiccup in performance). You should therefore ensure that your movement calculations are correct with respect to actual time and not the ideal time you are aiming for with the frame rate.

To achieve this you need to record the actual time elapsed since the last time around the game loop. Later movement calculations will then use this elapsed time value to come up with the time-correct values.

syncFrameRate() Code
The following code makes sure that your game is not trying to run any faster than this rate (the nsPerFrame variable):


 1:    public void syncFrameRate() {
 2:        long nextFrameTime = prevFrameTime + nsPerFrame;
 3:        long currTime = System.nanoTime();
 4:        while (currTime < nextFrameTime) {
 5:            Thread.yield();
 6:            try {
 7:                Thread.sleep(1);
 8:            } catch (Exception e) {}
 9:                currTime = System.nanoTime(};
10:        }
11:        elapsedFrameTime = currTime - prevFrameTime;
12:        prevFrameTime = currTime;
13:    }

Let's analyze some of the methods used in the code.

Line 3: System.nanoTime() is a new method in JDK 5.0 that finally enables the use of high-resolution timers in the Java core classes. The old System.currentTimeMillis() call that applications typically use is sufficient for most static or low frame-rate situations, but games usually require a finer degree of control than higher-resolution timers can provide. In recent simple timing tests on Windows machines I found System.currentTimeMillis() to have a minimum resolution of 10-15 milliseconds, whereas System.nanoTime() had a much better resolution of only one millisecond or so.

Line 5: Thread.yield() ensures that we cede CPU time to other waiting threads every time around the timing synchronization loop, even when we have exceeded our nsPerFrame time; sharing the CPU with other threads is usually a good idea.

Line 7: Thread.sleep(1) -- in our demo, we set this call to sleep for the minimum amount of time before spinning around the loop again. You may want to set this sleep time more carefully in your game according to how much time you can afford to give away to other threads. The trade-off here is that you want to sleep for the maximum amount of time possible to allow other threads to have fair access to the CPU, but the minimum amount of time so you can still wake up soon enough to hit your target time to process the next frame; sleeping too long can make it impossible to hit your ideal frame rate.

Line 12: prevFrameTime is assumed to be a variable of type long that is retained between frames just for the purposes seen in this syncFrameRate() method.

Line 11: elapsedFrameTime is the actual time passed since the last time around the loop. It's used in later processing of things like object movement.

gatherInput()
This stage is used to process all of the "input" that has accumulated since the last frame. This input includes both local input events such as keyboard and mouse as well as networking events in networked games.

Input is actually a two-stage process, the second of which is the call to gatherInput(). The first half of the input process occurs before this step on other threads. We'll go through both of these input stages below: Event accumulation and Intelligent Event accumulation.

Event Accumulation
In a typical AWT/Swing application, events are processed on the Event Dispatch Thread by calls to EventListener objects whenever events occur. The same thing happens here - we will attach EventListeners to find out when specific events occur. The only difference is that we won't process the events until the later gatherInput() stage. Instead we'll simply accumulate the information about what has happened and wait until gatherInput() to actually do something about all of those events.

The process for listening to events is the typical AWT/Swing one. First register some object to be a listener:


EventListener eventGatherer = new EventGatherer();
frame.addKeyboardListener(eventGatherer);

The actual process of gathering the input happens in the EventGatherer class that we have created. In the class below, we're assuming that spacebar events are of interest. Note that an actual implementation of the class would need to override the other KeyboardListener events as well (and may have many other methods besides); we are concentrating only on showing the process of tracking these types of events:


public class EventGatherer implements KeyboardListener {
    public void keyPressed(KeyEvent e) {
        if (e.getCharCode == KeyEvent.VK_SPACE) {
            spacebarEvents.add(e);
            return;
        } else if (...) {
            // etc.
        }
    }
}

Intelligent Event Accumulation
In the EventGatherer code above, note that we are calling spacebarEvents.add(e) instead of just toggling a variable that determines whether the spacebar is being held or not. In general, we want to accumulate information about all of the relevant events that occurred in each frame, not just which state things are in at the end of a frame.

As an example, the spacebar might be responsible for shooting some rapid-fire projectile. It's not enough to know whether the key is down or up once per frame because the time elapsed between frames may be long enough to allow several shots to be fired in that time. Instead, we need to know how long the spacebar has been down. Or, if it was pressed and released all within the same frame, we need to know how long it was down before it was released. Furthermore, if it was pressed and released several times, we should track that total time held and perhaps the number of times it was pressed and released.

We may want even more information than the total time held. Say a key determines movement for a character; the longer the key is down the more the character moves. If we track total time held, that at least gives us constant movement per time unit the key is held, but it will make character movement very stilted as characters will always move at the same rate. A more natural motion is to use acceleration and perhaps deceleration, taking the time held into account when determining how fast to move the character.

For all of these additional factors, we need to record additional information about each event. It's not enough to simply record that an event happened. Instead, we need to record when that event occurred, as well as what that event was.

The simple call to spacebarEvents.add(e) above hints at this; we are adding this new event to some list of events for that key, but we are adding it with the full event structure so we can record the event times as well as the event actions. From this information, we can later decode the information we need to track such things as total hold times and press/release data.

gatherInput(): Processing the Input
The steps outlined above (accumulating the input data) happen throughout a frame. Later on, exactly once per frame, the application takes all of the accumulated data and processes it accordingly:


public void gatherInput() {
    if (spacebarEvents.size() > 0) {
        processSpacebarEvents(elapsedFrameTime);
    }
    // etc.: process all other events here as well
}

It's important to synchronize access to the structure used for storing the events. Since we are, by definition, accessing that structure from different threads, the program needs to ensure that it only accesses it from one thread at any given time. Moreover, since we want to process all events at one time in gatherInput(), no more events can be added to the queue in parallel while we are working on it. Failure to do this will mean we process events that have not actually occurred yet. This is because any frame is being processed based on the time just passed, and we cannot take into account things that are happening while we are processing that frame because all of that must be processed on the next frame.

The method processSpacebarEvents(long) is passed in the elapsed time that we calculated in syncFrameRate(), and uses the argument to calculate event actions based on the events that occurred for the spacebar as well as the times that those events occurred.

This may appear pretty sketchy, but that's what having sample code is all about. In the Ping demo we do the event accumulation and processing steps outlined above to calculate accelerating movement for the game paddles in that code.

What About Networking?
At a high level, network events can be handled exactly as described earlier for local events - you accumulate the network events in separate threads asynchronously and then, once per frame, you process these events and calculate any necessary movement and actions.

The details behind this high-level view are, of course, much trickier. Networking can be far more complicated than the simple local event processing described earlier. We decided not to pursue networking in this article and demo and to instead just focus on simple game frameworks and rendering issues. Nevertheless it's useful to at least call out some of the important issues that will arise in any networked game.

Network Events
There are many different types of networking events that you may want or need to process. These include player movement, player action, and synchronization:

  • Player movement: Players on different machines will presumably have characters they control locally whose positions need to be communicated to the other machines involved in the game.
  • Player action: Actions such as firing, colliding, and speaking need to be communicated to all appropriate clients in the game.
  • Synchronization: Timing synchronization is critical in networking. Chances are slim that games on separate clients began at exactly the same moment, or even that the clocks on the different game clients are matched. There needs to be some kind of handshaking and potentially ongoing sanity-checking to make sure that one client's view of time and the world is the same as all other clients.
Networking Considerations
There are a variety of important considerations that must be taken into account when designing and implementing a network architecture for a game including network architecture, networking artifacts, and protocol:
  • Network architecture: Your game could use a peer-to-peer architecture, where each client of the game speaks directly to the other clients. This is possibly a simpler architecture with lower overhead, but requires that each client keeps a more complete model of the universe locally. This approach also has security implications, as any client has the ability to hack the universe and thus cheat in the game. A client/server architecture has higher overhead, but benefits from the security and manageability standpoint because there is always one single machine that has the master view of the universe.
  • Networking artifacts: Even in these days of widespread broadband access, there are still important network artifacts that cannot be ignored such as latency, synchronization, and loss.
  • Latency: Even if all players have DSL, there are probably still inherent delays in transmission between the clients, more so with geographically widespread clients. Your game must deal with latency aggressively through things like movement prediction. For example, instead of depending on every client transmitting new positions for their characters every frame, it would be far better for clients to simply transmit when movement trajectory/velocity has changed and what those new values are. Then the other clients can do their own calculations of where that character is every frame until they receive new information from that client.
  • Synchronization: As mentioned earlier, all of the clients need to have the same view of time in order to have the same view of the game universe. Issues such as latency can make synchronization difficult (you cannot tell the machines to start an action at the same time if the machines don't get that message to start at the same time).
  • Loss: There is always the potential for data loss over the network. If your game is dependent upon every data packet reaching its destination intact, there will be problems when that doesn't occur.
  • Protocol: The issue of data loss over the network raises the important issue of networking protocols. There are various protocols to choose from, some of which handle such things as packet loss. These higher-level protocols can detect loss and retransmit lost data, but at the cost of a higher overhead protocol with longer transmission and processing times. In general, with the very fast networking requirements of games, a better choice is the smallest and cheapest (in terms of overhead) protocol available. But if this choice means that your game may experience data loss and out-of-order data packets, your code must account for that possibility.
updateObjects()
Once we have determined our elapsed frame time and processed all of the input for this frame, it's time to update the positions of all objects. Object positions are based, in general, upon two factors: elapsed time (a moving object must be moving at some rate per time) and change in movement (presumably triggered by some event). There is also object collision that can cause movement change, but we'll handle that as part of this updateObjects() process.

The general idea behind updateObjects() is simple: for all objects that can move this frame, calculate their movement and reposition them accordingly:


public void updateObjects() {
    for (Movable movable : movables) {
        movable.update(elapsedFrameTime);
    }
    processCollisions();
}

The interesting for() statement is based on the new, expanded for() semantics in release 5.0. Essentially, we're just saying that for all of the objects that can move, go ahead and move them by calling update() on those objects.

The update() method left unspecified above is a method that takes the current elapsed time for this frame and calculates the new position for that object according to movement information that the object knows about. This includes the object's previous position and its speed (or acceleration, in the case of nonlinear movement).

processCollisions()
Collision processing can be one of the most complex parts of your game depending on several factors: how many objects can potentially collide; how many of those objects are dynamic (moving) objects; and how physically correct you would like your collisions to be.

In the simple case of the Ping demo there are only two types of collisions possible: the paddles with the walls, and the ball with the paddles and walls. The paddle/wall collisions are handled implicitly during the gatherInput() stage; keyboard events determine paddle movement and this movement is merely constrained to be within the area defined by the walls. The ball collisions are handled during the processCollisions() call and consist of checking the ball boundaries against the wall/paddle boundaries and calculating new positions based on any collisions and bounce effects.

Interestingly, even this "simple" collision caused artifacts in the original version of the Ping demo to use only the ball center instead of the ball bounds, as our code simplified the collision detection algorithm. This meant that the ball would not "collide" at exactly the right time and place; if one part of the ball collided with a paddle but the center of the ball did not, we would not detect the collision and the ball would flow right through. The current version of the demo fixes that problem by using simplifying assumptions about which sides of the ball can collide with which sides of each paddle.

In any case, the processCollisions() step in our demo consisted of checking a single moving object (the ball) against the various elements in the scene with which it might collide. Note that multiple collisions might be detected (the ball trajectory might intersect both a paddle and a wall, for example); in that case, the closest collision would be selected (if the ball hit the paddle first, the collision against the wall would be invalid because the ball would bounce off the paddle). If a collision was detected, a bounce would occur and a new position would be calculated. Then collision processing must happen again for the new trajectory that the ball takes after that first bounce. This process must be repeated until there are no more collisions for that object in this frame.

This process is illustrated in Figures 2-5.

Figure 2 shows the ball (blue) traveling toward the paddle (yellow) with the trajectory illustrated by the dotted line, in the direction of the arrow. We calculate two collisions (black Xs), one with the paddle and one with the wall (pink). The original endpoint of the ball would be where the gray ball is painted inside the wall (if there were no collisions).

Figure 3 shows the next step in processCollisions. We've calculated that the ball will bounce off the paddle first and travel in the resulting trajectory toward the wall, resulting in the new collision shown with the new black X.

Figure 4 shows the next step in processCollisions() where we have calculated a bounce off the wall and a trajectory for the ball flying back out into the playing area.

Finally, in Figure 5 we show the final state of the ball (still in gray) with the trajectory and collisions as shown by the lines and Xs that caused the ball to end up where it is.

One thing that this example glosses over is the actual calculations involved, both the calculation of each collision as well as the calculation of the bounce. We'll save that discussion for the code itself where you can see what we did to calculate these results in the demo. However three points are important to bring up about this process.

1.  Trajectory Versus Position Collision
The simplest approach to collision detection would be to simply calculate whether the end position of an object overlaps with any other object in the world. If so, do the right thing. If we had taken this approach in the previous example, it's easy to see what artifacts would result. In the first picture we would not have calculated the bounces as shown; we would have just detected that we were inside the wall and would then calculate a bounce based on that collision while ignoring the first collision that actually should have occurred with the paddle.

To do this correctly requires calculating collisions based on object trajectories, not just object positions. In the figures this means we need to calculate the collisions between the dotted line representing the object movement and the objects that the line encounters.

2.  Physically Accurate Collisions
Figures 2-5 show a single vector that we use to base the collisions on. However, the ball occupies an area, not just a point. To calculate correct collision information, we would need to calculate the intersection of the ball area with all available objects, not just some point or line representing its trajectory.

To simplify the demo code (and make sure it was ready to be shown at JavaOne), we actually used the simplified approach of intersecting a single line in the version we showed at the conference. It worked pretty well in general, but had visible artifacts. For example, if the collision point is based on the center of the ball, you'll notice the ball passing through objects up to that center point; not very realistic (even for a game this unrealistic to begin with), and the artifacts only worsen with the size of the objects that take this simplified approach.

For a real game with much more complex objects than our simple ball, say cars or planes, you would need to decide what level of simplification you could live with, if any, and what artifacts those assumptions would cause. For example, you could use a simple bounding box or circle around an object to calculate collisions; this is better than the point-based approach above, but would still have artifacts such as detecting collisions when there were none (because the bounding area might collide when the actual object inside that area would not).

3.  Bounce Calculation
The figures assume a standard thetaI == thetaR (angle of incidence equals angle of reflection) equation for the bounce. This works fine, in general, but ignores some more complicated and interesting possibilities such as putting english, or spin, on the ball. For example, if a paddle is moving when the ball hits it, it would be reasonable to figure in some kind of angle perturbation based on the speed of paddle movement, such as you would get if a tennis racket were moving sideways when it struck a ball (thus putting spin on the ball and changing the angle of reflection). The Ping demo shows some of this behavior, as we modify the angle of reflection based on the speed that the paddle is moving when it hits the ball.

This was the case for our simple one-collidable-object case in Ping - imagine how complex this process would be if our world consisted of multiple dynamic objects or if the objects were dynamically deforming or even if the collisions were accurately modeled on complex objects. The equations in all of these cases become much more involved and need to be carried out potentially many times in each frame as objects bounce off possibly several other objects in any given frame.

render()
The main idea in the rendering stage is to traverse the world of visible objects and draw all of them to the screen. Of course the details are a bit more involved. In general, for most 2D games, the scene rendering might be boiled down to something like:


1:    public void render() {
2:        renderBackground();
3:        renderObjects();
4:        renderForeground();
5:        showBuffer();
6:    }

Let's analyze each method call in turn.

Line 2: renderBackground() draws the background image or any other static graphics that tend to be the same in every frame. It underlies everything else in the game, so draw it first.

Line 3: renderObjects() draws all of the static and movable objects in a game. This includes things like the walls, paddles, and ball from the Ping demo. You may want to break apart the static and movable objects and draw one or the other first (for example, maybe your player characters should always appear on top of any static objects, in which case you should draw the static objects before the movable objects).

Line 4: renderForeground() draws anything that overlaps the game, such as the score, any help, status windows, or text, a dashboard in a driving game, or other things that are considered to be separate from the world of the actual game objects. Since these things need to be rendered on top of the rest of the game, we draw them last.

Line 5: showBuffer() - in general, games will always draw to an offscreen buffer instead of directly to the screen. This makes animations appear much smoother and game play more enjoyable. After everything is rendered to the back buffer, the final step is to show this buffer on the screen. The details of how to do that will be discussed in Part 2.

This is a pretty gross simplification of the rendering process. The actual work your application would do to rendering would be highly dependent upon the type of game that it is. For example, 3D games have very different requirements than 2D games. In the 2D domain, there are many different types of games (scrollers, top-down, action, word, arcade, etc.); how you choose to render your world depends much on what you have to render and what the interface is like.

There are, however, some basic elements of 2D rendering that are common to many different games in that domain. Next issue, we will dive into 2D rendering issues, such as buffering, fullscreen, image usage, and performance tips. We will also give an overview of the Ping demo code.

SIDEBAR

Important Caveats and Petty Justifications
We (the authors) are not game programmers, instead we develop graphics libraries and tend to know a thing or two about game programming concepts. Therefore this article is intended more for programmers who would like to know more about how to write basic games in Java rather than advanced game programmers. We hope the information about Java programming will benefit anyone who wants to know more about doing graphics programming on the Java platform, but we don't want to mislead anyone who is looking for state-of-the-art information on how to write a really slick circa-1980s arcade game...

Demo
This demo illustrates the points of the article and presentation and is not intended to be the end-all of 2D game programming. Instead, we focused on the general concepts of game frameworks and Java2D tips and tricks. So take the game in the spirit in which it is offered, consume it, and have fun writing something better.

More Stories By Chet Haase

Chet is an architect in the Java Client Group at Sun Microsystems. He spends most of his time working on graphics and performance issues and futures.

More Stories By Dmitri Trembovetski

Dmitri Trembovetski is an engineer in the Java 2D team at Sun Microsystems, Inc., where he focuses on graphics rendering and performance issues for the Solaris and Linux platforms. Read his frequent posts on the forums at http://javagaming.org.

Comments (1) View Comments

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.


Most Recent Comments
Rob Walch 10/12/04 09:20:43 AM EDT

Nice article. I would like to see more java game articles. J2ME and brew ones too!