Simple Obstacle Avoidance System
Maths & C++ & UE4/5
|| Introduction to the problem
Hi and welcome, I should preface this by saying that the mathematics going into this post has been simplified for easy understanding and proving formulae and theory is not going to be talked over.
Welcome to another post, I’ve been meaning to talk about this for a while but havn’t had the time to write it down. Along the development process of my game (Primal Dominion: Aftermath), I found myself questioning whether or not it was a feasible idea to incorporate procedural animations based on obstacles and structures in close proximity to the player. I devised a simple function that would do a sphere cast and I would determine an avoidance angle which would drive the upper body of the character away from the wall.
I generally wasn’t too sold on this idea as I felt like it was counter intuitive when playing, it gave the illusion of the dinosaur moving away and thus I would be convinced I am moving away and would end up colliding with walls thinking I would be safe. This insipired to me to rethink the system and incorporate it into a much more meaningful feature.
My next iteration had to meet the following criteria:
- Function as an assist away from walls and objects
- Dynamically change its radius/size to match speeds
- Use as few ray casts as possible
- Consider Terrain/Elevation/Slope
Following the criteria I ended with a result that looked like this:
Generally it works amazingly in extreme scenes like this where visibility is almost non existant, it keeps the player constantly moving and allows the player to not experience that disconnect you feel when you smack into a wall and have to reorient yourself back. However, and I will discuss these at the end of the post, I think there’s plenty of room for improvement as reliability and certain placements of objects can create some wild results.
Breaking down the solution
I’d briefly like to mention, I am going to be talking about Vector Math here quite extenstively as it’s integral to the system, so if you would like a refresher on the basics, here’s a link to one of my posts about it:
https://medium.com/@harrisbarra/understanding-dot-product-with-example-74dba339f29e
So back to the solution: to achieve this avoidance I started off with the basic idea that there are 3 ray casts firing at every frame to get a reasonbly big enough sector to find collisions from
Inherently, this means that we are subject to the issue of accuracy. Since there’s only 3 raycasts, we have space between each of those casts where an object can appear and be unnoticed by the system, this can be remedied by increasing the raycast count, however, for the sake of performance and simplicity I wanted to see how a system using the fewest required raycasts would work.
From the side profile, here are how the traces look on a flat (parallel) plane:
The avoidance raycasts are elevated because an issue from the previous iteration was that the spherecast would trigger on terrain, I had some fixes such as limiting the hits to only be considered if they were above the midpoint of the character but generally I thought it wasn’t a great idea. Another thing from there is that I didnt use a spherecast in this iteration, I wanted more control over the avoidance traces as not every dinosaur shares the same body type and so using individual casts allow me to position each of them as close to perfect on each dinosaur. (This system takes an inheritive approach)
You may also notice how there is a 4th cast which goes down, this cast is used to determine the slope angle and if it’s an incline/decline, so let’s start there.
Calculating Slope Values
How can we determine the slope direction based on just the raycast alone? Well we can get the surface normal based on that cast, we can then compare its relation to the forward vector via dot product.
This will give us the slope direction, aka incline/decline.
As we can see from the diagram above, both vectors are perpendicular meaning the dot of both of them will be 0. Excellent, since the ground is parallel, we are neither on an incline/decline.
In this example we are now on an slope, as we can see, the forward vector is still pointing horizontally with no vertical change, however the surface normal is pointing at an angle. We can also see that it’s pointing towards the same horizontal direction as V1. This means that the dot product will return a positive (> 0) value.
We can now attribute: Decline = Dot (A,B) > 0
In this example, we have now turned around the character, notice how the surface normal hasnt changed but our forward vector has changed. From just a glance, we can tell that these two vectors share different horizontal directions and as such the dot product of both of these will return negative.
Therefore we can attribute: Incline = Dot(A,B) < 0
Heres the code for this logic:
In the code we can use the ‘Sign’ function here to simplify this to give us easier to use values (-1/0/1).
Okay with this understanding of whether or not we’re going down or up a slope, we should now get the size. To get the slope size, we’re going to compare the surface normal direction to the downward trace direction.
The float AngleDP will be the size we’ll be using. The smaller the absolute value the more steeper the slope, the larger the absolute value, the more flatter the slope.
You may be questioning why I’m not interested in the actual slope angle, this is because each dinosaur is unique in their size and shape and will use specific custom values for each of them and so we want a normalized float to work with.
Making & Using Avoidance Raycasts
In my implementation I am using ArrowComponents to be used as my visual in-editor imposters for the traces. This allows me to tune each dinosaur much more easily.
Using the component I can get its location to get the Trace Start location, I can then use its rotation to get its direction. I can calulate the Trace End Location by using the character’s speed multiplied by the Component Rotation Vector:
In the snipped above I have a variable called ‘VelocityTraceMultiplier’ this is an additional float that allows me to boost the trace length depending on whether or not the dinosaur requires it. Now let’s incorporate the slope into the code:
In the code above, we are calculating a ZOffset, from the slope direction, the angle DP and a multiplier. We are also clamping the ZOffset to a fixed maximum value so the trace doesn’t go completely vertical.
We can then apply this offset to the ForwardEndLoc variable as we’re only interested in changing the direction of the vector, not the position.
The ZOffset is added only to the Z component of the EndLoc Vector as we only want to add / subtract height depending on the slope direction.
You may also notice that I interpolate at the end, this is to allow for smoother transitions between uneven surfaces like the jungle terrain, this is crucial as sudden changes can cause very extreme ZOffsets, so between ticks the outliers are dampened.
The code above is repeated for both the Left and Right Trace variables.
We can then create our raycasts with this information. Now if for example the left raycast hits something, we will set a variable called LeftInfluence to 1.0, if not we will set that to 0.0. If we’ve hit something on the middle trace aswell as the left, we will multiply the LeftInfluence by 2x, this means that the character will move away much faster as the object is considerably close. We can apply the same respective logic to the RightInfluence.
We can now drive the character left/right depending on the value of LeftInfluence subtract RightInfluence:
This works because +1 would move the character towards the right, -1 would move the character left, the avoidance should move right if the left trace is triggered and should move left if the right trace is triggered.
There is a bit more to this such as interpolating the values of the Influences so that the traces dont constantly move the character exclusively when hit, there interpolation acts as a buffer to allow the character move, interpolate back to 0 and then restore control to the user.
Future Improvements
As mentioned near the start, though I think this is a much better feature/solution, it can be improved.
I think the way I would expand on this is by expanding the number of casts to maybe double and using a scoring system to score traces by certain criteria to determine how strong and which direction the dino should move. This would help stop the current system from getting confused in certain tight situations and when approaching objects from awkward angles. I’d also have the raycasts gather at dynamic time intervals depending on how many raycasts have been triggered (the more the smaller the interval).
I know that this post may have been a bit long winded and difficult to understand fully, but I hope that I have made it as simple as it can be and the vector math makes sense. Thank you!
