System and method for identifying spawn locations in a video game

• US 10,226,701 B2
• Filed: 04/29/2016
• Issued: 03/12/2019
• Est. Priority Date: 04/29/2016
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Inventors: Curley, Jeffrey C., Kerby, Paul, Lin, Calvin, Hampton, Edward Alexander, Haile, Paul R.
• Primary Examiner(s): McClellan, James S
• Assistant Examiner(s): Carter, Kevin
• Application Number:
  US15/142,468
• Publication Number:
  US 20170312632A1
• Time in Patent Office: 1,047 Days
• CPC Class Codes: A63F 13/493 Resuming a game, e.g. after pausing, malfunction or power failure
• CPC Class Codes: A63F 13/573 using trajectories of game objects, e.g. of a golf ball according to the point of impact
• CPC Class Codes: A63F 13/60 Generating or modifying game content before or while executing the game program, e.g. authoring tools specially adapted for game development or game-integrated level editor

Abstract

Disclosed is a system and method of generating, for a given game map, an LOS catalog before gameplay and identifying a spawn location during gameplay based on the LOS catalog. For every unique pair of map nodes in a game map, the LOS catalog may indicate the minimum distance that must be traveled from a first map node of the pair to achieve LOS to a second map node of the pair, an identifier for the first map node, and an identifier for the second map node. When a gameplay session is initiated, the LOS catalog may be retrieved and used to identify relatively safe spawn points based on distances that must be traveled from enemy positions to achieve LOS to potential spawn points.

Claims

1. A computer-implemented method of determining distances required to travel to achieve line of site (“

LOS”

) between pairs of map nodes of a game map for a video game, of generating a LOS catalog based on the distances, and of generating a spawn point using the LOS catalog, the method being implemented in a computer system having one or more physical processors programmed with computer program instructions that, when executed by the one or more physical processors, cause the computer system to perform the method, the method comprising;

obtaining, by the computer system, a plurality of map nodes of the game map, the plurality of map nodes comprising at least a first map node and a second map node;

identifying, by the computer system, a path between the first map node and the second map node;

traversing, by the computer system, the path in at least a first direction from the first map node to the second map node;

identifying, by the computer system, a first location along the path at which LOS is achieved between the first location and the second map node;

determining, by the computer system, a first distance traveled to the first location along the path;

generating, by the computer system, an entry in the LOS catalog using an identification of the first map node, an identification of the second map node, and a distance based on the first distance traveled; and

identifying, by the computer system, the spawn point for a player based on the LOS catalog by determining a map node at which an unsafe game element is located and a minimum distance until LOS is achieved between the map node and the spawn point, wherein the spawn point is identified based on the minimum distance.

2. The method of claim 1, wherein the distance comprises the first distance.

3. The method of claim 1, further comprising:

traversing, by the computer system, the path in at least a second direction, different than the first direction, from the second map node to the first map node;

identifying, by the computer system, a second location along the path at which LOS is achieved between the second location and the first map node;

determining, by the computer system, a second distance traveled to the second location along the path; and

identifying, by the computer system, a smaller one of the first distance and the second distance, wherein the distance based on the first distance comprises the smaller one of the first distance and the second distance.

4. The method of claim 1, further comprising:

identifying, by the computer system, a third map node, not on the path, known to have LOS with the second location, wherein the third map node is also known to have a third distance to the second map node; and

identifying, by the computer system, a smaller one of the first distance and the third distance, wherein the distance based on the first distance comprises the smaller one of the first distance and the third distance.

5. The method of claim 1, wherein traversing the path in at least the first direction further comprises:

traversing, by the computer system, from the first map node to a non-node position that is between the first map node and the second map node or an intermediary map node that is between the first map node and the second map node, wherein the first location comprises the non-node position or the intermediary map node.

6. The method of claim 1, wherein identifying the first location along the path at which LOS is achieved further comprises:

issuing, by the computer system, a first LOS trace from the first location at a first height to the second map node;

issuing, by the computer system, a second LOS trace from the first location at a second height, different than the second height, to the second map node; and

determining, by the computer system, whether or not LOS exists from the first location to the second node based on the first LOS trace or the second LOS trace, wherein the first location is identified responsive to a determination that LOS exists from the first location.

7. The method of claim 1, wherein identifying the path further comprises:

identifying, by the computer system, a shortest path between the first map node and the second map node.

8. The method of claim 1, wherein the plurality of map nodes comprises a fourth map node, the method further comprising:

identifying, by the computer system, a second path between the first map node and the fourth map node;

traversing, by the computer system, the second path in at least a third direction from the first map node to the fourth map node;

identifying, by the computer system, a second location along the path at which LOS is achieved between the second location and the fourth map node;

determining, by the computer system, a second distance traveled to the second location along the second path; and

generating, by the computer system, a second entry in the LOS catalog using the identification of the first map node, an identification of the fourth map node, and a third distance based on the second distance traveled.

9. The method of claim 8, wherein the plurality of map nodes comprises a fifth map node, the method further comprising:

identifying, by the computer system, a third path between the fourth map node and the fifth map node;

traversing, by the computer system, the third path in at least a fourth direction from the fourth map node to the fifth map node;

identifying, by the computer system, a third location along the path at which LOS is achieved between the fourth location and the fifth map node;

determining, by the computer system, a third distance traveled to the third location along the third path; and

generating, by the computer system, a third entry in the LOS catalog using the identification of the fourth map node, an identification of the fifth map node, and a fourth distance based on the third distance traveled.

10. The method of claim 1, wherein the entry in the LOS catalog is generated prior to initiation of a given video game session, the method further comprising:

obtaining, by the computer system, an indication that a player should be spawned during gameplay of a session of the video game; and

causing, by the computer system, the player to be spawned at the spawn point during the session of the video game.

11. The method of claim 1, further comprising:

identifying, by the computer system, a second spawn point; and

determining, by the computer system, a second minimum distance until LOS is achieved between the map node and the second spawn point, wherein the spawn point is identified based on a determination that the minimum distance is greater than the second minimum distance.

12. The method of claim 1, further comprising:

identifying, by the computer system, a third map node having LOS with the first map node;

obtaining, by the computer system, a minimum distance to achieve LOS between the third map node and the second map node;

determining, by the computer system, that the minimum distance to achieve LOS between the third map node and the second map node is less than the distance;

obtaining, by the computer system, a second distance between the first map node and the third map node;

determining, by the computer system, a sum of;

the second distance between the first map node and the third map node, and the minimum distance to achieve LOS between the third map node and the second map node;

determining, by the computer system, that the sum is less than the distance; and

replacing, by the computer system, for the entry in the LOS catalog, the distance with the sum responsive to the determination that the sum is less than the distance.

13. A system for determining distances required to travel to achieve line of site (“

LOS”

) between pairs of map nodes of a game map for a video game, of generating a LOS catalog based on the distances, and of generating a spawn point using the LOS catalog, the system comprising;

one or more physical processors programmed with one or more computer program instructions which, when executed, cause the one or more physical processors to;

obtain a plurality of map nodes of the game map, the plurality of map nodes comprising at least a first map node and a second map node;

identify a path between the first map node and the second map node;

traverse the path in at least a first direction from the first map node to the second map node;

identify a first location along the path at which LOS is achieved between the first location and the second map node;

determine a first distance traveled to the first location along the path; and

generate an entry in the LOS catalog using an identification of the first map node, an identification of the second map node, and a distance based on the first distance traveled; and

identify the spawn point for a player based on the LOS catalog by determining a map node at which an unsafe game element is located and a minimum distance until LOS is achieved between the map node and the spawn point, wherein the spawn point is identified based on the minimum distance.

14. The system of claim 13, wherein the distance comprises the first distance.

15. The system of claim 13, wherein the one or more physical processors are further caused to:

traverse the path in at least a second direction, different than the first direction, from the second map node to the first map node;

identify a second location along the path at which LOS is achieved between the second location and the first map node;

determine a second distance traveled to the second location along the path; and

identify a smaller one of the first distance and the second distance, wherein the distance based on the first distance comprises the smaller one of the first distance and the second distance.

16. The system of claim 13, wherein the one or more physical processors are further caused to:

identify a third map node, not on the path, known to have LOS with the second location, wherein the third map node is also known to have a third distance to the second map node; and

identify a smaller one of the first distance and the third distance, wherein the distance based on the first distance comprises the smaller one of the first distance and the third distance.

17. The system of claim 13, wherein to traverse the path in at least the first direction, the one or more physical processors are further caused to:

traverse from the first map node to a non-node position that is between the first map node and the second map node or an intermediary map node that is between the first map node and the second map node, wherein the first location comprises the non-node position or the intermediary map node.

18. The system of claim 13, wherein to identify the first location along the path at which LOS is achieved, the one or more physical processors are further caused to:

issue a first LOS trace from the first location at a first height to the second map node;

issue a second LOS trace from the first location at a second height, different than the second height, to the second map node; and

determine whether or not LOS exists from the first location to the second node based on the first LOS trace or the second LOS trace, wherein the first location is identified responsive to a determination that LOS exists from the first location.

19. The system of claim 13, wherein to identify the path, the one or more physical processors are further caused to:

identify a shortest path between the first map node and the second map node.

20. The system of claim 13, wherein the plurality of map nodes comprises a fourth map node, and wherein the one or more physical processors are further caused to:

identify a second path between the first map node and the fourth map node;

traverse the second path in at least a third direction from the first map node to the fourth map node;

identify a second location along the path at which LOS is achieved between the second location and the fourth map node;

determine a second distance traveled to the second location along the second path; and

generate a second entry in the LOS catalog using the identification of the first map node, an identification of the fourth map node, and a third distance based on the second distance traveled.

21. The system of claim 20, wherein the plurality of map nodes comprises a fifth map node, and wherein the one or more physical processors are further caused to:

identify a third path between the fourth map node and the fifth map node;

traverse the third path in at least a fourth direction from the fourth map node to the fifth map node;

identify a third location along the path at which LOS is achieved between the fourth location and the fifth map node;

determine a third distance traveled to the third location along the third path; and

generate a third entry in the LOS catalog using the identification of the fourth map node, an identification of the fifth map node, and a fourth distance based on the third distance traveled.

22. The system of claim 13, wherein the entry in the LOS catalog is generated prior to initiation of a session of the video game, and wherein the one or more physical processors are further caused to:

obtain an indication that a player should be spawned during gameplay of the session of the video game; and

cause the player to be spawned at the spawn point during the session of the video game.

23. The system of claim 13, wherein the one or more physical processors are further caused to:

identify a second spawn point; and

determine a second minimum distance until LOS is achieved between the map node and the second spawn point, wherein the spawn point is identified based on a determination that the minimum distance is greater than the second minimum distance.

24. The system of claim 13, wherein the one or more physical processors are further caused to:

identify a third map node having LOS with the first map node;

obtain a minimum distance to achieve LOS between the third map node and the second map node;

determine that the minimum distance to achieve LOS between the third map node and the second map node is less than the distance;

obtain a second distance between the first map node and the third map node;

determine a sum of;

the second distance between the first map node and the third map node, and the minimum distance to achieve LOS between the third map node and the second map node;

determine that the sum is less than the distance; and

replace for the entry in the LOS catalog, the distance with the sum responsive to the determination that the sum is less than the distance.

25. A computer program product for determining distances required to travel to achieve line of site (“

LOS”

) between pairs of map nodes of a game map for a video game, of generating a LOS catalog based on the distances, and of generating a spawn point using the LOS catalog, the computer program product comprising;

one or more tangible, non-transitory computer-readable storage devices;

program instructions, stored on at least one of the one or more tangible, non-transitory computer-readable tangible storage devices that, when executed, cause a computer to;

obtain a plurality of map nodes of the game map, the plurality of map nodes comprising at least a first map node and a second map node;

identify a path between the first map node and the second map node;

traverse the path in at least a first direction from the first map node to the second map node;

identify a first location along the path at which LOS is achieved between the first location and the second map node;

determine a first distance traveled to the first location along the path; and

generate an entry in the LOS catalog using an identification of the first map node, an identification of the second map node, and a distance based on the first distance traveled; and

identify the spawn point for a player based on the LOS catalog by determining a map node at which an unsafe game element is located and a minimum distance until LOS is achieved between the map node and the spawn point, wherein the spawn point is identified based on the minimum distance.