Help with my AI path searching algorithm

[Aelis440]

So here is the code for my function:

Code: Select all

void NPC::searchPath(vector3df currentPos, s32 distance, int treeDepth, vector<line3d<f32>> pathPositions)
{
	// We got to 0, so we're done searching in this part of our tree.
	if (treeDepth == 0)
		return;
	// Else, recursion!
	else
	{
		// For all angles (at the given interval of pathingAngleInterval, which is 20) around our current position.
		// Note that the size of pathing angles should be 18 since 20 * 18 = 360.
		for (int i = 0; i < pathingAngles.size(); i++)
		{
			// First we will find our new position based on the given distance at this ith angle.
			vector3df tempPos;
			tempPos.X = currentPos.X + (distance * sin( pathingAngles[i] * DEGTORAD));
			tempPos.Z = currentPos.Z + (distance * cos( pathingAngles[i] * DEGTORAD));
			// We do not have to worry about height for this search algorithm in our game, thank goodness!
			tempPos.Y = target[0]->getTop().Y;
	
			// Create a line from our current position to our newly created position.
			line3d<f32> someLine(currentPos, tempPos);
			vector3df collisionPoint;
			// If we didn't hit anything...
			if (!cmgr->getCollisionPoint(someLine, selector, collisionPoint, triangle3df()))
			{
				// Check to see if we can get to our target!
				line3d<f32> lineToTarget(tempPos, target[0]->getTop());
				vector3df collisionPoint2;

				// Add this line to our vector of paths.
				vector<line3d<f32>> newPathPositions = pathPositions;
				newPathPositions.push_back(someLine);

				// If we did get to our target successfully...
				if(!cmgr->getCollisionPoint(lineToTarget, selector, collisionPoint2, triangle3df()))
				{
					// Add this vector to our vector of paths.
					newPathPositions.push_back(lineToTarget);
					// Now we are going to find out how long this path is.
					int currentTotalDistance = 0;
					for (int i = 0; i < newPathPositions.size(); i++)
					{
						currentTotalDistance += newPathPositions[i].getLength();
					}
					// If it's shorter than our shortest...
					if ( currentTotalDistance < shortestPathingDistance)
					{
						// make this our new path and our new shortest distance.
						this->pathPositions = newPathPositions;
						shortestPathingDistance = currentTotalDistance;
					}
					// We could return true here if we wanted to just find a path, but
					// we want to find the best path, so we will keep searching.
					//return true;
				}
				// Else we hit something so keep searching for a new path
				else
				{
					s32 newDistance = tempPos.getDistanceFrom(collisionPoint2);// - 3;
					line3d<f32> line(tempPos, collisionPoint2);
					vector<line3d<f32>> newPathPositions = pathPositions;
					newPathPositions.push_back(line);
					searchPath(collisionPoint2, newDistance, treeDepth - 1, newPathPositions);
				}
			}
			// Else we hit something so keep searching for a new path.
			else
			{
				s32 newDistance = currentPos.getDistanceFrom(collisionPoint);// - 3;
				line3d<f32> line(currentPos, collisionPoint);
				vector<line3d<f32>> newPathPositions = pathPositions;
				newPathPositions.push_back(line);
				searchPath(collisionPoint, newDistance, treeDepth - 1, newPathPositions);
			}
		}
	return;
	}
}

It works great, but it kind of lags my game quite a bit (note, this is with an initial depth of 2, which is not that great to begin with). Is there any way to optimize this? I've done some tricks outside of this code to ensure that this is not getting called often, but I'm at the end with those tricks. So at this point, I just kind of need to make it better. Any tips would be greatly appreciated!

Lastly, if anyone wants to rewrite this to an A* algorithm, I would worship you like a God forever

[vitek]

The first thing that jumps out at me is that you are passing std::vector<core::line3df> by value to the function. You could avoid a bunch of unnecessary copies if you passed by const reference. You might get some gain by using a const reference for currentPos also.

Code: Select all

if (!cmgr->getCollisionPoint(someLine, selector, collisionPoint, triangle3df()))

I'm almost certain this is actually illegal. You shouldn't be able to pass a temporary triangle3df where a non-const reference to triangle3df is expected. You should declare a triangle3df outside the call and pass it in. It won't affect performance, but it is someting to keep in mind.

Code: Select all

vector<line3d<f32>> newPathPositions = pathPositions; 
newPathPositions.push_back(someLine);

You create several temporary vectors in your loop. If he loop does iterate 18 times for every level, you are creating 18 copies of the input vector for every level. Memory allocation is typically pretty expensive, and should be avoided if possible. If you declared the vector outside the loop and just assigned, you would avoid the memory allocation in many cases.

If you passed the input parameter by reference, you could push new path positions on to the vector, and pop them when you were done. This would avoid most of the memory allocations and the copies.

Code: Select all

currentTotalDistance += newPathPositions[i].getLength(); 

Instead of using getLength() you could use getLengthSQ(). This avoids a sqrt, which is computationally expensive. Even better, you could use std::vector<SEntry> where SEntry is defined like...

Code: Select all

struct SEntry
{
  core::line3df line;
  f32 length;
};

When you insert a new path, you would calculate the length then and insert that into the vector. Then you could avoid recalculating the length every time.

Since currentTotalDistance is the length of all of the lines in pathPositions plus the length of the new lines, you could precalculate the length of all of the existing lines in pathPositions when the function is called. Then you need to add the lengths of the new lines when you push them into the vector.

That should get you started. If you have trouble figuring out where to optimize, you should use a profiler. That is what they are for.

Travis

[vitek]

Also, the triangle selection stuff is going to be pretty expensive. Once you have the map built up, you should be able to precalculate most of this stuff.

Travis

[vitek]

I think this should work (provided you make the changes as mentioned above and in the code below)...

Code: Select all

void NPC::searchPath(const vector3df& currentPos, f32 distance, int depth, std::vector<SEntry>& pathPositions) 
{ 
   // you must ensure that pathPositions is a local. we don't want to modify it.
   // if you need to create a copy, then be sure to do that.
   // pathingAngles[i] should be in radians to avoid unnecessary multiplies 

   // We got to 0, so we're done searching in this part of our tree. 
   if (depth == 0) 
      return; 

   core::triangle3df collisionTri;
   core::vector3df collisionPoint;

   // For all angles (at the given interval of pathingAngleInterval, which is 20) around our current position. 
   // Note that the size of pathing angles should be 18 since 20 * 18 = 360. 
   for (int i = 0; i < pathingAngles.size(); i++) 
   { 
      // First we will find our new position based on the given distance at this ith angle. 
      core::vector3df tempPos; 

      // pathingAngles[i] should be in radians to avoid unnecessary multiplies
      tempPos.X = currentPos.X + (distance * sinf(pathingAngles[i])); 
      tempPos.Y = currentPos.Y;
      tempPos.Z = currentPos.Z + (distance * cosf(pathingAngles[i])); 
    
      // Create a line from our current position to our newly created position. 
      const core::line3d<f32> someLine(currentPos, tempPos); 

      // If we didn't hit anything... 
      if (!cmgr->getCollisionPoint(someLine, selector, collisionPoint, collisionTri)) 
      { 
         // Check to see if we can get to our target! 
         const core::line3d<f32> lineToTarget(tempPos, target[0]->getTop()); 

         // Add this line to our vector of paths. 
         SEntry entry;
         entry.line = someLine;
         entry.length = entry.line.getLength();

         pathPositions.push_back(entry); 

         // If we did get to our target successfully... 
         if(!cmgr->getCollisionPoint(lineToTarget, selector, collisionPoint, collisionTri)) 
         {
            SEntry entry;
            entry.line = lineToTarget;
            entry.length = entry.line.getLength();

            // Add this vector to our vector of paths. 
            pathPositions.push_back(entry); 

            // Now we are going to find out how long this path is. 
            f32 currentTotalDistance = 0.f; 
            for (u32 i = 0; i < pathPositions.size(); i++) 
            { 
               currentTotalDistance += pathPositions[i].length; 
            } 

            // If it's shorter than our shortest... 
            if (currentTotalDistance < shortestPathingDistance) 
            { 
               // make this our new path and our new shortest distance. 
               this->pathPositions = pathPositions; 
               shortestPathingDistance = currentTotalDistance; 
            }

            pathPositions.pop_back();

            // We could return true here if we wanted to just find a path, but 
            // we want to find the best path, so we will keep searching. 
            //return true; 
         }

         // Else we hit something so keep searching for a new path 
         else 
         {
            SEntry entry;
            entry.line.set(tempPos, collisionPoint);
            entry.length = entry.line.getLength();

            pathPositions.push_back(entry);

            searchPath (collisionPoint, entry.length, depth - 1, pathPositions); 

            pathPositions.pop_back();
         }

         pathPositions.pop_back();
      } 
      // Else we hit something so keep searching for a new path. 
      else 
      {
         SEntry entry;
         entry.line.set (currentPos, collisionPoint);
         entry.length = entry.line.getLength();

         pathPositions.push_back(entry);

         searchPath (collisionPoint, entry.length, depth - 1, pathPositions); 

         pathPositions.pop_back();
      } 
  } 
}

[Aelis440]

Thanks a bunch!!! I will try all of this when I get home.

One quick question though, can you explain this further, I don't quite understand what you mean:

Also, the triangle selection stuff is going to be pretty expensive. Once you have the map built up, you should be able to precalculate most of this stuff.

Are you suggesting to keep a version of my map (or anything I want my AI to search against) which is extremely low poly and implement it as a triangle selector so I can keep the triangle count low? I'm assuming this would make the ray tests faster. Also, what do you mean by precalculate, what exactly would I precalculate?

Thanks again!!!

[vitek]

You could generate data to represent the movements that are allowed from the different areas on the map. You could precalculate all of this offline and generate a data file that stores all of the transitions. Once you have that, you just load the data file. This avoids all of the triangle intersection stuff, but it only works if you can generate the data file before the map is actually used.

Travis

[Aelis440]

Ah, makes sense, thanks a ton!