Utilizing ray tracing for enhanced artificial intelligence path-finding

• US 8,234,234 B2
• Filed: 03/20/2007
• Issued: 07/31/2012
• Est. Priority Date: 03/20/2007
• Status: Expired due to Fees

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Shearer, Robert Allen
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): RIFKIN, BEN M
• Application Number:
  US11/688,390
• Publication Number:
  US 20080231628A1
• Time in Patent Office: 1,960 Days
• Field of Search: 706/52
• US Class Current: 706/52
• CPC Class Codes: G06T 15/50 Lighting effects

Abstract

Embodiments of the invention provide methods and apparatus to use ray-tracing to perform artificial intelligence path-finding. Embodiments of the invention may cast a ray into a three-dimensional scene to determine a path from a starting point to an ending point. The ray may have a trajectory which originates at the starting point and proceeds towards the ending point. The artificial intelligence system may perform ray-tracing using a spatial index to determine if the ray intersects any objects within the three-dimensional scene. If the ray reaches the ending point without intersecting any objects, the path of the ray from the starting point to the ending point is the determined path. However, if the ray intersects an object, the artificial intelligence system may cast additional rays into the three-dimensional scene and perform ray tracing with the additional rays to determine a path from the start point to the end point.

Claims

1. A computer-implemented method of artificial intelligence path finding in a virtual environment, comprising:

determining, using ray tracing and for a character in the virtual environment, a path from a starting point to an ending point of a three-dimensional scene of the virtual environment, comprising, by operation of one or more computer processors;

issuing an initial ray into the three-dimensional scene of the virtual environment, wherein the initial ray originates at the starting point and has a trajectory directed towards the ending point;

determining if the initial ray intersects an object between the starting point and the ending point in the three-dimensional scene of the virtual environment by performing ray tracing;

upon determining that the initial ray does not intersect any objects within the three-dimensional scene of the virtual environment, setting the path from the starting point to the ending point for the character to include the trajectory of the initial ray; and

upon determining that the initial ray intersects an object within the three-dimensional scene of the virtual environment, issuing additional rays into the three-dimensional scene until a predetermined condition is satisfied, wherein the predetermined condition is satisfied upon determining that a ray is issued which does not intersect the object, wherein each additional ray originates at the starting point and has a trajectory different from the trajectory of any previously issued ray, wherein the additional rays are issued in an alternating manner from at least two sides of the initial ray, wherein each side of the initial ray is a distinct half-plane defined by the initial ray, wherein each additional ray issued from each side is farther from the initial ray than any additional ray previously issued from the respective side of the initial ray, as measured by an angle between the respective additional ray and the initial ray.

2. The method of claim 1, wherein at least two of the at least two sides of the initial ray are opposite to one another, and wherein the path from the starting point to the ending point is determined without generating any pathfinding grid dividing the three-dimensional scene.

3. The method of claim 2, wherein determining if the initial ray intersects any objects in the three-dimensional scene by performing ray-tracing comprises:

traversing the initial ray through a spatial index which partitions the three-dimensional scene by taking branches to nodes corresponding to bounding volumes intersected by the ray.

4. The method of claim 3, wherein the spatial index is pre-existing spatial index that is generated for at least one of image processing and physics simulation, and wherein the spatial index comprises at least one of a k-dimensional tree (kd-tree), a binary space partitioning (BSP) tree, and an octree.

5. The method of claim 4, wherein the nodes of the special index define bounding volumes which partition the three-dimensional scene, and wherein at least one node of the kd-tree defines a single splitting plane for splitting a bounding volume in the three-dimensional scene.

6. The method of claim 5, wherein the at least one node of the kd-tree comprises an internal node containing:

(i) information which indicates an axis along which the splitting plane is drawn;

(ii) information which indicates a position of the splitting plane along the axis; and

(iii) a pointer to a child node.

7. The method of claim 6, wherein the child node is selected from a second internal node and a leaf node, wherein the leaf node represents a bounding volume that is not further subdivided by any splitting plane defined by the kd-tree, wherein the leaf node comprises a pointer to at least one of the objects within the three-dimensional scene.

8. The method of claim 7, wherein the object obstructs movement of the character along the trajectory of the initial ray, and wherein the predetermined condition is also satisfied upon determining that the character is capable of performing a predefined action to overcome the object at a point at which the at least one additional ray intersects the object.

9. The method of claim 8, wherein issuing the additional rays into the three-dimensional scene further comprises:

once an additional ray is issued which does not intersect the object, determining a point past the object and issuing a new ray into the three-dimensional scene from the point past the object, wherein the new ray has a trajectory directed towards the ending point;

determining if the new ray intersects an object within the three-dimensional scene by performing ray tracing; and

upon determining that the new ray does not intersect an object within the three-dimensional scene, setting the path from the starting point to the ending point to include;

(i) a first segment from the starting point to the point past the object along a trajectory of the additional ray; and

(ii) a second segment from the point past the object to the ending point along a trajectory of the new ray.

10. The method of claim 9, wherein issuing the additional rays into the three-dimensional scene further comprises, upon determining that the initial ray intersects an object within the three-dimensional scene:

determining, from the property of the object and the capability of the character, whether the character is capable of performing a predefined action to overcome the object;

upon determining that the character is capable of performing the predefined action to overcome the object, issuing the additional ray into the three-dimensional scene, the additional ray having a starting point beyond the object and a trajectory directed towards the end point; and

upon determining that the character is not capable of performing any action necessary to overcome the object, issuing a new ray into the three-dimensional scene, the new ray having;

(i) a starting point within the trajectory of the initial ray but prior to intersecting the object and (ii) a trajectory not directed towards the end point.

11. A non-transitory computer readable storage medium containing a program which, when executed, performs operations comprising:

determining, using ray tracing and for a character in a virtual environment, a path from a starting point to an ending point of a three-dimensional scene of the virtual environment, comprising, by operation of one or more computer processors when executing the program;

issuing an initial ray into a three-dimensional scene of a virtual environment, wherein the initial ray originates at the starting point and has a trajectory directed towards the ending point;

determining if the initial ray intersects an object between the starting point and the ending point in the three-dimensional scene of the virtual environment by performing ray tracing;

upon determining that the initial ray does not intersect any objects within the three-dimensional scene of the virtual environment, setting a path from the starting point to the ending point for the character to include the trajectory of the initial ray; and

upon determining that the initial ray intersects an object within the three-dimensional scene of the virtual environment, issuing additional rays into the three-dimensional scene until a predetermined condition is satisfied, wherein the predetermined condition is satisfied upon determining that a ray is issued which does not intersect the object, wherein each additional ray originates at the starting point and has a trajectory different from the trajectory of any previously issued ray, wherein the additional rays are issued in an alternating manner from at least two sides of the initial ray, wherein each side of the initial ray is a distinct half-plane defined by the initial ray, wherein each additional ray issued from each side is farther from the initial ray than any additional ray previously issued from the respective side of the initial ray, as measured by an angle between the respective additional ray and the initial ray.

12. The non-transitory computer readable storage medium of claim 11, wherein determining if the initial ray intersects any objects in the three-dimensional scene by performing ray-tracing comprises:

traversing the initial ray through a spatial index which partitions the three-dimensional scene by taking branches to nodes corresponding to bounding volumes intersected by the ray.

13. The non-transitory computer readable storage medium of claim 11, wherein issuing the additional rays into the three-dimensional scene comprises:

if the initial ray intersects an object within the three-dimensional scene, issuing additional rays into the three-dimensional scene until a ray is issued which does not intersect the object, wherein each additional ray originates at the starting point and has a trajectory different from the trajectory of any previously issued ray; and

once an additional ray is issued which does not intersect the object, determining a point past the object, and issuing a new ray into the three-dimensional scene from the point past the object, wherein the new ray has a trajectory directed towards the ending point.

14. The non-transitory computer readable storage medium of claim 13, wherein issuing the additional rays into the three-dimensional scene further comprises:

determining if the new ray intersects an object within the three-dimensional scene by performing ray tracing; and

if the new ray does not intersect an object within the three-dimensional scene, setting the path from the starting point to the ending point to include;

(i) a first segment from the starting point to the point past the object along a trajectory of the additional ray; and

(ii) a second segment from the point past the object to the ending point along a trajectory of the new ray.

15. The non-transitory computer readable storage medium of claim 11, wherein issuing the additional rays into the three-dimensional scene comprises:

if the initial ray intersects an object within the three-dimensional scene, determining, from the property of the object and the capability of the character, whether the character is capable of performing a predefined action to overcome the object.

16. The non-transitory computer readable storage medium of claim 15, wherein the additional ray has a trajectory different from the trajectory of the initial ray, and wherein the additional ray is determined based on at least a capability of the character of performing one or more predefined actions necessary to overcome the object, wherein issuing the additional rays into the three-dimensional scene further comprises:

upon determining that the character is capable of performing the predefined action to overcome the object, issuing the additional ray into the three-dimensional scene, the additional ray having a starting point beyond the object and a trajectory directed towards the end point.

17. An artificial intelligence system, comprising:

a memory device containing a spatial index having nodes which correspond to bounding volumes which partition a three-dimensional scene of a virtual environment; and

a processing element configured to determine, for a character in the virtual environment, a path from a starting point to an ending point of a three-dimensional scene of the virtual environment by;

issuing an initial ray into a three-dimensional scene of the virtual environment, wherein the initial ray originates at the starting point and has a trajectory directed towards the ending point;

determining if the initial ray intersects an object between the starting point and the ending point in the three-dimensional scene of the virtual environment by performing ray tracing;

upon determining that the initial ray does not intersect any objects within the three-dimensional scene of the virtual environment, setting a path from the starting point to the ending point for the character to include the trajectory of the initial ray; and

upon determining that the initial ray intersects an object within the three-dimensional scene of the virtual environment, issuing additional rays into the three-dimensional scene until a predetermined condition is satisfied, wherein the predetermined condition is satisfied upon determining that a ray is issued which does not intersect the object, wherein each additional ray originates at the starting point and has a trajectory different from the trajectory of any previously issued ray, wherein the additional rays are issued in an alternating manner from at least two sides of the initial ray, wherein each side of the initial ray is a distinct half-plane defined by the initial ray, wherein each additional ray issued from each side is farther from the initial ray than any additional ray previously issued from the respective side of the initial ray, as measured by an angle between the respective additional ray and the initial ray.

18. The artificial intelligence system of claim 17, wherein the processing element performs ray-tracing by:

traversing the initial ray through a spatial index which partitions the three-dimensional scene by taking branches to nodes corresponding to bounding volumes intersected by the ray.

19. The artificial intelligence system of claim 17, wherein issuing the additional rays into the three-dimensional scene comprises:

issuing additional rays into the three-dimensional scene until a ray is issued which does not intersect the object, wherein each additional ray originates at the starting point and has a trajectory different from the trajectory of any previously issued ray; and

upon determining that an additional ray is issued which does not intersect the object, determining a point past the object and issuing a new ray into the three-dimensional scene from the point past the object, wherein the new ray has a trajectory directed towards the ending point.

20. The artificial intelligence system of claim 19, wherein issuing the additional rays into the three-dimensional scene further comprises:

determine if the new ray intersects an object within the three-dimensional scene by performing ray tracing; and

if the new ray does not intersect an object within the three-dimensional scene, set the path from the starting point to the ending point to include;

(i) a first segment from the starting point to the point past the object along a trajectory of the additional ray; and

(ii) a second segment from the point past the object to the ending point along a trajectory of the new ray.

21. The artificial intelligence system of claim 17, wherein the object obstructs movement of the character along the trajectory of the initial ray, wherein the additional ray has a trajectory different from the trajectory of the initial ray, and wherein the additional ray is determined based on at least a capability of the character of performing one or more predefined actions necessary to overcome the object, wherein issuing at least one additional ray into the three-dimensional scene comprises:

determining, from the property of the object and the capability of the character, whether the character is capable of performing a predefined action to overcome the object, and

if so, issuing an additional ray into the three-dimensional scene, the additional ray having a starting point beyond the object and a trajectory directed towards the end point.

22. A computer-implemented method of artificial intelligence path finding in a virtual environment, comprising:

generating a initial path box within a three-dimensional scene of the virtual environment, wherein the initial path box encompasses at least a portion of a character and a path to be traversed by the character within the three-dimensional scene of the virtual environment;

tracing the initial path box through a spatial index having nodes defining bounding volumes which partition the three-dimensional scene to determine if the initial path box intersects objects within the three-dimensional scene of the virtual environment; and

based on the results of tracing the initial path box through the spatial index, determining a path for the character to traverse from a starting point to an ending point within the three-dimensional scene of the virtual environment, comprising, by operation of one or more computer processors;

upon determining that the initial path box intersects an object within the three-dimensional scene of the virtual environment, tracing additional path boxes into the three-dimensional scene until a predetermined condition is satisfied, wherein the predetermined condition is satisfied upon determining that a path box is issued which does not intersect the object, wherein each additional path box originates at the starting point and has a trajectory different from the trajectory of any previously issued path box, wherein the additional path boxes are issued in an alternating manner from at least two sides of the initial path box, wherein each additional path box issued from each side is farther from the initial path box than any additional path box previously issued from the respective side of the initial path box, as measured by an angle between the respective additional path box and the initial path box.