🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Trying to figure out ways to avoid obstacles with this new vector based approach

posted in DreamLand editor
Published June 27, 2024
Advertisement

A couple days ago I felt lost. And I still do. I had no idea where to start. Eventually I came up with this code. I`m creating an additional vector that points in the opposite direction of where the obstacle is. If I move using this vector I can make some room between the unit and the obstacle, which then allows me to move a little bit towards the required path node using the initial vector. It works but it appears ugly. The unit doesn`t have a constant speed while going around the obstacle. Also I haven't tried yet but my guess is that the unit will get "confused" if there are several obstacle units next to each other, which I guess is the main problem

if (useInitialVec)
{
float VectorX = NextNodeX - UpixPosX;
float VectorY = NextNodeY - UpixPosY;
float VecLength = sqrt(VectorX * VectorX + VectorY * VectorY);
float SpeedPercent = (0.016 * 100) / VecLength;
float AdvanceX = (VectorX * SpeedPercent) / 100;
float AdvanceY = (VectorY * SpeedPercent) / 100;

float DesiredX = UpixPosX + AdvanceX;
float DesiredY = UpixPosY + AdvanceY;

float DesCDtop = DesiredY - unitsize / 2;
float DesCDbott = DesiredY + unitsize / 2;
float DesCDleft = DesiredX - unitsize / 2;
float DesCDright = DesiredX + unitsize / 2;

bool CDTest = CDCheck(id,&obstacleid, DesCDtop, DesCDbott, DesCDleft, DesCDright);

if (CDTest == false)
{
 UpixPosX = DesiredX;
 UpixPosY = DesiredY;
}
else
{
 useInitialVec = false;
}
}
else
{
useInitialVec = true;
float ObstX;
float ObstY;
GetObstPos(obstacleid, &ObstX, &ObstY);

float VectorX = UpixPosX - ObstX;
float VectorY = UpixPosY - ObstY;
float VecLength = sqrt(VectorX * VectorX + VectorY * VectorY);
float SpeedPercent = (1 * 100) / VecLength;
float AdvanceX = (VectorX * SpeedPercent) / 100;
float AdvanceY = (VectorY * SpeedPercent) / 100;

UpixPosX = UpixPosX + AdvanceX;
UpixPosY = UpixPosY + AdvanceY;
}
0 likes 8 comments

Comments

JoeJ

I`m creating an additional vector that points in the opposite direction of where the obstacle is. If I move using this vector I can make some room between the unit and the obstacle, which then allows me to move a little bit towards the required path node using the initial vector.

Yeah, that's the right kind of thinking.

The first thing i notice in your code is that you use logic where it isn't needed.
Maybe because you are used as a programmer to think in logical if else terms.

But this is not how simulation works.
And it's not what you want either, since logic requires a from of intelligence. Yours actually, but you are not there when the player plays your game, so eventually your predefined decision tree won't work well in dynamic, unpredictable cases.

That's the primary reason why we do simulations. We want to minimize and replace complex logic with simple laws of physics, which feel natural and predictable because they imitate real world laws of physics.

This does not mean you need to read textbook about physics. Physics does pretty much what you have said in your quote. So by just following your intuition, you will arrive at natural laws of physics anyway.

But non the less - physics is useful. It helps to know about it. It increases awareness about things which feel subconsciously natural, but then are not as easy to reproduce with code as thought.
So i'll give a little primer on physics, focusing on which aspects matter to us for what.

To follow real world physics, you would define a unit somehow like this:

struct Unit
{
	float pos;
	float velocity;
	// float mass; // this is cosntant, so might be elsewhere. and we don't need it for now, assuming everything has a mass of one. So eaach unit is as heavy as any other.
};

(I just get a flashback - did i already gave this tutorial some time ago? Anyway, moving on…)

A unit moves along its velocity vector. (Well, my unit is one dimensional, so there is no vector. It can only move on a global line. But you would use x,y or a vec2 for each variable. The math remains the same otherwise.)

The longer the duration of movement, the larger the displacement, obviously.
Which is simple math:

struct Unit
{
	float pos;
	float velocity;
	
	void Move (float timestep)
	{
		pos += velocity * timestep;
	}	
};

You do this indirectly.
But you obfuscate the simple math with bad terminology and redundant equations such as (1 * 100) / 100.

Make it easy for your brain to learn! Remove the redundant math, and adopt the same terminology we all use. So you can read and apply our tutorials, learning easier and faster.
Be nice to your brain! ; P

So now we have defined movement like nature does it (accepting some piece wise approximation of nature, so we con turn equations into executable math).

But how does movement change in nature?
If two rocks collide, do their positions change in an instant moment?
No. this would be like teleporting. Star Trek. Nature is not like that.
Do their velocities instantly change?
No, neither. Nothing changes instantly in nature. Any change is smooth, if we look at it close enough. Because it takes time until the energy from a cause can generate some effect.

So what do we do to achieve such smooth change over time?
We apply a force to an object. Force causes acceleration, and acceleration is the change of velocity.

Yes, this is the point where it gets confusing. But it is what it is.
Let's add it:

struct Unit
{
	float pos;
	float velocity;
	
	void Move (float timestep)
	{
		pos += velocity * timestep;
	}	
	
	void ApplyAcceleration (float acc, float timestep)
	{
		velocity += acc * timestep;
	}
};

The math is still simple.
But to understand what happens we need to draw curves on paper, or better: Make a program and observe how it behaves over time.
Nobody can explain it to you, so experimentation is key!

Now, being game devs, we can do what we want. It helps to know laws of physics, but we don't have to respect them if we don't want to.
So we might eventually do things like this:

If a unit collides with a static wall, we might change it's position directly to resolve penetration. (Incorrect, but it might work and do what we want.)

If a unit moves too fast for whatever reason, we might clip its velocity to some given max value. (It's incorrect to change velocity directly, but we don't care.)

If a unit comes too close to another unit, we might apply acceleration to both units to separate them smoothly over time. (Correct! But be warned: Controlling objects with acceleration is much harder than the other 2 options.)

That's no concrete advise on what you should do. I just want to increase your awareness about what it means to affect a system that changes over time in a simulation. What's the options, and what's the difference between them.
You should adopt the equations and related terminology as soon as possible.
Because those equations are already reduced to minimal complexity. It's the best you can get.
Following your own intuition would bring you to the same realization after some time, but till then it's all vague, uncertain, and thus:

A couple days ago I felt lost. And I still do. I had no idea where to start. Eventually I came up with this code.

Nothing wrong with what you do. But you can take shortcuts. ; )

June 27, 2024 03:07 PM
JoeJ

The unit doesn`t have a constant speed while going around the obstacle. Also I haven't tried yet but my guess is that the unit will get "confused" if there are several obstacle units next to each other, which I guess is the main problem

I think none of those are potential problems.

Imagine your a stuck in a tiny prison room. What's your velocity? Zero. As expected.

Imagine you are stuck in a dense crowd of people on the street. What's your velocity? It's the same as for the guys nearby. That's the only speed and direction you can do.

There is no confusion in simulations. But there is ‘jitter’… ; )

June 27, 2024 03:12 PM
Calin

Thanks for encouragement. I must add several units and set them on a collision course I haven’t done that yet so I have no idea what might happen.
I don’t think I’m going to use the physics approach though. An approach like that doesn’t work well for workers in a RTS I think. I have ideas for trying something else.

June 27, 2024 06:27 PM
JoeJ

I don’t think I’m going to use the physics approach though.

But you already do. The code you show models physics. Units in most modern RTS games are modeled with physics. Zerglings for example. Interesting AI behavior sits on top of a basic implementation of physics.

Even if physical realism is not your goal, the stuff you do is still called ‘physics’, so learning about physics helps against uncertainty originating from physics.

I give you an example:
When i was young, i made 2D action games on home computer. It was fun. But my games were not as good as Super Mario.
But i did not realize the reason. Not at all. I was not aware.
I realized the reason only 10 years ago, when i started playing Super Mario daily with my wife.
Being aware about physics now, i saw: In Super Mario, the player controls the acceleration of Mario, not his velocity like in PacMan or my home computer games.
Velocity is clipped so it does not exceed a given limit.
Depending on buttons pressed, the player has two options for speed. A slow and a fast mode, affecting the applied acceleration and the speed limit.
This also applies vertically. The player controls how strong gravity is, to adjust jump height while in air.

Quake does the same thing for its character controller. Almost all modern games do it.

I can see all this now, and i could make my own Super Mario game.
But i could not do it back then on my C64, because i did not understand how games utilize the laws of physics.

But - do as you wish. Call it vector instead velocity, and percentage instead of time. Ignore common sense and knowledge, and reinvent the wheels. It works.
But it is like learning guitar with a bad technique, e.g. hopping over strings with the pick.
It works, but you'll never be able to play fast. Even after years of practicing, you can't.
So you go to the guitar teacher and say ‘Show me how to play as fast as Yngwie!’
And the teacher says: ‘Well, why didn't you come earlier? I would have told you your technique sucks on the first day. Now you need to unlearn the wrong technique, and learn the proper one from scratch. It will get better, but not as good as Yngwie. You are too old now, and you have already wasted too much time on the wrong technique’.

June 28, 2024 07:16 AM
Calin

I have sent several units on a collision course and it worked. To my surprise they patiently avoided each over. There is also a bug, sometimes units start racing against each other by going in the same direction but overall it works. Initially I had the feeling it takes forever for a unit to go around another unit but now I don’t have the same impression anymore.

Jitter is not a problem, when I see units trembling a bit it reminds me of someone walking.

June 28, 2024 06:03 PM
Calin

But you already do

I will use whatever works. Sadly my physics based solution is half baked. I don’t know how to fix the bugs and unwanted behavior so I’m back to square one. Basically if I figured out how to use two vectors doesn’t mean I have a working solution, it’s just a hot potato which I don’t know how to handle. I don’t know how learning works but sometimes I reach to the correct conclusion by experimenting in the wrong direction.

June 29, 2024 08:29 PM
JoeJ

I don’t know how learning works

Googling related stuff and seeing how it's done.

Searching for ‘boids’, this is my first find, with an interactive demo and source code on github. Javascript, but easy to port.
There are probably better tutorials (eventually even from people who would use the proper physical terms.)
Such birds swarm behavior is maybe not precisely what you want, but it may help to get there.

Regarding bugs, here are some points where i see potential problems:

Not sure what ‘useInitialVec’ is meant to do, but you could visualize it's state by cahnging the color of units depending on if it's set or not. Then you can see if bad behavior is related too the flag, and if behaves as expected or not.

You use a box to check for collisions, but to resolve a collision you do not care where the collision happens, nor how deep the penetration is. I expect discontinuities from that.
The simplest example to handle this ‘correctly’ would be:
Use circles for unit - unit collision, not rectangles.
Calculate the distance between circle centers.
The exact penetration is then: (radiusA + radiusB) - distance.
To resolve the collision precisely, you can then use half of the pentration to displace both units by the same amount in opposite directions (assuming they have both the same mass). It's much simple math than trying the same for rectangles.

The same idea can then be used to model avoidance by using a larger radius and applying the displacement to velocity or acceleration, not position. A matter of experimentation.

June 30, 2024 05:59 AM
Calin

Regarding circle vs circle collision. If the distance between units centers is smaller then two times radius you have a collision?

June 30, 2024 11:53 AM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Profile
Author
Advertisement
Advertisement