1 /*
2 * Example program for the Allegro library, by Shawn Hargreaves.
3 *
4 * This program demonstrates the use of spline curves to create smooth
5 * paths connecting a number of node points. This can be useful for
6 * constructing realistic motion and animations.
7 *
8 * The technique is to connect the series of guide points p1..p(n) with
9 * spline curves from p1-p2, p2-p3, etc. Each spline must pass though
10 * both of its guide points, so they must be used as the first and fourth
11 * of the spline control points. The fun bit is coming up with sensible
12 * values for the second and third spline control points, such that the
13 * spline segments will have equal gradients where they meet. I came
14 * up with the following solution:
15 *
16 * For each guide point p(n), calculate the desired tangent to the curve
17 * at that point. I took this to be the vector p(n-1) -> p(n+1), which
18 * can easily be calculated with the inverse tangent function, and gives
19 * decent looking results. One implication of this is that two dummy
20 * guide points are needed at each end of the curve, which are used in
21 * the tangent calculations but not connected to the set of splines.
22 *
23 * Having got these tangents, it becomes fairly easy to calculate the
24 * spline control points. For a spline between guide points p(a) and
25 * p(b), the second control point should lie along the positive tangent
26 * from p(a), and the third control point should lie along the negative
27 * tangent from p(b). How far they are placed along these tangents
28 * controls the shape of the curve: I found that applying a 'curviness'
29 * scaling factor to the distance between p(a) and p(b) works well.
30 *
31 * One thing to note about splines is that the generated points are
32 * not all equidistant. Instead they tend to bunch up nearer to the
33 * ends of the spline, which means you will need to apply some fudges
34 * to get an object to move at a constant speed. On the other hand,
35 * in situations where the curve has a noticeable change of direction
36 * at each guide point, the effect can be quite nice because it makes
37 * the object slow down for the curve.
38 */
39
40
41 #include <stdio.h>
42
43 #include <allegro.h>
44
45
46
47 typedef struct NODE
48 {
49 int x, y;
50 fixed tangent;
51 } NODE;
52
53
54 #define MAX_NODES 1024
55
56 NODE nodes[MAX_NODES];
57
58 int node_count;
59
60 fixed curviness;
61
62 int show_tangents;
63 int show_control_points;
64
65
66
67 /* calculates the distance between two nodes */
node_dist(NODE n1,NODE n2)68 fixed node_dist(NODE n1, NODE n2)
69 {
70 #define SCALE 64
71
72 fixed dx = itofix(n1.x - n2.x) / SCALE;
73 fixed dy = itofix(n1.y - n2.y) / SCALE;
74
75 return fixsqrt(fixmul(dx, dx) + fixmul(dy, dy)) * SCALE;
76 }
77
78
79
80 /* constructs nodes to go at the ends of the list, for tangent calculations */
dummy_node(NODE node,NODE prev)81 NODE dummy_node(NODE node, NODE prev)
82 {
83 NODE n;
84
85 n.x = node.x - (prev.x - node.x) / 8;
86 n.y = node.y - (prev.y - node.y) / 8;
87 n.tangent = itofix(0);
88
89 return n;
90 }
91
92
93
94 /* calculates a set of node tangents */
calc_tangents(void)95 void calc_tangents(void)
96 {
97 int i;
98
99 nodes[0] = dummy_node(nodes[1], nodes[2]);
100 nodes[node_count] = dummy_node(nodes[node_count-1], nodes[node_count-2]);
101 node_count++;
102
103 for (i=1; i<node_count-1; i++)
104 nodes[i].tangent = fixatan2(itofix(nodes[i+1].y - nodes[i-1].y),
105 itofix(nodes[i+1].x - nodes[i-1].x));
106 }
107
108
109
110 /* draws one of the path nodes */
draw_node(int n)111 void draw_node(int n)
112 {
113 circlefill(screen, nodes[n].x, nodes[n].y, 2, palette_color[1]);
114
115 textprintf_ex(screen, font, nodes[n].x-7, nodes[n].y-7,
116 palette_color[255], -1, "%d", n);
117 }
118
119
120
121 /* calculates the control points for a spline segment */
get_control_points(NODE n1,NODE n2,int points[8])122 void get_control_points(NODE n1, NODE n2, int points[8])
123 {
124 fixed dist = fixmul(node_dist(n1, n2), curviness);
125
126 points[0] = n1.x;
127 points[1] = n1.y;
128
129 points[2] = n1.x + fixtoi(fixmul(fixcos(n1.tangent), dist));
130 points[3] = n1.y + fixtoi(fixmul(fixsin(n1.tangent), dist));
131
132 points[4] = n2.x - fixtoi(fixmul(fixcos(n2.tangent), dist));
133 points[5] = n2.y - fixtoi(fixmul(fixsin(n2.tangent), dist));
134
135 points[6] = n2.x;
136 points[7] = n2.y;
137 }
138
139
140
141 /* draws a spline curve connecting two nodes */
draw_spline(NODE n1,NODE n2)142 void draw_spline(NODE n1, NODE n2)
143 {
144 int points[8];
145 int i;
146
147 get_control_points(n1, n2, points);
148 spline(screen, points, palette_color[255]);
149
150 if (show_control_points)
151 for (i=1; i<=2; i++)
152 circlefill(screen, points[i*2], points[i*2+1], 2, palette_color[2]);
153 }
154
155
156
157 /* draws the spline paths */
draw_splines(void)158 void draw_splines(void)
159 {
160 int i;
161
162 acquire_screen();
163
164 clear_to_color(screen, makecol(255, 255, 255));
165
166 textout_centre_ex(screen, font, "Spline curve path", SCREEN_W/2, 8,
167 palette_color[255], palette_color[0]);
168 textprintf_centre_ex(screen, font, SCREEN_W/2, 32, palette_color[255],
169 palette_color[0], "Curviness = %.2f",
170 fixtof(curviness));
171 textout_centre_ex(screen, font, "Up/down keys to alter", SCREEN_W/2, 44,
172 palette_color[255], palette_color[0]);
173 textout_centre_ex(screen, font, "Space to walk", SCREEN_W/2, 68,
174 palette_color[255], palette_color[0]);
175 textout_centre_ex(screen, font, "C to display control points", SCREEN_W/2,
176 92, palette_color[255], palette_color[0]);
177 textout_centre_ex(screen, font, "T to display tangents", SCREEN_W/2, 104,
178 palette_color[255], palette_color[0]);
179
180 for (i=1; i<node_count-2; i++)
181 draw_spline(nodes[i], nodes[i+1]);
182
183 for (i=1; i<node_count-1; i++) {
184 draw_node(i);
185
186 if (show_tangents) {
187 line(screen, nodes[i].x - fixtoi(fixcos(nodes[i].tangent) * 24),
188 nodes[i].y - fixtoi(fixsin(nodes[i].tangent) * 24),
189 nodes[i].x + fixtoi(fixcos(nodes[i].tangent) * 24),
190 nodes[i].y + fixtoi(fixsin(nodes[i].tangent) * 24),
191 palette_color[1]);
192 }
193 }
194
195 release_screen();
196 }
197
198
199
200 /* let the user input a list of path nodes */
input_nodes(void)201 void input_nodes(void)
202 {
203 clear_to_color(screen, makecol(255, 255, 255));
204
205 textout_centre_ex(screen, font, "Click the left mouse button to add path "
206 "nodes", SCREEN_W/2, 8, palette_color[255],
207 palette_color[0]);
208 textout_centre_ex(screen, font, "Right mouse button or any key to finish",
209 SCREEN_W/2, 24, palette_color[255], palette_color[0]);
210
211 node_count = 1;
212
213 show_mouse(screen);
214
215 do {
216 poll_mouse();
217 } while (mouse_b);
218
219 clear_keybuf();
220
221 for (;;) {
222 poll_mouse();
223
224 if (mouse_b & 1) {
225 if (node_count < MAX_NODES-1) {
226 nodes[node_count].x = mouse_x;
227 nodes[node_count].y = mouse_y;
228
229 show_mouse(NULL);
230 draw_node(node_count);
231 show_mouse(screen);
232
233 node_count++;
234 }
235
236 do {
237 poll_mouse();
238 } while (mouse_b & 1);
239 }
240
241 if ((mouse_b & 2) || (keypressed())) {
242 if (node_count < 3)
243 alert("You must enter at least two nodes",
244 NULL, NULL, "OK", NULL, 13, 0);
245 else
246 break;
247 }
248 }
249
250 show_mouse(NULL);
251
252 do {
253 poll_mouse();
254 } while (mouse_b);
255
256 clear_keybuf();
257 }
258
259
260
261 /* moves a sprite along the spline path */
walk(void)262 void walk(void)
263 {
264 #define MAX_POINTS 256
265
266 int points[8];
267 int x[MAX_POINTS], y[MAX_POINTS];
268 int n, i;
269 int npoints;
270 int ox, oy;
271
272 acquire_screen();
273
274 clear_to_color(screen, makecol(255, 255, 255));
275
276 for (i=1; i<node_count-1; i++)
277 draw_node(i);
278
279 release_screen();
280
281 do {
282 poll_mouse();
283 } while (mouse_b);
284
285 clear_keybuf();
286
287 ox = -16;
288 oy = -16;
289
290 xor_mode(TRUE);
291
292 for (n=1; n < node_count-2; n++) {
293 npoints = (fixtoi(node_dist(nodes[n], nodes[n+1]))+3) / 4;
294 if (npoints < 1)
295 npoints = 1;
296 else if (npoints > MAX_POINTS)
297 npoints = MAX_POINTS;
298
299 get_control_points(nodes[n], nodes[n+1], points);
300 calc_spline(points, npoints, x, y);
301
302 for (i=1; i<npoints; i++) {
303 vsync();
304 acquire_screen();
305 circlefill(screen, ox, oy, 6, palette_color[2]);
306 circlefill(screen, x[i], y[i], 6, palette_color[2]);
307 release_screen();
308 ox = x[i];
309 oy = y[i];
310
311 poll_mouse();
312
313 if ((keypressed()) || (mouse_b))
314 goto getout;
315 }
316 }
317
318 getout:
319
320 xor_mode(FALSE);
321
322 do {
323 poll_mouse();
324 } while (mouse_b);
325
326 clear_keybuf();
327 }
328
329
330
331 /* main program */
main(void)332 int main(void)
333 {
334 int c;
335
336 if (allegro_init() != 0)
337 return 1;
338 install_keyboard();
339 install_mouse();
340 install_timer();
341
342 if (set_gfx_mode(GFX_AUTODETECT, 640, 480, 0, 0) != 0) {
343 if (set_gfx_mode(GFX_SAFE, 640, 480, 0, 0) != 0) {
344 set_gfx_mode(GFX_TEXT, 0, 0, 0, 0);
345 allegro_message("Unable to set any graphic mode\n%s\n",
346 allegro_error);
347 return 1;
348 }
349 }
350
351 set_palette(desktop_palette);
352
353 input_nodes();
354 calc_tangents();
355
356 curviness = ftofix(0.25);
357 show_tangents = FALSE;
358 show_control_points = FALSE;
359
360 draw_splines();
361
362 for (;;) {
363 if (keypressed()) {
364 c = readkey() >> 8;
365 if (c == KEY_ESC)
366 break;
367 else if (c == KEY_UP) {
368 curviness += ftofix(0.05);
369 draw_splines();
370 }
371 else if (c == KEY_DOWN) {
372 curviness -= ftofix(0.05);
373 draw_splines();
374 }
375 else if (c == KEY_SPACE) {
376 walk();
377 draw_splines();
378 }
379 else if (c == KEY_T) {
380 show_tangents = !show_tangents;
381 draw_splines();
382 }
383 else if (c == KEY_C) {
384 show_control_points = !show_control_points;
385 draw_splines();
386 }
387 }
388 }
389
390 return 0;
391 }
392
393 END_OF_MAIN()
394