Steering behaviours: collision avoidance with rectangles

Question

I'm trying to implement collision avoidance steering behaviour using rectangles. Most of the tutorials I've found are with circles, and there's a substantial difference. For example, I've been reading this:http://gamedevelopment.tutsplus.com/tutorials/understanding-steering-behaviors-collision-avoidance--gamedev-7777

My current approach: first, detect the nearest rectangle as done in the article. I create a point called ahead in front of my entity and then check if that point is inside the rectangle. After calculating the nearest object, I decompose my rectangle in a set of points, equally spaced in the rectangle walls. My entity will flee those points.

EDIT: I've also proven to convert my rectangle in an electromagnetic repulsive rectangle with 4 bars of homogeneus charged. It didn't worked. I also tried the "containment" section described in Craig Reynolds' website and it also didn't worked properly.

That works reasonably well: my entities try to avoid the rectangle. However, they sometimes get a bit into it, and when they're near the rectangle they start flipping to left and right quickly. That is not a very natural behaviour, so I think I want to prove another thing.

I've read this in gamedev SO: Wall avoidance steering I think that this could be what I need, approximately. However, I need some guidance on this.

• First, the answer speakes about a dot product of the wall-boid vectors (let's call them WBi). Which is the another vector I have to multiply with? In the code sample is noted as partsList but I don't know what it is. So, first question: what is this second vector?

• In my opinion, this algorithm as a very important flow. If the force is exerted in the direction of normal of the wall, and by chance my entity goes with velocity normal to the wall, it will stop. This, I think, could be a rare event because more steering forces are involved... Second question: there is a way to avoid this? Is this effect important enough to take care of it even if I have more forces?

• In fact, I need an algorithm capable of detecting and avoding rectangles with steering behaviors -or, at less, a way to move my entities in a space with obstacles using something compatible with steering behaviors, because I use them for coordinate movement.

Take in account that some combinations of rectangles could create convex shapes.

EDITS:

• The rectangles aren't rotated.

Answer 1

While a bit different to your example above, I have implemented a spring algorithm into my game that has worked for me. The idea is that if the object comes close at a certain determined buffer distance to another object, a magic invisible spring appears and corrects the path of the object(s). Here is a video recording of my game engine demonstration illustrating what I mean. The yellow vectors visualize the spring between the two objects that appears when the objects come close together. The longish brick object uses a sliding spring, the short brick object uses a fixed spring at the object's center.

To calculate a repulsive spring action, use the physics to determine the acceleration conditional on the distances between the objects and some chosen parameters like spring_stiffness and mass, e.g.

float spring_stiffness = 3.0;
float mass = 0.5;
float dist = CalculateDistanceObjectToObject(*ObjectA, *ObjectB);
float stretch = dist-buffer_distance;
float angle = GetAngleofVector(ObjectB.Position - ObjectA.Position);
float acceleration =  (spring_stiffness/mass)*stretch;
float acceleration_x = sin(angle*TOARC)*acceleration;
float acceleration_y = cos(angle*TOARC)*acceleration;

Where stretch is 0 for the spring at rest. Trigger acceleration when distance is under a certain pre-determined value.

Use as buffer as the circle spanning around plus some preferable extension. If you like your objects to avoid each other at closer distance, keep the extension small (e.g. 20%).

This works fine fir circular objects. If you have very longish objects like walls, you need to adapt the code to have a "sliding" spring. For my demonstration above, I used a SAT (Separate Axis Theorem Approach). Note how the yellow line shifts with the flightpath. For this you need to look up tutorial on how to calculate the closest collision point between two boundaries and attach a "sliding spring between the objects.

Another useful extension is to determine mass that decreases when the distance is getting smaller between the objects, to avoid, by all means, a collision, as the spring force consequently increases. I use an algorithm that increases mass to infinity if the distance between the objects is approaching zero. float mass=0.5f/((2.5f-radius)/(dist-radius)); where radius is the both objects inner circle. (Note: You may also want to modify this to be smoother, e.g. sinus function etc.).

A finer point is to use this for AI control. Use the determined acceleration vector as the 'set_acceleration' and link it with your game control, e.g. turn into the direction, switch on thrusters and accelerate until set_acceleration == actual_acceleration. This would give an impression like the object is on collision course and does a last minute correction, fires its thrusters to escape.

Edit: The game logic could therefore look something like:

1. Determine a circle with radius from the object's center to its farthest corner. Do this for all objects during initialization stage of the game (call this minimum_circle).
2. Create a second buffer_circle by a chosen realistic expansion of the minimum circle (e.g. 20 % larger than minimum_circle)
3. Check distances between all objects circle_buffers (if necessary make use of calculation saving algorithms, e.g. check distances within a certain sector etc.)
4. Flag a collision approach between object A and object B.
5. If two buffer_circles intersect (=distance(A.pos,B.pos)-A.buffer_circle.size-B.buffer_circle.size<=0), apply spring algorithm to create a repelling force with spring_size=A.buffer_circle.size+B.buffer_circle_size
6. Determine either object A or B to be the eluding one, e.g. wall vs player/AI. Consequently decrease mass of object A relative to object B, so the spring force increases to infinite if distance between the minimum circles approaches zero.
7. Unflag collision approach and release spring algorithm when object A and B buffer_circle's are not intersecting anymore.

Optionally you may at point 5 give one of your object a random initial push (up/down or normal of net_speed_vector, to give it a bit more realism if two objects are on direct head-on approach with each other. Also, if rectangles are subject to change, change the circle size (buffer and minimum) accordingly with it, so that the spring algorithm gets instantly updated.