Methods and apparatus for analyzing a game situation using positional information in a game space

• US 7,588,493 B2
• Filed: 10/22/2002
• Issued: 09/15/2009
• Est. Priority Date: 10/26/2001
• Status: Active Grant

• Current Assignee: Electronic Arts Incorporated
• Original Assignee: Electronic Arts Incorporated
• Inventors: Harrower, Geoffrey, Rupert, Jason
• Primary Examiner(s): Vo; Peter DungBa
• Assistant Examiner(s): Yoo; Jasson H
• Application Number:
  US10/491,585
• Publication Number:
  US 20050037826A1
• Time in Patent Office: 2,520 Days
• Field of Search: 463 1- 5, 463 30- 34, 345419-420, 345423-424, 345/427, 345441-443
• US Class Current: 463/4
• CPC Class Codes: A63F 13/422 automatically for the purpose of assisting the player, e.g. automatic braking in a driving game
• CPC Class Codes: A63F 13/5375 for graphically or textually suggesting an action, e.g. by displaying an arrow indicating a turn in a driving game
• CPC Class Codes: A63F 13/56 Computing the motion of game characters with respect to other game characters, game objects or elements of the game scene, e.g. for simulating the behaviour of a group of virtual soldiers or for path finding
• CPC Class Codes: A63F 13/577 using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars
• CPC Class Codes: A63F 13/812 Ball games, e.g. soccer or baseball
• CPC Class Codes: A63F 13/822 Strategy games; Role-playing games A63F13/825, A63F13/828 take precedence
• CPC Class Codes: A63F 13/847 Cooperative playing, e.g. requiring coordinated actions from several players to achieve a common goal
• CPC Class Codes: A63F 2300/305 for providing a graphical or textual hint to the player
• CPC Class Codes: A63F 2300/6054 by generating automatically game commands to assist the player, e.g. automatic braking in a driving game
• CPC Class Codes: A63F 2300/64 for computing dynamical parameters of game objects, e.g. motion determination or computation of frictional forces for a virtual car
• CPC Class Codes: A63F 2300/646 for calculating the trajectory of an object
• CPC Class Codes: A63F 2300/6607 for animating game characters, e.g. skeleton kinematics
• CPC Class Codes: A63F 2300/6623 for animating a group of characters
• CPC Class Codes: A63F 2300/8011 Ball
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2207/30221 Sports video; Sports image
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51

Abstract

In a computer game, a game situation is analyzed using states of a plurality of game elements by determining a state for each of the plurality of game elements (10), generating a representation of a Voronoi diagram among the game elements using at least some of the game elements (10) as Voronoi sites and performing an analysis of the game situation using the Voronoi diagram (16). The analysis can be spatial analysis and/or tactical analysis to determine a move of a computer controlled entity based on the tactical analysis. The game space might represent playing spaces for soccer, baseball or basketball. The state of a game element might include momentum, speed, and direction of travel (14), velocity and/or team association of the game element. For a soccer game analysis, multiple Voronoi diagrams might be generated and the analyses done using the multiple Voronoi diagrams.

Claims

1. A method performed by a gaming device of analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, the method comprising:

dividing the game space, using the gaming device, into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

determining, with the gaming device, a state for each of the plurality of game elements, wherein the state of each game element includes at least the game element'"'"'s position in the representation of the game space formed by the plurality of cells;

selecting, with the gaming devices a position in a cell in the plurality of cells, the selected position not including a position of any game elements;

performing, with the gaming device, an analysis of the game situation based on the representation of the game space using a first game element'"'"'s position in the representation of the game space in relation to the selected position in the cell; and

performing an action, with the gaming device, that changes state of at least one game element in the plurality of game elements using the analysis of the game situation.

2. The method of claim 1, wherein performing the analysis comprises determining with the gaming device a future position for the first game element in the cell.

3. The method of claim 2, further comprising causing the first game element to move to the future position with the gaming device.

4. The method of claim 2, wherein the first game element comprises a computer controlled entity.

5. The method of claim 2, wherein the first game element comprises a game element that does not possess an object in the game situation.

6. The method of claim 5, wherein the first game element is on a same team as a second game element that possesses the object in the game situation.

7. The method of claim 6, wherein the second game element that possesses the object comprises a passer and the first game element comprises a receiver, wherein performing the analysis comprises determining with the gaming device an action to pass the object from the passer to the receiver at the future position.

8. The method of claim 6, wherein the second game element that possesses the object comprises a human controlled entity.

9. The method of claim 2, wherein the state of each game element comprises at least one of a momentum of the game element, a speed of the game element, the game element'"'"'s direction of travel, and the game element'"'"'s velocity.

10. The method of claim 9, wherein performing the analysis comprises using at least one of the momentum of the first game element, the speed of the first game element, the first game element'"'"'s direction of travel, and the first game element'"'"'s velocity to determine the future position with the gaming device.

11. The method of claim 1, wherein selecting the position in the cell comprises selecting the position in a cell that does not include a game element in the plurality of game elements.

12. The method of claim 1, wherein the first game element'"'"'s position is a position closest to a second game element that possesses an object in the game situation, wherein performing the analysis comprises determining with the gaming device that the first game element is in the position closest to the second game element that possesses the object in the game situation.

13. The method of claim 1, wherein the plurality of game elements comprise soccer players and the game space represents a soccer field.

14. The method of claim 1, wherein the plurality of game elements comprise baseball players and the game space represents a baseball field.

15. The method of claim 1, wherein the plurality of game elements comprise basketball players and the game space represents a basketball court.

16. A method performed by a gaming device of analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, each of the plurality of game elements being associated with a team in a plurality of teams, the method comprising:

dividing the game space, using the gaming device, into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

determining, with the gaming device, a first game element in the plurality of game elements that possesses an object in the game space;

determining, with the gaming device, a second game element in the plurality of game elements on a same team as the first game element;

determining a state of the second game element, with the gaming device, wherein the state of the second game element includes at least the second game element'"'"'s position in a cell in the plurality of cells;

performing, with the gaming device, an analysis of the game situation based on the representation of the game space using the position of the second game element in the cell; and

performing an action, with the gaming device, that changes state of at least one game element in the plurality of game elements using the analysis of the game situation.

17. The method of claim 16, wherein the second game element'"'"'s position comprises a position closest to the first game element based on position'"'"'s of all game elements associated with the same team.

18. The method of claim 16, wherein the first player comprises a human-controlled player and the second player comprises a computer-controlled player.

19. The method of claim 16, wherein performing the analysis comprises determining with the gaming device an action for the second game element.

20. The method of claim 19, wherein determining the action comprises determining with the gaming device a future position for the second game element in the game space.

21. The method of claim 20, further comprising causing the second game element to move to the future position with the gaming device.

22. The method of claim 20, wherein the future position does not include a game element in the plurality of game elements.

23. The method of claim 20, wherein the state of the second game element comprises at least one of a momentum of the second game element, a speed of the second game element, the second game element'"'"'s direction of travel, and the second game element'"'"'s velocity.

24. The method of claim 23, wherein performing the analysis comprises using at least one of the momentum of the second game element, the speed of the second game element, the second game element'"'"'s direction of travel, and the second game element'"'"'s velocity to determine the future position with the gaming device.

25. The method of claim 16, wherein the first game element comprises a passer and the second game element comprises a receiver, wherein performing the analysis comprising determining with the gaming device an action to pass the object from the passer to the receiver at the future position.

26. The method of claim 16, wherein the plurality of game elements comprise soccer players and the game space represents a soccer field.

27. The method of claim 16, wherein the plurality of game elements comprise baseball players and the game space represents a baseball field.

28. The method of claim 16, wherein the plurality of game elements comprise basketball players and the game space represents a basketball court.

29. A method performed by a gaming device of analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, each of the plurality of game elements being associated with a team in a plurality of teams, the method comprising:

dividing the game space, with the gaming device, into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

selecting, with the gaming device, a position in a cell of the plurality of cells, the selected position not including a position of any game elements;

determining a state of a first game element, with the gaming device, wherein the state of the first game element includes at least the first game element'"'"'s position in the representation of the game space;

determining, with the gaming device, that the first game element should be moved to the position not including any game elements based on an analysis of the game situation using the representation of the game space and the first game element'"'"'s position; and

performing an action based on the determination that the first game element should be moved to the position not including any game elements.

30. The method of claim 29, further comprising determining a second game element with the gaming device, the second game element possessing an object in the game situation.

31. The method of claim 30, further comprising causing the first game element to move to the position not including any game elements with the gaming device in response to the action.

32. The method of claim 30, wherein the first game element comprises a computer controlled entity and the second game element comprises a human controlled entity.

33. The method of claim 30, wherein the first game element and the second game element comprise computer controlled entities.

34. An apparatus for analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, the apparatus comprising:

a processor; and

a memory coupled to the processor and configured to store processor-executable logic comprising;

logic configured to divide the game space, into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

logic configured to determine a state for each of the plurality of game elements, wherein the state of each game element includes at least the game element'"'"'s position in the plurality of cells;

logic configured to select a position in a cell in the plurality of cells, the selected position not including a position of any game elements;

logic configured to perform an analysis of the game situation based on the representation of the game space using a first game element'"'"'s position in the representation of the game space in relation to the selected position in the cell; and

logic configured to perform an action that changes state of at least one game element in the plurality of game elements using the analysis of the game situation.

35. The apparatus of claim 34, wherein the logic configured to perform the analysis comprises logic configured to determining a future position for the first game element in the cell.

36. The apparatus of claim 35, further comprising logic configured to cause the first game element to move to the future position.

37. The apparatus of claim 35, wherein the first game element comprises a computer controlled entity.

38. The apparatus of claim 35, wherein the first game element comprises a game element that does not possess an object in the game situation.

39. The apparatus of claim 38, wherein the first game element is on a same team as a second game element that possesses the object in the game situation.

40. The apparatus of claim 39, wherein the second game element that possesses the object comprises a passer and the first game element comprises a receiver, wherein the logic configured to perform the analysis comprises logic configured to determine an action to pass the object from the passer to the receiver at the future position.

41. The apparatus of claim 39, wherein the second game element that possesses the object comprises a human controlled entity.

42. The apparatus of claim 35, wherein the state of each game element comprises at least one of a momentum of the game element, a speed of the game element, the game element'"'"'s direction of travel, and the game element'"'"'s velocity.

43. The apparatus of claim 42, wherein the logic configured to perform the analysis comprises logic configured to use at least one of the momentum of the first game element, the speed of the first game element, the first game element'"'"'s direction of travel, and the first game element'"'"'s velocity to determine the future position.

44. The apparatus of claim 34, wherein the logic configured to select the position in a cell comprises logic configured to select a cell that does not include a game element in the plurality of game elements.

45. The apparatus of claim 34, wherein the first game element'"'"'s position comprises a position closest to a second game element that possesses an object in the game situation, wherein the logic configured to perform the analysis comprises logic configured to determine that the first game element is in the position closest to the second game element that possesses the object in the game situation.

46. The apparatus of claim 34, wherein the plurality of game elements comprise soccer players and the game space represents a soccer field.

47. The apparatus of claim 34, wherein the plurality of game elements comprise baseball players and the game space represents a baseball field.

48. The apparatus of claim 34, wherein the plurality of game elements comprise basketball players and the game space represents a basketball court.

49. An apparatus for analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, each of the plurality of game elements being associated with a team in a plurality of teams, the apparatus comprising:

a processor; and

a memory coupled to the processor and configured to store processor-executable logic comprising;

logic configured to divide the game space, into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

logic configured to determine a first game element in the plurality of game elements that possesses an object in the game space;

logic configured to determine a second game element in the plurality of game elements on a same team as the first game element;

logic configured to determine a state of the second game element, wherein the state of the second game element includes at least the second game element'"'"'s position in a cell in the plurality of cells;

logic configured to perform an analysis of the game situation based on the representation of the game space using the position of the second game element; and

logic configured to perform an action that changes state of at least one game element in the plurality of game elements using the analysis of the game situation.

50. The apparatus of claim 49, wherein the second game element'"'"'s position comprises a position closest to the first game element based on position'"'"'s of all game elements associated with the same team.

51. The apparatus of claim 49, wherein the first player comprises a human-controlled player and the second player comprises a computer-controlled player.

52. The apparatus of claim 49, wherein the logic configured to perform the analysis comprises logic configured to determine an action for the second game element.

53. The apparatus of claim 52, wherein the logic configured to determine the action comprises logic configured to determine a future position for the second game element in the game space.

54. The apparatus of claim 53, further comprising logic configured to cause the second game element to move to the future position.

55. The apparatus of claim 53, wherein the future position does not include a game element in the plurality of game elements.

56. The apparatus of claim 53, wherein the state of the second game element comprises at least one of a momentum of the second game element, a speed of the second game element, the second game element'"'"'s direction of travel, and the second game element'"'"'s velocity.

57. The apparatus of claim 56, wherein the logic configured to perform the analysis comprises logic configured to use at least one of the momentum of the second game element, the speed of the second game element, the second game element'"'"'s direction of travel, and the second game element'"'"'s velocity to determine the future position.

58. The apparatus of claim 49, wherein the first game element comprises a passer and the second game element comprises a receiver, wherein the logic configured to perform the analysis comprises logic configured to determine an action to pass the object from the passer to the receiver at the future position.

59. The apparatus of claim 49, wherein the plurality of game elements comprise soccer players and the game space represents a soccer field.

60. The apparatus of claim 49, wherein the plurality of game elements comprise baseball players and the game space represents a baseball field.

61. The apparatus of claim 49, wherein the plurality of game elements comprise basketball players and the game space represents a basketball court.

62. An apparatus for analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, each of the plurality of game elements being associated with a team in a plurality of teams, the apparatus comprising:

a processor; and

a memory coupled to the processor and configured to store processor-executable logic comprising;

logic configured to divide the game space into a plurality of cells having boundaries such that game elements are positioned in cells in the plurality of cells and each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

logic configured to select a position in a cell of the plurality of cells, the selected position not including a position of any game elements;

logic configured to determine a state of a first game element, wherein the state of the first game element includes at least the first game element'"'"'s position in the representation of the game space;

logic configured to determine that the first game element should be moved to the position not including any game elements based on an analysis of the representation of the game space and the first game element'"'"'s position; and

logic configured to perform an action based on the determination that the first game element should be moved to the position not including any game elements.

63. The apparatus of claim 62, further comprising logic configured to determine a second game element, the second game element possessing an object in the game situation.

64. The apparatus of claim 63, further comprising logic configured to cause the first game element to move to the position not including any game elements in response to the action.

65. The apparatus of claim 62, wherein the first game element comprises a computer controlled entity and the second game element comprises a human controlled entity.

66. The apparatus of claim 62, wherein the first game element and the second game element comprise computer controlled entities.

67. A computer program product stored on a computer-readable storage medium for analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, the computer program product comprising:

code for dividing the game space into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

code for determining a state for each of the plurality of game elements wherein the state of each game element associated with the computer game includes at least the game element'"'"'s position in the plurality of cells;

code for selecting a position in a cell in the plurality of cells, the selected position not including a position of any game elements;

code for performing an analysis of the game situation based on the representation of the game space using a first game element'"'"'s position in the representation of the game space in relation to the selected position in the cell; and

code for performing an action that changes state of at least one game element in the plurality of game elements using the analysis of the game situation.

68. The computer program product of claim 67, wherein the code for performing the analysis comprises code for determining a future position for the first game element in the cell.

69. The computer program product of claim 68, further comprising code for causing the first game element to move to the future position.

70. The computer program product of claim 68, wherein the first game element comprises a computer controlled entity.

71. The computer program product of claim 68, wherein the first game element comprises a game element that does not possess an object in the game situation.

72. The computer program product of claim 71, wherein the first game element is on a same team as a second game element that possesses the object in the game situation.

73. The computer program product of claim 72, wherein the second game element that possesses the object comprises a passer and the first game element comprises a receiver, wherein the code for performing the analysis comprises code for determining an action to pass the object from the passer to the receiver at the future position.

74. The computer program product of claim 72, wherein the second game element that possesses the object comprises a human controlled entity.

75. The computer program product of claim 68, wherein the state of each game element comprises at least one of a momentum of the game element, a speed of the game element, the game element'"'"'s direction of travel, and the game element'"'"'s velocity.

76. The computer program product of claim 75, wherein the code for performing the analysis comprises using at least one of the momentum of the first game element, the speed of the first game element, the first game element'"'"'s direction of travel, and the first game element'"'"'s velocity to determine the future position.

77. The computer program product of claim 67, wherein the code for selecting the position in the cell comprises code for selecting a cell that does not include a game element in the plurality of game elements.

78. The computer program product of claim 67, wherein the first game element'"'"'s position comprises a position closest to a second game element that possesses an object in the game situation, wherein the code for performing the analysis comprises code for determining that the game element is in the position closest to the game element that possesses the object in the game situation.

79. The computer program product of claim 67, wherein the plurality of game elements comprise soccer players and the game space represents a soccer field.

80. The computer program product of claim 67, wherein the plurality of game elements comprise baseball players and the game space represents a baseball field.

81. The computer program product of claim 67, wherein the plurality of game elements comprise basketball players and the game space represents a basketball court.

82. A computer program product stored on a computer-readable storage medium for analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, each of a plurality of game elements being associated with a team in a plurality of teams, the computer program product comprising:

code for dividing the game space into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells;

code for determining a first game element in the plurality of game elements that possesses an object in the game space;

code for determining a second game element in the plurality of game elements on a same team as the first game element;

code for determining a state of the second game element, wherein the state of the second game element includes at least the second game element'"'"'s position in a cell in the plurality of cells;

code for performing an analysis of the game situation based on the representation of the game space using the position of the second game element; and

code for performing an action that changes state of at least one game element in the plurality of game elements using the analysis of the game situation.

83. The computer program product of claim 82, wherein the second game element'"'"'s position comprises a position closest to the first game element based on position'"'"'s of all game elements associated with the same team.

84. The computer program product of claim 82, wherein the first player comprises a human-controlled player and the second player comprises a computer-controlled player.

85. The computer program product of claim 82, wherein the code for performing the analysis comprises code for determining an action for the second game element.

86. The computer program product of claim 85, wherein the code for determining the action comprises code for determining a future position for the second game element in the game space.

87. The computer program product of claim 86, further comprising code for causing the second game element to move to the future position.

88. The computer program product of claim 86, wherein the future position does not include a game element in the plurality of game elements.

89. The computer program product of claim 86, wherein the state of the second game element comprises at least one of a momentum of the second game element, a speed of the second game element, the second game element'"'"'s direction of travel, and the second game element'"'"'s velocity.

90. The computer program product of claim 89, wherein the code for performing the analysis comprises code for using at least one of the momentum of the second game element, the speed of the second game element, the second game element'"'"'s direction of travel, and the second game element'"'"'s velocity to determine the future position.

91. The computer program product of claim 82, wherein the first game element comprises a passer and the second game element comprises a receiver, wherein the code for performing the analysis comprising code for determining an action to pass the object from the passer to the receiver at the future position.

92. The computer program product of claim 82, wherein the plurality of game elements comprise soccer players and the game space represents a soccer field.

93. The computer program product of claim 82, wherein the plurality of game elements comprise baseball players and the game space represents a baseball field.

94. The computer program product of claim 82, wherein the plurality of game elements comprise basketball players and the game space represents a basketball court.

95. A computer program product stored on a computer-readable storage medium for analyzing a game situation of a computer game, wherein the gaming device manages a representation of a game space and a plurality of game elements each having a position within the game space, each of a plurality of game elements being associated with a team in a plurality of teams, the computer program product comprising:

code for dividing the game space into a plurality of cells having boundaries such that each cell is associated with a game element of the plurality of game elements and the boundary of each cell is such that points within that cell are closer to the position of the game element associated with that cell than the points are to the positions of game elements associated with other cells of the plurality of cells, wherein the plurality of game elements are positioned in cells in the plurality of cells;

code for selecting a position in a cell of the plurality of cells, the selected position not including a position of any game elements;

code for determining a state of a first game element, wherein the state of the first game element includes at least the first game element'"'"'s position in the representation of the game space;

code for determining that the first game element should be moved to the position not including any game elements based on an analysis of the game situation using the representation of the game space and the first game element'"'"'s position; and

code for performing an action based on the determination that the first game element should be moved to the position not including any game elements.

96. The computer program product of claim 95, further comprising code for determining a second game element, the second game element possessing an object in the game situation.

97. The computer program product of claim 96, further comprising code for causing the first game element to move to the position not including any game elements.

98. The computer program product of claim 96, wherein the first game element comprises a computer controlled entity and the second game element comprises a human controlled entity.

99. The computer program product of claim 96, wherein the first game element and the second game element comprise computer controlled entities.