U.S. Pat. No. 11,794,107

DETAILED DESCRIPTION

The present specification is directed towards multiple embodiments. The following disclosure is provided in order to enable a person having ordinary skill in the art to practice the invention. Language used in this specification should not be interpreted as a general disavowal of any one specific embodiment or used to limit the claims beyond the meaning of the terms used therein. The general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Also, the terminology and phraseology used is for the purpose of describing exemplary embodiments and should not be considered limiting. Thus, the present invention is to be accorded the widest scope encompassing numerous alternatives, modifications and equivalents consistent with the principles and features disclosed. For purpose of clarity, details relating to technical material that is known in the technical fields related to the invention have not been described in detail so as not to unnecessarily obscure the present invention.

The term “a multi-player online gaming environment” or “massively multiplayer online game” may be construed to mean a specific hardware architecture in which one or more servers electronically communicate with, and concurrently support game interactions with, a plurality of client devices, thereby enabling each of the client devices to simultaneously play in the same instance of the same game. Preferably the plurality of client devices number in the dozens, preferably hundreds, preferably thousands. In one embodiment, the number of concurrently supported client devices ranges from 10 to 5,000,000 and every whole number increment or range therein. Accordingly, a multi-player gaming environment or massively multi-player online game is a computer-related technology, a non-generic technological environment, and should not be abstractly considered a generic method of organizing human activity divorced from its specific technology environment.

In various embodiments, a computing device includes an input/output controller, at least one communications interface and system memory. The system memory includes at least one random access memory (RAM) and at least one read-only memory (ROM). These elements are in communication with a central processing unit (CPU) to enable operation of the computing device. In various embodiments, the computing device may be a conventional standalone computer or alternatively, the functions of the computing device may be distributed across multiple computer systems and architectures.

In some embodiments, execution of a plurality of sequences of programmatic instructions or code enable or cause the CPU of the computing device to perform various functions and processes. In alternate embodiments, hard-wired circuitry may be used in place of, or in combination with, software instructions for implementation of the processes of systems and methods described in this application. Thus, the systems and methods described are not limited to any specific combination of hardware and software.

The term “module”, “application” or “engine” used in this disclosure may refer to computer logic utilized to provide a desired functionality, service or operation by programming or controlling a general purpose processor. Stated differently, in some embodiments, a module, application or engine implements a plurality of instructions or programmatic code to cause a general purpose processor to perform one or more functions. In various embodiments, a module, application or engine can be implemented in hardware, firmware, software or any combination thereof. The module, application or engine may be interchangeably used with unit, logic, logical block, component, or circuit, for example. The module, application or engine may be the minimum unit, or part thereof, which performs one or more particular functions.

The term “swept volume” used in this disclosure may refer to a virtual volume generated by sweeping a solid or a collection of surfaces in game space along a path or trajectory.

In the description and claims of the application, each of the words “comprise” “include” and “have”, and forms thereof, are not necessarily limited to members in a list with which the words may be associated. It should be noted herein that any feature or component described in association with a specific embodiment may be used and implemented with any other embodiment unless clearly indicated otherwise.

As used herein, the indefinite articles “a” and “an” mean “at least one” or “one or more” unless the context clearly dictates otherwise.

Gaming Environment

FIG.1Aillustrates an embodiment of a multi-player online gaming or massively multiplayer online gaming system/environment100in which the systems and methods of the present specification may be implemented or executed. The system100comprises client-server architecture, where one or more game servers105are in communication with one or more client devices110over a network115. Players and non-players, such as computer graphics artists or designers, may access the system100via the one or more client devices110. The client devices110comprise computing devices such as, but not limited to, personal or desktop computers, laptops, Netbooks, handheld devices such as smartphones, tablets, and PDAs, gaming consoles and/or any other computing platform known to persons of ordinary skill in the art. Although four client devices110are illustrated inFIG.1A, any number of client devices110can be in communication with the one or more game servers105over the network115.

The one or more game servers105can be any computing device having one or more processors and one or more computer-readable storage media such as RAM, hard disk or any other optical or magnetic media. The one or more game servers105include a plurality of modules operating to provide or implement a plurality of functional, operational or service-oriented methods of the present specification. In some embodiments, the one or more game servers105include or are in communication with at least one database system120. The database system120stores a plurality of game data associated with at least one game that is served or provided to the client devices110over the network115. In some embodiments, the one or more game servers105may be implemented by a cloud of computing platforms operating together as game servers105.

In accordance with aspects of the present specification, the one or more game servers105provide or implement a plurality of modules or engines such as, but not limited to, a master game module130and a collision detection simulation module132. The one or more client devices110are configured to implement or execute one or more of a plurality of client-side modules some of which are same as or similar to the modules of the one or more game servers105. In some embodiments each of the player and non-player client devices110executes a client-side game module130′ (also referred to as—client game module130′) that may further integrate a client-side collision detection simulation module132′. In some embodiments, however, the client-side collision detection simulation module132′ may not be required and all simulation processes related to the collision detection functionality may be implemented at the one or more game servers105.

In some embodiments, the at least one non-player client device110gis used by a computer graphics artist or designer to log into the one or more game servers105(via the client game module130′) and execute the module132on the server to generate one or more GUIs that enable the computer graphics artist or designer to customize and set one or more parameters, attributes or characteristics related to a composite model defined to represent a player controlled avatar or virtual character.

While various aspects of the present specification are being described with reference to functionalities or programming distributed across modules or engines130and132, it should be appreciated that, in some embodiments, some or all of the functionalities or programming associated with these modules or engines may be integrated within fewer modules or in a single module—such as, for example, in the master game module130itself on the server side.

In embodiments, the master game module130is configured to execute an instance of an online game to facilitate interaction of the players with the game. In embodiments, the instance of the game executed may be synchronous, asynchronous, and/or semi-synchronous. The master game module130controls aspects of the game for all players and receives and processes each player's input in the game. In other words, the master game module130hosts the online game for all players, receives game data from the client devices110and transmits updates to all client devices110based on the received game data so that the game, on each of the client devices110, represents the most updated or current status with reference to interactions of all players with the game. Thus, the master game module130transmits game data over the network115to the client devices110for use and rendering by the game module130′ to provide local versions and current status of the game to the players.

On the client-side, each of the one or more player client devices110implements the game module130′ that operates as a gaming application to provide a player with an interface between the player and the game. The game module130′ generates the interface to render a virtual environment, virtual space, game space, map or virtual world associated with the game and enables the player to interact in the virtual environment to perform a plurality of game and other tasks and objectives. The game module130′ accesses at least a portion of game data, received from the game server105, to provide an accurate representation of the game to the player. The game module130′ captures and processes player inputs and interactions within the virtual world or environment and provides at least a portion as updates to the game server110over the network115.

The database system120described herein may be, include, or interface to, for example, an Oracle™ relational database sold commercially by Oracle Corporation. Other databases, such as Informix™, DB2 (Database 2) or other data storage, including file-based, or query formats, platforms, or resources such as OLAP (On Line Analytical Processing), SQL (Structured Query Language), a SAN (storage area network), Microsoft Access™ or others may also be used, incorporated, or accessed. The database system120may comprise one or more such databases that reside in one or more physical devices and in one or more physical locations.

While the embodiments of the present specification will be illustrated with reference to the multi-player online gaming or massively multiplayer online gaming system/environment100ofFIG.1A, the embodiments are equally applicable to offline gaming environments such as the system/environment140ofFIG.1B. As shown inFIG.1B, the system140includes a display150, graphics hardware152, a computing platform154, a user interface156and a storage device or memory158. The computing platform154may include a number of components for processing data, rendering the game space or virtual environment and detecting collision, such as a graphics system160and the collision detection simulation module132.

The graphics system160may perform rendering operations based on the results of the simulation operations performed by the collision detection simulation module132. The rendering operations, performed by graphics system160, may include visibility, culling and tessellation operations, for example. Based on results of the rendering operations, commands (such as Open GL commands) may be issued by graphics system160to the graphics hardware152to cause a display of a rendered frame on display150.

Collision Detection Simulation Module

In accordance with some aspects of present specification, the collision detection simulation module132implements a plurality of instructions or programmatic code to define and generate, during run-time, a virtual composite model representative of a player controlled avatar or virtual character. While the embodiments of the present specification have been described with reference to a player controlled avatar or virtual character, it should be appreciated that this is in no way limiting and that the systems and method of the present specification may be equally implemented for a player controlled virtual object.

As shown inFIG.2, the composite model215comprises a first geometric primitive or model205having a first shape and size and a second geometric primitive or model210having a second shape and size. In embodiments, the second geometric primitive or model210is bounded by and encompassed by, or positioned within, the first geometric primitive or model205.

The avatar or virtual character220is shown standing upright, for example, on a ground225(assuming that the ground level225is already known) such that a central longitudinal axis222of the avatar or virtual character220is parallel to the z-axis of a world coordinate system230while the ground225is parallel to the x-y plane defined in the world coordinate system230.

In some embodiments, the first geometric primitive or model205is a cylinder that at least partially bounds and approximately represents the avatar or virtual character220. In embodiments, the first size of the cylinder205is defined by the following parameters: a) a center line lcy(containing the center of mass of the cylinder mcy) and b) a radius rcysuch that the center line lcyis coaxial with the central longitudinal axis222of the avatar or virtual character220. In some embodiments, the first size (in terms of the center line lcyand the radius rcy) of the cylinder205is defined such that the cylinder205bounds at least a portion of the avatar or virtual character220. In an embodiment, the first size (in terms of the center line lcyand the radius rcy) of the cylinder205is defined such that the cylinder205bounds an entirety of the avatar or virtual character220.

In some embodiments, the second geometric primitive or model210is a capsule (also known as a sphero-cylinder) having a cylindrical body211with semi-spherical/hemispherical first and second ends or caps212,213. In embodiments, the second size of the capsule210is defined by the following parameters: a) a center line lcap(containing the center of mass of the capsule mcap) and b) a radius rcapsuch that the center line lcapis coaxial with the central longitudinal axis222of the avatar or virtual character220.

In some embodiments, lcy>lcapand rcy>rcapmeaning that the first size of the cylinder205is larger than the second size of the capsule210so that the capsule210is bounded or encompassed within the larger cylinder205. That is, the second size (in terms of the center line lcapand the radius rcap) of the capsule210is defined such that the capsule210is bounded or encompassed by the cylinder205. In some embodiments, the second size (in terms of the center line lcapand the radius rcap) of the capsule210is further defined such that the capsule210bounds at least a portion of the avatar or virtual character220.

As shown inFIG.2, in some embodiments, the second size (in terms of the center line lcapand the radius rcap) of the capsule210is defined such that a bottom end of the cap213of the capsule210(the cap213being the one that is closer to the ground225compared to the cap212) lays a predefined distance ‘dcap’ above the ground225.

As shown inFIG.2, in some embodiments, the cylinder205and capsule210models are positioned such that the respective center of masses mcy, mcapof the cylinder205and the capsule210coincide with the center of mass mvcof the avatar or the virtual character220.

Sweep Tests

In accordance with some aspects of the present specification, the collision detection simulation module132is configured to perform run-time processing of player input (associated with manipulation of the avatar or virtual character) and collision detection based simulation to enable rendering of the frames of the virtual game space or environment.

Vertical Sweep Test

In accordance with some aspects of the present specification, at run-time at the beginning of a frame (having a frame duration tframe), the collision detection simulation module132is configured to perform a vertical sweep test using the first geometric primitive or model205—that is the cylinder205. In some embodiments, the first geometric primitive or model205is swept vertically downwards to identify a ground obstacle, a ground level and/or a sloping ground/surface. As shown inFIG.3A, the cylinder model205is swept or translated from a first position302vertically downwards to a second position304by an extent or a distance ‘E’. In some embodiments, the extent or distance ‘E’ is a sum of the radius rcapof the second geometric primitive or model210(that is, the capsule210), the distance ‘dcap’ of the cap213above the ground225and a predefined distance ‘t’. In various embodiments, the predefined distance T is customizable by a computer graphics designer. It should be appreciated that the distance ‘t’ ensures that using the vertical sweep test the first geometric primitive or model205finds the ground225in every frame. In scenarios where the avatar or virtual character220is standing on the ground225(or slightly above the ground225), at least some portion of the distance T may extend below the ground225. However, when the avatar or virtual character220is jumping, for example, then the distance T would lie above the ground225.

In some embodiments, the vertical sweep test is performed automatically by the module132and is not necessarily triggered by a prior collision determination. In some embodiments, the vertical sweep test is performed independent of a player's inputs related to the avatar or virtual character220. In other words, the vertical sweep test, for each frame, is performed irrespective of whether the player does or does not manipulate the avatar or virtual character220.

In some embodiments, determination of a ground level or a sloping ground/surface, using the first geometric primitive or model205for a downward vertical sweep test, amounts to determining an intersection between a cylinder representative of the avatar or virtual character220and a plane representative of a horizontal ground level or a sloping ground/surface. Thus, in order to determine ground level or a sloping surface, the downward vertical sweep test determines an intersection of the cylinder model205with the ground225(which may or may not have a slope) represented by a plane.

In some embodiments, in order to determine collision with a ground obstacle the module132is configured to a) determine a first image obtained by projecting the cylinder model205, in the second position304, onto the z-axis of the world coordinate system230, b) determine a second image obtained by projecting the ground obstacle onto the z-axis of the world coordinate system230, b) determine if a first condition is fulfilled, wherein the first condition is indicative of an overlap or intersection between the first and second image projections, c) determine a third image obtained by projecting the cylinder model205, in the second position304, onto the xy plane of the world coordinate system230, d) determine a fourth image obtained by projecting the ground obstacle onto the xy plane, and e) determine if a second condition is fulfilled, wherein the second condition is indicative of an overlap or intersection between the third and fourth image projections. In some embodiments, if both the first and second conditions are fulfilled, the module132concludes that there exists a potential collision of the avatar or virtual character220with the ground obstacle.

In some embodiments, the ground obstacle may be represented by a geometric primitive or model of a shape such as, but not limited to, a cylinder, a sphere, a capsule, a rectangle, a pyramid or a polyhedron. In some embodiments, the ground obstacle may be represented by a mesh of geometric primitives. Thus, in embodiments, the cylinder model205is used to perform a downward vertical sweep test against both shape-based and mesh-based world collision geometry.

After performing the downward vertical sweep, the model132is configured to move or translate the cylinder model205from the second position304back to the first position302prior to performing a horizontal sweep test using the capsule model210.

It should be appreciated that the capsule model210does not participate in the vertical sweep test, in accordance with some embodiments of the present specification.

Horizontal Sweep Test

In accordance with some aspects of the present specification, at run-time at the beginning of the frame (having the frame duration tframe), the collision detection simulation module132is configured to perform a horizontal sweep test using the second geometric primitive or model210—that is the capsule model210in order to determine potential collision or contact of the model210with an obstacle positioned on the ground225. It should be appreciated that a level of the ground225is already determined using the cylinder model205in the vertical sweep test.

As shown inFIG.3B, during run-time at the beginning of the frame, the module132receives player input (such as, for example, related to manipulation of the player controlled avatar or virtual character220) and determines or simulates the movement of the avatar or virtual character220from a first position310to a second position312in the frame (having the frame duration tframe).

In some embodiments, where the ground obstacle is stationary, the module132uses the direction and velocity imparted to the virtual character220at the first position310, as a result of the player input, in order to determine the second position312by predicting a path or trajectory that the virtual character220would likely traverse in order to move from the first position310to the second position312.

In some embodiments, where the ground obstacle is moving, the module132uses the direction and ‘relative’ velocity imparted to the virtual character220at the first position310, as a result of the player input, with reference to the ground obstacle in order to determine the second position312by predicting a path or trajectory that the virtual character220would likely traverse in order to move from the first position310to the second position312.

In some embodiments, the module132is configured to simulate a forward horizontal sweep of the capsule model210from the first position310to the determined second position312along the predicted path or trajectory. The simulation results in a volume315(also referred to as ‘swept volume’) virtually swept by the capsule model210from the first position310to the second position312.

In some embodiments, determination of collision with the ground obstacle, using the capsule model210for a forward horizontal sweep test, amounts to determining presence of the ground obstacle within the virtual volume315swept by the capsule model210. That is, if the ground obstacle is determined to be present within the swept volume315, the module132concludes a potential collision between the avatar or virtual character220and the ground obstacle. In some embodiments, the module132performs collision simulation for only those ground obstacles that lie within the virtual environment or game space occupied by the swept volume315.

In some embodiments, the module132determines if the capsule model210and the ground object are likely to collide by a) determining if a first condition is fulfilled, wherein the first condition is indicative of whether a first image obtained by projecting the swept volume315onto the xy plane of the world coordinate system230and a second image obtained by projecting an outer contact surface of the ground object onto the xy plane overlap or contact, and b) determining if a second condition is fulfilled, wherein the second condition is indicative of whether a third image obtained by projecting the swept volume315onto the z axis of the world coordinate system230and a fourth image obtained by projecting the outer contact surface of the ground object onto the z axis overlap or contact. If both the first and second conditions are fulfilled, the module132concludes that the avatar or virtual character will collide or contact the ground obstacle while traversing from the first position310to the second position312.

In some embodiments, the outer contact surface of the ground obstacle may be represented by a collision mesh in the exact shape of the ground obstacle or by a 3 dimensional shape overlaying or bounding the ground obstacle such as, but not limited to, a cylinder, a sphere, a capsule, a rectangle, a pyramid or a polyhedron. Thus, the first condition is determined by the module132based on a two-dimensional calculation using the x and y coordinates of the capsule model210and a collision mesh or a 3 dimensional bounding shape or volume of the ground obstacle. Also, the second condition is determined by the module132based on a one-dimensional calculation using the z coordinates of the capsule model210and a collision mesh or a 3 dimensional bounding shape or volume of the ground obstacle.

It should be appreciated that since the capsule model210is positioned at the distance ‘dcap’ of the cap213above the ground225, the module132detects collision of the avatar or virtual character220with only those ground obstacles that have a height (or a vertical dimension along a direction parallel to the z axis) greater than the distance ‘dcap’. This enables the player controlled avatar or virtual character to move over small ground obstacles (having heights less than or equal to the distance ‘dcap’) on the ground225without requiring frequent halts or changes in the speed and/or direction of motion that would otherwise result from collision detection with the small obstacles.

FIG.4is a flowchart of a plurality of exemplary steps of a method400of predicting collision detection, in accordance with some embodiments of the present specification. The method400is executed by the module132(FIG.1A) during run-time to simulate frames of a virtual environment or game space based on player input. In embodiments, the method400is executed on a frame-by-frame basis for consecutive rendering of frames of the virtual environment or game space.

Referring now toFIGS.1and4, at step402, a composite model is virtually defined for a player controlled avatar or virtual character for the purpose of collision detection with a ground obstacle. In some embodiments, the avatar or virtual character is oriented vertically on a ground such that a central longitudinal axis of the avatar or virtual character is parallel to a z axis of a world coordinate system. In some embodiments, the composite model comprises a first geometric primitive or model having a first shape and size and a second geometric primitive or model having a second shape and size. In embodiments, the second geometric primitive or model is bounded by and positioned within the first geometric primitive or model.

In some embodiments, the first geometric primitive or model is a cylinder model that at least partially bounds and approximately represents the avatar or virtual character. The cylinder model is characterized by a center line lcy(containing the center of mass of the cylinder mcy) and a radius rcysuch that the center line lcyis coaxial with the central longitudinal axis of the avatar or virtual character. In an embodiment, the first size (in terms of the center line lcyand the radius rcy) of the cylinder model is defined such that the cylinder model bounds an entirety of the avatar or virtual character.

In some embodiments, the second geometric primitive or model is a capsule model having a cylindrical body with semi-spherical/hemispherical first and second ends or caps (also referred to as top and bottom ends or caps). The capsule model is characterized by a center line lcap(containing the center of mass of the capsule mcap) and a radius rcapsuch that the center line lcapis coaxial with the central longitudinal axis of the avatar or virtual character. The capsule model has first and second end caps (hemispherical) of radii rcap.

In some embodiments, the second size (in terms of the center line lcapand the radius rcap) and positioning of the capsule model is defined such that a) the capsule model is bounded or encompassed by the cylinder model, b) the capsule model bounds at least a portion of the avatar or virtual character, and c) a tip of the second cap (that lies closer to the ground compared to the first cap) lies a predefined height or distance ‘dcap’ above the ground.

At step404, first data indicative of player input is acquired or detected at the beginning of a frame duration tframe(that is, at the beginning of a current frame). In some embodiments, the first data includes a first position (or a current position/location) of the avatar or virtual character along with first direction and first velocity, relative to the ground object, imparted to the avatar or virtual character as a result of the player's manipulation of the avatar or virtual character.

In some embodiments, periodic polling of the one or more client devices110is performed to acquire the first data. In some embodiments, the periodic polling is performed at a predetermined polling rate. In some embodiments, the polling rate is equal to the frame rate Rframe—that is, the rate at which frames are rendered for display on the one or more client devices110. That is, the collision check is performed at display intervals of the game space frames. If the frame rate is Rframethen the frame duration tframe=1/Rframe. For example, if the frame rate is 60 fps (frames per second) then the frame duration tframe= 1/60 seconds=polling period or duration. In alternate embodiments, however, the polling rate may be set higher than the frame rate.

In some embodiments, an outer contact surface of the ground obstacle may be represented by a collision mesh in an exact shape of the ground obstacle or by a 3 dimensional geometric shape overlaying or bounding the ground obstacle such as, but not limited to, a cylinder, a sphere, a capsule, a rectangle, a pyramid or a polyhedron.

At step406, second data indicative of at least a second position (or a predicted position/location), at the end of the frame duration tframe(that is, for a next frame to be rendered), of the avatar or virtual character is determined or predicted. In some embodiments, the second position is determined by predicting a path or trajectory that the avatar or virtual character would likely traverse, from the first position to the second position, based on the first direction and first velocity data derived from the player input.

At step408, the first geometric primitive or model (that is, the cylinder model) is swept vertically downwards in order to identify the ground obstacle, and/or a ground level or surface that may be horizontal or sloping (with reference to an xy plane of the world coordinate system). In some embodiments, the first geometric primitive or model is swept vertically downwards, from an initial third position to a fourth position, by an extent or a distance ‘E’. In some embodiments, the extent or distance ‘E’ is a sum of the radius rcapof the second geometric primitive or model (that is, the capsule model), the height or distance ‘dcap’ of the second cap above the ground and a predefined distance ‘t’. In various embodiments, the predefined distance ‘t’ is customizable by a computer graphics designer.

At step410, the first geometric primitive or model is swept vertically upwards back to the third position.

At step412, the second geometric primitive or model (that is, the capsule model) is swept forward horizontally from the first position to the second position along the predicted path or trajectory in order to determine if the avatar or virtual character is likely to collide or contact the ground obstacle.

It should be appreciated that since the second geometric primitive or model is positioned at the distance ‘dcap’ of the second cap (or the bottom cap) above the ground (the level of which has already been identified at step408using a vertical sweep test), the module132detects collision of the avatar or virtual character with the ground obstacle only if a height (or a vertical dimension along a direction parallel to the z axis) of the ground obstacle is greater than the distance ‘dcap’.

At step414, a determination is made, based on the vertical and horizontal sweep tests of steps408and412, as to whether a collision is detected. If a collision is detected then, at step416, an adjusted position, direction and/or velocity of the avatar or virtual character may be determined for a next frame. However, if no collision is detected then, at step418, the avatar or virtual character is moved to the second position and the second data is used to generate rendering instructions for the next frame.

It should be appreciated that, in alternate embodiments, the order of the steps of the method400may be modified. For example, in some embodiments, the step404may be performed prior to the step402.

The above examples are merely illustrative of the many applications of the system of present specification. Although only a few embodiments of the present specification have been described herein, it should be understood that the present specification might be embodied in many other specific forms without departing from the spirit or scope of the specification. Therefore, the present examples and embodiments are to be considered as illustrative and not restrictive, and the specification may be modified within the scope of the appended claims.