Utilizing ray tracing for enhanced artificial intelligence path-finding

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.

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.

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.