[SHMUP] Spline based movement

[SHMUP] Spline based movement

ngiacomelli

Member #5,114

October 2004

I've been working on a SHMUP in my free time but it's all coming together now. One of the last things I have chosen to address is enemy AI and movement. At first I was hesitant about incorporating a spine-based movement system for two reasons:

I have little or no experience with splines and a poor head for mathematics
I considered a spine-based approach 'overkill'.

While the first point is still relevant, the second point no longer is. The more I thought about having to hardcode various movement routines for each enemy type or incorporate a scripting engine, the more splines came to seem logical.

What I'm looking for is some kind of spline implementation that will let me:

Plot points for an enemy to move to.
State how fast an enemy should move from point A -> point B.
State how long an enemy should stay on a certain point.

When I consider this system, it seems like most of my problems solve themselves. I would be able to make enemies carry out sophisticated loops and formations, while keeping a generic format for movement across all enemy types (which could then be stored in a map file). Currently, I'm planning to have enemy waves appear via a simple timing system. Whereby various waves are defined and then activated after a certain amount of time has elapsed.

The question is, what type of spline implementation am I look at? I'm really looking for a minimal solution. Any example code is appreciated (I'm working in C).

Any suggestions?

ixilom

Member #7,167

April 2006

I'm currently at work so I can't provide any real code, but I can tell you what I've done for my SHMUP (which will never be finished >:( )

What I did was pre-calculate 1000 bezier spline paths and store them in x and y array pairs:

int spline_path_x[MAX_PATHS][MAX_SPLINE_STEPS];
int spline_path_y[MAX_PATHS][MAX_SPLINE_STEPS];

This way each enemy just needs an float index which points out where in the spline path it is.

// e->spline_path ... Which path is this enemy using ?
// e->spline_index ... where in the path is this enemy ?

e->spline_index += 0.1f; // the larger the number, the faster it will travel

e->x = spline_path_x[e->spline_path][(int)e->spline_index];
e->y = spline_path_x[e->spline_path][(int)e->spline_index];

Can't really remember how I did the precalculations as my math skills are worthless and I probably just stole it from someone

___________________________________________
Democracy in Sweden? Not since 2008-Jun-18.
<someone> The lesbians next door bought me a rolex for my birthday.
<someone> I think they misunderstood when I said I wanna watch...

ngiacomelli

Member #5,114

October 2004

The only thing I struggle to really understand from exspline.c is how the object is walked around the spline. Here's the method provided:

1void walk(void)
2{
3   #define MAX_POINTS    256
4 
5   int points[8];
6   int x[MAX_POINTS], y[MAX_POINTS];
7   int n, i;
8   int npoints;
9   int ox, oy;
10 
11   acquire_screen();
12 
13   clear_to_color(screen, makecol(255, 255, 255));
14 
15   for (i=1; i<node_count-1; i++)
16      draw_node(i);
17 
18   release_screen();
19 
20   do {
21      poll_mouse();
22   } while (mouse_b);
23 
24   clear_keybuf();
25 
26   ox = -16;
27   oy = -16;
28 
29   xor_mode(TRUE);
30 
31   for (n=1; n < node_count-2; n++) {
32      npoints = (fixtoi(node_dist(nodes[n], nodes[n+1]))+3) / 4;
33      if (npoints < 1)
34   npoints = 1;
35      else if (npoints > MAX_POINTS)
36   npoints = MAX_POINTS;
37 
38      get_control_points(nodes[n], nodes[n+1], points);
39      calc_spline(points, npoints, x, y);
40 
41      for (i=1; i<npoints; i++) {
42   vsync();
43   acquire_screen();
44   circlefill(screen, ox, oy, 6, palette_color[2]);
45   circlefill(screen, x<i>, y<i>, 6, palette_color[2]);
46   release_screen();
47   ox = x<i>;
48   oy = y<i>;
49 
50   poll_mouse();
51 
52   if ((keypressed()) || (mouse_b))
53      goto getout;
54      }
55   }
56 
57   getout:
58 
59   xor_mode(FALSE);
60 
61   do {
62      poll_mouse();
63   } while (mouse_b);
64 
65   clear_keybuf();
66}

The questions I have:

The code is quite messy, how is the objects current location along the spline calculated?
How can you tell when an object passes over a particular node?
How would you regulate the objects speed from one node to the other?

Northburns

Member #8,821

July 2007

Quote:

The code is quite messy, how is the objects current location along the spline calculated?
How can you tell when an object passes over a particular node?
How would you regulate the objects speed from one node to the other?

1)
The manual entry for

void calc_spline(const int points[8], int npts, int *x, int *y);

says that it calculates npts points to x and y arrays. This is done to each curve in the exspline.c, one curve at a time (calculate one curve, move the ball to those points, repeat to all curves).
2)
The ball has been drawn on a node when a the next spline is calculated. I'm not sure if it's that good solution (it's accurate and fast, though), but you could always check for distance.
3)
I'm thinking that the only way would be calculating the distance between calculated nodes, and going from there.. There has to be a faster way.

I hope my observations prove at least a bit useful.

Offtopic: The example is pretty messy, there's a raptor-danger: goto

EDIT---
(Removed a smiley. Didn't work afterall)

Wilson Saunders

Member #5,872

May 2005

The basic concept of a spline is:
You have 4 points in space and a number that goes from 0 to 1. You get a fifth point which is along a smooth path based on that number.

Since you are using this to calculate position not draw a line you don't need to store points. Instead have the enemy calculate its position based on a timed index that ranges from 0 to 1. The faster the enemy goes from 0 to 1 the faster it will move on the screen.

I will post code if you need it when I get home.

________________________________________________
Play my games at http://monkeydev.com

ngiacomelli

Member #5,114

October 2004

Wilson, I'm not sure I follow. What does the value between 0-1 signify? Is that calculated between each node, or from the first node to the last?

Any example code you have would be helpful!

Wilson Saunders

Member #5,872

May 2005

Nial Giacomelli said:

Wilson, I'm not sure I follow. What does the value between 0-1 signify? Is that calculated between each node, or from the first node to the last?

A spline travels from Point A to Point B, using Points C and D to calculate a curving path. When the value I talk about is 0 the calculated spline point is at point A. When the value is 1 the calculated spline point is at Point B. Of course the points between are generated by fractional numbers.

You will have to wait for me to get home in 5 hours before I can show you code.

________________________________________________
Play my games at http://monkeydev.com

Northburns

Member #8,821

July 2007

In the mean time, check out this article on Wikipedia:
Bézier Curve
The spline is a cubic Bézier curve. (I found the animated image very helpful myself)

ngiacomelli

Member #5,114

October 2004

After reading the Wikipedia article I feel I understand the concept slightly more. What confuses me is the fact that a spline can contain any number of nodes, yet the article only mentions 4 points. Is this because a Bezier spline needs at least four points? Or is it because easy curve in a spline needs 4 points (two nodes and two directional points)?

Source code is certainly appreciated!

23yrold3yrold

Member #1,134

March 2001

Basically you interpolate along the spline to move the ship. In my old shmup I would interpolate one point, and then one point beyond, so the ship always knew where "forward" was and turned as it travelled the path.

I guess I could try to dig up some source code ... this is going back like 5 years here.

--
Software Development == Church Development
Step 1. Build it.
Step 2. Pray.

Wilson Saunders

Member #5,872

May 2005

As promised here are two functions used to calculate a point along a spline.

Explanation of variables:

frac: must be between 0 and 1, so if your enemy will be on the screen for 200 frames and it is currently the 150th frame frac will be 150/200 or 0.75.
start: the location where the spline starts or in your case the spawn point of the ship.
end: the location where the spline ends, or in your case where you want the ship to fly off screen if it survives the gauntlet.
mid1: a point that the ship will fly towards (but not reach) after it has spawned.
mid2: a point that the ship will fly away from as it approaches the end point. Really there is no better way to put it.

1float getXloc(float startX, float endX, float mid1X, float mid2X, float frac){
2    float inv = 1-frac;
3    return inv*inv*inv*startX +
4    3*inv*inv*frac*(mid1X)+ 
5    3*inv*frac*frac*(mid2X)+ 
6    frac*frac*frac*endX;
7}
8 
9float getYloc(float startY, float endY, float mid1Y, float mid2Y, float frac){
10    float inv = 1-frac;
11    return inv*inv*inv*startY +
12    3*inv*inv*frac*(mid1Y)+ 
13    3*inv*frac*frac*(mid2Y)+ 
14    frac*frac*frac*endY;
15}

Any way experiment with setting start end, mid1, and mid2 at various parts of the screen then having frac go from 0.0 to 1.0 based on timer updates.

________________________________________________
Play my games at http://monkeydev.com

ngiacomelli

Member #5,114

October 2004

EDIT 2: Now that I have my spline implementation working, I've added a speed float to each node. When an enemy reaches a node, it checks its speed value and then adds that value to the frac value each logic tick until frac >= 1 (it has reached the next node).

This works nicely, but I've realised that if two nodes are close together, the enemy will move slower at the same speed value than if the the two nodes were further apart. It's just a case of tweaking the speed value for these nodes to get a seemingly constant speed, but is this the standard way of doing things?

The code helped, but I still have some questions (is it like hitting your head on a brick wall?)

Your ship travels from Point A to Point B. You have a variable between 0 and 1, 0 meaning the ship is at Point A and 1 meaning it has arrived at Point B. So I assume you would want to regulate the increase of this number (frac) to control your ships speed?

Supposing I have a spline made up of 10 nodes, and I want my ship to walk that spline. I assume that rather than making Point A the first node and Point B the 10th, I would make Point B the second? Then, when frac reached 1, I would update the value of Point A and Point B until Point B > the maximum node count?

Pseudo code:

if( frac >= 1 && pointb < node_count ) {
   pointa++;
   pointb++;
   frac=0;
}

Point C and D are purely for directional information, to tell the ship how to move from A to B. In exspline.c I've found the following function:

1void get_control_points(NODE n1, NODE n2, int points[8])
2{
3   fixed dist = fixmul(node_dist(n1, n2), curviness);
4 
5   points[0] = n1.x;
6   points[1] = n1.y;
7 
8   points[2] = n1.x + fixtoi(fixmul(fixcos(n1.tangent), dist));
9   points[3] = n1.y + fixtoi(fixmul(fixsin(n1.tangent), dist));
10 
11   points[4] = n2.x - fixtoi(fixmul(fixcos(n2.tangent), dist));
12   points[5] = n2.y - fixtoi(fixmul(fixsin(n2.tangent), dist));
13 
14   points[6] = n2.x;
15   points[7] = n2.y;
16}

Would I be right to assume that this is a method of taking two nodes (Point A, B) and returning their control points (Point C, D)?

EDIT: It seems to be working ! Hurray! Thanks to all who helped out.