AI flee path finding problems

Problems building or running the engine, queries about how to use features etc.
Post Reply
shenjoku
Gremlin
Posts: 193
Joined: Sat Aug 06, 2011 11:02 pm
x 6

AI flee path finding problems

Post by shenjoku »

I hope this is the right forum to put this in. I'm really not sure where this should go since it's not really Ogre specific...

I'm working on fixing the flee AI that I wrote a long time ago so that it is a bit smarter at avoiding enemies but I'm a bit stuck. What I'm trying to do is something like the following:
1. Look at the position of all of the attackers of the AI and generate an orientation vector to each one.
2. From these orientation vectors, calculate a new "escape vector" that optimally avoids all of the enemies as best as possible.

I have an idea of how to potentially make this work but I'm unsure of how to correctly calculate everything. Let me give an example taken directly from what I have so far. This picture shows the vectors from the target to all of the enemies that are attacking it (white lines), which are being rendered in real time by Ogre, and I've drawn in a sample vector that should be calculated to avoid everyone (red line).
flee_avoid.png
flee_avoid.png (54.01 KiB) Viewed 768 times
it's important to note that I'm not 100% sure that the line I drew is the correct escape vector for this example. Since there are two large areas that are fairly close in size there could potentially be multiple solutions, so keep that in mind. But for now, let's just assume the red line I drew is the one solution for this example to simplify things.

The current idea I have of calculating this escape vector is by doing something like the following:
1. Get the angle between every possible combination of the vectors, essentially splitting up a circle into wedges that are defined by the vectors to the enemies.
2. Compare the wedges and find the one with the largest angle. This is where the multiple solutions would come in. If there are multiple wedges very close in size then it would probably have to randomly pick one.
3. Calculate a vector that bisects the selected wedge, which will be the escape vector pictured in red.

So if we redraw the original example to show a circle you can more clearly see all of the wedges that are created by the various vectors:
flee_circle.png
flee_circle.png (52.77 KiB) Viewed 768 times
How would I go about doing something like this? I'm unsure of how to split up the circle. Would you use the dot product of the vectors or something? That's what I'm currently trying to do but I'm not sure what to do with the results.

Here's a code example to show you what I have so far. This loop gets the dot product of every possible combination of the vectors available.

Code: Select all


// This container gets populated elsewhere. It contains the normalized orientation vectors from the target to each enemy attacking it
// (all of the white lines in the sample pictures). It's important to note that they are not sorted in any particular order, but they could easily
// be if that makes some part of the algorithm easier.
std::vector<Ogre::Vector2> enemyOrientationVectors;

for (std::vector<Ogre::Vector2>::const_iterator iter(enemyOrientationVectors.cbegin()), backIter(--enemyOrientationVectors.cend()); iter != backIter; ++iter)
{
	for (std::vector<Ogre::Vector2>::const_iterator nextIter(iter + 1), endIter(enemyOrientationVectors.cend()); nextIter != endIter; ++nextIter)
	{
		const Ogre::Real dotProduct(iter->dotProduct(*nextIter));

		// Some debug output to see the dot product and angle of each combination.
		gDOS <<  "dot of " << iter - enemyOrientationVectors.cbegin() << " and " << nextIter - enemyOrientationVectors.cbegin() << ": " << dotProduct << " Angle: " << Ogre::Radian(acos(dotProduct)).valueDegrees() << "\n";

		// TODO: Do something with the dot product to figure out which combination of vectors generates the best results, or maybe calculate something else? Not sure...
	}
}
Some sample output from this loop looks like this:

Code: Select all

Targeter angles: 167.005 156.801 153.435 -118.811 135 147.995 -146.31 155.376 -18.4349 
dot of 0 and 1: 0.984183 Angle: 10.204
dot of 0 and 2: 0.972082 Angle: 13.5704
dot of 0 and 3: 0.272552 Angle: 74.1838
dot of 0 and 4: 0.847998 Angle: 32.0054
dot of 0 and 5: 0.945457 Angle: 19.0108
dot of 0 and 6: 0.686013 Angle: 46.6847
dot of 0 and 7: 0.979474 Angle: 11.6289
dot of 0 and 8: -0.995495 Angle: 174.56
dot of 1 and 2: 0.998274 Angle: 3.36645
dot of 1 and 3: 0.0977948 Angle: 84.3878
dot of 1 and 4: 0.928477 Angle: 21.8014
dot of 1 and 5: 0.98821 Angle: 8.80678
dot of 1 and 6: 0.546268 Angle: 56.8887
dot of 1 and 7: 0.999691 Angle: 1.42491
dot of 1 and 8: -0.996546 Angle: 175.236
dot of 2 and 3: 0.0391856 Angle: 87.7542
dot of 2 and 4: 0.948683 Angle: 18.4349
dot of 2 and 5: 0.995495 Angle: 5.44032
dot of 2 and 6: 0.496139 Angle: 60.2551
dot of 2 and 7: 0.999426 Angle: 1.94149
dot of 2 and 8: -0.989949 Angle: 171.87
dot of 3 and 4: -0.27881 Angle: 106.189
dot of 3 and 5: -0.0557272 Angle: 93.1946
dot of 3 and 6: 0.887018 Angle: 27.4991
dot of 3 and 7: 0.0730159 Angle: 85.8128
dot of 3 and 8: -0.180104 Angle: 100.376
dot of 4 and 5: 0.974391 Angle: 12.9946
dot of 4 and 6: 0.196116 Angle: 78.6901
dot of 4 and 7: 0.937425 Angle: 20.3764
dot of 4 and 8: -0.894427 Angle: 153.435
dot of 5 and 6: 0.411587 Angle: 65.6954
dot of 5 and 7: 0.991712 Angle: 7.3818
dot of 5 and 8: -0.972082 Angle: 166.43
dot of 6 and 7: 0.525269 Angle: 58.3136
dot of 6 and 8: -0.613941 Angle: 127.875
dot of 7 and 8: -0.994172 Angle: 173.811
Does this approach make sense? Is there a better way to do this that would be easier/faster? I'm open to any suggestions that aren't overly complicated. I'm trying to keep this simple unless it really turns out to be necessary to get more complicated.
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7157
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 534

Re: AI flee path finding problems

Post by Kojack »

First solution off the top of my head:
- Do a loop through a small list of potential directions (maybe 8-16 points in a circle around you, that's probably enough).
- For each of these potential directions, calculate the danger rating (see below).
- Move towards the potential direction with the lowest danger.

The danger rating would be based on something like accumulated proximity (inverse distance) to the enemies.
You can also adjust the danger rating based on things like nearby collectibles (a weapon or armour pickup could make a riskier direction more desirable).
If the character has a limited turn speed, you could increase the danger rating of a direction based on it's angle from the character's current facing direction.
shenjoku
Gremlin
Posts: 193
Joined: Sat Aug 06, 2011 11:02 pm
x 6

Re: AI flee path finding problems

Post by shenjoku »

That's an interesting idea. When you mention checking points along a circle, what would determine the radius to use? Would you make it big enough to encompass all of the enemy positions or something? Or is it just some arbitrary size? I'm not sure what would make the most sense.

EDIT: After trying out your approach I noticed that if you run into a case like the screenshots in the OP where there is a big group behind the target and much fewer numbers directly ahead, opposite the large group, then it will run headlong into the small group since the danger rating is skewed by the distance gain of the larger group eclipsing the gain of the smaller group. I'm not entirely sure how to deal with this using just your danger rating suggestion so I've settled on a combination of the danger rating and my original "pick the biggest wedge" idea. I haven't combined them yet, since I just now finished getting both algorithms working and well optimized, so I'm not sure how it'll work out but it seems promising so we'll see :)
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7157
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 534

Re: AI flee path finding problems

Post by Kojack »

The circle size would be just a couple of steps worth, to see which direction would be the safest in the immediate future. It's like how in grid based A* path finding you look at the 8 squares around your current location to see which one has the lowest cost.

Instead of accumulated (so several bots on one side unbalances it), you could just record the maximum danger of any bot for each direction. That would be more likely to want to move to the gaps.
Post Reply