BEPUphysics

I am trying to make enemies in my game avoid obstacles on the terrain.
At the moment a ray cast is sent from the enemy position and direction and can detect any obstacles in front. And I can get the entity that is the obstacle.
What I want to do, is get the width of the entity perpendicular to the direction it was detected from. As in the ray will hit the obstacle at an angle, so I need the width of the obstacle perpendicular to this so that the enemy can move to just outside this point, to allow it to get around the obstacle.

How do you go about this in BEPU?

Typically, determining the precise relative dimensions of an object is unnecessary and too expensive for obstacle avoidance. An incremental correction to avoid the object is usually sufficient. This presentation from Valve touches on the high level idea, among other things: http://www.valvesoftware.com/publicatio ... _booth.pdf

The query is usually done using some kind of volume. You can use convex casts to trace volumes, but these are generally a little slower and slightly more difficult to use. Instead of using convex casts, you could use ray casts in multiple directions. With some minimum amount of temporal coherence, you could get away with using a single ray cast per update pointing in a different direction. That single ray cast cycles through a 'volume' such that in 3-10 frames the whole volume is tested. That way, you get more information about the environment in front of you for the same cost.

The incremental approach also has the advantage of being very general. You don't need to perform any logic specifically designed for a box obstacle versus a mesh obstacle; the ray casts will build up a picture of the environment over time that the creature can use.

So you are saying that:

-The enemy performs a ray cast to detect an obstacle in front of it's path. (It is currently moving towards a target position.)
-To move around it, it performs extra ray casts at a few different angles either side to try and detect the edges of the obstacle.
-And then moves in the direction where the ray doesn't hit the obstacle.

Is this what you were saying?

You say about only doing one ray cast per update? Surely that would mean it could take a while for the creature to move around an obstacle?

The total solution looks more like this:

-Compute the high-level path using A* on a navmesh or similar algorithms.
-The path tells the character how to move in the medium and long term. It can look ahead to a goal along the path and move towards it.
-Small objects, especially dynamic ones, may not be represented in the navmesh. We wouldn't want the character to get stuck if it happens across a trash can. In addition, a loose following of the path (as occurs in reactive path following for example) would require microadjustments to handle elements of the environment like walls smoothly. 'Obstacle avoidance' is these microadjustments.

Because obstacle avoidance is just adjusting the character's motion a bit, you don't need a whole lot of information about the obstacles. Knowing that 'an obstacle was detected in this direction, this distance away' is enough to force the AI to turn away from that direction or slow down to avoid impact. The normal of the impact can also be used to inform fancier responses.

So no, the rays aren't meant to find the edges of the obstacle. The ray casts simply tell the AI 'something was there, avoid it.' It turns a bit, performs more ray casts, sees that 'something is still there, avoid it' and so on until the obstacle is cleared. The character is constantly moving during this process, incrementally changing its motion to avoid the obstacle. A well-tuned end result would behave like a L4D zombie.

Note that it's possible to not use A* or other global path finders, but obstacle avoidance without a guiding path will look blind. It might run into a cove, spin around a bit wondering where to go, pop out, walk back in, then eventually go around the outside and so on. Obstacle avoidance can only see immediate obstacles, not the whole path.

I just serendipitously ran across this website during some unrelated searching that may help visualize the approach: http://www.red3d.com/cwr/steer/Obstacle.html

Edit- Even closer to what I was talking about: http://www.red3d.com/cwr/steer/Containment.html
It uses 'point probes' as opposed to ray casts, but the concept is basically the same.

There's a bunch of other behavior visualizations and resources on the parent site too: http://www.red3d.com/cwr/steer/

I have stumbled across that website before, which is where I got the steering behaviour idea from.

The other point to mention, is that I implemented A* path-finding for the enemies and I just found that it was so intensive that the whole game just crawled to a halt with XNA running the update method 60 times a second. And even with trying to make it run less often, I just couldn't get it to run correctly.

In the world of our game, it is simply littered with small obstacles, like trees and things, so it won't have walls or anything, or dead ends. Therefore, I deemed path-finding A* to be overkill in this situation.

However, enemy movement would be smoother and better if A* and obstacle avoidance combination was used. I just couldn't get it to run correct, it just slowed the whole game to a crawl, with it being too intensive to calculate path from enemy to the player every time it needed to move.

al9191 wrote:... it just slowed the whole game to a crawl, with it being too intensive to calculate path from enemy to the player every time it needed to move.

While I've got no experience of all this path-finding business, your last comment got me thinking of an analogy....

If you were planning a journey to an unknown destination... would you check the map and replan the route every time you moved? Could your AI not plan a few steps ahead, carry them out, plan a few more steps, carry those out... and so on?

Like I say... no experience of this stuff... but thought I might try throwing some ideas in there. Sorry if I'm stating the obvious or being plain daft.

In the world of our game, it is simply littered with small obstacles, like trees and things, so it won't have walls or anything, or dead ends.

If that's true, then the 'containment' based approach will work fine without a global path once the queries are tuned. It still might do something a little dumb sometimes, but it could still be perfectly acceptable.

If you were planning a journey to an unknown destination... would you check the map and replan the route every time you moved? Could your AI not plan a few steps ahead, carry them out, plan a few more steps, carry those out... and so on?

Like I say... no experience of this stuff... but thought I might try throwing some ideas in there. Sorry if I'm stating the obvious or being plain daft.

Yup, L4D does something a bit similar. It only needs to recompute paths if the current path is so off that regular ol' obstacle avoidance and climbing is deemed insufficient to reach the current path (though I'm just going by the presentation, I have no insider knowledge ). Actual path computation is expensive, but it isn't very common. I'd assume they also do some deferring of path computation, too- even if the calculations get too long, a zombie can get away with not having an optimal path for a few seconds occasionally.

Ok thanks very much.

For the containment based approach it says:
"When a probe point touches an obstacle, it is projected (indicated by a black line) to the nearest point on the surface of the obstacle (red dot) and the normal to the surface at that point is determined (red line). Steering is determined by taking the component of this surface normal which is perpendicular to the vehicle's forward direction. The vehicle's velocity is indicated by a magenta vector, and its steering force is indicated by a blue vector."

1) Is the projected point onto surface of obstacle what you can get from the ray cast result HitData object? And so the normal is found in that HitData object as well?

2) How do you get the component of the surface normal which is perpendicular to vehicle's forward direction? Is there anything built into BEPU to do this?

1) Is the projected point onto surface of obstacle what you can get from the ray cast result HitData object? And so the normal is found in that HitData object as well?

The ray cast returns the first impact location, the normal at that impact location, and the distance along the ray to the impact point in units of the ray direction's length (the T value).

The point probe and point-to-surface projection mechanism is a different form of query. The ray cast replaces it completely and is likely to be more robust in many cases.

2) How do you get the component of the surface normal which is perpendicular to vehicle's forward direction? Is there anything built into BEPU to do this?

To get the component of a normalized vector A which is perpendicular to another normalized vector B, you can use the dot product and subtraction. The component of A which is parallel to B is a projection from A onto B ((A dot B) * B). Subtract the parallel component from A. The resulting vector only includes the component of A which is perpendicular to B. There's nothing in BEPUphysics to handle this since it's all pretty direct geometry and linear algebra.

There's an informal and incomplete summary of some general geometry/math tricks in my second post of this thread: viewtopic.php?f=4&t=1442

Don't get too bogged down in the details of a specific implementation, though. The important idea is that 'there's an obstacle, steer away from it.' There are many valid ways of doing it.

Ah ok then.

I did have few ideas for different ways of steering away from the obstacle, some are more complicated than others, will try some different methods and see which is best.

Thanks very much for the help.

Just for clarification, when talking about path-finding, is it therefore common that a path-finding algorithm will be ran, and the enemy will use the graph as it is being computed, so an optimised version to begin with. (Rather than computing graph, and then using it.)?

Just for clarification, when talking about path-finding, is it therefore common that a path-finding algorithm will be ran, and the enemy will use the graph as it is being computed, so an optimised version to begin with. (Rather than computing graph, and then using it.)?

I don't know how common it is to use a partially computed path, specifically. If I had to guess, I'd say the more common approach is computing the whole path using traditional A* or something similar while using some interim behaviors when an optimal path isn't currently available.

Relying entirely on obstacle avoidance completely for a couple of seconds while the path generator gets around to computing the optimal path would probably work fine in most cases. Some kind of partial computation could be used to fill these gaps too.