How to do Basic Obstacle Avoidance

I need a way for a object to travel through 3D space from a start point and to an endpoint, while avoiding moving obstacles along the way.
An A* pathfinding algorithm would not work, because the movement needs to be fluid (not obviously grid-based) and using a grid that detailed would be prohibitively expensive. In addition, the obstacles are also moving, meaning that A* would search for paths each frame for each object (or every 30 frames, etc.), killing performance.
I was thinking of simply adding vectors to the object’s current linV based on their position relative obstacles. Unfortunately, I don’t know how to do this. (i’ve never taken physics.) Is this a valid approach, and if so, where can I go to learn about 3D vectors in particular?
(Many sites telling how to use 2D vectors, but I have no idea how to extrapolate that knowledge into the 3rd dimension.)

Pathfinding is good if you need to calculate a plan that you want to follow.
E.g. a list of waypoints.
It does not tell you how to reach each waypoint. It is just - a plan. The plan might be invalid over time. It might be just plain wrong because it is calculated from incorrect assumtions (map).
The plan can be recalculated any time.

You already have your two waypoints. So your plan is: I’m on Waypoint A - now travel to B.
What you need is a travel strategy.

This can be quite simple:

  • rotate to the waypoint
  • go forward
  • when you are near wayoint B your done.

To avoid obstacles:
Simplest way:
Let the physics do it for you. Just make your object dynamic and use forces or velocity. If the object hits a target it will slide along it always forcing toward the target.
Problem: The object can get stuck. Is it really a problem? This is up to you.

Partial solution:
add a collision mesh around the object that prefers to slide along an obstacle rather then getting stuck. Good shape is sphere.

Additional solutions:

  • Scan the space around the object. If there is an obstacle, try to move into the other direction (but still target the waypoint b)
  • Add random motion (always or when get stuck)
  • wait until the obstacle is gone
    etc.

Maybe this helps

You could look into theta* pathfinding. It’s very similar to A*, but paths are any-angle rather than a combination of the 8 main directions one after another. I’d seriously consider this over A* any day. The only drawback is it relies on line of sight to calculate the best paths so if there is a path to the destination through a minefield then the npcs will wander straight through it.
http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/

If you don’t want to recalculate the path every logic tick then you could always put a delay on it based on distance. For example, if your bot is far from the player then as the player moves about the path will not really change very much so the path can be recalculated every few seconds of so. Only when the bot is a second’s travel away from the player would the calculation need to be more often. Surely every logic tick would be overkill even for a bot that is right next to the player?

Between recalculations, the bot could maybe avoid objects by adding a tangent vector (or the negative of the vector to the obstruction) to the movement and then renormalising the movement vector so the bot doesn’t speed up. You don’t need to know math to use vectors other than simple addition, subtraction and multiplication really. Blender and BGE both have the mathutils module which includes a Vector class. LinV is given as a vector anyway, I think, and creating your own vector is a simple matter of vec = mathutils.Vector(1,0,0) for a vector of 1 on the x axis. Vectors can simply be added, multiplied, etc. To compute a precise angle then a bit of trig would be necessary.

http://www.euclideanspace.com/ is a great site if you really want to get to grips with the nitty gritty of under-the-hood programming.

Edit: Monster’s suggestions would be easier to implement, and work very well, but I just thought I’d share some more ideas. Theta* just blew me away when I first found it. I guess what I’m sugegsting is a hybrid pathfinding method with theta* for the basic pathfinding, but used sparingly, and object avoidance to correct the path when necessary. I’m not sure how difficult this would be.

A hybrid solotuion usually works best.
Try some tests to see if you can get various ideas to work and then try to mix them together as needed.

If you are making a comercial game with a high powered game engine (with graphics exceleration and all that) you could use A* or Theta* but for the simple games I think waypoints work well. They are easy to understand and work with litle overhead. You can even have moving waypoints…

There is no need to calculate the full path to the object, only find you local neighbouring waypoints (each waypoint can be programmed to do this on start up and then save them as a list to be accessed later- at this point they can ignore neighbours which are blocked by line of sight- freeing the AI characters from having to make the calcualtion later). Choose from that list the way point closest to your target and track to it. Add the waypoints you already moved through to an ignore list and your AI will eventually get to the target. If there are no near waypoints which are not on the ignore list, clear the list and start again.
It’s rare in small games that an AI character will need to move across the whole map to find the player so usually they will only be moving from room to room, or across a couple of city blocks.

A* is restricted to 8 directions?

A* runs on a node-graph as model. It does not even need to have a 2D or 3D representation.

I think what you mean is a special variant of the model. The node-graph is directly transformed out of a grid in 2D or 3D space. The most simple transformation of such grids look at the direct neighbours (90° or 45°) as descirbed in http://en.wikipedia.org/wiki/Any-angle_path_planning. The model does not know any other edges between the nodes.
Theta* and Field D* transform the model in a way that they calculate edges between nodes that are not connected by edges in the provided grid.
The A* runs on the resulting model. This transformation can take place on the fly, which reduces the processing time and memory usage a lot.

Anyway, I think it is not necessary in the described scenario.

@Sneaselx: You can have a look at my FreeViewer. If you set the target to your target waypoint and distance to zero it should fly to that target waypoint. It tries to avoid obstacles as long as a direct view at the target. At least it will not fly through them. Look at the videos you can find for the FreeViewControl. You do not need the user input, so FreeView should be enough. Maybe that matches your needs.

If you provide me an example of your “level” file, I can integrate it into your scene for you. it could be just a demo, so you can do it by yourself later.

You can also generate the graph from the polygons of the environment for A*, but you are asking about obstacle avoidance not pathfinding.

A great resource for AI is the book “Artificial Intelligence for Games” by Ian Millington, there are about 10 pages on obstacle/collision avoidance in there.

I keep checking out the copy my University library has :stuck_out_tongue: