U.S. Pat. No. 11,673,045

DETAILED DESCRIPTION

The embodiments set forth below represent the information to enable those skilled in the art to practice the embodiments and illustrate the best mode of practicing the embodiments. Upon reading the following description in light of the accompanying drawing figures, those skilled in the art will understand the concepts of the disclosure and will recognize applications of these concepts not particularly addressed herein. It should be understood that these concepts and applications fall within the scope of the disclosure and the accompanying claims.

Any flowcharts discussed herein are necessarily discussed in some sequence for purposes of illustration, but unless otherwise explicitly indicated, the embodiments are not limited to any particular sequence of steps. The use herein of ordinals in conjunction with an element is solely for distinguishing what might otherwise be similar or identical labels, such as “first message” and “second message,” and does not imply a priority, a type, an importance, or other attribute, unless otherwise stated herein. The term “about” used herein in conjunction with a numeric value means any value that is within a range of ten percent greater than or ten percent less than the numeric value.

As used herein and in the claims, the articles “a” and “an” in reference to an element refers to “one or more” of the element unless otherwise explicitly specified. The word “or” as used herein and in the claims is inclusive unless contextually impossible. As an example, the recitation of A or B means A, or B, or both A and B.

Individuals living in geographically distant locations frequently play online games with one another. Such individuals each have a game computer, such as a personal computer, a gaming console, or a mobile device, which continuously communicates with a game server that receives inputs from all the game computers, makes determinations based on the inputs, and sends messages to each of the game computers regarding the determinations so the game advances identically for each player.

Action online games often involve relatively concurrent actions by multiple players, and the first acting player may have an advantage over a later acting player. Actions from two different players may occur within milliseconds of one another. Players may be relatively geographically distant from one another, such as one player in Europe and another in New York, and the differences in the network delay between the game server and each game computer may be substantial.

Due to the differences in network delay between different game computers and the game server, it can be difficult or impossible for the game server to precisely know which of two substantially concurrent actions occurred first. This can lead to erroneous determinations by the game server, which results in advancing a game in a way that is inconsistent with the actual actions of the players.

The embodiments disclosed herein implement event synchronization in an online game. A central computing device, such as a game server, time synchronizes with each of a plurality of other computing devices, such as personal computers, game consoles, and/or mobile devices, executing an online game. The central computing device determines an event to be depicted on each of the computing devices at a future time and sends, to the computing devices, event information that identifies the event and an event depiction timestamp that identifies a future time at which the event is to be depicted by the computing devices.

The computing devices receive the event information, and, at the designated future time, concurrently depict the event to each of the players. The computing devices then receive user input from the players in response to the depiction of the event. Each computing device generates a timestamp, which identifies the time of the user input, and action information, which identifies the user input, and sends the timestamp and the action information to the central computing device.

The central computing device collects the information sent by the computing devices, and determines, based on the timestamps and the user inputs, an appropriate next game event to be depicted. The central computing device sends to the computing devices the next game event to be depicted by the computing devices and an event timestamp that identifies the future time at which the next game event is to be depicted to the players. In this manner, the central computing device and the computing devices can ensure perfectly synchronized events such that the central computing device can make precise determinations as to which players acted at which times, irrespective of significant network delays among the different computing devices and the central computing device.

FIG.1Ais block diagram of an environment10in which embodiments may be practiced. The environment10includes a central computing device12and a plurality of computing devices14-1-14-N (generally, computing devices14). The central computing device12and the computing devices14each have one or more processor devices16and a memory18. The computing device14-1is located in a premises20-1, such as a residence, a business, or the like. The computing device14-N is located in a premises20-N. While only one computing device14is illustrated in each of premises20-1,20-N, in practice any number of computing devices14may be in a single premises20. The computing devices14may comprise, by way of non-limiting example, a desktop or mobile computing device, a smart phone, a computing tablet, a game console, or the like. The premises20-1and the premises20-N may be substantially different physical distances from the central computing device12. For example, the central computing device12and the premises20-1may be located in Arizona, and the premises20-N may be located in Spain.

The computing device14-1includes a game client22-1via which a user24-1can play an online game. The game client22-1depicts the game on a display device26-1.

An access device28-1, such as a cable modem, an xDSL modem, an optical network unit (ONU), or the like, is configured to couple the computing device14-1, either directly or indirectly through a gateway device such as a router (not illustrated), to an access aggregation point30-1, such as, by way of non-limiting example, a digital subscriber line access multiplexer (DSLAM), an optical line termination (OLT), a cable modem termination system (CMTS), or the like, that is part of a wide area network (WAN)32.

Similarly, the computing device14-N includes a game client22-N via which a user24-N can play a game. The game client22-N depicts the game on a display device26-N.

An access device28-N is configured to couple the computing device14-N, either directly or indirectly through a gateway device such as a router (not illustrated), to an access aggregation point30-N, that is part of the WAN32.

The central computing device12is communicatively coupled to the access aggregation points30. The central computing device12includes a game controller34that communicates with the game clients22to provide the users24with the online game. In some embodiments, the central computing device12may include a simulated player36, which appears to an actual user, such as the user24-1, as another human player, such that the user24-1can enjoy the online game even without another human player, such as the user24-N.

The game controller34includes an event synchronizer38that ensures that the game clients22-1,22-N concurrently depict all, or certain, events on the display devices26-1,26-N concurrently so that each user24-1,24-N is presented with the event at precisely the same time. Initially, the event synchronizer38time synchronizes with the game clients22. This may be done, for example, using precision time protocol (PTP), or via a global positioning system (GPS) signal.

In one embodiment, the game controller34operates as a PTP master clock. The event synchronizer38may communicate with the access device28-1via the access aggregation point30-1and make the access device28-1a PTP slave clock. The game client22-1is locked to the PTP slave clock that interacts with the game controller34to synchronize time. Similarly, the event synchronizer38communicates with the access device28-N via the access aggregation point30-N and makes the access device28-N a PTP slave clock. The game client22-N is locked to the PTP slave clock that interacts with the game controller34to synchronize time, such that the central computing device12and the computing devices14-1,14-N are all time synchronized.

In one embodiment, the event synchronizer38may communicate with the access device28-1via the access aggregation point30-1and make the access device28-1a PTP master clock. The game client22-1includes a PTP slave clock that interacts with the access device28-1to synchronize time. Similarly, the event synchronizer38communicates with the access device28-N via the access aggregation point30-N and makes the access device28-N a PTP master clock. The game client22-N includes a PTP slave clock that interacts with the access device28-N to synchronize time, such that the central computing device12and the computing devices14-1,14-N are all time synchronized.

In another embodiment, where there are constant and known delays between the game clients22and the corresponding access devices28, GPS may be used to synchronize events. In such embodiments, the game controller34has a GPS receiver and establishes a clock synchronized to its GPS receiver. The access device28-1also has a GPS receiver and establishes a clock synchronized to its GPS receiver. The game client22-1is locked to the clock in the access device28-1. Both the game controller34and the game client22-1are locked to clocks synchronized to GNSS GPS via their respective GPS receivers. The event synchronizer38may communicate with the access device28-1via the access aggregation point30-1and communicate synchronization events and responses between the game controller34and the game client22-1.

Similarly, the access device28-N also has a GPS receiver and establishes a clock synchronized to its GPS receiver. The game client22-N is locked to the clock in the access device28-N. Both the game controller34and the game client22-N are locked to clocks synchronized to GNSS GPS via their respective GPS receivers. The event synchronizer38may communicate with the access device28-N via the access aggregation point30-N and communicates synchronization events and responses between the game controller34and the game client22-N.

It is noted that, because the game controller34is a component of the central computing device12, functionality implemented by the game controller34may be attributed to the central computing device12generally. Moreover, in examples where the game controller34comprises software instructions that program the processor device16to carry out functionality discussed herein, functionality implemented by the game controller34may be attributed herein to the processor device16of the central computing device12.

As an example of event synchronization in an online game according to one embodiment, assume that the user24-1desires to play a particular shooting game on the computing device14-1. The shooting game may involve a shooting implement such as handgun, a rifle, a tank, a bow, or the like that emits some object, such as a bullet, a shell, an arrow, or the like. In this example, the shooting game involves a bow as the shooting implement, and the object that is emitted is an arrow. In this game, the winner is the individual who hits the target first with an arrow.

The user24-1initiates the game client22-1on the computing device14-1. The game client22-1may, as part of an initialization stage, communicate with the game controller34to identify the game client22-1as participating in the game. The game controller34may begin a time synchronization process with the game client22-1, such as a GPS time synchronization process, a PTP time synchronization process, or the like. The game controller34may also determine a network delay value that quantifies an amount of time for a message to travel between the game controller34and the computing device14-1. The network delay value may be a predetermined network delay value based on historical measurements between the game controller34and the computing device14-1, or may be determined during the initialization stage. In that latter case, the game controller34may send the computing device14-1a predetermined type of message with a timestamp. The computing device14-1receives the message, generates a response message with a timestamp, and sends the response message back to the game controller34.

Thereafter, the user24-N initiates the game client22-N on the computing device14-N. The game client22-N, as part of the initialization stage, communicates with the game controller34to identify the game client22-N as participating in the game. The game controller34begins the time synchronization process with the game client22-N discussed above with the client22-1. Afterward, the game controller34is time synchronized with the computing devices14-1,14-N. The game controller34also determines a network delay value that quantifies an amount of time for a message to travel between the game controller34and the computing device14-N.

Based on the network delay values associated with the computing device14-1and the computing device14-N, the game controller34determines a timing window. The timing window defines a period of time during which only a single synchronized event is to be processed by the computing devices14. In some implementations, the timing window may be based on a greatest network delay value associated with the computing devices14-1,14-N. In some embodiments, the timing window may be the greatest network delay value plus some predetermined buffer value as a safety margin.

Some or many of the events in the game may not be time-synchronized events. As an example, the game client22-1may provide a period of time, during which the user24-1can select a particular bow from a plurality of different potential bows to use, and allows the user24-1to get in a ready position to shoot a target that will appear on the display device26-1at some point in the future. Similarly, the game client22-N provides a period of time, during which the user24-N can select a particular bow from the plurality of different potential bows to use, and allows the user24-N to get in a ready position to shoot the target that will appear on the display device26-N at some point in the future. The game clients22-1and22-N send the game controller34a message indicating that the users24-1and24-N are ready for a target.

The game controller34generates a message that includes 1) event information that identifies an event, and 2) an event depiction timestamp that identifies a future time at which the game clients22-1and22-N are to concurrently depict the event to the users24-1,24-N via the display devices26-1,26-N, respectively. The event information, in this example, indicates that a target is to be depicted at a certain location on the display devices26-1,26-N at the future point in time identified by the event depiction timestamp. The game controller34sends the message to the game clients22-1,22-N executing on the computing devices14-1,14-N, respectively.

It is noted that, because a game client22is a component of the corresponding computing device14, functionality implemented by the game client22may be attributed to the corresponding computing device14generally. Moreover, in examples where the game client22comprises software instructions that program the processor device16to carry out functionality discussed herein, functionality implemented by the game client22may be attributed herein to the processor device16of the corresponding computing device14.

Referring now toFIG.1B, the game clients22-1,22-N receive the message and, at the future point in time, concurrently present the target at the identified location on the display devices26-1,26-N. The users24-1,24-N each adjust the bow as they deem appropriate to successfully hit the depicted target with an arrow and release the arrow via some user input. The game clients22-1,22-N each receive the corresponding user inputs and generate a message that includes action information that identifies the user input and includes an action timestamp that identifies the time at which the user input was received by the corresponding game clients22-1,22-N. In this example, the action information also includes orientation information of the bows of each of the users24-1,24-N and velocity information regarding a speed at which each user24-1,24-N emitted the arrows. The game clients22-1,22-N send the messages to the game controller34.

The game controller34receives the messages. Assume that, due to geographic proximity, the game controller34receives the message from the game client22-N prior to receiving the message from the game client22-1. The game controller34orders the messages based on the action timestamps in the messages. In this example, even though the message from the game client22-1was received later than the message from the game client22-N, the action timestamp in the message from the game client22-1is several milliseconds earlier than that in the message from the game client22-N. The game controller34thus determines that the user24-1reacted earlier than the user24-N. The game controller34determines that the velocity information and orientation information from the messages also indicates that the user24-1struck the target prior to the user24-N.

Referring now toFIG.1C, the game controller34generates messages that contain event information that identifies an event for each of the game clients22-1,22-N. The event for the game client22-1is a message that indicates that the user24-1won the game, and the event for the game client22-N is a message that the user24-N lost the game, and sends the messages to the game clients22-1,22-N. This event is not time synchronized, and thus the game controller34does not include an action timestamp that identifies a future time at which the messages are to be concurrently displayed. Thus, the game clients22-1,22-N display the relevant events upon receipt, in a non-synchronized manner.

FIG.1Dillustrates an alternative implementation of the game to that illustrated inFIG.1C. In this implementation of the game, the game may be won by the first player who first hits five targets. In this implementation, after determining that the user24-1struck the target prior to the user24-N, the game controller34generates a second synchronized message that includes 1) event information that identifies an event, and 2) an event depiction timestamp that identifies a future time at which the game clients22-1,22-N are to concurrently depict the event to the users24-1,24-N via the display devices26-1,26-N, respectively. The event information, in this example, indicates that a target is to be depicted at a different location on the display devices26-1,26-N at the future point in time identified by the event depiction timestamp. The event information may also include information indicating that the user24-1has a score of 1 and the user24-N as a score of zero. The game controller34sends the message to the game clients22-1,22-N executing on the computing devices14-1,14-N, respectively.

The game clients22-1,22-N receive the message and, at the future point in time, concurrently present the target at the identified location on the display devices26-1,26-N, along with information indicating the current score. The users24-1,24-N each adjust the bow as they deem appropriate to successfully hit the depicted target with an arrow and release the arrow via some user input. The game clients22-1,22-N each receive the corresponding user inputs and generate a message that includes action information that identifies the user input and includes an action timestamp that identifies the time at which the user input was received by the corresponding game clients22-1,22-N. This process may repeat until one of the users24-1-24-N wins the game.

FIG.2is a flowchart of a method for event synchronization in an online game, according to one embodiment. The central computing device12sends, to the plurality of computing devices14, event information that identifies an event and an event depiction timestamp that identifies a future time at which to depict the event, wherein the central computing device12and the plurality of computing devices14are time synchronized with one another (FIG.2, block1000). The central computing device12receives, from a first set of computing devices14of the plurality of computing devices14, a corresponding set of first messages, each first message including action information that identifies a user input received by a corresponding computing device14and an action timestamp that identifies a time at which the user input was received by the corresponding computing device14(FIG.2, block1002). The central computing device12, based on the action timestamps and the user inputs in the set of first messages, determines a next event to be depicted (FIG.2, block1004). The central computing device12sends, to the plurality of computing devices14, next event information that identifies the next event (FIG.2, block1006).

FIG.3is a diagram40that illustrates actions taken in successive timing windows42-1,42-2, and42-3(generally, timing windows42) according to one embodiment. As discussed above, the timing windows42-1,42-2, and42-3are a same, fixed period of time that defines the period of time during which only a single synchronized event is to be processed by the computing devices14. The timing windows42may be determined by the central computing device12and be based on a greatest network delay value associated with the computing devices14-1,14-N.

At a time T1during the timing window42-1, the central computing device12communicates event information regarding a synchronized event to the computing devices14-1and14-N, which are time-synchronized with the central computing device12. The event information contains an event depiction timestamp that identifies a time T2. At the time T2, the computing devices14-1and14-N depict the event on the display devices26-1,26-N. The computing device14-1sends a message identifying a user input and a timestamp of the user input to the central computing device12, which is received by the central computing device12at a time T3. The computing device14-N sends a message identifying a user input and a timestamp of the user input to the central computing device12, which is received by the central computing device12at a time T4. The central computing device12processes the messages, based in part on the timestamps contained in the messages, and generates next event information that identifies a next synchronized event, and an event depiction timestamp that identifies a time T6of the timing window42-2. At a time T5, the central computing device12communicates the next event information regarding the next synchronized event to the computing devices14-1,14-N. At the time T6, the computing devices14-1and14-N depict the event on the display devices26-1,26-N.

Based on the network delay values associated with the computing device14-1and the computing device14-N, the game controller34determines a timing window. The timing window defines a period of time during which only a single synchronized event is to be processed by the computing devices14. In some implementations, the timing window may be based on a greatest network delay value associated with the computing devices14-1,14-N. In some embodiments, the timing window may be the greatest network delay value plus some predetermined buffer value as a safety margin.

FIGS.4A-4Care sequence diagrams that illustrate messages communicated between and actions taken by components illustrated inFIGS.1A-1Cto implement event synchronization in an online game according to another embodiment. The computing device14-1connects to the central computing device12during the initialization stage of the game (step2000). The central computing device12initiates a PTP session with the access device28-1and sends one or more appropriate PTP messages to the access device28-1(step2002). The access device28-1initiates a PTP session with the computing device14-1and sends one or more appropriate PTP messages to the computing device14-1(step2004).

The computing device14-N connects to the central computing device12during the initialization stage of the game (step2006). The central computing device12initiates a PTP session with the access device28-N and sends one or more appropriate PTP messages to the access device28-N (step2008). The access device28-N initiates a PTP session with the computing device14-N and sends one or more appropriate PTP messages to the computing device14-N (step2010). The central computing device12and the computing devices14-1and14-N now have a synchronized clock.

To determine the network delay (sometimes referred to as propagation delay) between the central computing device12and the computing device14-1, the central computing device12sends a timestamped message to the computing device14-1(step2012). The computing device14-1timestamps the timestamped message and returns the timestamped message to the central computing device12(step2014). The central computing device12then determines the network delay between the central computing device12and the computing device14-1(step2016). The central computing device12sends a timestamped message to the computing device14-N (step2018). The computing device14-N timestamps the timestamped message and returns the timestamped message to the central computing device12(step2020). The central computing device12then determines the network delay between the central computing device12and the computing device14-N (step2022).

The central computing device12then determines a timing window that identifies a period of time during which only a single synchronized event may be sent to and received from the computing devices14-1,14-N (step2024). In one embodiment, the central computing device12determines the timing window based on a greatest network delay value associated with the computing devices14-1,14-N, and adds an additional predetermined buffer value, such as 10 milliseconds (ms), 100 ms, or the like, as a safety margin.

The central computing device12determines a next event for the online game, and generates event information that identifies the event and an event depiction timestamp that identifies a future time at which the event is to be depicted by the computing devices14-1,14-N (step2026). Referring now toFIG.4B, the central computing device12sends the event information to the computing devices14-1,14-N (steps2028,2030). The computing devices14-1,14-N receive the event information, and, at the future time, concurrently display the event on the display devices26-1,26-N, respectively (steps2032,2034). The computing device14-1first receives user input from the user24-1(step2036). The computing device14-N then subsequently receives user input from the user24-N (step2038). The computing device14-1generates a message that includes action information that identifies the orientation of the shooting implement of the user24-1, in this example a blow, and information indicating the user24-1released the arrow, and a timestamp that identifies the time that the arrow was released. The action information may include any other information relevant to the determination of whether or not the arrow struck the target and the timing of the strike, such as velocity, or the like. The computing device14-1sends the message to the central computing device12(step2040).

The computing device14-N generates a message that includes action information that identifies the orientation of the shooting implement of the user24-N, and information indicating the user24-N released the arrow, and a timestamp that identifies the time that the arrow was released. The computing device14-N sends the message to the central computing device12(step2042). Even though the message from the computing device14-1was sent prior to the message from the computing device14-N, due to differences in network delay, the central computing device12receives the message from the computing device14-N prior to receiving the message from the computing device14-1.

The central computing device12-1orders the messages based on the timestamps contained in the messages (step2044). Based on the ordered messages, and the information contained in the message, such as the orientation of the bows, velocity of the arrows, and the like, the central computing device12-1determines that the user24-1won that particular round (step2046).

Referring now toFIG.4C, the central computing device12-1generates event information for the computing device14-1that includes a message that indicates that the user24-1won that round, and sends the event information to the computing device14-1for presentation to the user24-1(step2048). Note that the message does not include a depiction timestamp because the event is not a synchronized event. The central computing device12-1also generates event information for the computing device14-N that includes a message that indicates that the user24-N lost that round, and sends the event information to the computing device14-N for presentation to the user24-N (step2050).

The central computing device12-1then starts the next round by determining a next event for the online game, and generates event information that identifies the next event and an event depiction timestamp that identifies a future time at which the next event is to be depicted by the computing devices14-1,14-N (step2052). The central computing device12sends the event information to the computing devices14-1,14-N (steps2054,2056). The computing devices14-1,14-N receive the event information, and, at the future time, concurrently display the event on the display devices26-1,26-N, respectively (steps2058,2060). This process repeats until the online game finishes.

FIG.5is a flowchart of a method for event synchronization in an online game from the perspective of a computing device, according to another embodiment.FIG.5will be discussed in conjunction withFIGS.1A-1C. The computing device14-1receives, from the central computing device12, event information that identifies an event and an event depiction timestamp that identifies a future time at which the computing device14-1is to depict the event, wherein the central computing device12and the computing device14-1are time synchronized with one another (FIG.5, block3000). The computing device14-1depicts, on the display device26-1, the event at the future time (FIG.5, block3002). The computing device14-1receives user input that identifies an action (FIG.5, block3004). The computing device14-1generates a timestamp that identifies a time of receipt of the user action (FIG.5, block3006). The computing device14-1generates a message that identifies the action and that includes the timestamp (FIG.5, block3008). The computing device14-1sends the message to the central computing device12(FIG.5, block3010).

FIG.6is a block diagram of a computing device44suitable for implementing the central computing device12, or a computing device14, according to various implementations. The computing device44, when implementing the central computing device12, may comprise any computing or electronic device capable of including firmware, hardware, and/or executing software instructions to implement the functionality described herein with regard to the central computing device12, such as a computer server, a desktop computing device, a laptop computing device, or the like. The computing device44, when implementing a computing device14, may comprise any computing or electronic device capable of including firmware, hardware, and/or executing software instructions to implement the functionality described herein with regard to the computing device14, such as a desktop or laptop computer, a game console, a smartphone, a computing tablet, or the like.

The computing device44includes the processor device16, the memory18, and a system bus46. The system bus46provides an interface for system components including, but not limited to, the system memory18and the processor device16. The processor device16can be any commercially available or proprietary processor.

The system bus46may be any of several types of bus structures that may further interconnect to a memory bus (with or without a memory controller), a peripheral bus, and/or a local bus using any of a variety of commercially available bus architectures. The system memory18may include non-volatile memory48(e.g., read-only memory (ROM), erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM), etc.), and volatile memory50(e.g., random-access memory (RAM)). A basic input/output system (BIOS)52may be stored in the non-volatile memory48and can include the basic routines that help to transfer information between elements within the computing device44. The volatile memory50may also include a high-speed RAM, such as static RAM, for caching data.

The computing device44may further include or be coupled to a non-transitory computer-readable storage medium such as a storage device54, which may comprise, for example, an internal or external hard disk drive (HDD) (e.g., enhanced integrated drive electronics (EIDE) or serial advanced technology attachment (SATA)), HDD (e.g., EIDE or SATA) for storage, flash memory, or the like. The storage device54and other drives associated with computer-readable media and computer-usable media may provide non-volatile storage of data, data structures, computer-executable instructions, and the like. Although the description of computer-readable media above refers to an HDD, it should be appreciated that other types of media that are readable by a computer, such as Zip disks, magnetic cassettes, flash memory cards, cartridges, and the like, may also be used in the operating environment, and, further, that any such media may contain computer-executable instructions for performing novel methods of the disclosed examples.

A number of modules can be stored in the storage device54and in the volatile memory50, including an operating system and one or more program modules, such as the game controller34and/or the game client22, which may implement the functionality described herein in whole or in part. All or a portion of the examples may be implemented as a computer program product56stored on a transitory or non-transitory computer-usable or computer-readable storage medium, such as the storage device54, which includes complex programming instructions, such as complex computer-readable program code, to cause the processor device16to carry out the steps described herein. Thus, the computer-readable program code can comprise software instructions for implementing the functionality of the examples described herein when executed on the processor device16.

The computing device44may also include a communications interface58suitable for communicating with a network as appropriate or desired.

Those skilled in the art will recognize improvements and modifications to the preferred embodiments of the disclosure. All such improvements and modifications are considered within the scope of the concepts disclosed herein and the claims that follow.