1 /***************************************************************************
2 alienBlaster
3 Copyright (C) 2004
4 Paul Grathwohl, Arne Hormann, Daniel Kuehn, Soenke Schwardt
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 ***************************************************************************/
20 #include "formation.h"
21 #include "enemy.h"
22 #include "enemys.h"
23 #include <iostream>
24
25 using namespace std;
26
Formation(FormationTypes whichFormation,Vector2D centerAtStart,Vector2D startVel,int nrEnemys,FormationEnemySets enemyTypes,int flagsFormationChangePolicy,FormationShotPatterns shotPattern)27 Formation::Formation( FormationTypes whichFormation, Vector2D centerAtStart,
28 Vector2D startVel, int nrEnemys,
29 FormationEnemySets enemyTypes,
30 int flagsFormationChangePolicy,
31 FormationShotPatterns shotPattern ) {
32
33 formationType = whichFormation;
34 formationCenter = centerAtStart;
35 formationSpeed = startVel;
36
37 changeOnKill = flagsFormationChangePolicy & FORMATION_CHANGE_ON_KILL;
38 changeSpontaneous = flagsFormationChangePolicy & FORMATION_CHANGE_SPONTANEOUS;
39 changeOften = flagsFormationChangePolicy & FORMATION_CHANGE_OFTEN;
40 changeSeldom = flagsFormationChangePolicy & FORMATION_CHANGE_SELDOM;
41 if ( changeSpontaneous && !changeSeldom && !changeOften ) changeSeldom = true;
42 if ( changeOften ) {
43 nextFormationChange =
44 FORMATION_CHANGE_OFTEN_DELAY +
45 rand() % (FORMATION_CHANGE_OFTEN_RAND_DELAY+1);
46 } else if ( changeSeldom ) {
47 nextFormationChange =
48 FORMATION_CHANGE_SELDOM_DELAY +
49 rand() % (FORMATION_CHANGE_SELDOM_RAND_DELAY+1);
50 }
51
52 if ( nrEnemys > FORMATION_MAX_NR_ENEMYS[ formationType ] )
53 nrInvolved = FORMATION_MAX_NR_ENEMYS[ formationType ];
54 else if ( nrEnemys < 0 ) nrInvolved = 0;
55 else nrInvolved = nrEnemys;
56
57 this->shotPattern = shotPattern;
58 actShootingEnemy = 0;
59
60 if ( shotPattern == FORMATION_SP_NONE ) formationFires = false;
61 else formationFires = true;
62
63 vector<Vector2D> targetPos;
64 fillTargetPos( targetPos );
65
66 for ( int i = 0; i < nrInvolved; i++ ) {
67 Enemy *newOne;
68 switch ( enemyTypes ) {
69 case FORMATION_ENEMY_SET_DEFAULT:
70 case FORMATION_ENEMY_SET_FIGHTER:
71 {
72 newOne = new Enemy( formationCenter + targetPos[ i ], formationSpeed, FIGHTER,
73 true, formationFires );
74 break;
75 }
76 case FORMATION_ENEMY_SET_BOMBER:
77 {
78 newOne = new Enemy( formationCenter + targetPos[ i ], formationSpeed, BOMBER,
79 true, formationFires );
80 break;
81 }
82 case FORMATION_ENEMY_SET_FIGHTER_BOMBER:
83 {
84 newOne =
85 new Enemy( formationCenter + targetPos[ i ], formationSpeed,
86 (EnemyTypes)(FIGHTER + (i % 2)),
87 true, formationFires );
88 break;
89 }
90 }
91 enemys->addEnemy( newOne );
92 involvedEnemys.push_back( newOne );
93 }
94
95 enemyWasKilled = false;
96 // wait at least 100 ms before the first shot
97 nextFirePrimary = 100;
98 nextFireSecondary = 100;
99
100 // cout << "Type: " << formationType << " SP: " << shotPattern << endl;
101 }
102
~Formation()103 Formation::~Formation() {}
104
105
enemyKilled(Enemy * killedEnemy)106 void Formation::enemyKilled( Enemy *killedEnemy ) {
107 for ( int i = 0; i < nrInvolved; i++ ) {
108 if ( involvedEnemys[i] == killedEnemy ) {
109 enemyWasKilled = true;
110 involvedEnemys.erase( involvedEnemys.begin() + i );
111 nrInvolved--;
112 break;
113 }
114 }
115 }
116
update(int dT)117 void Formation::update( int dT ) {
118 if ( changeSpontaneous ) handleSpontaneousFormationChange( dT );
119
120 if ( enemyWasKilled ) {
121 // change the formation?
122 if ( changeOnKill && (rand() % 100 < 70) ) chooseNewFormationType();
123 moveEnemyInFormation();
124 enemyWasKilled = false;
125 }
126 formationCenter += formationSpeed * dT / 1000.0;
127 shoot( dT );
128 }
129
130
handleSpontaneousFormationChange(int dT)131 void Formation::handleSpontaneousFormationChange( int dT ) {
132 nextFormationChange -= dT;
133 if ( changeSpontaneous && nextFormationChange < 0 ) {
134
135 chooseNewFormationType();
136 moveEnemyInFormation();
137
138 if ( changeOften ) {
139 nextFormationChange =
140 FORMATION_CHANGE_OFTEN_DELAY +
141 rand() % (FORMATION_CHANGE_OFTEN_RAND_DELAY+1);
142 } else if ( changeSeldom ) {
143 nextFormationChange =
144 FORMATION_CHANGE_SELDOM_DELAY +
145 rand() % (FORMATION_CHANGE_SELDOM_RAND_DELAY+1);
146 }
147 }
148 }
149
150
moveEnemyInFormation()151 void Formation::moveEnemyInFormation() {
152 // calc the target positions in the new formation (relative to the center of the formation)
153 vector<Vector2D> targetPos;
154 fillTargetPos( targetPos );
155
156 // choose the best mapping from enemy to targetPosition
157 // (shortest way for enemy to its position is best)
158 vector<Vector2D> relPosForEnemies;
159 getBestMapping( targetPos, relPosForEnemies );
160
161 // give the enemy its order
162 for ( int i = 0; i < nrInvolved; i++ ) {
163 involvedEnemys[i]->setNewRelTargetPos( relPosForEnemies[ i ] );
164 }
165 }
166
167
chooseNewFormationType()168 void Formation::chooseNewFormationType() {
169 bool found = false;
170 int i = 0;
171 while ( i < 10 && !found ) {
172 FormationTypes newFormationType = (FormationTypes)(rand() % (NR_FORMATION_TYPES-1));
173 if ( formationType == newFormationType ) {
174 newFormationType = (FormationTypes)(NR_FORMATION_TYPES - 1);
175 }
176 if ( nrInvolved <= FORMATION_MAX_NR_ENEMYS[ newFormationType ] ) {
177 formationType = newFormationType;
178 found = true;
179 }
180 i++;
181 }
182 }
183
184
fillTargetPos(vector<Vector2D> & targetPos)185 void Formation::fillTargetPos( vector<Vector2D> &targetPos ) {
186 switch ( formationType ) {
187 case FORMATION_V:
188 {
189 fillTargetPosFormationV( targetPos );
190 break;
191 }
192 case FORMATION_REVERSE_V:
193 {
194 fillTargetPosFormationReverseV( targetPos );
195 break;
196 }
197 case FORMATION_BLOCK:
198 {
199 fillTargetPosFormationBlock( targetPos );
200 break;
201 }
202 case FORMATION_LINE:
203 {
204 fillTargetPosFormationLine( targetPos );
205 break;
206 }
207 default:
208 {
209 for ( int i = 0; i < nrInvolved; i++ ) {
210 targetPos.push_back( Vector2D(0,0) );
211 }
212 break;
213 }
214 }
215 }
216
217
fillTargetPosFormationV(vector<Vector2D> & targetPos)218 void Formation::fillTargetPosFormationV( vector<Vector2D> &targetPos ) {
219 switch ( nrInvolved ) {
220 case 1:
221 {
222 targetPos.push_back( Vector2D(0,0) );
223 break;
224 }
225 case 2:
226 {
227 targetPos.push_back( Vector2D(-30,0) );
228 targetPos.push_back( Vector2D(30,0) );
229 break;
230 }
231 case 3:
232 {
233 targetPos.push_back( Vector2D(-50,25) );
234 targetPos.push_back( Vector2D(0,-25) );
235 targetPos.push_back( Vector2D(50,25) );
236 break;
237 }
238 case 4:
239 {
240 targetPos.push_back( Vector2D(-80,25) );
241 targetPos.push_back( Vector2D(-30,-25) );
242 targetPos.push_back( Vector2D(30,-25) );
243 targetPos.push_back( Vector2D(80,25) );
244 break;
245 }
246 case 5:
247 {
248 targetPos.push_back( Vector2D(-100,50) );
249 targetPos.push_back( Vector2D(-50,0) );
250 targetPos.push_back( Vector2D(0,-50) );
251 targetPos.push_back( Vector2D(50,0) );
252 targetPos.push_back( Vector2D(100,50) );
253 break;
254 }
255 case 6:
256 {
257 targetPos.push_back( Vector2D(-130,50) );
258 targetPos.push_back( Vector2D(-80,0) );
259 targetPos.push_back( Vector2D(-30,-50) );
260 targetPos.push_back( Vector2D(30,-50) );
261 targetPos.push_back( Vector2D(80,0) );
262 targetPos.push_back( Vector2D(130,50) );
263 break;
264 }
265 case 7:
266 {
267 targetPos.push_back( Vector2D(-150,75) );
268 targetPos.push_back( Vector2D(-100,25) );
269 targetPos.push_back( Vector2D(-50,-25) );
270 targetPos.push_back( Vector2D(0,-75) );
271 targetPos.push_back( Vector2D(50,-25) );
272 targetPos.push_back( Vector2D(100,25) );
273 targetPos.push_back( Vector2D(150,75) );
274 break;
275 }
276 default:
277 {
278 cout << "fillTargetPosFormationV: too many enemys involved: " << nrInvolved << endl;
279 for ( int i = 0; i < nrInvolved; i++ ) {
280 targetPos.push_back( Vector2D(0,0) );
281 }
282 break;
283 }
284 }
285 }
286
287
fillTargetPosFormationReverseV(vector<Vector2D> & targetPos)288 void Formation::fillTargetPosFormationReverseV( vector<Vector2D> &targetPos ) {
289 switch ( nrInvolved ) {
290 case 1:
291 {
292 targetPos.push_back( Vector2D(0,0) );
293 break;
294 }
295 case 2:
296 {
297 targetPos.push_back( Vector2D(-30,0) );
298 targetPos.push_back( Vector2D(30,0) );
299 break;
300 }
301 case 3:
302 {
303 targetPos.push_back( Vector2D(-50,-25) );
304 targetPos.push_back( Vector2D(0,25) );
305 targetPos.push_back( Vector2D(50,-25) );
306 break;
307 }
308 case 4:
309 {
310 targetPos.push_back( Vector2D(-80,-25) );
311 targetPos.push_back( Vector2D(-30,25) );
312 targetPos.push_back( Vector2D(30,25) );
313 targetPos.push_back( Vector2D(80,-25) );
314 break;
315 }
316 case 5:
317 {
318 targetPos.push_back( Vector2D(-100,-50) );
319 targetPos.push_back( Vector2D(-50,0) );
320 targetPos.push_back( Vector2D(0,50) );
321 targetPos.push_back( Vector2D(50,0) );
322 targetPos.push_back( Vector2D(100,-50) );
323 break;
324 }
325 case 6:
326 {
327 targetPos.push_back( Vector2D(-130,-50) );
328 targetPos.push_back( Vector2D(-80,0) );
329 targetPos.push_back( Vector2D(-30,50) );
330 targetPos.push_back( Vector2D(30,50) );
331 targetPos.push_back( Vector2D(80,0) );
332 targetPos.push_back( Vector2D(130,-50) );
333 break;
334 }
335 case 7:
336 {
337 targetPos.push_back( Vector2D(-150,-75) );
338 targetPos.push_back( Vector2D(-100,-25) );
339 targetPos.push_back( Vector2D(-50,25) );
340 targetPos.push_back( Vector2D(0,75) );
341 targetPos.push_back( Vector2D(50,25) );
342 targetPos.push_back( Vector2D(100,-25) );
343 targetPos.push_back( Vector2D(150,-75) );
344 break;
345 }
346 default:
347 {
348 cout << "fillTargetPosFormationReverseV: too many enemys involved: "
349 << nrInvolved << endl;
350 for ( int i = 0; i < nrInvolved; i++ ) {
351 targetPos.push_back( Vector2D(0,0) );
352 }
353 break;
354 }
355 }
356 }
357
358
fillTargetPosFormationBlock(vector<Vector2D> & targetPos)359 void Formation::fillTargetPosFormationBlock( vector<Vector2D> &targetPos ) {
360 switch ( nrInvolved ) {
361 case 1:
362 {
363 targetPos.push_back( Vector2D(0,0) );
364 break;
365 }
366 case 2:
367 {
368 targetPos.push_back( Vector2D(-30,0) );
369 targetPos.push_back( Vector2D(30,0) );
370 break;
371 }
372 case 3:
373 {
374 targetPos.push_back( Vector2D(-30,25) );
375 targetPos.push_back( Vector2D(0,-25) );
376 targetPos.push_back( Vector2D(30,25) );
377 break;
378 }
379 case 4:
380 {
381 targetPos.push_back( Vector2D(-30,-25) );
382 targetPos.push_back( Vector2D(-30,25) );
383 targetPos.push_back( Vector2D(30,-25) );
384 targetPos.push_back( Vector2D(30,25) );
385 break;
386 }
387 case 5:
388 {
389 targetPos.push_back( Vector2D(-40,-30) );
390 targetPos.push_back( Vector2D(-40,30) );
391 targetPos.push_back( Vector2D(0,0) );
392 targetPos.push_back( Vector2D(40,-30) );
393 targetPos.push_back( Vector2D(40,30) );
394 break;
395 }
396 case 6:
397 {
398 targetPos.push_back( Vector2D(-60,-30) );
399 targetPos.push_back( Vector2D(-60,30) );
400 targetPos.push_back( Vector2D(0,-30) );
401 targetPos.push_back( Vector2D(0,30) );
402 targetPos.push_back( Vector2D(60,-30) );
403 targetPos.push_back( Vector2D(60,30) );
404 break;
405 }
406 case 7:
407 {
408 targetPos.push_back( Vector2D(-60,-50) );
409 targetPos.push_back( Vector2D(-60,0) );
410 targetPos.push_back( Vector2D(0,-50) );
411 targetPos.push_back( Vector2D(0,0) );
412 targetPos.push_back( Vector2D(0,50) );
413 targetPos.push_back( Vector2D(60,-50) );
414 targetPos.push_back( Vector2D(60,0) );
415 break;
416 }
417 default:
418 {
419 cout << "fillTargetPosFormationBlock: too many enemys involved: " << nrInvolved << endl;
420 for ( int i = 0; i < nrInvolved; i++ ) {
421 targetPos.push_back( Vector2D(0,0) );
422 }
423 break;
424 }
425 }
426 }
427
428
fillTargetPosFormationLine(vector<Vector2D> & targetPos)429 void Formation::fillTargetPosFormationLine( vector<Vector2D> &targetPos ) {
430 switch ( nrInvolved ) {
431 case 1:
432 {
433 targetPos.push_back( Vector2D(0,0) );
434 break;
435 }
436 case 2:
437 {
438 targetPos.push_back( Vector2D(-30,0) );
439 targetPos.push_back( Vector2D(30,0) );
440 break;
441 }
442 case 3:
443 {
444 targetPos.push_back( Vector2D(-60,0) );
445 targetPos.push_back( Vector2D(0,0) );
446 targetPos.push_back( Vector2D(60,0) );
447 break;
448 }
449 case 4:
450 {
451 targetPos.push_back( Vector2D(-90,0) );
452 targetPos.push_back( Vector2D(-30,0) );
453 targetPos.push_back( Vector2D(30,0) );
454 targetPos.push_back( Vector2D(90,0) );
455 break;
456 }
457 case 5:
458 {
459 targetPos.push_back( Vector2D(-120,0) );
460 targetPos.push_back( Vector2D(-60,0) );
461 targetPos.push_back( Vector2D(0,0) );
462 targetPos.push_back( Vector2D(60,0) );
463 targetPos.push_back( Vector2D(120,0) );
464 break;
465 }
466 case 6:
467 {
468 targetPos.push_back( Vector2D(-150,0) );
469 targetPos.push_back( Vector2D(-90,0) );
470 targetPos.push_back( Vector2D(-30,0) );
471 targetPos.push_back( Vector2D(30,0) );
472 targetPos.push_back( Vector2D(90,0) );
473 targetPos.push_back( Vector2D(150,0) );
474 break;
475 }
476 default:
477 {
478 cout << "fillTargetPosFormationLine: too many enemys involved: " << nrInvolved << endl;
479 for ( int i = 0; i < nrInvolved; i++ ) {
480 targetPos.push_back( Vector2D(0,0) );
481 }
482 break;
483 }
484 }
485 }
486
487
488
489
490 ///////////////////////////////////////////////
491
492
getBestMapping(vector<Vector2D> & targetPos,vector<Vector2D> & relPosForFighters)493 void Formation::getBestMapping( vector<Vector2D> &targetPos,
494 vector<Vector2D> &relPosForFighters ) {
495
496 int actPerm[nrInvolved];
497 vector<Vector2D> *bestMapping = new vector<Vector2D>();
498 vector<Vector2D> *testMapping = new vector<Vector2D>();
499 for ( int i = 0; i < nrInvolved; i++ ) {
500 bestMapping->push_back( Vector2D( 0,0 ) );
501 testMapping->push_back( Vector2D( 0,0 ) );
502 actPerm[ i ] = i;
503 }
504 float mapCost = 1000000;
505
506 int nrPerm = factorial( nrInvolved );
507
508 for ( int perm = 0; perm < nrPerm; perm++ ) {
509 calcNextPerm( actPerm );
510 float testMappingCost = calcTestMapping( actPerm, targetPos, testMapping );
511 if ( mapCost > testMappingCost ) {
512 vector<Vector2D> *tmpMapping = bestMapping;
513 bestMapping = testMapping;
514 testMapping = tmpMapping;
515 mapCost = testMappingCost;
516 }
517 }
518
519 for ( int e = 0; e < nrInvolved; e++ ) {
520 relPosForFighters.push_back( (*bestMapping)[e] );
521 }
522 delete bestMapping;
523 delete testMapping;
524 }
525
526
calcNextPerm(int * perm)527 void Formation::calcNextPerm( int *perm ) {
528 int n = nrInvolved;
529 int i = n-1;
530 int j = n;
531 int tmp;
532
533 while ( i != 0 && perm[ i-1 ] >= perm[ i ] ) {
534 i--;
535 }
536 if ( i == 0 ) {
537 for ( int k = 0; k < n/2; k++ ) {
538 tmp = perm[ k ];
539 perm[ k ] = perm[ n - k - 1 ];
540 perm[ n - k - 1 ] = tmp;
541 }
542 return;
543 }
544 while ( perm[ j-1 ] <= perm[ i-1 ] ) {
545 --j;
546 }
547 tmp = perm[ i-1 ];
548 perm[ i-1 ] = perm[ j-1 ];
549 perm[ j-1 ] = tmp;
550
551 i++;
552 j = n;
553
554 while ( i < j ) {
555 tmp = perm[ i-1 ];
556 perm[ i-1 ] = perm[ j-1 ];
557 perm[ j-1 ] = tmp;
558 i++;
559 j--;
560 }
561 }
562
563
calcTestMapping(int * perm,vector<Vector2D> & targetPos,vector<Vector2D> * mapping)564 float Formation::calcTestMapping( int *perm, vector<Vector2D> &targetPos,
565 vector<Vector2D> *mapping ) {
566
567 float cost = 0;
568
569 for ( int i = 0; i < nrInvolved; i++ ) {
570 // enemy i shall fly to the position targetPos[perm[i]]
571 // save the vector from its actual pos to its new targetpos in mapping
572 (*mapping)[ i ] =
573 targetPos[ perm[i] ] + formationCenter -
574 involvedEnemys[ i ]->getPos();
575
576 if ( cost < (*mapping)[ i ].getLength() ) {
577 cost = (*mapping)[ i ].getLength();
578 }
579 }
580 return cost;
581 }
582
583
factorial(int n)584 int Formation::factorial( int n ) {
585 int result = 1;
586 for ( int i = 2; i <= n; i++ ) {
587 result *= i;
588 }
589 return result;
590 }
591
592
593
shoot(int dT)594 void Formation::shoot( int dT ) {
595 if ( shotPattern == FORMATION_SP_NONE ) return;
596 nextFirePrimary -= dT;
597 // nextFireSecondary -= dT;
598
599 float enemyRatio = FORMATION_MAX_NR_ENEMYS[ formationType ] / (float)nrInvolved;
600
601 while ( nextFirePrimary < 0 ) {
602 switch ( shotPattern ) {
603 case FORMATION_SP_VOLLEY_FAST:
604 case FORMATION_SP_VOLLEY_MEDIUM:
605 case FORMATION_SP_VOLLEY_SLOW:
606 {
607 for ( int i = 0; i < nrInvolved; i++ ) {
608 involvedEnemys[ i ]->firePrimary();
609 }
610 break;
611 }
612 case FORMATION_SP_RAND_FAST:
613 case FORMATION_SP_RAND_MEDIUM:
614 case FORMATION_SP_RAND_SLOW:
615 {
616 involvedEnemys[ rand() % nrInvolved ]->firePrimary();
617 break;
618 }
619 case FORMATION_SP_LEFT_RIGHT_FAST:
620 case FORMATION_SP_LEFT_RIGHT_MEDIUM:
621 {
622 actShootingEnemy = (actShootingEnemy + 1) % nrInvolved;
623 involvedEnemys[ actShootingEnemy ]->firePrimary();
624 break;
625 }
626 case FORMATION_SP_RIGHT_LEFT_FAST:
627 case FORMATION_SP_RIGHT_LEFT_MEDIUM:
628 {
629 actShootingEnemy--;
630 if ( actShootingEnemy < 0 ) actShootingEnemy = nrInvolved-1;
631 involvedEnemys[ actShootingEnemy ]->firePrimary();
632 break;
633 }
634 default:
635 {
636 break;
637 }
638 }
639
640 nextFirePrimary +=
641 lroundf( (FORMATION_SP_PRIMARY_DELAY[ shotPattern ] +
642 rand() % (FORMATION_SP_PRIMARY_RAND_DELAY[ shotPattern ] + 1)) * enemyRatio );
643 }
644 }
645
646