Debian Codegraph @

engine/unit/unit_find.cpp

raw
1 // ____ _ __
2 // / __ )____ _____ | | / /___ ___________
3 // / __ / __ \/ ___/ | | /| / / __ `/ ___/ ___/
4 // / /_/ / /_/ (__ ) | |/ |/ / /_/ / / (__ )
5 // /_____/\____/____/ |__/|__/\__,_/_/ /____/
6 //
7 // A futuristic real-time strategy game.
8 // This file is part of Bos Wars.
9 //
10 /**@name unit_find.cpp - The find/select for units. */
11 //
12 // (c) Copyright 1998-2008 by Lutz Sammer and Jimmy Salmon
13 //
14 // This program is free software; you can redistribute it and/or modify
15 // it under the terms of the GNU General Public License as published by
16 // the Free Software Foundation; only version 2 of the License.
17 //
18 // This program is distributed in the hope that it will be useful,
19 // but WITHOUT ANY WARRANTY; without even the implied warranty of
20 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 // GNU General Public License for more details.
22 //
23 // You should have received a copy of the GNU General Public License
24 // along with this program; if not, write to the Free Software
25 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
26 // 02111-1307, USA.
27 //
28
29 //@{
30
31 /*----------------------------------------------------------------------------
32 -- Includes
33 ----------------------------------------------------------------------------*/
34
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <assert.h>
38 #include <limits.h>
39
40 #include "stratagus.h"
41 #include "video.h"
42 #include "sound.h"
43 #include "unitsound.h"
44 #include "unittype.h"
45 #include "actions.h"
46 #include "player.h"
47 #include "missile.h"
48 #include "unit.h"
49 #include "unit_cache.h"
50 #include "interface.h"
51 #include "map.h"
52 #include "pathfinder.h"
53
54 /*----------------------------------------------------------------------------
55 -- Defines
56 ----------------------------------------------------------------------------*/
57
58 /*
59 ** Configuration of the small (unit) AI.
60 */
61 #define PRIORITY_FACTOR 0x00010000
62 #define HEALTH_FACTOR 0x00000001
63 #define DISTANCE_FACTOR 0x00100000
64 #define INRANGE_FACTOR 0x00010000
65 #define INRANGE_BONUS 0x01000000
66 #define CANATTACK_BONUS 0x00100000
67
68 /*----------------------------------------------------------------------------
69 -- Local Data
70 ----------------------------------------------------------------------------*/
71
72 /*----------------------------------------------------------------------------
73 -- Functions
74 ----------------------------------------------------------------------------*/
75
76 /**
77 ** Find all units of type.
78 **
79 ** @param type type of unit requested
80 ** @param table table in which we have to store the units
81 ** @param tablesize size of table array
82 **
83 ** @return Returns the number of units found.
84 */
85 int FindUnitsByType(const CUnitType *type, CUnit **table, int tablesize)
86 {
87 int num = 0;
88
89 for (int i = 0; i < NumUnits && num < tablesize; ++i) {
90 CUnit *unit = Units[i];
91 if (unit->Type == type && !unit->IsUnusable()) {
92 table[num++] = unit;
93 }
94 }
95 return num;
96 }
97
98 /**
99 ** Find all units of type.
100 **
101 ** @param player we're looking for the units of this player
102 ** @param type type of unit requested
103 ** @param table table in which we have to store the units
104 ** @param tablesize size of table array
105 **
106 ** @return Returns the number of units found.
107 */
108 int FindPlayerUnitsByType(const CPlayer *player, const CUnitType *type,
109 CUnit **table, int tablesize)
110 {
111 int nunits = player->TotalNumUnits;
112 int typecount = player->UnitTypesCount[type->Slot];
113 int num = 0;
114
115 for (int i = 0; i < nunits && typecount && num < tablesize; ++i) {
116 CUnit *unit = player->Units[i];
117 if (unit->Type == type) {
118 if (!unit->IsUnusable()) {
119 table[num++] = unit;
120 }
121 --typecount;
122 }
123 }
124 return num;
125 }
126
127 /**
128 ** Unit on map tile.
129 **
130 ** @param tx X position on map, tile-based.
131 ** @param ty Y position on map, tile-based.
132 ** @param type UnitTypeType, (unsigned)-1 for any type.
133 **
134 ** @return Returns first found unit on tile.
135 */
136 CUnit *UnitOnMapTile(int tx, int ty, unsigned type)
137 {
138 CUnit *table[UnitMax];
139 int n;
140
141 n = UnitCache.Select(tx, ty, table, UnitMax);
142 for (int i = 0; i < n; ++i) {
143 // Note: this is less restrictive than UnitActionDie...
144 // Is it normal?
145 if (table[i]->Type->Vanishes) {
146 continue;
147 }
148 if (type != (unsigned)-1 && (unsigned)table[i]->Type->UnitType != type) {
149 continue;
150 }
151 return table[i];
152 }
153
154 return NoUnitP;
155 }
156
157 /**
158 ** Choose target on map area.
159 **
160 ** @param source Unit which want to attack.
161 ** @param x1 X position on map, tile-based.
162 ** @param y1 Y position on map, tile-based.
163 ** @param x2 X position on map, tile-based.
164 ** @param y2 Y position on map, tile-based.
165 **
166 ** @return Returns ideal target on map tile.
167 */
168 CUnit *TargetOnMap(const CUnit *source, int x1, int y1, int x2, int y2)
169 {
170 CUnit *table[UnitMax];
171 CUnit *best = NoUnitP;
172 int n;
173
174 n = UnitCache.Select(x1, y1, x2, y2, table, UnitMax);
175 for (int i = 0; i < n; ++i) {
176 CUnit *unit = table[i];
177 if (!unit->IsVisibleAsGoal(source->Player)) {
178 continue;
179 }
180 if (x2 < unit->X || x1 >= unit->X + unit->Type->TileWidth ||
181 y2 < unit->Y || y1 >= unit->Y + unit->Type->TileHeight) {
182 continue;
183 }
184 if (!CanTarget(source->Type, unit->Type)) {
185 continue;
186 }
187
188 //
189 // Choose the best target.
190 //
191 if (!best || best->Type->Priority < unit->Type->Priority) {
192 best = unit;
193 }
194 }
195 return best;
196 }
197
198 /*----------------------------------------------------------------------------
199 -- Finding special units
200 ----------------------------------------------------------------------------*/
201
202 /**
203 ** Resource on map tile
204 **
205 ** @param tx X position on map, tile-based.
206 ** @param ty Y position on map, tile-based.
207 ** @param resource Resource number or -1 for any.
208 **
209 ** @return Returns the resource if found, or NoUnitP.
210 */
211 CUnit *ResourceOnMap(int tx, int ty, int resource)
212 {
213 CUnit *table[UnitMax];
214 int n;
215
216 n = UnitCache.Select(tx, ty, table, UnitMax);
217 for (int i = 0; i < n; ++i) {
218 if (table[i]->IsUnusable() || !table[i]->Type->CanHarvestFrom) {
219 continue;
220 }
221 if (resource == -1) {
222 if (!UnitHoldsResources(table[i])) {
223 continue;
224 }
225 } else {
226 if (table[i]->ResourcesHeld[resource] == 0) {
227 continue;
228 }
229 }
230 return table[i];
231 }
232 return NoUnitP;
233 }
234
235 /*----------------------------------------------------------------------------
236 -- Finding units for attack
237 ----------------------------------------------------------------------------*/
238
239 /**
240 ** Attack units in distance, with large missile
241 **
242 ** Choose the best target, that can be attacked. It takes into
243 ** account allied unit which could be hit by the missile
244 **
245 ** @param u Find in distance for this unit.
246 ** @param range Distance range to look.
247 **
248 ** @return Unit to be attacked.
249 **
250 ** @note This could be improved, for better performance / better trade.
251 ** @note Limited to attack range smaller than 16.
252 ** @note Will be moved to unit_ai.c soon.
253 */
254 static CUnit *FindRangeAttack(const CUnit *u, int range)
255 {
256 int x;
257 int y;
258 int n;
259 int cost;
260 int d;
261 int effective_hp;
262 int enemy_count;
263 int missile_range;
264 int attackrange;
265 int hp_damage_evaluate;
266 int good[32][32];
267 int bad[32][32];
268 CUnit *table[UnitMax];
269 CUnit *dest;
270 const CUnitType *dtype;
271 const CUnitType *type;
272 const CPlayer *player;
273 int xx;
274 int yy;
275 int best_cost;
276 int i;
277 int sbad;
278 int sgood;
279 CUnit *best;
280
281 type = u->Type;
282 player = u->Player;
283
284 // If catapult, count units near the target...
285 // FIXME : make it configurable
286 //
287
288 missile_range = type->Missile.Missile->Range + range - 1;
289 attackrange = u->Stats->Variables[ATTACKRANGE_INDEX].Max;
290 // Evaluation of possible damage...
291 hp_damage_evaluate = u->Stats->Variables[BASICDAMAGE_INDEX].Value
292 + u->Stats->Variables[PIERCINGDAMAGE_INDEX].Value;
293
294 Assert(2 * missile_range + 1 < 32);
295
296 //
297 // If unit is removed, use containers x and y
298 if (u->Removed) {
299 x = u->Container->X;
300 y = u->Container->Y;
301 n = UnitCache.Select(x - missile_range, y - missile_range,
302 x + missile_range + u->Container->Type->TileWidth,
303 y + missile_range + u->Container->Type->TileHeight, table, UnitMax);
304 } else {
305 x = u->X;
306 y = u->Y;
307 n = UnitCache.Select(x - missile_range, y - missile_range,
308 x + missile_range + u->Type->TileWidth,
309 y + missile_range + u->Type->TileHeight, table, UnitMax);
310 }
311
312 if (!n) {
313 return NoUnitP;
314 }
315
316 for (y = 0; y < 2 * missile_range + 1; ++y) {
317 for (x = 0; x < 2 * missile_range + 1; ++x) {
318 good[y][x] = 0;
319 bad[y][x] = 0;
320 }
321 }
322
323 enemy_count = 0;
324 // FILL good/bad...
325 for (i = 0; i < n; ++i) {
326 dest = table[i];
327 dtype = dest->Type;
328 if (!dest->IsVisibleAsGoal(u->Player)) {
329 table[i] = 0;
330 continue;
331 }
332
333 // won't be a target...
334 if (!CanTarget(type, dtype)) { // can't be attacked.
335 table[i] = 0;
336 continue;
337 }
338
339 if (!player->IsEnemy(dest)) { // a friend or neutral
340 table[i] = 0;
341
342 // Calc a negative cost
343 // The gost is more important when the unit would be killed
344 // by our fire.
345
346 // It costs (is positive) if hp_damage_evaluate>dest->HP ...)
347 // FIXME : assume that PRIORITY_FACTOR>HEALTH_FACTOR
348 cost = HEALTH_FACTOR * (2 * hp_damage_evaluate - dest->Variable[HP_INDEX].Value) /
349 (dtype->TileWidth * dtype->TileWidth);
350 if (cost < 1) {
351 cost = 1;
352 }
353 cost = (-cost);
354 } else {
355 //
356 // Calculate the costs to attack the unit.
357 // Unit with the smallest attack costs will be taken.
358 //
359 cost = 0;
360 //
361 // Priority 0-255
362 //
363 cost += dtype->Priority * PRIORITY_FACTOR;
364 //
365 // Remaining HP (Health) 0-65535
366 //
367 // Give a boost to unit we can kill in one shoot only
368
369 //
370 // calculate HP which will remain in the enemy unit, after hit
371 //
372 effective_hp = (dest->Variable[HP_INDEX].Value - 2 * hp_damage_evaluate);
373
374 //
375 // Unit we won't kill are evaluated the same
376 //
377 if (effective_hp > 0) {
378 effective_hp = 0;
379 }
380
381 //
382 // Unit we are sure to kill are all evaluated the same (except PRIORITY)
383 //
384 if (effective_hp < -hp_damage_evaluate) {
385 effective_hp = -hp_damage_evaluate;
386 }
387
388 //
389 // Here, effective_hp vary from -hp_damage_evaluate (unit will be killed) to 0 (unit can't be killed)
390 // => we prefer killing rather than only hitting...
391 //
392 cost += -effective_hp * HEALTH_FACTOR;
393
394 //
395 // Unit can attack back.
396 //
397 if (CanTarget(dtype, type)) {
398 cost += CANATTACK_BONUS;
399 }
400
401 //
402 // the cost may be divided accros multiple cells
403 //
404 cost = cost / (dtype->TileWidth * dtype->TileWidth);
405 if (cost < 1) {
406 cost = 1;
407 }
408
409 //
410 // Removed Unit's are in bunkers
411 //
412 if (u->Removed) {
413 d = MapDistanceBetweenUnits(u->Container, dest);
414 } else {
415 d = MapDistanceBetweenUnits(u, dest);
416 }
417
418 if (d <= attackrange || (d <= range && UnitReachable(u, dest, attackrange))) {
419 ++enemy_count;
420 } else {
421 table[i] = 0;
422 }
423 }
424
425 x = dest->X - u->X + missile_range + 1;
426 y = dest->Y - u->Y + missile_range + 1;
427
428 // Mark the good/bad array...
429 for (xx = 0; xx < dtype->TileWidth; ++xx) {
430 for (yy = 0; yy < dtype->TileWidth; ++yy) {
431 if ((x + xx < 0) || (y + yy < 0) ||
432 (x + xx >= 2 * missile_range + 1) ||
433 (y + yy >= 2 * missile_range + 1)) {
434 continue;
435 }
436 if (cost < 0) {
437 good[y + yy][x + xx] -= cost;
438 } else {
439 bad[y + yy][x + xx] += cost;
440 }
441 }
442 }
443 }
444
445 if (!enemy_count) {
446 return NoUnitP;
447 }
448
449 // Find the best area...
450 // The target which provide the best bad/good ratio is choosen...
451 best_cost = -1;
452 best = NoUnitP;
453 for (i = 0; i < n; ++i) {
454 if (!table[i]) {
455 continue;
456 }
457 dest = table[i];
458 dtype = dest->Type;
459
460 // put in x-y the real point which will be hit...
461 // (only meaningful when dtype->TileWidth > 1)
462 if (u->X < dest->X) {
463 x = dest->X;
464 } else if (u->X > dest->X + dtype->TileWidth - 1) {
465 x = dest->X + dtype->TileWidth - 1;
466 } else {
467 x = u->X;
468 }
469
470 if (u->Y < dest->Y) {
471 y = dest->Y;
472 } else if (u->Y > dest->Y + dtype->TileHeight - 1) {
473 y = dest->Y + dtype->TileHeight - 1;
474 } else {
475 y = u->Y;
476 }
477
478 // Make x,y relative to u->x...
479 x = x - u->X + missile_range + 1;
480 y = y - u->Y + missile_range + 1;
481
482 sbad = 0;
483 sgood = 0;
484 for (yy = -(type->Missile.Missile->Range - 1);
485 yy <= type->Missile.Missile->Range - 1; ++yy) {
486 for (xx = -(type->Missile.Missile->Range - 1);
487 xx <= type->Missile.Missile->Range - 1; ++xx) {
488 if ((x + xx < 0) || (y + yy < 0) ||
489 ((x + xx) >= 2 * missile_range + 1) ||
490 ((y + yy) >= 2 * missile_range + 1)) {
491 continue;
492 }
493
494 sbad += bad[y + yy][x + xx];
495 sgood += good[y + yy][x + xx];
496 if (!yy && !xx) {
497 sbad += bad[y + yy][x + xx];
498 sgood += good[y + yy][x + xx];
499 }
500 }
501 }
502
503 // don't consider small damages...
504 if (sgood < 20) {
505 sgood = 20;
506 }
507
508 cost = sbad / sgood;
509 if (cost > best_cost) {
510 best_cost = cost;
511 best = dest;
512 }
513 }
514 return best;
515 }
516
517 /**
518 ** Reference unit used by CompareUnitDistance.
519 */
520 static const CUnit *referenceunit;
521
522 /**
523 ** Returns a value less then 0, 0 or bigger then 0,
524 ** when the first unit is repectively nearer, at the same distance
525 ** or further away then the 2nd from the referenceunit.
526 */
527 static int CompareUnitDistance(const void *v1, const void *v2)
528 {
529 CUnit *c1 = *(CUnit **)v1;
530 CUnit *c2 = *(CUnit **)v2;
531
532 int d1 = MapDistanceBetweenUnits(referenceunit, c1);
533 int d2 = MapDistanceBetweenUnits(referenceunit, c2);
534
535 if (d1 - d2 != 0) {
536 return d1 - d2;
537 } else {
538 return c1->Slot - c2->Slot;
539 }
540 }
541
542
543 /**
544 ** Attack units in distance.
545 **
546 ** If the unit can attack must be handled by caller.
547 ** Choose the best target, that can be attacked.
548 **
549 ** @param unit Find in distance for this unit.
550 ** @param range Distance range to look.
551 **
552 ** @return Unit to be attacked.
553 **
554 */
555 CUnit *AttackUnitsInDistance(const CUnit *unit, int range)
556 {
557 CUnit *dest;
558 const CUnitType *type;
559 const CUnitType *dtype;
560 CUnit *table[UnitMax];
561 int x;
562 int y;
563 int n;
564 int i;
565 int d;
566 int attackrange;
567 int cost;
568 int best_cost;
569 const CPlayer *player;
570 CUnit *best_unit;
571
572 // if necessary, take possible damage on allied units into account...
573 if (unit->Type->Missile.Missile->Range > 1 &&
574 (range + unit->Type->Missile.Missile->Range < 15)) {
575 return FindRangeAttack(unit, range);
576 }
577
578 //
579 // Select all units in range.
580 //
581 x = unit->X;
582 y = unit->Y;
583 type = unit->Type;
584 n = UnitCache.Select(x - range, y - range, x + range + type->TileWidth,
585 y + range + type->TileHeight, table, UnitMax);
586
587 if (range > 25 && n > 9) {
588 referenceunit = unit;
589 qsort((void*)table, n, sizeof(CUnit*), &CompareUnitDistance);
590 }
591
592 best_unit = NoUnitP;
593 best_cost = INT_MAX;
594
595 player = unit->Player;
596 attackrange = unit->Stats->Variables[ATTACKRANGE_INDEX].Max;
597
598 //
599 // Find the best unit to attack
600 //
601
602 for (i = 0; i < n; ++i) {
603 dest = table[i];
604
605 if (!dest->IsVisibleAsGoal(unit->Player)) {
606 continue;
607 }
608
609 if (!player->IsEnemy(dest)) { // a friend or neutral
610 continue;
611 }
612
613 dtype = dest->Type;
614 if (!CanTarget(type, dtype)) { // can't be attacked.
615 continue;
616 }
617
618 //
619 // Calculate the costs to attack the unit.
620 // Unit with the smallest attack costs will be taken.
621 //
622 cost = 0;
623 //
624 // Priority 0-255
625 //
626 cost -= dtype->Priority * PRIORITY_FACTOR;
627 //
628 // Remaining HP (Health) 0-65535
629 //
630 cost += dest->Variable[HP_INDEX].Value * HEALTH_FACTOR;
631 //
632 // Unit in attack range?
633 //
634 d = MapDistanceBetweenUnits(unit, dest);
635
636 // Use Circle, not square :)
637 if (d > range) {
638 continue;
639 }
640 if (d <= attackrange && d >= type->MinAttackRange) {
641 cost += d * INRANGE_FACTOR;
642 cost -= INRANGE_BONUS;
643 } else {
644 cost += d * DISTANCE_FACTOR;
645 }
646 //
647 // Unit can attack back.
648 //
649 if (CanTarget(dtype, type)) {
650 cost -= CANATTACK_BONUS;
651 }
652
653 //
654 // Take this target?
655 //
656 if (cost < best_cost && (d <= attackrange ||
657 UnitReachable(unit, dest, attackrange))) {
658 best_unit = dest;
659 best_cost = cost;
660 }
661 }
662
663 return best_unit;
664 }
665
666 /**
667 ** Attack units in attack range.
668 **
669 ** @param unit Find unit in attack range for this unit.
670 **
671 ** @return Pointer to unit which should be attacked.
672 */
673 CUnit *AttackUnitsInRange(const CUnit *unit)
674 {
675 Assert(unit->Type->CanAttack);
676 return AttackUnitsInDistance(unit, unit->Stats->Variables[ATTACKRANGE_INDEX].Max);
677 }
678
679 /**
680 ** Attack units in reaction range.
681 **
682 ** @param unit Find unit in reaction range for this unit.
683 **
684 ** @return Pointer to unit which should be attacked.
685 */
686 CUnit *AttackUnitsInReactRange(const CUnit *unit)
687 {
688 int range;
689
690 Assert(unit->Type->CanAttack);
691
692 if (unit->Player->Type == PlayerPerson) {
693 range = unit->Type->ReactRangePerson;
694 } else {
695 range = unit->Type->ReactRangeComputer;
696 }
697
698 return AttackUnitsInDistance(unit, range);
699 }
700
701 //@}