Please download the dossier by clicking on the dossier button x
×

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
First Claim
Patent Images

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.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×