U.S. Pat. No. 10,226,701

DETAILED DESCRIPTION OF THE INVENTION

The invention described herein relates to a system and method for generating, for a given game map, a minimum distance to LOS catalog (also referred to interchangeably herein as “LOS catalog”) and identifying a spawn location during gameplay based on the LOS catalog.

The LOS catalog may, for each potential spawn location of a game map, indicate a minimum distance to travel from each other map node of a game map to achieve LOS to the potential spawn location. In other words, for every spawn location and other map node pair, the LOS catalog may indicate the minimum distance that may be traveled from the other map node to the spawn location to achieve LOS. A distance may be measured in any distance unit defined by a given video game. As such, the distances provided in a given LOS catalog may be specific for a given video game or game map.

The minimum distance may represent a distance that an enemy player (or opponent) at a given map node, for example, would have to travel before a player spawned at the potential spawn location is visible to the enemy player. In this context, a first spawn location having a greater minimum distance from a given map node (occupied by an enemy player) to achieve LOS may be safer than a second spawn location having a smaller minimum distance from a given map node occupied by an enemy player (occupied by an enemy player) to achieve LOS. Other factors may be considered to assess the relative safety of a spawn location as well. As such, the LOS catalog may be used to identify a safe spawn location, from among various spawn locations, based on information from the LOS catalog and one or more enemy locations (e.g., map nodes at which an enemy or opponent is located).

Exemplary System Architecture

FIG. 1depicts an exemplary architecture of a system100of generating, for a given game map, a minimum distance to LOS catalog and identifying a safe spawn location during gameplay based on the LOS catalog, according to an implementation of the invention.

In one implementation, system100may include one or more computer systems110, one or more databases130, one or more end user devices140, and/or other components.

Computer system110may be configured as a server (e.g., having one or more server blades, processors, etc.), a gaming console, a handheld gaming device, a personal computer (e.g., a desktop computer, a laptop computer, etc.), a smartphone, a tablet computing device, and/or other device that is programmed to generate a distance to LOS catalog and/or identify safe spawn locations as described herein.

Computer system110may include one or more processors112(also interchangeably referred to herein as processors112, processor(s)112, or processor112for convenience), one or more storage devices114(which may store a LOS catalog application120and a game engine122), and/or other components. Processors112may be programmed by one or more computer program instructions. For example, processors112may be programmed by LOS catalog application120and/or other instructions. LOS catalog application120and game engine122may each include various instructions that program computer system110. As described herein, LOS catalog application120and game engine may each be described as programming computer system110to perform various operations. However, it should be understood that a portion (or all) of LOS catalog application120and/or game engine122may, alternatively or additionally, program other system components (e.g., end user device140) to perform at least some of the functions of the applications.

According to an aspect of the invention, end user device140may be configured as a gaming console, a handheld gaming device, a personal computer (e.g., a desktop computer, a laptop computer, etc.), a smartphone, a tablet computing device, and/or other device that can be programmed to perform various functions (e.g., of LOS catalog application120) described herein. Although not illustrated inFIG. 1, an end user device140may include one or more physical processors programmed by computer program instructions. For example, end user device140may be programmed by all or a portion of LOS catalog application120(e.g., when hosting a multi-player video game with other user devices, or when locally playing a multi-player video game with multiple users).

Although illustrated inFIG. 1as single components, computer system110and end user device140may each include a plurality of individual components (e.g., computer devices), each programmed with at least some of the functions described herein. In this manner, some components of computer system110and/or end user device140may perform some functions while other components may perform other functions, as would be appreciated. The one or more processors112may each include one or more physical processors that are programmed by computer program instructions. The various instructions described herein are exemplary only. Other configurations and numbers of instructions may be used, so long as the processor(s)112are programmed to perform the functions described herein.

Furthermore, it should be appreciated that although the various instructions are illustrated inFIG. 1as being co-located within a single processing unit, in implementations in which processor(s)112includes multiple processing units, one or more instructions may be executed remotely from the other instructions.

The description of the functionality provided by the different instructions described herein is for illustrative purposes, and is not intended to be limiting, as any of instructions may provide more or less functionality than is described. For example, one or more of the instructions may be eliminated, and some or all of its functionality may be provided by other ones of the instructions. As another example, processor(s)112may be programmed by one or more additional instructions that may perform some or all of the functionality attributed herein to one of the instructions.

The various instructions described herein may be stored in a storage device114, which may comprise random access memory (RAM), read only memory (ROM), and/or other memory. The storage device may store the computer program instructions (e.g., the aforementioned instructions) to be executed by processor112as well as data that may be manipulated by processor112. The storage device may comprise floppy disks, hard disks, optical disks, tapes, or other storage media for storing computer-executable instructions and/or data.

The various databases130described 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. Database130may comprise one or more such databases that reside in one or more physical devices and in one or more physical locations. Database130may store a plurality of types of data and/or files and associated data or file descriptions, administrative information, or any other data.

Each of the various components illustrated inFIG. 1may be coupled to at least one other component via a network102, which may include any one or more of, for instance, the Internet, an intranet, a PAN (Personal Area Network), a LAN (Local Area Network), a WAN (Wide Area Network), a SAN (Storage Area Network), a MAN (Metropolitan Area Network), a wireless network, a cellular communications network, a Public Switched Telephone Network, and/or other network. InFIG. 1, as well as in other drawing Figures, different numbers of entities than those depicted may be used. Furthermore, according to various implementations, the components described herein may be implemented in hardware and/or software that configure hardware.

The foregoing system architecture is exemplary only and should not be viewed as limiting. Other system configurations may be used as well, as would be appreciated by those having skill in the art.

LOS Catalog Application120and Game Engine122

FIG. 2depicts an exemplary block diagram of LOS catalog application120and game engine122, according to an implementation of the invention. LOS catalog application120may generate a distance to LOS catalog. Game engine122may use the LOS catalog, together with information indicating whether unsafe elements exist at a given game node, to identify a spawn location at which to spawn a player.

The instructions of LOS catalog application120may include, without limitation, a distance to LOS engine202(referred to interchangeably as “LOS engine202”), a LOS modeling engine204, and/or other instructions206that program computer system110to perform various operations, each of which are described in greater detail herein.

Game engine122may include a spawn engine210that identifies spawn locations for players during gameplay based on the LOS catalog and in-game information and/or other instructions. As used herein, for convenience, the various instructions will be described as performing an operation, when, in fact, the various instructions program the processors112(and therefore computer system110) to perform the operation.

When describing various implementations of generating a LOS catalog, reference throughout this disclosure will be made toFIGS. 3, 4A, 4B, 4C, 4D, 5A, and 5B, as well as various processing operations illustrated inFIGS. 6, 7A, and 7B.

When describing various implementations of using the LOS catalog to identify spawn locations for players, reference throughout this disclosure will be made toFIGS. 8 and 9.

FIG. 3depicts a schematic diagram300of map nodes N1-N18of a game map and exemplary paths301A,301B between a first map node N1and a second map node N5, according to an implementation of the invention. A given map node may represent an area of a game that a player (e.g., the player's character, object, etc.) may traverse during gameplay. Each map node may include 2-dimensional or 3-dimensional coordinates/characteristics, depending on the type of game to which the game map relates. The various map nodes N1-N18are exemplary only. Other numbers and configurations of map nodes may be used depending on the design of the game map. Furthermore, some or all of the map nodes N1-N18may serve as potential spawn locations, depending on a game designer's default selections, user configurations, and/or other information that indicates which map nodes of a game map should be used as potential spawn locations.

Various pathfinding algorithms may identify the shortest path between two map nodes and calculate the minimum distance to achieve LOS between the two map nodes along the shortest path (as will be described further below). In the Figures, the shortest path is illustrated as path301A, and will be used in examples herein throughout. Using the shortest path approach, the minimum distance to LOS between a map node and a spawn location may represent the shortest distance that an enemy player at the map node must travel to achieve LOS to a player spawned at the spawn location.

In some implementations, the system may identify and traverse two or more paths (which may represent the shortest N paths or all paths) between two map nodes, and calculate a minimum distance to LOS for each path. The system in these implementations may use the average minimum distances, mean minimum distances, and/or other cumulative minimum distances associated with the multiple paths to determine the minimum distance to LOS between two nodes. For example, the minimum distance from a map node to a spawn location may be determined by averaging the minimum distances along two or more paths. For computational efficiency, however, only the shortest path between two map nodes may be used to determine a minimum distance to LOS for the two map nodes.

FIG. 4Adepicts a schematic diagram of traversing a path301A from the second map node N1to the first map node N5in a first direction (denoted by the arrows) to identify the minimum distance to travel from the second map node to the first map node to achieve LOS to the first map node, according to an implementation of the invention. Filled (or solid) map nodes (e.g., N3and N4, N19) represent nodes in which LOS to the first map node N5exists. In some instances, a nearby node having known LOS to a target node, but not on the identified path, may be traversed to from the path to measure the distance to travel to the nearby node. For example, even though map node N19is not on path301A, it may be traversed to because it has known LOS to map node N5(e.g., based on prior traversals of the game map). This may be the case whether or not there exists a path from N19to map node N5, so long as there exists LOS between N19and map node N5. Traveling to N19from path301A may, in some instances, represent the minimum distance to achieve LOS to the target N5from map node N1even though N19is not on path301A.

FIG. 4Bdepicts a schematic diagram of traversing the path301A from the first map node N5to the second map node N1in a second direction (denoted by the arrows, and opposite the direction ofFIG. 4A) to identify the minimum distance to travel from the second map node to the first map node to achieve LOS to the first map node, according to an implementation of the invention. Filled (or solid) map nodes (e.g., N2) represent nodes in which LOS to the second map node N1exists.

FIG. 4Cdepicts a schematic diagram400of traversing a path401A that includes non-node positions between a pair of map nodes (N2, N5) to determine a minimum distance to LOS between the map nodes (N2, N5), according to an implementation of the invention. As used herein, a non-node position (e.g., positions indicated by distances traversed d1-6ofFIGS. 4C and 4D) on a map is a position (e.g., an Artificial Intelligence mesh point) that is not a map node but can be traversed by a player. Typically, though not necessarily, such non-node positions may be generated after a map is compiled or otherwise instantiated (e.g., after the map has been designed by a game developer or others).

As illustrated inFIG. 4C, a visual obstruction402(e.g., a virtual object) may obstruct LOS between a given pair of positions (whether either position is a node or non-node position) on a game map. Such LOS obstruction may be in two or more dimensions. LOS engine202may traverse a path401A between nodes N1and N5. Although not illustrated, LOS engine202may traverse path401A in two directions (e.g., a first direction from N1to N5and a second direction, which may be a reverse of the first direction, from N5to N1) and compare the results of the two passes to determine an overall minimum distance to achieve LOS, as described herein. At various points (e.g., points defined by distances traveled d1-4) along path401A, LOS engine202may determine whether LOS exists between each point and node N5. As illustrated, LOS engine202may determine that LOS is first detected from N1to N5along path401A at a point corresponding to a distance traveled d4. LOS engine202may store this value as a first minimum distance for the first pass from N1to N5. LOS engine202may repeat the foregoing operations in a second pass from N5to N1to determine a second minimum distance to achieve LOS. LOS engine202may select the smaller of the first and the second minimum distances as representative of the minimum distance to achieve LOS between nodes N1and N5.

FIG. 4Ddepicts a schematic diagram400of traversing an alternative path401B that includes non-node positions, based on previously known LOS information, to determine a minimum distance to LOS between a pair of map nodes (N2, N5), according to an implementation of the invention. In some implementations, LOS engine202may access information that indicates LOS between a pair of map nodes (e.g., N2and N5) exists, and use that information when determining a minimum distance to achieve LOS between another pair of map nodes (e.g., N1and N5). For example, because LOS is known to exist between N2and N5, LOS engine202may identify a path401B from N1to N2when determining a minimum distance to achieve LOS between N1and N5. This is because pathing from N1to N2may identify a position along path401B (which may include N2itself, a non-node position (as illustrated inFIG. 4D), or intervening nodes (not illustrated inFIG. 4D) along path401B) that has LOS to N5at a smaller distance than any points along path401A (illustrated inFIG. 4C).

Although not explicitly illustrated in the Figures, LOS engine202may traverse a path that includes both nodes and non-node positions as well.

FIG. 5Adepicts a schematic diagram500A of determining whether LOS exists between two map nodes N1and N2, according to an implementation of the invention.FIG. 5Bdepicts a schematic diagram500B of determining whether LOS exists between two map nodes N1and N2, according to an implementation of the invention.FIGS. 5A and 5Billustrate testing whether LOS exists at various heights (H1, H2, H3, . . . HN).

Generating a LOS Catalog

FIG. 6depicts a process600of generating a minimum distance to LOS catalog, according to an implementation of the invention. Although LOS engine202is described below as performing various operations of process600, other components of system100may, alternatively or additionally, perform one or more operations of process600. Furthermore, in the examples that follow, although a potential spawn location is described as being analyzed with respect to another map node, process600may be used to determine minimum distance to LOS between any pair of map nodes of a game map.

In an operation602, LOS engine202may obtain a set of map nodes for which minimum distances to LOS is to be obtained. The set of map nodes may include potential spawn locations, which may include a portion or all map nodes of a game map. The potential spawn locations may be pre-selected by a game designer, modified by a player or others, and/or may otherwise be selected from among map nodes of the game map.

In an operation604, LOS engine202may identify a potential spawn location from among the set of potential spawn locations for pairwise processing with other map nodes. For example, as will be described below, for each potential spawn location, LOS engine202may iterate through each other map node of the game map to build a catalog of minimum distances required to travel from each other map node to the potential spawn location to achieve LOS to the potential spawn location.

This process may be iterated for each potential spawn location, building a comprehensive set of minimum distances to achieve LOS to a given spawn location from a given map node. For example, referring toFIG. 3, a potential spawn location (map node N1) may be analyzed with respect to each other map node (map nodes N2-N18) to determine a minimum distance that must be traveled from another map node to achieve LOS with the potential spawn location. To do so, a path may be traversed from the other map node to the potential spawn location. Determining a minimum distance that must be traveled from another map node N5to achieve LOS to a potential spawn location N1is illustrated. To determine the minimum distance, one or more paths (301A,301B,401A,401B) between the potential spawn location N1and other map node N5may be traversed.

The foregoing process may be repeated for each potential spawn location/other map node pair to generate the LOS catalog. Assuming that all unique pairwise comparisons of map nodes are performed, the total number of pairwise comparisons would be given by equation (1) below:
N2(1),

wherein N=number of map nodes in a game map.

As an example, for 18 map nodes, the foregoing would yield324pairwise comparisons.

However, LOS engine202may optimize storage requirements of a LOS catalog. For example, LOS engine202may ignore self-node comparisons (e.g., node N1to N1) and store only the smaller of the directions from a given map node to another map node (e.g., N1to N2and N2to N1). Assuming only the foregoing optimizations are made (further optimizations may be performed as well), the total number of pairwise comparisons would be given by equation (2) below:

N*⁡(N+1)2,(2)

wherein N=number of map nodes in a game map.

According to equation (2), for 18 nodes, the number of entries in the LOS catalog would be equal to 171, a reduction from 324. Using the foregoing and other optimization techniques, the processing requirements to generate and the storage requirement to store the LOS catalog may be substantially reduced.

In an operation606, LOS engine202may identify the next map node from among the other map nodes for processing with the next potential spawn location identified in operation604.

In an operation608, LOS engine202may determine and store (in a memory) a minimum distance required to travel from the second map node to achieve LOS to the first map node. Such storage may be temporary until iterative processing of process600is complete, resulting in generation of the LOS catalog. The determined minimum distance may be indicative of the relative safety of the analyzed spawn location (e.g., the first map node) with respect to another map node (e.g., the second map node) of the game map. Details of determining the minimum distance are described in greater detail with respect toFIGS. 7A and 7B.

In an operation610, LOS engine202may determine whether there exist additional other map nodes to analyze. Responsive to a determination that other map nodes are to be analyzed, LOS engine202may return to operation606and identify another map node to analyze with respect to the potential spawn location. Responsive to a determination that no other map nodes are to be analyzed, meaning that for a given potential spawn location, all pairwise comparisons with other map nodes of the game map have been analyzed, in an operation612, LOS engine202may determine whether other potential spawn locations are to be analyzed. Responsive to a determination that other potential spawn locations are to be analyzed, LOS engine202may return to operation604, where the next spawn location to be analyzed is identified.

Responsive to a determination that other potential spawn locations are to be analyzed, in an operation614, LOS engine202may generate and store the LOS catalog based on the stored minimum distances. For example, the game map, LOS catalog, and/or any versions thereof, may be stored at and retrieved from an LOS database, such as a database130.

Table 1 (below) illustrates an exemplary LOS catalog (e.g., generated by process600) that includes entries for two potential spawn locations (N1and N2) and a total of 18 map nodes N1-N18. It should be understood that the entries in Table 1 (and Table 2 below) are for illustrative purposes only. Typically, there are hundreds of map nodes (if not more) and dozens of potential spawn locations (if not more) in a given game map.

TABLE 1Potential SpawnMapMinimumLocationNodeDistance to LOSN1N23N1N35N1N45N1N55N1. . .. . .N1N184N2N33N2N43N2N53N2. . .. . .N2N186

Determining a Minimum Distance to LOS Between Two Map Nodes

FIG. 7Adepicts a first portion of a process700of determining a minimum distance to travel from a given map node to achieve LOS to a potential spawn location, according to an implementation of the invention.FIG. 7Bdepicts a second portion of process700of determining a minimum distance to travel from a given map node to achieve LOS to a potential spawn location, according to an implementation of the invention. Process700may be used to determine a minimum distance from a given map node to another map node (not limited to a potential spawn location) as well. As such, the various processing operations ofFIGS. 7A and 7Bwill be described with respect to LOS between a spawn location and a map node for convenience and not limitation. The output of process700may be used as a value for the minimum distance to LOS in the LOS catalog for a given pair of map nodes, whether or not one or both nodes of the pair is a potential spawn point.

In an operation702, LOS engine202may obtain a spawn location and map node for which to obtain a minimum travel distance to achieve LOS from the map node to the spawn location. For example, referring toFIGS. 4A, 4B, 4C, AND 4D, LOS engine202may perform a pairwise analysis for potential spawn location N1and map node N5.

In an operation704, LOS engine202may determine whether LOS exists from the map node to the spawn location. To accomplish the foregoing, LOS engine202may issue one or more line of site traces (e.g., using a min/max kd-tree, ray tracing techniques, Bresenham's line algorithm for two-dimensional games, etc.) starting from one map node to another map node and/or vice versa. For example, LOS engine202may issue one or more line of site traces from the map node to the spawn location. In some implementations, LOS engine202may account for elevation differences in a 3D game map when determining whether LOS exists from the map node to the spawn location. Referring toFIGS. 5A and 5B, for instance, LOS engine202may issue one or more line of site traces from each of various heights (H1, H2, H3. . . HN) at a position P to a node N2(or non-node position on a map). Position P may include a node (such as a node N1) or a non-node position on a map between nodes. In some instances, LOS engine202may issue one or more line of site traces from a given height at position P to more than one height of another node N2.

Each height (H1, H2, H3. . . HN) may represent different player stances/positions. For example, a first height may represent a laid down position of the player, a second height may represent a crouched position of the player, a third height may represent a standing position of the player, and a fourth height may represent a highest jumping position of the player. Other heights may be used as well. For example, another height may represent a position of a player standing on a virtual object. In either example, an average player height may be used for the foregoing line of site traces.

In some implementations, if line of site traces from (or to) any one of the heights results in LOS, LOS engine202may determine that LOS exists from the position P to the spawn location. In some implementations, LOS engine202may analyze a line of site trace from (or to) a particular height separately from the other heights. For example, LOS engine202may determine whether line of site exists from the position P to the spawn location depending on whether line of site traces from (or to) any one of the first three heights (e.g., laid down, crouched, or standing position) results in LOS and depending on whether line of site exists from the map node to the spawn location depending on whether line of site traces from (or to) a fourth height (e.g., the jumping position). In a particular example, the jumping position (and/or other heights) may be separately weighted in making the determination of whether or not LOS exists from the position P to the spawn location. Such weights may be based on empirical observations, such as observations relating to the relative frequency that players are at different heights for a given position. For example, even if LOS is achieved at a jumping height but not at a standing height at a given position, this does not necessarily mean that an enemy player at the given position will be at the jumping height (e.g., an enemy player may be observed to usually be in a standing height rather than a jumping height at the given position). The foregoing types of observations may be map-specific because at a given position in the map, a player may tend to be at one height rather than another height (e.g., a given position on a map may require or otherwise be advantageous for a player to be either crouching, standing, jumping, etc.). Based on the frequency of heights that players are observed to be at a given position, the system or developer may apply different weights for those heights for that given position. In this manner, heights having less frequency of actual occurrence may be weighted lower than heights having a greater frequency of actual occurrence.

In implementations in which various heights are used to assess LOS (as illustrated inFIGS. 5A and 5B), the storage requirements for the LOS catalog may be given by equation (3) below.

N*⁡(N+1)2*M⁢⁢bytes,(3)

wherein N=number of map nodes in a game map, and

wherein M=number of bytes used to store height value sets.

For example, if two sets of heights (e.g., a jumping height and all other heights), then M would equal two.

It should be noted that LOS is not necessarily limited to a visual line of site in a two-dimensional or three-dimensional video game in which a player is able to visually see another player. For example, in two dimensional contexts (such as side-scrolling games, top-down games, etc.), even though a player may be able to visually see another player, LOS may not exist between the two players depending on the particular mechanics of that game. In particular, LOS may not exist between two players if a barrier between the players prevents some action (e.g., a player shooting another player) from occurring. In these instances, determining whether LOS exists may involve traversing a path between two nodes of the game (as described herein), but the line of sight traces may involve determining whether the action (such as shooting another player) is possible.

Responsive to a determination that LOS exists between the map node and the spawn location, in an operation706, LOS engine202may store an indication that LOS exists between the map node and the spawn location. For example, LOS engine202may store a distance to LOS value of zero (to indicate no distance need be traveled to achieve LOS from the map node to the spawn location).

Responsive to a determination that LOS does not exist between the map node and the spawn location, in an operation708, LOS engine202may identify and traverse a path (e.g., a shortest path301A between N1and N5illustrated inFIGS. 4A and 4B, a path401A illustrated inFIG. 4C, and/or a path401B illustrated inFIG. 4D) between the spawn location and the map node. As will be described further, LOS engine202may traverse a given path in two directions (e.g., in a first direction indicated by arrows inFIG. 4Aand a second, opposite, direction indicated by arrows inFIG. 4B). LOS engine may determine a minimum distance to achieve LOS between the map node and the spawn location for each direction, and identify the smaller of the two minimum distances, which may be used as the minimum distance to achieve LOS for the spawn location and map node pair.

LOS engine202may apply one or more conventional pathfinding algorithms (e.g., A*—commonly referred to as “A-Star”) to identify the path. In some instances, the identified path is the shortest path between two nodes. Such a path may include intervening nodes (e.g., N2-N4illustrated inFIGS. 4A and 4B), and/or non-node positions (e.g., positions indicated by distances traversed d1-6along a path401A illustrated inFIG. 4Cand a path401B illustrated inFIG. 4D). LOS engine202may traverse a distance to a position along the path, which may include traversing to each intervening node in a given direction and/or traversing to various points along a path denoted by distance traveled d1-6illustrated inFIGS. 4C and 4D.

In an operation710, when LOS engine202traverses to a position along the path (e.g., one of intervening nodes one of N2-N4or a non-node position), it may determine whether LOS exists from the position to the potential spawn location (e.g., N1). Such a determination may be made in a manner similar to that described above with respect to operation704. In some implementations, LOS engine202may traverse, from a position on the identified path, to a nearby node not on the identified path that is known to have LOS to the potential spawn location.

Responsive to a determination that LOS exists between the traversed-to position and the spawn location, in an operation712, LOS engine202may record the distance traveled to the position, which represents the minimum distance to achieve LOS while traveling from the potential spawn location N1to the other node N5along path301A in a first direction (denoted by arrows inFIG. 4A). LOS engine202may then proceed to operation716(illustrated inFIG. 7B), described below.

Responsive to a determination that LOS does not exist between the traversed-to position, and the spawn location, in an operation714, LOS engine202may determine whether the other node has been reached. If yes, LOS engine202may return to operation708, in which LOS engine202traverses to another distance to a next position along the path. If the other node has been reached, LOS engine202may proceed to operation716(illustrated inFIG. 7B).

In an operation716, LOS engine202may repeat operations708-714, but traversing path301A or401A in the opposite direction.

In an operation718, LOS engine202may compare the minimum distances obtained from the first direction and the second direction. If no minimum distance was recorded for a given directional pass (meaning that there was no LOS in a position traversed between the pair of nodes along the direction traversed), then the distance traveled between the pair of nodes will be used as a minimum distance. Alternatively, a predefined maximum default value may be used as a minimum distance. For example, and without limitation, prior to a pathing operation, a minimum distance may be defaulted to the maximum default value, which is replaced when LOS is achieved. Alternatively, when no minimum distance is determined, then the maximum default value is selected.

In either instance, the minimum distance to achieve LOS may be stored as, without limitation, a single byte. In this example, the maximum default value may be quantized to be stored using the single byte. For example, the maximum default value (or the actual minimum distance to achieve LOS) may be quantized by dividing the distance by 10. In this example, the data may be initialized to 255 (implying a distance to line of sight of 2550 in distance units). When a minimum distance that is shorter than the maximum default value is found, the minimum distance will be used instead of the maximum default value.

In an operation720, LOS engine202may select and return the smaller of the two minimum distances. Alternatively, LOS engine202may calculate an average the two smaller minimum distances and return the average.

In one non-limiting example, a minimum distance may be returned as a quantized value ranging from 0.0 to 1.0. For example, the minimum distance may be returned based on equation (4) below.

1-d255,(4)

wherein d=distance units.

According to equation (4), a minimum distance value of 1.0 indicates instantaneous LOS exists (because distance units, d, is zero), while a minimum distance value of 0.0 indicates the distance is equal to the max distance of 2550 distance units (because, per the above, the maximum distance value of 2550 divided by 10 is 255). Other quantization values may be used as well.

In some implementations, referring toFIGS. 4C and 4D, LOS may be known to exist between a given map node N5and another map node N2, which is not necessarily along a path between a pair of nodes (N1and N5) being processed. If so, then LOS engine202may traverse a path401B from one of the pair of nodes being analyzed (e.g., N1) to the map node (N2) having known LOS with the other of the pair of map nodes being analyzed (e.g., N5) and may periodically determine, at positions at various distances traversed (e.g., d5and d6), whether LOS exists between the positions and the other map node (e.g., N5) using processing operations described herein with respect toFIGS. 5A and 5B. For example, LOS engine202may determine that LOS is first achieved at a position corresponding to a distance traveled (d6) along path401B. LOS engine202may determine that LOS is first achieved at a position corresponding to a distance traveled (d4) along path401A. In these instances, LOS engine202may compare the minimum distances to achieve LOS between N1to N5based on paths401A and401B to obtain the overall minimum distance to achieve LOS between N1and N5. For example, LOS engine202may identify which one of d4and d6is smaller, and use the smaller value as the minimum distance to achieve LOS between the pair of map nodes N1and N5.

In some implementations, for a given pair of nodes (e.g., N1and N5) for which a minimum distance to achieve LOS between the pair has been determined (e.g., based on process600and/or process700), LOS engine202may identify a set of one or more nodes (each of these nodes also being referred to as an NLOSnode) having LOS to a first node (e.g., N1) of the pair. For each node in the set of NLOSnodes, LOS engine202may obtain a minimum distance (Dmin) to LOS between the NLOSnode and the second node of the pair (e.g., N5). Dminmay have been previously determined based on prior processing (e.g., via process600and/or process700). If Dminis smaller than the minimum distance to achieve LOS between N1and N5, LOS engine202may determine a distance between N1and the NLOSnode (e.g., by determining the length of a 3D distance vector between N1and the NLOSnode). LOS engine202may sum the distance with Dminand determine whether the sum is smaller than the minimum distance to achieve LOS between N1and N5. If so, then LOS engine202may replace the minimum distance to achieve LOS between N1and N5with the sum. This is because, in the foregoing instance, a player may achieve LOS faster (e.g., smaller minimum distance) by traversing from node N1to NLOSthan had the player traversed from N1to N5using the path used to obtain the previous minimum distance to achieve LOS (as determined based on process600and/or process700). On the other hand, if the sum is greater than the minimum distance to achieve LOS between N1and N5that was previously determined (e.g., based on process600and/or process700), then LOS engine202may not replace the minimum distance with the sum.

LOS engine202may repeat the foregoing for the other one (e.g., N5) of the pair of nodes (e.g., N1and N5) and select the smaller of the two resulting values. LOS engine202may process a given pair of nodes using two or more passes of the foregoing process of using NLOSnodes to refine and update the LOS catalog as well. Furthermore, LOS engine202may repeat the foregoing for each pair of nodes for which minimum distance to achieve LOS between the pair has been determined (e.g., using process600and/or process700).

It should be noted that all or a portion of process600and/or700may be repeated to account for any changes to a game map for which a LOS catalog has been generated. This may account for changes in map node locations, including any changes to spawn location locations, of the game map. For example, and without limitation, to the extent that the number of map node location changes for a given game map exceeds a predefined threshold value (e.g., one or more changes), an all-new LOS catalog may be generated for the changed game map. Otherwise, only portions of the LOS catalog affected by the changed map node locations may be updated. Furthermore, for updated game maps, changes to the LOS catalog may be stored as deltas that each indicate how the updated LOS catalog has changed relative to a previous version of the LOS catalog. In this sense, game maps and corresponding LOS catalogs, in some implementations, may be managed using version control techniques for storage and computational efficiency.

Revising LOS Catalogs Based on Empirical and/or Game Map Data

In an implementation, LOS modeling engine204may observe gameplay and record actual traversal times between map nodes. These traversal times may be used to determine weights for minimum distance to LOS. For example, even though a first sets of nodes may be spaced apart an equal distance as a second set of nodes, the first set of nodes may be more difficult to traverse (and therefore take longer to traverse) due to obstacles, tendency of players to congregate, and/or other factors. In these instances, the minimum distance until LOS is achieved for the first set of nodes may be weighted higher (e.g., have a distance weight >1), effectively increasing the minimum distance. Alternatively or additionally, the minimum distance until LOS is achieved for the second set of nodes may be weighted lower (e.g., have a distance weight <1), effectively decreasing the minimum distance.

Table 2 illustrates an exemplary LOS catalog having weighted minimum distances based on empirical and/or game map data, according to an implementation of the invention.

TABLE 2Minimum Distanceuntil LOS achievedPotential SpawnMapfrom Map Node toDistancelocationNodeSpawn locationWeightN1N231.2N1N351.0N1N451.0N1N551.0N1. . .. . .. . .N1N1841.0N2N331.0N2N431.0N2N530.9N2. . .. . .. . .N2N1861.5

Identifying a Spawn Location for a Player Based on the LOS Catalog

In an implementation, game engine122may load a game map and its corresponding LOS catalog (either an unweighted version of the LOS catalog such as illustrated in Table 1 or weighted version of the LOS catalog such as illustrated in Table 2). Game engine122may process gameplay between one or more players. During gameplay, a player (whether a human player or an NPC player) may be killed, or otherwise require spawning.

FIG. 8depicts a process800of identifying a spawn location, from among potential spawn locations on a game map, at which to spawn a player based on a distance to LOS catalog, according to an implementation of the invention.

In an operation802, spawn engine210may obtain an indication to spawn the player. In an operation804, spawn engine210may obtain an identification of potential spawn locations. The identification may be obtained from the LOS catalog or other source.

In an operation806, spawn engine210may determine a distance from the closest unsafe map node to the spawn location. A map node may be considered “unsafe” if an unsafe game element that has LOS to the spawned player is currently located at the map node. The distance to an unsafe map node may be defined by a minimum distance to achieve LOS from the unsafe map node to the spawn location. The foregoing determination is further described below with respect toFIG. 9.

In an operation808, spawn engine210may store the distance for the spawn location in a memory for later comparison to other distances for other spawn locations.

In an operation810, spawn engine210may determine whether additional spawn locations are to be analyzed. Responsive to a determination that additional spawn locations are to be analyzed, spawn engine210may return to operation806to iterate through all potential spawn locations and store each of their respective distances.

Responsive to a determination that no additional spawn locations are to be analyzed, in an operation812, spawn engine210may compare the distances for each of the spawn locations (e.g., previously stored in memory) and select a spawn location based on the comparison. For example, spawn engine210may select a spawn location having the greatest distance to an unsafe map node may be selected.

In some implementations, spawn engine210may select a spawn location based further on one or more other spawn factors. In other words, the greatest distance to an unsafe map node may be used as one of many factors. The other spawn factors may include, without limitation, a number of unsafe elements (e.g., number of enemy players, virtual grenades, automated virtual weapons, etc.) in nearby map nodes (e.g., a number of enemy players at the closest N map nodes, where N is an integer value greater than zero), a characteristic of an unsafe element (e.g., a type of weapon carried by an enemy player—where an enemy player carrying only a handgun may be less dangerous than an enemy carrying a rifle), and/or other factors.

In some implementations, the spawn factors may each be weighted and their corresponding weighted values may be cumulated to generate an overall score for each spawn location. Such weights may be pre-assigned by a game developer, user or others. Alternatively or additionally, the weights may be updated based on observations of the performance of players spawned at various spawn locations, and corresponding conditions around those spawn locations. For example, spawn engine210may observe that a high density of nearby enemy players contributes more so to kills of spawned players than does a type of weapon carried by an enemy player. Accordingly, the density of nearby enemy players may be weighted more heavily than a type of weapon carried by an enemy player. Likewise, spawn engine210may observe that a short distance to LOS contributes more so to kills of spawn players than other spawn factors. Spawn engine210may quantify such importance based on observations of time before a spawned player is killed, a number of times spawned players are killed under certain spawn factor conditions, and/or other observed gameplay metric.

FIG. 9depicts a process900of identifying a closest unsafe map node to a spawn location based on a minimum distance to LOS catalog and location of unsafe game elements, according to an implementation of the invention. Process900may receive as input a spawn location (e.g., a map node identifier corresponding to a spawn location) from operation806illustrated inFIG. 8. As such, in some implementations, process900may be executed for each potential spawn location described with respect toFIG. 8.

In an operation902, spawn engine210may identify unsafe map nodes. An unsafe map node may include a map node occupied by an unsafe game element. An unsafe game element may include a moving or stationary game element that can target a spawned player if LOS exists between the game element and a spawned player. An unsafe game element may include, without limitation, an enemy human or NPC player, an object (e.g., an automated weapon) that can target a spawned player, and/or other game element that can target a spawned player.

In an operation904, spawn engine210may identify a minimum distance needed to travel from an unsafe map node to the spawn location. In an operation906, spawn engine210may store the minimum distance for the unsafe map node.

In an operation908, spawn engine210may determine whether more unsafe map nodes are to be processed. Responsive to a determination that more unsafe map nodes are to be processed, spawn engine210may return to operation904.

Responsive to a determination that no more unsafe map nodes are to be processed, spawn engine210may identify and return the smallest minimum distance from among the distances identified and stored at operations904and906. In this manner, process900may identify the closest unsafe map node to a given spawn location (e.g., smaller minimum distances to LOS may correspond to greater unsafety compare to greater minimum distances to LOS).

The various processing operations and/or data flows depicted inFIGS. 6, 7A, 7B, 8, and 9may be accomplished using some or all of the system components described in detail above and, in some implementations, various operations may be performed in different sequences and various operations may be omitted. Additional operations may be performed along with some or all of the operations shown in the depicted flow diagrams. One or more operations may be performed simultaneously. Accordingly, the operations as illustrated (and described in greater detail below) are exemplary by nature and, as such, should not be viewed as limiting.

It should be noted that although LOS catalog is described in various examples as relating to LOS distance values for pairs of map nodes (whether or not a given map node of a given pair is a spawn point), the system may determine a distance to achieve LOS between other types of positions along a path, including non-node positions, as well. As such, an LOS catalog may include distances to achieve LOS between pairs of non-node positions, pairs of a non-node position and a map node, and/or other pair of positions for which a distance to achieve LOS between the pair may be determined and recorded. It is further noted that doing so, however, may increase the storage requirements of the LOS catalog and reduce the efficiency of the system.

Other implementations, uses and advantages of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. The specification should be considered exemplary only, and the scope of the invention is accordingly intended to be limited only by the following claims. As used herein throughout, the term “exemplary” is intended to convey “an example of.”