WO1998014886A1

WO1998014886A1 - Synchronization of events occurring over a network in the presence of latency

Info

Publication number: WO1998014886A1
Application number: PCT/US1997/017661
Authority: WO
Inventors: H. Scott Roy; William D. Harvey
Original assignee: Sandcastle, Inc.
Priority date: 1996-09-30
Filing date: 1997-09-30
Publication date: 1998-04-09
Also published as: AU4804097A

Abstract

A method for synchronizing events in a multi-player game played from multiple computers compensates for network delays between events occurring on different computers. Latency between local and remote computers in a game is measured by the local computer (1901). The local computer receives local game inputs from a local player to control a local character and remote inputs to control a remote character. While the local computer waits for remote inputs to begin, the remote character is displayed independent of remote inputs while masking visual effects are applied to the remote character (1903-1905). While the local computer waits for remote inputs to end, the local character is displayed independent of local inputs while masking visual effects are applied to the local character (1906-1909). Masking visual effects are applied for a time period based on the latency between the computers (1902). The masking visual effect applied to the local character provides sufficient time to receive a signal from the remote computer indicating occurrence of a remote event. The local computer determines the proper order for corresponding remote and local events based on when the signal was received (1910).

Description

SYNCHRONIZATION OF EVENTS OCCURRING OVER A NETWORK IN THE PRESENCE OF LATENCY

FIELD OF THE INVENTION The present invention pertains to the field of computer networking. More particularly, the present invention relates to determining an order of events occurring on a network in the presence of network latency. BACKGROUND OF THE INVENTION

Use of the Internet has increased rapidly in recent years. Of the many possible uses of the Internet, one which has generated particular interest for many users is the use of the Internet to play computer games. Current technology allows two players at different geographic locations to play a game together using a direct telephone or ISDN connection, and it also allows more than two players to play a game over local area networks (LANs) in which each player uses a different computer. There are unique problems, however, associated with implementing a multi -player computer game across a wide area network (WAN) , particularly one as expansive as the Internet .

One such problem results from the communications delays of the Internet, which can be substantial and unpredictable. In computer games, players enter inputs to control various objects represented on a display device. In a network- implemented game, different objects may run on different machines. Because inputs from a human being tend to be unpredictable in a game situation, objects running on a remote computer must be represented on a local computer at a time delay. The problem is that it is common in computer games for two or more objects to interact (i.e., to appear to come into contact) . For example, two game characters might contact each other, or a game character might strike a ball. If an interaction occurs between two objects, the interaction should be accurately depicted on the display device of each participating computer. However, if a computer game is played over the Internet, the inherent delays of the Internet can make it difficult to achieve this result. In particular, if two objects are shown with different amounts of time delay, then their interactions will not appear to be correct.

Consider the well-known pong game, in which two players, Player A and Player B, manipulate their respective game controllers to hit a ball back and forth across a screen using paddles. If the game is played over the Internet, then Player A' s paddle will be shown on Player B's computer at a time delay, while Player B's paddle will not be shown at a time delay. Similarly, on Player A' s computer, Player B's paddle will be shown at a time delay, while Player A' s paddle will not be shown at a time delay. If Player A hits the ball, then his paddle must be shown on Player B's computer as actually hitting the ball. However, because of the time delay, Player B's computer will not have the position of Player A' s paddle at the time of contact until some time after the contact has occurred. Hence, there is a problem of synchronizing interactions between objects that are distributed across a network.

Therefore, what is needed is a technique for synchronizing computer-implemented objects that must interact in a network environment subject to substantial and unpredictable delays. What is further needed is a technique for synchronizing computer- implemented objects that interact in a multi-player game environment implemented on the Internet. Another problem associated with implementing a multi -player game over the Internet is determining the order of events that occur on different computers and ensuring that each player sees these events occur in the same order. This problem may arise in any game in which two or more players using different computers each try to complete some task first. For example, in a game simulating a race, each player might control a game character's progress through a race course to a finish line. Another game which is sensitive to event ordering is a "shootout," or a contest of who is the quickest to draw and fire a weapon. Internet delays create difficulty in determining the correct order of events, such as a player finishing a task, because those events occur on different computers. This problem is most serious when the time differences between events are close to the network latency in magnitude. For example, if one player beats another by one half of a second in a race, and the network latency between the two players is a full second, then in a naive implementation, the players may see different outcomes, and each may think he won the race .

Therefore, a technique is needed for determining an order for events occurring in a network environment subject to substantial and unpredictable delays and for showing those events occurring in the same order on all machines. In particular, a technique is needed for determining an order for events occurring in a multi- player game environment on the Internet .

SUMMARY OF THE INVENTION

A method is provided of synchronizing progress of multiple objects through a total of N + M states in a sequence of events. Each object is affected by a particular one of multiple input sequences during the sequence of events. In the method, N states are generated for each object based on its input sequence, and M states are generated for each object independent of its input sequence. Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements and in which:

Figure 1 illustrates a number of computer systems connected over the Internet . Figure 2 illustrates a computer system in which the presented invention can be implemented.

Figure 3 illustrates a display showing a number of objects .

Figure 4 is a representation of two timelines corresponding to two objects.

Figure 5 is snapshot showing a moment in time on one player's computer at which two objects are represented at different points on their timelines.

Figure 6 is snapshot showing a moment in time on one player's computer with respect to several different objects maintained by that computer.

Figure 7 illustrates a display corresponding to a computer- implemented pong game.

Figure 8 is a representation of a timeline of a ball in a pong game.

Figure 9 is a representation of the ball in a pong game being displaced along its timeline. Figure 10A illustrates the display screens associated with two players of a pong game running over the Internet at the same moment in time.

Figures 10B and IOC are snapshots showing the same moment in time on each of the displays shown in Figure 10A.

Figure 10D illustrates the display screens associated with two players of a pong game running over the Internet at the same moment in time. Figures 10E and 10F are snapshots showing the same moment in time on each of the displays shown in Figure 10D.

Figure 10G illustrates the display screens associated with two players of a pong game running over the Internet at the same moment in time.

Figures 10H and 101 are snapshots showing the same moment in time on each of the displays shown in Figure 10G.

Figures 11A and 11B are representations of altering the progression of an object along its timeline.

Figures 12 is a flow diagram illustrating a routine for synchronizing two objects according to one embodiment .

Figure 13 is a representation of a timeline of a ball in a computer-implemented football game running on the Internet .

Figure 14 is a representation of the ball in a football game being displaced along its timeline.

Figures 15 is a flow diagram illustrating a routine for synchronizing two objects according to an alternative embodiment.

Figure 16 is a representation of timelines associated with two game characters in a computer- implemented racing game. Figure 17A is a representation of the timelines of Figure 16 as perceived by a first player of the racing game in the absence of the present invention.

Figure 17B is a representation of timelines of Figure 16 as perceived by a second player of the racing game in the absence of the present invention.

Figure 18A is a representation of the timelines of Figure 16 as perceived by a first player of the racing game using the present invention. Figure 18B is a representation of timelines of Figure 16 as perceived by a second player of the racing game using the present invention.

Figures 19 is a flow diagram illustrating a routine for determining the order of two events occurring in a network-implemented computer game.

Figures 20 is a flow diagram illustrating a routine for determining the order of two events occurring in a network-implemented racing game.

Figure 21A illustrates a computer- implemented racing game.

Figure 21B illustrates the computer- implemented racing game of Figure 21A, as perceived by two players, in the absence of event synchronization.

Figure 21C illustrates the computer- implemented racing game of Figure 21A, as perceived by two players, with event synchronization.

DETAILED DESCRIPTION

A method is described of determining an order of events occurring on a network in the presence of network latency. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be evident, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate description of the present invention. To implement a computer game over a network that has significant communications latency, such as the Internet, it is necessary to synchronize interactions between objects that are controlled from different computers, so that the interactions look correct to all players. It is further necessary to determine the correct order of events that occur on different computers, such that the same order is determined for those events by each computer on the network. As will be described below, the present invention includes techniques for achieving these results.

Referring now to Figure 1, a network configuration 1 is illustrated in which the present invention can be implemented. A number of computer systems 2A, 2B, and 2C are in communication with each other over the Internet 3. Each of the computers 2A, 2B, and 2C is used by a different person (player) in playing a multi-player computer game over the Internet 3.

Figure 2 illustrates one possible architecture for any of the computer systems 2A, 2B, and 2C. Note that the architecture of Figure 2 is provided only for purposes of illustration- -a computer system used in conjunction with the present invention is not limited to any particular architecture. The computer system 2 of Figure 2 includes a central processing unit (CPU) 10, random access memory (RAM) 11, a mass storage device 12, a modem 13, a visual display device 14, a game controller 15, and read-only memory (ROM) 16. Mass storage device 12 includes an optical, magnetic, or other similar storage medium suitable for use with a personal computer system. The game controller 15 may include a joystick, a mouse, a trackball, a keyboard, a special-purpose game controller designed for use with certain games, or any combination of these devices.

In one embodiment, the present invention is carried out in each computer system participating in the game in response to its CPU 10 executing sequences of instructions contained in memory, such as RAM 11. That is, execution of the sequences of instructions contained in memory causes the CPU 10 to synchronize interactions between objects, as will be described below. The instructions may be loaded into memory from a persistent store, such as mass storage device 12, and/or from one or more of the other computer systems (collectively referred to as a "host computer system" ) over the Internet 3. For example, a host computer system may transmit a sequence of instructions to the participating computer system in response to a message transmitted to the host computer system over a network by the participating computer system. As the participating computer system receives the instructions via a network connection, such as modem 13, the computer system 2 stores the instructions in memory. The computer system 2 may store the instructions for later execution or execute the instructions as they arrive over the network connection. The host computer system may be one of the computer systems participating in the game .

In some cases, the downloaded instructions may be directly supported by the CPU 10. Consequently, execution of the instructions may be performed directly by the CPU 10. In other cases, the instructions may not be directly executable by the CPU 10. Under these circumstances, the instructions may be executed by causing the CPU 10 to execute an interpreter that interprets the instructions, or by causing the CPU 10 to execute instructions which convert the received instructions to instructions which can be directly executed by the CPU 10.

In alternative embodiments, hardwired circuitry may be used in place of, or in combination with, software instructions to implement the present invention. Thus, the present invention is not limited to any specific combination of hardware circuitry and software, nor to any particular source for the instructions executed by a computer system. In one embodiment, each computer system participating in the game includes software for generating the multi-player computer game (the "game software"), including software embodying the present invention. The game software may be stored in mass storage device 12, RAM 11, ROM 16, or any combination of these devices. In addition, the game software may be distributed between two or more of the participating computer systems 2.

I. Synchronization of Interactions Between Objects In accordance with the present invention, each object in the game has one or more "timelines." A timeline is a function that gives the state of an object at different points in time throughout a given time interval. The "state" can include information about an object's position, size, color, or orientation as displayed on the display device 14, or any other characteristic of the object, regardless of whether or not that characteristic can be perceived by a person. A timeline may be thought of as a history of an object with respect to all of the information included in the object's state.

In one embodiment, each computer system participating in the game maintains a timeline for each object that is capable of interacting with another object. For each such object, each computer system may actually maintain more than one timeline, where each timeline represents a different characteristic. However, in order to simplify description, it is henceforth assumed that each computer maintains only one timeline for each object, and that the object's timeline includes all of the information about that object.

At any point in time, a computer system maintains information on the present state of all objects that are controlled from that (local) computer system. However, because of the substantial delays on the Internet, the computer system does not have knowledge of the present state of objects controlled from other (remote) computer systems. Rather, information on the present state of objects that are controlled from remote computer systems only becomes available after some delay. Nonetheless, each computer system can represent an object at any point on the object's timeline that corresponds to a point in time in the past, present, or future. When displaying an object at a point on its timeline for which complete information is not available, the local computer will determine the most likely state of the object. In a technique known as "dead-reckoning, " the most likely state of an object at a given point in time is estimated based on a known state of the object at an earlier point in time. For example, the object's current position might be estimated based on a known position, speed, and/or direction of the object at an earlier time. In any event, it is imperative that when two objects interact, they are both shown simultaneously arriving at the points on their respective timelines at which the interaction occurs.

Figure 3 illustrates a computer display 25 on which a number of different objects 31-37 are rendered during execution of a computer game. At various points in time, two or more of the objects 31-37 may interact in various different ways. Figure 4 illustrates two timelines 41 and 42 associated with two objects. The timelines 41 and 42 describe the position of each respective object with respect to time. At any given point in time, the state of the object is defined by a point on its timeline, as represented by points 43 and 44 in Figure 4. At a point in time when the objects come into contact as depicted on a display device, the timelines 41 and 42 intersect, as represented by point 45 in Figure 4. Hence, each object has a point on its timeline that corresponds to the time of interaction, namely point 45 in the example of Figure 4.

As mentioned above, a local computer does not have information on the present state of objects that are controlled from remote computers until after some delay. This effect is illustrated in Figure 5. Figure 5 shows a "snapshot" showing a moment in time on one player's (local) computer at which two objects are represented at different points on their timelines. In Figure 5, two timelines 47 and 48 correspond to two different objects. Each of the two objects is displayed on at least two computers, a local computer and one or more remote computers. Timeline 48 corresponds to an object that is controlled by one player from the local computer. Timeline 47 corresponds to an object controlled by another player from a remote computer. At the moment the snapshot is taken, the object controlled from the local computer is displayed at a point 50 on its timeline 48. Point 50 corresponds to the present time t_A. In contrast, the object controlled from the remote computer is displayed at point 49, corresponding to an earlier point in time t_B. The difference t_A - t_B between the present time t_A and time t_B is equal to the delay in communications between the local computer and the remote computer. Refer now to Figure 6, which shows a snapshot of objects 31-37 (in Figure 3) at a moment in time on a local computer. That is, Figure 6 represents the states of objects 31-37 as they are displayed by the local computer at the moment of the snapshot. Timelines

31A-37A correspond to objects 31-37, respectively. To simplify explanation, the position coordinate for timelines 31A-37A are not shown- -only the time coordinate is shown. In the example of Figure 6, objects 31-33 and object 37 are controlled by a first player from the local computer; objects 34 and 35 are controlled by a second player from a first remote computer; and, object 36 is controlled by a third player from a second remote computer. An "X" denotes the point at which computer system 2A is displaying each object on its timeline at the moment of the snapshot .

Objects 31-33 and 37 are represented at the present point in time t_A on their respective timelines, because these objects are all controlled from the local computer system 2A. In contrast, objects 34-36 are all controlled from a remote computer and are therefore represented at earlier points t_B on their respective timelines compared to objects 31-33 and 37. This time lag is necessitated by network latency, because there is a delay in the local computer's receiving state information for objects 34-36 . In this example, object 36 is controlled from a different computer than objects 34 and 35 and is subject to a greater network delay than those objects. Hence, object 36 is displayed at an earlier point in time t_c than are objects 34 and 35. In accordance with the present invention, a computer system determines the point on an object's timeline at which to display the object, based on the network latency and interactions that object has with other objects. That is, based on this information, the j - computer system will select which state of the object to presently display from any of the states the object will actually have or that the computer predicts the object might have during a particular time interval. The selected state will not necessarily correspond to either the present time or to the most recent time for which state information about an object has been received. This technique will be described below in detail .

Refer now to Figure 7, which illustrates a display 61 associated with the well-known pong video game. In the pong game, two players control two different paddles 62 and 63, respectively, to hit a ball 64 back and forth across the display 61. Player A' s paddle 62 is capable of movement only along line 65, while player B's paddle 63 is capable of movement only along line 66. In this simple example, the ball travels at a constant speed, which will be referred to as its "normal" speed. A player scores a point when his opponent misses the ball 64. Figure 8 shows a representation of a timeline 69 of the ball 64. The timeline 69 represents the position of the ball 64 at each point in time from time 0 to time 600. (Note that the units of time are unimportant and that the time values mentioned herein are only given for purposes of explanation.) Line 65A in Figure 8 corresponds to line 65 in Figure 7, while line 66A in Figure 8 corresponds to line 66 in Figure 7.

During the game, Player A hits the ball 64 with his paddle 62 at time 100, sending the ball 64 across the display 61 toward the paddle 63 of Player B. The point of impact (interaction) between Player A' s paddle 62 and the ball 64 is represented in Figure 8 by point 70. At time 200, Player B strikes the ball 64 with his paddle 63, sending it back across the display 61 towards Player A. The point of interaction between Player B's paddle 63 and the ball 64 is represented by point 71 in Figure 8.

A problem occurs when the pong game is implemented over the Internet. Although Player A' s computer always has current knowledge of the position of Player A' s paddle 62, Player A' s computer never has current knowledge of Player B's paddle 63, as a result of network latency. The problem, therefore, is how to represent a contact between the ball 64 and Player B's paddle 63 on Player A' s computer, given that the position of Player B's paddle 63 is not known until after the interaction has occurred. Using dead-reckoning, Player A' s computer could only guess at the position of Player B's paddle at the time of interaction. Using the present invention, Player A' s computer does not dead-reckon the position of Player B's paddle, but instead shows it at a time delay. In addition, the progression of the ball 64 along its timeline is altered at various points in time, based on the measured network latency, in order to synchronize the ball's interactions with both players' paddles when it hits the paddles.

In one embodiment, the rate at which the ball 64 progresses along its timeline on Player A' s computer is altered immediately after Player A hits the ball to a speed slower than the normal speed. Visually, the ball 64 appears to slow down as it travels across the display of Player A' s computer. The change in speed can be made gradually to make it less apparent to the user. As a result, when the ball 64 appears to reach Player B's paddle 63 on Player A' s computer, it will be running at the same time delay as Player B's paddle, so that the interaction between the ball 64 and Player B's paddle 63 will look correct, and so that the new trajectory of the ball 64 can be determined. The extent to which the speed of the ball is decreased will depend upon the measured communications delay between Player A' s computer and Player B's computer. The speed of the ball 64 can be decreased slightly more than is necessary to allow Player A' s computer to receive the interaction-time position of Player B's paddle 63 before the ball 64 is shown reaching Player B's paddle 63 on Player A' s display 61. In one embodiment, the latency is measured periodically during the game .

Once the ball 64 is shown on Player A' s display 61 as contacting Player B's paddle 63, the rate of its progress along its timeline is increased to slightly faster than the normal rate of speed until the ball 64 contacts Player A' s paddle 62, so the ball 64 is back in the present time when it appears to reach Player A' s paddle 62 on Player A' s computer. Again, these changes in speed can be made gradually to make them less apparent to the user.

The above technique is also independently used by Player B's computer system. That is, (in the above embodiment) the rate at which the ball 64 progresses along its timeline on Player B's computer is altered immediately after Player B hits the ball to a speed slower than the normal speed. As a result, when the ball 64 appears to reach Player A' s paddle 62 on Player B's computer, it will be running at the same time delay as

Player A' s paddle 62, so that the interaction between the ball 64 and Player A' s paddle 62 will look correct on Player B's computer. Once the ball 64 is shown on Player B's computer as contacting Player A' s paddle 62, the rate of progress of the ball 64 along its timeline is increased to slightly faster than the normal rate of speed until the ball 64 contacts Player B's paddle 62, so that the ball 64 is back in the present time when it reaches Player B's paddle 63 on Player B's computer. As compared to a situation with no latency, a player sees the ball move away from him slower than normal and toward him faster than normal. Thus, with the above technique, the enjoyment of the game is not diminished for either player, because each player must react to the ball with at least the same degree of skill and quickness as if both player's were using the same computer (i.e., as if there were no delay) .

Figure 9 illustrates the position of the pong ball 64 over time, as displayed on Player A' s display 61, according to one embodiment. At a time just before time 100, the ball 64 is traveling toward Player A' s paddle 62, as represented by line 69A in Figure 9. At time 100, Player A' s paddle 62 strikes the ball 64, sending the ball 64 back toward Player B's paddle 63. At the moment of interaction between the ball 64 and Player A' s paddle 62, the speed of the ball along its timeline is decreased based on the measured one-way latency Δt between Player A' s computer and Player B's computer, as shown by line 72. As seen by Player A, the speed of the ball 64 is consequently reduced when traveling away from Player A' s paddle 62 so that the ball 64 reaches line 66 on the display 61 at a time no sooner than the time at which Player A' s computer receives the position of Player B's paddle 63 at the time of interaction. Thus, the ball 64 is shown as reaching line 66 (see Figure 7) at a time 200 + Δt on Player A' s display 61. Upon striking Player B's paddle 63 at time 200 + Δt , the speed of the ball 64 is increased, as displayed on Player A' s display 61, so that the ball 64 is displayed at the present point on its timeline when it reaches Player A' s paddle 62. This process is then repeated as long as Player A and Player B continue to strike the ball 64 with their paddles.

Figures 10A through 101 further illustrate the technique of altering the progression of the ball 64 along its timeline to compensate for network latency. Figure 10A illustrates computer displays 61A and 61B of Players A and B, respectively, at a time t . Figure 10B shows the position on Player A' s display 61A of the ball 64, Player A' s paddle 62, and Player B's paddle 63 at time t-_L- Figure IOC shows the position on Player B's display 61B of the ball 64, Player A' s paddle 62, and Player B's paddle 63 at time t_λ .

At time t_{l t} the ball is traveling toward Player B's paddle 63. On Player A' s display 61A, Player A' s paddle 62 is displayed at the present time t-^ on its timeline. However, Player B's paddle 63 is shown at a different time, t₁ - Δt, on its timeline, where Δt is the one-way network latency. According to the present invention, at time t_x Player A' s computer is shifting the ball 64 back in time along its timeline . Therefore, at time t-_L the ball 64 is displayed on Player A' s display 61A at a point on its timeline that is earlier than the present time t_x. Specifically, the ball 64 is displayed at a point on its timeline that is slightly later than t-_L - Δt , because the ball 64 has almost reached Player B's paddle 63. By the time the ball 64 appears to reach Player B's paddle 63 on Player A' s display (at some time later than t_x) , it will have been shifted along its timeline back to the same point in time at which Player B's paddle 63 is displayed.

In contrast, Player B's computer always has current information regarding the location of Player B's paddle 63, but not regarding the location of Player A' s paddle 62. Hence, at time t Player B's paddle 63 is displayed at the present time t_x on its timeline, while Player A' s paddle 62 is displayed at time t_x - Δt on its timeline. Further, since the ball 64 is traveling toward Player B's paddle 63 at time t_lf Player B's computer is shifting the ball 64 forward on its timeline, so that it will be displayed on Player B's display 61B at the (then) present time when it reaches Player B's paddle. Since the ball 64 has nearly reached Player B's paddle 63 at time t_x, the ball 64 is displayed on Player B's display 61B close to the (current) present time t .

Refer now to Figures 10D through 10F, which illustrate a second point in time t₂ that is later than time t_x. Figure 10D illustrates displays 61A and 61B at time t₂. At time t₂, the ball 64 has already struck Player B's paddle 63 and is traveling back toward Player A' s paddle 62. Player A' s paddle 62 is displayed on his display 61A at the present time t₂ on its timeline, while Player B's paddle 63 is displayed at time t₂ - Δt on its timeline. Conversely, on Player B's display 61B at time t₂, Player A' s paddle 62 is displayed at time t₂ - Δt on its timeline, while Player B's paddle 63 is displayed at the current time t₂ on its timeline.

At time t₂ the ball is being shifted forward along its timeline on Player A' s computer and backward along its timeline on Player B's computer. The ball 64 is approximately half-way between Player A' s paddle 62 and Player B's paddle 63. Consequently, the ball 64 is displayed on Player A' s display 61A approximately halfway between the present time t₂ and time t₂ - Δt on its timeline, as illustrated in Figure 10E. Similarly, the ball 64 is also displayed on Player B's display 61B approximately half-way between the present time t_{2 and txme} t₂ - Δt on its timeline, as illustrated in Figure 10F.

Figures 10G through 101 correspond to a third point in time t₃ that is later than time t₂. At time t₃, the ball has just struck Player A' s paddle 62, as shown in Figure 10G. However, Player B's computer has not yet received an indication from Player A' s computer that the contact has occurred. Therefore, at time t3 the ball 64 is being shifted backward along its timeline on Player A' s computer; however, it is also still being shifted backward along its timeline on Player B's computer, since the contact with Player B's paddle 63 has not yet been displayed on Player B's display 61B. As soon as Player B's computer receives an indication that the interaction has occurred (which may be simply the position of Player A' s paddle 62 at the time of interaction), Player B's computer will begin to shift the ball 64 backward along its timeline. Hence, at time t3, Player A' s display 61A shows the ball 64 at a point on its timeline slightly earlier than the present time t₃, since the ball has just left Player A' s paddle 62 and is now moving backward along its timeline. Player B's display 61B shows the ball essentially at point t₃ - Δt on its timeline, because the interaction is just about to occur on Player B's display 61B.

In an alternative embodiment, instead of altering the speed of the ball as displayed on Player A' s computer, the ball is paused on the display 61 at a convenient point, such as at the point at which the ball 64 reaches line 66 (Figure 7) . The pause is long enough to allow Player A' s computer to receive the position of Player B's paddle 63 at the time the ball reached line 66. In another embodiment, the displayed speed of the ball may be varied as it travels from one end of the display to the other.

Figure 12 illustrates a routine performed by a local computer for synchronizing two interacting objects. Either or both of these objects may be running on a remote computer. Initially, the local computer measures the one-way communications delay Δt between itself and the remote computers on which the objects are running (step 1201) . The local computer uses this latency to set the time delay according to which certain objects will be displayed (such as the remote player's paddle in the pong game) (step 2102) . Latency measurements may be made on a periodic basis . Upon the occurrence of a trigger event (step 1203), the local computer computes the time and location of the next interaction (step 1204) . An example of a trigger event is the striking of the pong ball by a player's paddle. Next, the local computer shifts one of the objects along its timeline to bring the two interacting objects into synchronization (step 1205) . The amount by which the object is shifted is dependent upon the difference in time delay between the two objects and the time at which the interaction will occur. Note that this shifting can be gradual or instantaneous. A gradual shifting will occur if the progress of an object along its timeline slows down or speeds up. The user might perceive this as a change in the speed of movement of the object. Conversely, an instantaneous shifting of the object along its timeline might appear as the object's jumping ( " teleporting" ) from one point to another on the display. Teleporting results from the transferring of the object directly from a first point in time on its timeline to a second point in time on its timeline, such that the object does not pass through the points in time that are between the first and second points in time, as it advances along its timeline. The particular method chosen (gradual or instantaneous) for shifting an object along its timeline is at the discretion of the game designer.

Figure 11A illustrates the relationship between real time on a local computer and the displayed point in time of the ball 64 on the local computer, according to one embodiment of the pong game. If the ball 64 were always displayed with no time delay, as if both players were using the same computer, then the relationship could be represented by line 74. However, the relationship in this embodiment of the present invention is instead given by line 75. In Figures 11A and 11B, times 200 and 400 are the times on the local computer at which the ball 64 strikes the remote player's paddle 62. Time 300 represents the time at which the ball 64 strikes the local player's paddle 62. In the embodiment of Figure 11A, the speed of the ball along its timeline is varied according to the direction in which it is traveling in order to compensate for network latency.

Figure 11B relates to a different embodiment of the pong game, in which the ball is "jumped" to a different point in time on its timeline, rather than altering the rate at which the ball progresses along its timeline. In this embodiment, the ball 64 is shown on the local computer's display moving at a speed slower than normal when traveling away from the local player's paddle 62 and at the normal speed when traveling toward the local player's paddle 62. However, the ball 64 is immediately moved forward on its timeline to the local computer's timeframe as soon as the local computer receives confirmation that the ball hit the remote player's paddle, as indicated by the discontinuities in line 76 at times 200 + Δt and 400 + Δt . The local player will see the ball instantly teleport from one point on the display to another in this embodiment . The present invention can be implemented in various other types of network- implemented computer games to accurately represent interactions between objects. For example, in game involving hand-to-hand combat between two characters, a contact between one character's fist and part of the other character's body is a common interaction. The fist of the character throwing the punch (the local character) can be shifted back along its timeline by showing a slow, dramatic backswing while the event message indicating the punch is sent to the remote computer system. The (local) player initiating the punch will see the contact made after it has occurred on his opponent's computer and after a message confirming the contact has been received by his local computer. Conversely, a punch initiated by his opponent will appear as a quick jab with little or no backswing.

Alternatively, the present invention can be applied to many "throw-and-catch" computer games (e.g., football, baseball, etc.) to represent an interaction between a thrown ball and a receiving character. An example of such a throw-and-catch type of game is now discussed with respect to Figures 13-15. Assume that the game comprises two game characters moving about the screen, throwing a ball back and forth. Each time the ball is thrown, the receiving player must maneuver his character to intercept the ball. In this game example, the precise trajectory of the ball is not known (unlike the pong game) , because the ball can be intercepted by the receiving character at any point along its flight path. That is, the ball is essentially a missile. Therefore, in this embodiment the ball must be synchronized with the receiving player's character immediately upon being released by the throwing player.

In the following discussion, each player controls a character on his local computer in a throw-and-catch game like the one just described. There is a one-way latency Δt between the two computers, so that each player sees the other's character running at a time delay Δt . To simplify explanation, it is assumed that neither player moves and that each player releases the ball immediately upon receiving it from the other player. Figure 13 illustrates the actual position (as opposed to the displayed position) of the ball, as maintained on both computers. In Figure 13, the position of the ball with respect to time is given by lines 70. At time 100, the ball reaches line 71 corresponding to Player A' s character. At this point, the ball remains motionless for a time Δt while a "throw" event message is sent over the network to Player B's computer. At time 200, the ball reaches Player B's character, the position of which is indicated by line 72. Again, the ball remains motionless for a time Δt while a "throw" event message is sent over the network, this time to Player A' s computer.

In contrast with Figure 13, Figure 14 illustrates the displayed (not actual) position of the ball with respect to time on Player A' s computer. The path of the ball, as displayed on Player A' s computer, is denoted by line 70A. At time 100, Player A receives the ball and immediately enters a "throw" input, causing the "throw" event message to be immediately sent to Player B's computer. As soon as the "throw" input is entered, Player A' s computer also pauses the ball on its timeline for a time Δt to synchronize the ball with Player B's character. After Δt, both the ball and Player B's character are running at the same time delay, so that when Player B's character catches the ball, it will look correct on Player A' s computer.

Note that when Player A' s character throws the ball, the ball is first displayed motionless on Player A' s computer for a total time of 2Δt after the throw event is sent, where 2Δt is the round-trip latency. Half of this time 2Δt is for Player A' s throw event to reach Player B's computer; the other half is for Player A' s computer to shift the ball back into the timeframe of Player B. This entire delay 2Δt can be masked from

Player A by an appropriate visual effect. An example of a masking visual effect is to show a very long "wind-up" (e.g., pre-throw arm movement) by Player A' s character before the character is shown releasing the ball at time 100 + 2Δt. When the ball is shown on Player A' s computer as reaching Player B's character at time 200 + Δt, it appears to be caught by Player B and then immediately thrown back by Player B with no delay.

Figure 15 illustrates a routine performed by a local computer system to represent an interaction between two game objects, according to the embodiment described in Figures 13 and 14. Initially, the latency between participating computer systems is periodically measured until a trigger event is detected (step 1501) . When a trigger event is detected (step 1502), an event message is transmitted by the local computer system to the remote computer system (step 1503) . The object is then paused on its timeline for a time equal to Δt while an appropriate visual effect is executed to mask this pause (step 1504) . At a time equal to Δt after transmission of the event message, progression of the object along its timeline is initiated while continuing the masking visual effect (step 1505) . Next, at a time equal to 2Δt after transmission of the event message, the local computer system begins displaying progress of the object along its timeline at its normal rate. Note that at this time, the displayed state (i.e., position) of the object lags behind its actual state by a time of Δt . While displaying the progress of the object, the local computer system also waits for a response to the event message

(such as a message indicating that the ball was received and thrown) . At a time Δt after the remote computer system has sent the response, the local computer receives the response (step 1507) . The local computer system then processes the response while displaying an appropriate visual effect (step 1508) .

II. Synchronization of Events

Another problem associated with implementing a multi -player game over the Internet is determining the order of events that occur on different computers and ensuring that each computer represents those events occurring in the same order and with the same outcome . This problem may arise in any game in which two or more players using different computers each try to accomplish some task before the other. One example of a game which is sensitive to event ordering is a "shootout", i.e., a contest of who is the quickest to draw and fire a weapon. Another example is a racing game, in which each player controls a game character's progress through a race course to a finish line. The speed of each player's character might be based on the rapidity with which the player presses keys on a keyboard or a game controller. One such racing game is depicted in Figures 21A through 21C. Figure 21A shows the display for the game in which one player controls character 91 while another player controls character 92, and each player attempts to be the first to move his character to the finish line 93. Figures 21A through 21C are discussed further below. In games such as these, communications delays of the Internet make it difficult to determine the correct order of events, such as a character finishing a race, because those events occur on different computers. The present invention therefore provides a technique for determining a correct order of events in a game implemented over the Internet, and for showing these events occurring in the same (correct) order and with the same outcome on each computer participating in the game. This technique shall be referred to herein as "event synchronization" .

Figure 16 represents timelines 81 and 82 of two players involved in a computer-implemented racing game. Timelines 81 and 82 represent positions of the players A and B, respectively, with respect to time. The race begins at a starting line represented by line 83 and ends at a finish line represented by line 84. It can be seen from Figure 16 that Player B wins the race (he reaches the finish line 84 at an earlier time than Player A) . The difference between the finishing times of Players A and B is the margin of victory MV.

Without the event synchronization of the present invention, if this game were played over the Internet by Players A and B using different computers, each player would see a different result . Refer to Figures 17A and 17B. Figure 17A represents the race as it is displayed on Player A' s computer. Assume now that the one-way network latency Δt happens to be slightly greater than the actual margin of victory (MV) . The race then appears on A' s computer according to timelines 81A and 82A, which represent the movements of Players A and B, respectively. Thus, Player A perceives that he finishes the race before Player B. In contrast, Figure 17B represents the race as it is perceived by Player B. In particular, timelines 81B and 82B represent the positions of Player A and Player B, respectively, as displayed by Player B's computer. Hence, Player B perceives that he finishes the race before Player A. Such inconsistent results are unacceptable in a game of this nature. The present invention therefore provides a technique for determining the order of events and ensuring that Players A and B see the same outcome.

Figures 18A and 18B illustrate a solution to the above problem according to a simple embodiment of the present invention. In this embodiment, the remote player' s game character is shown on the local computer moving at a constant speed until a time T after the start of the race. It may be preferable to make the time T somewhat greater than the one-way latency Δt, to account for variations in latency during the game. For purposes of this description, therefore, it is assumed that T is greater than the one-way latency Δt . The constant speed at which the remote player' s game character is shown may be based upon an average player's performance, either from empirical data or a guess, or it may be based on any other reasonable criterion. Thus, at some time before time T after the start of the race, the actual inputs from the remote player begin to be received by the local computer. Therefore, from time T forward, the remote player's game character is shown directly according to the inputs received from the remote computer.

In order to accurately display the result of the race to both players, this initial automatic movement of the remote player' s character is compensated for by a corresponding automatic movement of the local player's character. Therefore, a buffer zone is added to the end of the race course. More specifically, the race course is modified so that the buffer zone begins where the race formally ended, and the finish line is moved to the end of the buffer zone. While the local player's character passes through the buffer zone at the end of the race, his character no longer responds to inputs from the local player. Instead, the local player's character is moved through the buffer zone automatically, according to the same assumption applied to the remote player's character at the start of the race. The length of the buffer zone is computed so that it takes the local player's character a time T to pass through the buffer zone (i.e., the same amount of time that the remote player's character was moved automatically at the start of the race) . As the local player's character passes through the buffer zone, the remote player's input is allowed to catch up to that of the local player.

The addition of the buffer zone can be masked from the user so that it appears to be a part of the race course. Furthermore, the fact that the local player's character is not responding to input while moving through this buffer zone can also be hidden from the local player by generating an appropriate masking visual and/or audio effect. For example, in the racing game the local player's character is shown moving forward, even though it is not doing so in response to the local player's inputs .

According to this technique, each player will perceive the same result in the race, although not necessarily at the same instant, as shown in Figures 18A and 18B. Figures 18A and 18B represent the racing game as it is displayed on Player A' s computer and Player B's computer, respectively, using the present invention. In Figure 18A, timelines 81A and 82A represent the position over time of Players A and B, respectively. On Player A' s computer, the previous end of the race course is denoted by line 84A. A buffer zone 87A has been added to the end of the race course, so that the finish line now appears to Player A at a location indicated by line 85A. The buffer zone 87A is computed before the start of the race, so that it will take Player A' s character exactly T to pass through it at the predetermined speed, S. On Player A' s computer, Player B's character is moved automatically for a time T from the start of the race at a predetermined speed, S. In contrast, Player A' s character responds to Player A' s inputs immediately. Hence, Player B's character only begins moving according to actual input from the remote computer at a time T after the start of the race. When Player A' s character reaches line 84A (the former finish line) , his character begins to move automatically until the end of the race. Therefore, Player A perceives that he loses the race to Player B by a time of MV.

Similarly, as shown in Figure 18B, Player B will perceive the race slightly differently, although the end of the race will appear the same as it did to Player A. That is, Player B will perceive that he wins the race by a time of MV. In Figure 18B, timeline 81B represents Player A' s game character as displayed to Player B, while line 82B represents Player B's game character as displayed to Player B. On Player B's computer, the previous end of the race course is denoted by line 84B. A buffer zone 87B has been added to the end of the race course, so that the finish line now appears to Player B at a location indicated by line 85B. The buffer zone 87B is computed before the start of the race, so that it will take Player B's character exactly T to pass through it at the predetermined speed, S. At the start of the race, Player B's character immediately responds to input while Player A' s character is moved automatically at speed S for a time T. When Player B's character reaches the beginning of the buffer zone at line 84B, then his character is moved automatically until the end of the race. Thus, Player B perceives that he wins the race by MV.

Thus, the above-described event synchronization technique can be summarized as follows. During a game, the players control various objects in an effort to achieve a goal first (e.g., to complete a race first) . In response to the players' control inputs, the objects progress through a sequence of events (e.g., the race). During the sequence of events, each object advances through a total of N + M states in response to an input sequence from one of the players (where N and M are integers) . In accordance with the present invention, a local computer generates, for each object, N states for that object in response to the object's input sequence. Further, the local computer generates M states for the object independent of the object's input sequence (e.g., the automatic movement of a character) . Note that a number of variations on the above technique are possible. For example, a local computer can select and alter the distribution of the N input- based states and the M input -independent states within the sequence of events for a given object, based on the latency. In particular, some of the automatic movement (i.e., a subset of the M states) for a given character can be performed at the beginning of the race, while the rest of the automatic movement (a different subset of the M states) for that character is performed in the middle or at the end of the race. In addition, the N + M states for each object in the sequence of events may not be the same for each object. For example, the game may require the local player to complete one task before the remote player completes a completely different task.

Figure 19 is a flow diagram illustrating an overall routine performed by a local computer for determining an order of events (event synchronization) occurring over a network and for displaying the result consistently on all participating computers. Initially, the one-way latency Δt over the network is measured (step 1901) . Next, an appropriate masking visual effect is determined based upon this latency (step 1902) . In the racing game example, the masking visual effect is to automatically move the remote player's character. In the shootout game example, one possible masking visual effect is to show the remote player's character drawing his weapon. This action would be shown at a speed chosen to allow time for a message to be received from the remote computer.

After the appropriate masking visual effect is determined, the game sequence is initiated on the local computer (step 1903). The local player's game character L is then shown progressing according to input, while the remote player' s game character R is shown progressing independent of any input and according to a masking visual effect (step 1904). This routine continues until input is received for the remote computer (step 1905) . When input is received from the remote computer, then both L and R are advanced through the game sequence according to their respective inputs. Note, however, that R is displayed according to inputs that are older than L's inputs by a time equal to Δt (step 1906) . When L finishes the game sequence (step 1907) , then L is advanced through the sequence independent of the local player's inputs and according to an appropriate masking visual effect, while R continues to be shown progressing according to input (step 1908) . When an end-of -event signal is received from the remote player (step 1909) , then both L and R are shown ending the game sequence with the correct outcome and time differential (step 1910) . For example, in the racing game described above, if an end-of-race signal is received from the remote computer before L reaches the end of the buffer zone on the local computer, then the local computer determines that R wins the race; otherwise, the local computer determines that L wins the race .

Figure 20 is a flow diagram illustrating an event synchronization routine performed by a local computer for the racing game example described above. Initially, the latency Δt is measured just before the start of the race (step 2001) . Next, a race course is generated by the game software, including a start buffer zone and finish buffer zone, each of which is computed based on the measured latency (step 2002) . Note that the start buffer zone is included as a part of the normal race course, whereas the finish buffer zone is added to the end of the normal race course to create a new finish line. When a start signal is received (step 2003,) the local player's character L is displayed according to input, which is queued, while the remote player's character R is displayed moving at a constant predetermined speed, S (step 2004) . When R reaches the end of the start buffer zone (step 2005) , the local computer determines whether any input has been received from the remote computer (step 2006) . If not, R is paused in place until such input is received (step 2007) . If input has been received from the remote player, however, then each player's character is then displayed based upon queued input (step 2008) . Note again that R will be displayed according to input that is older than that of L. When L reaches the beginning of the finish buffer zone (step 2009) , then L is displayed at the constant predetermined speed, S, while R is displayed according to queued input (step 2010) . As L passes through the finish buffer zone, the remote player's input is allowed to catch up to that of the local player. When either L or R reaches the end of the finish buffer zone (step 2011) , whether in response to actual input (R) or to automatic movement (L) , then the player whose character reached the end of the finished buffer zone first is determined to be the winner of the race (step 2012) . On a given local computer, the margin of victory (MV) is computed to be the difference in finish times between the two game characters .

Figures 21A through 21C illustrate the above- described racing game, as it would appear to the players, with the use of event synchronization and without the use of event synchronization. Player A controls game character 91 while Player B controls game character 92, each in an effort to reach the finish line 93 first. Figure 21A shows the true outcome of the game (i.e., the outcome if no network latency were present) . The true outcome is that the race ends in a tie. Without the present invention, each player would see a different outcome of the race due to network latency, as shown in Figure 21B. Player A would see outcome 94A, in which his character 91 appears to win the race; however, Player B would see outcome 94B, in which his character 92 appears to win the race.

In contrast, Figure 21C shows what each player would see when event synchronization is applied. A buffer zone is added to the end of the race course, as represented by the area between line 93 and line 95. The finish line is moved to the end of the buffer zone (i.e., line 95) . As a result of the technique described above, Player A and Player B each see the race end in a tie, which is the correct outcome.

Thus, a method has been described of representing interactions between objects distributed over a network, and of determining an order of events occurring over the network, in the presence of network latency. Although the present invention has been described with reference to specific exemplary embodiments, it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the invention as set forth in the claims. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.

Claims

CLAIMSWhat is claimed is:

1. In a system maintaining a plurality of objects, each of the objects advancing through N + M states in a sequence of events, each of the objects being affected by a different one of a plurality of input sequences during the sequence of events, a method of synchronizing progress of the objects through said N + M states, the method comprising the steps of: generating N states for each object based on its input sequence; and generating M states for each object independent of its input sequence.

2. A method according to claim 1, further comprising the step of determining M based on a network latency criterion.

3. A method according to claim 2, wherein the system is one of a plurality of nodes in communication on a network, wherein the input sequences originate from different ones of the nodes, and wherein the network latency criterion corresponds to a communications latency between at least two of the nodes .

4. A method according to claim 1, further comprising the step of determining a distribution of the N and M states within the sequence of events for each object based on a network latency criterion.

5. A method according to claim 4, wherein the step of generating M states comprises the steps of : generating a first subset of said M states before generating said N states; and generating a second subset of said M states after generating said N states.

6. A method according to claim 1, wherein the N + M states may be different for each object.

7. A method according to claim 1, wherein each of the input sequences is for causing one of a plurality of events, each event associated with one of the objects, wherein the method further comprises the step of assigning a chronological order to the events.

8. A method of enabling a target computer to synchronize progress of a plurality of objects through N + M states, the method comprising the step of transmitting sequences of instructions from a host computer to a target computer, the sequences of instructions including instructions which, when executed on the target computer, cause the target computer to perform the method recited in claim 1.

9. In a computer system maintaining a first object and a second object, the first object being controlled by a first input sequence in a sequence of events and the second object being controlled by a second input sequence in the sequence of events, a method of representing to a user a progression of the objects through a plurality of states in the sequence of events, the method comprising the steps of : generating a first sequence of states for the first object based on the first input sequence; generating a second sequence of states for the first object independent of the first input sequence; generating a third sequence of states for the second object based on the second input sequence; generating a fourth sequence of states for the second object independent of the second input sequence; displaying the first object as advancing through both the first sequence of states and the second sequence of states; and displaying the second object as advancing through both the third sequence of states and the fourth sequence of states .

10. A method according to claim 9, further comprising the step of determining the second sequence of states and the fourth sequence of states based on a network latency criterion.

11. A method according to claim 10, wherein the computer system is one of a plurality of nodes in communication on a network, wherein the first and second input sequences originate from different ones of the nodes, and wherein the network latency criterion corresponds to a communications latency between at least two of the nodes.

12. A method according to claim 11, further comprising the step of measuring the communications latency between said at least two of the nodes .

13. A method according to claim 9, further comprising the step of determining a distribution of the first sequence of states and the second sequence of states within the sequence of events based on a network latency criterion.

14. A method according to claim 9, wherein the step of displaying the first object comprises the steps of: displaying the first object as advancing through a first subset of the second sequence of states before displaying the first object as advancing through any of the first sequence of states; and displaying the first object as advancing through a second subset of the second sequence of states after displaying the first object as advancing through at least some of the second sequence of states .

15. A method according to claim 9, wherein the step of displaying the first object comprises the steps of: displaying the first object as advancing through the first sequence of states while displaying the second object as advancing through the fourth sequence of states; and displaying the first object as advancing through the second sequence of states while displaying the second object as advancing through the third sequence of states.

16. A method according to claim 9, wherein the first sequence of states is different from the third sequences of states .

17. A method according to claim 8, wherein the first input sequence is for causing a first event and the second input sequence is for causing a second event, wherein the method further comprises the step of assigning an order to the first event and the second event .

18. A method of enabling a target computer to represent a progression of a plurality of object through a plurality of states in a sequence of events, the method comprising the step of transmitting sequences of instructions from a host computer to a target computer, the sequences of instructions including instructions which, when executed on the target computer, cause the target computer to perform the method recited in claim 9.

19. In a computer system maintaining a first object and a second object, a method of assigning an order to a first event and a second event, the first event associated with the first object and the second event associated with the second object, the method comprising: receiving first inputs for causing the first event and second inputs for causing the second event; displaying the first object according to the first inputs and the second object according to the second inputs to generate a sequence of events; at a predetermined point in the sequence of events, ignoring the first inputs while continuing to process the second inputs throughout a predetermined interval; and throughout the predetermined interval, displaying the first object such that the ignoring of the first inputs is masked from a user; receiving a signal indicating the occurrence of the second event; and determining the order of the first event and the second event based on a relationship between the signal and the predetermined interval .

20. A method according to claim 19, wherein the first inputs originate from a first network node and wherein the second inputs originate from a second network node in communication with the first network node, wherein said communication is subject to a latency.

21. A method according to claim 20, further comprising the steps of determining the predetermined interval based on the latency.

22. A method according to claim 21, further comprising the step of measuring the latency.

23. A method according to claim 19, wherein the predetermined interval corresponds to a distance.

24. A method according to claim 19, wherein the predetermined interval corresponds to a time interval.

25. A method according to claim 24, further comprising the steps of : determining when the signal was received relative to the time interval; and if the signal was received prior to the end of the time interval, determining that the second event occurred before the first event .

26. A method according to claim 25, further comprising the step of: if the signal was received after the end of the time interval, determining that the first event occurred before the second event.

27. A machine-readable program storage medium tangibly embodying a program of instructions, the instructions executable on a computer system maintaining a plurality of objects, the instructions executable to perform method steps for representing progress of the objects through a sequence of events, the computer system causing each of the objects to advance through N + M states during the sequence of events in response to a plurality of input sequences, the method steps comprising the steps of: generating N states for each object based on its input sequence ; and generating M states for each object independent of its input sequence.

28. A machine-readable program storage medium according to claim 27, wherein the computer system is one of a plurality of nodes in communication on a network, wherein the input sequences originate from different ones of the nodes, and wherein the method steps further comprise the step of determining M based on a communications latency between at least two of the nodes .

29. A machine-readable program storage medium according to claim 27, wherein the method steps further comprise the step of determining a distribution of the N and M states within the sequence of events for each object based on a network latency.

30. A machine-readable program storage medium according to claim 27, wherein the step of generating M states comprises the steps of: generating a first subset of said M states before generating said N states; and generating a second subset of said M states after generating at least some of said N states.

31. A machine-readable program storage medium according to claim 27, wherein the N + M states may be different for each object.

32. A machine-readable program storage medium according to claim 27, wherein each of the input sequences is for causing one of a plurality of events, each event associated with one of the objects, wherein the method further comprises the step of assigning a chronological order to the events.