Seek steering

[viranimus]

Okay, I am having a serious, serious problem that I just cannot resolve. It's C++ and DirectX, and it's an arrow-like ship object that has to seek to the position of the player in an Asteroids-esque looking environment.

For the most part it works, but sometimes when the player is up and to the right of the bot at just the right moment, the bot will deviate from its course and pull a big left-turn loop before re-aligning itself with the playership. If I let the player just sit in place, the ship will fly through the player as expected, and begin to loop back around. The problem that occurs here is that the bot alternates between left and right turn loops on the left side of the player, effectively doing a figure 8 dance until it hits the left side of the window, re-aligns itself with the player, lather, rinse repeat forever.

And then SOMETIMES, the bot will get stuck in an infinite loop- literally, just doing left turn circles. There is something about this that is making it get stuck in these left-hand loops, and I've been at this problem all day. Below is my code, as well-commented as I can make it.

The targetAngle function returns the angle between the bot and the target- If I set the angle of the bot to this angle, tAlpha, it would point at the player directly.

The basis for my calculations was the difference between tAlpha and alpha, which is dAlpha for delta alpha.

STEER is 3.0, which is for degrees per frame of steering. Every frame I want the program to determine where the target is (target is the player), so it gets those coords, and if the angle is bigger that the bots current angle, increase the bots current angle. Visa versa for smaller angles.

Can anybody tell me why this isn't working the way I feel it should be working?

//Seek steering behavior
void Bot::steerSeek(float targetX, float targetY){
	float tAlpha=targetAngle(targetX, targetY); //Angle from bot to target
	float dAlpha=tAlpha-alpha; //Difference between target angle and current angle
	//If target angle is greater than current angle
	if(tAlpha>alpha){
		//If the difference in angles is less than or equal to 180 degrees
		if(dAlpha<=180){
			vx=rotateX(vx, vy, STEER);
			vy=rotateY(vx, vy, STEER);
			alpha+=STEER; //Increase current angle
		}
		else if(dAlpha>180){
			vx=rotateX(vx, vy, -STEER);
			vy=rotateY(vx, vy, -STEER);
			alpha-=STEER; //Decrease current angle
		}
	}
	//If target angle is less than current angle
	if(tAlpha<alpha){
		//If the difference in angles is less than or equal to 180
		if(dAlpha<=180){
			vx=rotateX(vx, vy, -STEER);
			vy=rotateY(vx, vy, -STEER);
			alpha-=STEER; //Decrease current angle
		}
		else if(dAlpha>180){
			vx=rotateX(vx, vy, STEER);
			vy=rotateY(vx, vy, STEER);
			alpha+=STEER; //Increase current angle
		}
	}
	rotateBot(alpha); //Adjust orientation
	thrust();
	move();
}

EDIT: Sorry, I should notate that vx and vy are the x and y components of the bot's curreng velocity vector, respectively.

[Disch]

One problem that jumps out immediately:

			vx=rotateX(vx, vy, STEER); // <- changing vx here
			vy=rotateY(vx, vy, STEER); // <- using NEW vx value here.  Not intentional? 

This might cause wonkiness. Also if your angles are outside of [0,360) these calculations simply won't work. So unless you are wrapping to make sure you're always within those bounds (I don't see where you are in this routine) this approach will just fail.

For example... an angle of -90 degrees is the same as 270, so you would need to decrease the angle.... but since -90 is less than 180 this code would be increasing it.



==========================================

The good news is there is a much simpler approach to this problem in Linear Algebra. It's the dot product (and perpendicular dot product).

Get used to these functions. Once you understand them, you'll find 1001 uses for them. They really are extremely versatile:

inline float     dot(const Vector& a, const Vector& b) { return (a.x*b.x) + (a.y*b.y); }
inline float perpDot(const Vector& a, const Vector& b) { return (a.y*b.x) - (a.x*b.y); }

These functions are magic. They have the below properties:

    dot(A,B) == cos( theta ) * length( A ) * length( B )
perpDot(A,B) == sin( theta ) * length( A ) * length( B )

// where 'theta' is the angle between vectors A,B 

Since I don't know whether or not you really care, I'll spare you the details of what this means, and I'll just tell you that this can be applied as follows:

- let vector A be the movement vector of the enemy (the direction he's currently facing)
- let vector B be the vector between the player and the enemy


- dot(A,B) will be positive if the enemy is moving closer to the enemy, and negative if moving away.

- perpDot(A,B) will be positive if the player is to the right of the enemy, and negative if the player is to the left (** note I might have this backwards... positive might mean to the left.... I can never remember which is which... try it and see! **)

- perpDot(A,B) will be zero if A and B are parallel (ie: enemy is moving directly towards the player, or directly away from them).



For your purposes, you can use perpDot to determine if you need to steer left or right. If perpDot is zero (parallel), you can use dot() to determine whether or not you are facing the right way:

Vector shipDirection = /*the direction the ship is facing*/;
Vector targetDirection = targetPosition - shipPosition;

float pd = perpDot( shipDirection, targetDirection );
if( pd < 0 )
  turnRight();  // or left if I have it backwards
else if( pd > 0 )
  turnLeft();  // or right if I have it backwards
else if( dot(shipDirection, targetDirection) < 0 )
  turnRight();  // need to pull a 180, pick a direction and go for it
//else we have no need to turn because we're heading right for them 

EDIT: If you are interested in understanding more of why/how this works, I can get into more detail. Just let me know. I just didn't want to waste the time on it if you weren't interested.

[viranimus]

Well...

It appears as though I need to do some work on re-organizing my assets in the program.

Thank you very much- I was already aware of the Dot product and it's magical properties, but I wasn't sure if I could use them here. As I said, movement is very much like it is in asteroids, so the only buttons you can press are up to apply acceleration in the direction the ship is facing, and the left and right keys to rotate the ship about the centroid of its triangle.

How would I apply such theory to this structure?

Again, thank you very much for your input here, and also for any continued support hereafter.

[Disch]

How would I apply such theory to this structure?

Really the only way I can see to apply dot/perpDot here is as previously described (to determine whether or not a ship is left/right of its target). Everything else can be easily accomplished in a way similar to what I'm sure you're already doing.

To apply the above, I would just replace your posted steerSeek function with something similar to the example in my previous post. Nothing else in the program would have to change.