Bezier curve?

[LutinMalefique]

hi,

i'm still working on my shmup game, i just finished my npc's pathpoint system : once created, they go from one point to another, but in a straight line.

I would like to interpolate this straight line to a curve.  I started to learn about b?zier curves and take a look at some pseudo C code but it's not easy, any help will be welcome. So nobody ever used, or try to implement this algorithm in gamecore?

[pixel_legolas]

I was just looking through the docs but don't seem to find anything, there was something about PathType but doesn't state what different ones there are

[LutinMalefique]

PathType is a reference to the Gamecore's pathfinding system. It's a good one but after some tests i realize that it was not for me.
In terms of level design, it was a nightmare to create different "roads" and I couldn't control when and how much NPCs had to be generated. (take a look at the screenshot, with my path system i just need some boxes)



I know, in space, the location where npcs go to, it should not be that hard to make them move along a curve between 2 points.

[LutinMalefique]

OK, I have some ideas after reading a few articles on Wikipedia and a book  (Real-Time rendering by Akenine-Moller, Haines & Hoffman;  an excellent book for anyone interested in game development)

Here an animation from wikipedia to explain what i want to do.


I should have a working code next week.

[pixel_legolas]

dude, you are on a high level here good luck with that stuff, curves in pathfinding is a must nad hope it can be done, noone wants path models to be edgy

[gekido]

The vehicle script & player script have some examples of what you are looking to do.

Instead of simply rotating the plane directly to face the new pathpoint, what you want to do is have a 'maximum turn angle' that the planes can do at once, and a 'desired turn angle'.  

The section of the character script that is relevant is this:

Code:

// find out how far our desired direction is from our current direction
if (!camMove.IsZero())
{
float rotationCos = camMove.DotProduct( mtx.ZAxis);
float rotation = acos( rotationCos);

// let the character rotate so much each turn (so we don't 'pop' to the new direction)
float maxRotation = ROTATION_SPEED * seconds;
if (rotation > maxRotation)
rotation = maxRotation;
// are we turning left or right
bool left = (camMove.CrossProduct( mtx.ZAxis).y < 0);
// apply the rotation
if (left)
mtx.RotateAxis( Vector( 0, 1, 0), -rotation);
else
mtx.RotateAxis( Vector( 0, 1, 0), rotation);
}

The vehicle script handles all movement & turning by basically simulating player input, like this:

Code:

// path finder is in control
if (pathFinder.GetWaypointCount() > 0)
{
   // find a point on our path in front of the car
   float lookAhead = -object.GetBoundingBoxMin().z + PATH_LOOK_AHEAD;

   Vector startPos = object.GetCurMatrix().T;
   startPos.y += object.GetBoundingBoxMin().y; // put the start position at the bottom of the vehicle

   // find a waypoint somewhere in front of us
   WaypointInfo waypointInfo = pathFinder.GetForwardWaypointInfo( startPos, lookAhead, true);

   // get a vector to point us in the direction of our waypoint
   waypointMove = startPos - waypointInfo.destination;
   waypointMove.Normalize();

   // figure out whether we should be turning left or right
   float turnAngle = mtx.XAxis.DotProduct( waypointMove);

   // clamp the angle to a value between -1 and 1 so we can figure out if it's a left or right turn
   turnAngle = clamp( turnAngle * PATH_TURN_SHARPNESS, -1, 1);  

   // simulate the player input by setting the 'left' or 'right' variables to get the car to turn
   if (turnAngle < 0)
      left = -turnAngle;
   else
      right = turnAngle;

}

In this case, the variable 'left' and 'right' are the equivalent of the player pressing the left or right turning buttons - and the vehicle will turn appropriately as a result.

The vehicle script also adjusts the speed of the vehicle based on the sharpness of the turn and some other details, but the relevant parts are above.

Hope this helps.

[gekido]

Ah, just re-read your post and realized that you are implementing your own pathfinding system instead of using the native one.

The basic principles are the same though.

1) get start position & destination position
2) figure out vector between them
3) figure out the 'desired rotation' that the object would need to do to face that direction and whether it exceeds the 'max rotation' that the object is allowed to do in a single step
4) figure out if it's a left or right turn
5) apply the rotation

repeat until object 'desired rotation' is within reasonable limits to point them in the direction of their new destination.

The only real difference is that instead of using the pathfinding waypoint system to determine the destination x,y,z coordinate you have to figure out the new destination yourself (by looking up your custom waypoint location).

The rest of the code should be hopefully enough to point you in the right direction.

[LutinMalefique]

Here some news, everything is far from being fully fonctional but i made some progress (thanks to this article http://www.gamedev.net/reference/programming/features/curvessurfaces/ )

The NPC began to follow a curved path between points, but they stop before the end  
I haven't found where i'm wrong but i'm working on it.

Bezier Curves for a SHMUP

[LutinMalefique]

i've found where i was wrong  

With the code I used, NPC only read the first point of the curve, so i created an array to stock all the curve points calculated.
 Right now, the code needs some "polish" and i must do some stress test to be sure that kind of pathfinding will work for my game.

[gekido]

Sweet - can't wait to see how it turns out!

[flim]

Is that similar to the "FlightControl" game on iPhone?

[LutinMalefique]

@ flim
no, it will be a shoot'em up, like 1942 or DoDonpachi
History of shooting games

[LutinMalefique]

Just a short update with a video showing a working script.

Gamecore SHMUP, working B?zier spline

All boxes have a purpose : one spawn point (what NPC load, how many..), one start point (first point of the path), a final point and one or two mid points.
So to calculate the B?zier curve, three or four points are used and by moving boxes in the editor i can change the curve.
I'm not fully satisfy, it's just for showing you my progress 

[pixel_legolas]

cool stuff, you are scripting champ

[Jim]

Looks really cool, great progress... I'm planning on beginning a Space Shooter pretty soon... Working on the details of how I want to set it up (story, characters, gameplay elements) etc...