Pathfinding problem. Need help
Author
Actually I am not even sure if this is a pathfinding problem.
Here is the brief overview of the problem.
Please see this image first: http://img88.imageshack.us/my.php?image=pathfindingproblemjq2.jpg
There is an AI controlled vehicle. This vehicle has circular and direct movement. At any given time the vehicle can choose to turn left, turn right or go straight. It is OK to turn right when you were turning left and vice versa.
This vehicle is trying to reach a target. We need to find a path where it can reach the target. (There is a keypoint missing in the drawing. Target T is on a line. When the vehicle reaches T it should make a 90 degree angle with the line).
I am really stuck in this problem. Is this a very common situation or it's really harder than I think. By the way the path need not to be optimum (shortest length).
Please help.
Author
Actually I think it's better if I rephrase the issue to make it more understandable. There are boundaries which the vehicle should never hit. If it crashes any boundary GAME OVER!
I am trying to land the vehicle first on some good point (T) parallel to the border. Then I will follow the real target. When the real target is not close to any border it's easy to target it (I have an algorithm which works fine). But when the real target is close to the border I have to apply this strategy.
So what I want is basically to land the vehicle parallel to the border that the real target is close to. Whenever the vehicle reaches the T it's direction vector should be parallel to the border. So I can follow the border and when the time is right I can direct the vehicle to the target.
I am trying to land the vehicle first on some good point (T) parallel to the border. Then I will follow the real target. When the real target is not close to any border it's easy to target it (I have an algorithm which works fine). But when the real target is close to the border I have to apply this strategy.
So what I want is basically to land the vehicle parallel to the border that the real target is close to. Whenever the vehicle reaches the T it's direction vector should be parallel to the border. So I can follow the border and when the time is right I can direct the vehicle to the target.
____________________________________________| || || || || || || .V-> Vehicle direction || vector pointing right || || || || || || || || || ||____V->T_________________Real Target here___
Author
I really need some help about this. At least any web links to a similar problem would be helpful. I am sure some of the other game devs have seen this problem before.
Okay, so I hope I understand you correctly. You have a car, and you want it to reach point T. However, when the car reaches point T, the car's velocity should be in the same direction as the border which T is closest to. Is this right? If so, then I hope my post will help, but if not, please clarify and I'll try to help again.
Anyways, here are my thoughts (I'm going to act as if you have no idea what to do, so if you already have better ideas or plans than what I present, go ahead and use them. I just want to make sure I don't explain one area and still leave you wondering about another area):
1. Create a grid that has nodes (or squares) big enough for the car to turn in. For example, if the car is going straight up and it needs to make a 90 degree turn to the right, then you would have to check the node straight above the car and also just to the right. I'll draw a little picture to help you get the idea.
Store each node's info so that you know whether or not it is accessible (if it is a wall or not) and it's terrain cost, etc...
2. Select your final destination node (point T)
3. Select a semi-final destination node.This is the node you will travel to by using your pathfinding algorithm. The reason you have a semi-final destination is because you want to "turn" into your final destination so that you are headed the right direction. This node should make it so that your car will be headed in the correct direction after your final step. When selecting this node, make sure that you can move from it to your destination node without any risk of hitting a wall. If you don't really know how to go about selecting the semi-final destination node, ask and I'll try to help, but I think you'll be able to figure it out, just make sure you really think about it.
4. Move from your semi-final destination node to your final destination mode. This should only involve one step.
Anyways, here are my thoughts (I'm going to act as if you have no idea what to do, so if you already have better ideas or plans than what I present, go ahead and use them. I just want to make sure I don't explain one area and still leave you wondering about another area):
1. Create a grid that has nodes (or squares) big enough for the car to turn in. For example, if the car is going straight up and it needs to make a 90 degree turn to the right, then you would have to check the node straight above the car and also just to the right. I'll draw a little picture to help you get the idea.
Store each node's info so that you know whether or not it is accessible (if it is a wall or not) and it's terrain cost, etc...
2. Select your final destination node (point T)
3. Select a semi-final destination node.This is the node you will travel to by using your pathfinding algorithm. The reason you have a semi-final destination is because you want to "turn" into your final destination so that you are headed the right direction. This node should make it so that your car will be headed in the correct direction after your final step. When selecting this node, make sure that you can move from it to your destination node without any risk of hitting a wall. If you don't really know how to go about selecting the semi-final destination node, ask and I'll try to help, but I think you'll be able to figure it out, just make sure you really think about it.
4. Move from your semi-final destination node to your final destination mode. This should only involve one step.
Author
The issue is I cannot represent this problem with nodes (Or maybe I did not understand this concept well enough). Here is how the car's position change at any time T.
if going straight:
mPosition += ( mDirection * float( elapsedTime ) * mCurrentSpeed );
if turning left or right:
Basically calculate the angular velocity based on the time elapsed between the frames. Update the direction vector. Calculate the new position.
By the way you exactly understood the problem.
if going straight:
mPosition += ( mDirection * float( elapsedTime ) * mCurrentSpeed );
if turning left or right:
// Calculate the angular velocity float angularVelocity = CalculateAngularVelocity( mCurrentSpeed, elapsedTime, turningAngle ); // Get the 360 modulus of the angle if ( angularVelocity >360.0f ) angularVelocity -= 360.0f * ( int( angularVelocity ) / 360 ); // Update the car's direction mDirection = mDirection.rotateAboutGlobalZ( DEG2RAD( angularVelocity ) ); // Calculate the rotation angle based on the direction vector mRotationAngle = RAD2DEG(atan2f( -mDirection.y, mDirection.x )); if ( mRotationAngle < 0.0f ) { mRotationAngle *= -1.0f; mRotationAngle += 90.0f; } else mRotationAngle = 90.0f - mRotationAngle; // Calculate the new position mPosition = GetNewPositionAfterRotation( mRotationCenter, mPosition, angularVelocity );Basically calculate the angular velocity based on the time elapsed between the frames. Update the direction vector. Calculate the new position.
By the way you exactly understood the problem.
Why can't you use a grid? They would probably simplify the problem a lot.
+
=
=
Anyways, if you truly can't use a grid but you still want to have the correct velocity direction, then maybe these three articles will be of help (the last one looks like it's just what you need)
Link 1
Link 2
Link 3
+
=
=
Anyways, if you truly can't use a grid but you still want to have the correct velocity direction, then maybe these three articles will be of help (the last one looks like it's just what you need)
Link 1
Link 2
Link 3
Author
I will check all of them. I may ask more questions after reading the articles though. Thank you so much.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
