Simple tower defense tutorial, part 3
Let's first have a look at the last state of the game from the previous part:
The goal of this part is to add obstacles and path finding for the enemies.
Obstacles
We begin with adding obstacles to the game. In most tower defense games, there's a fixed path that the enemies follow. In other cases, the player can block the path with towers.
Since we want to be a little innovative, we'll add destructible obstacles that the player can build. The enemies will then try to find a path around these obstacles, but if there's no way around, they will try to destroy the obstacle. This is way more hardcore than most such games, but it's a fun challenge to implement.
We'll thus create now a new tower type "wall" and draw it as solid blocks:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 typedef struct GameTime
7 {
8 float time;
9 float deltaTime;
10 } GameTime;
11
12 GameTime gameTime = {0};
13
14 //# Enemies
15
16 #define ENEMY_MAX_PATH_COUNT 8
17 #define ENEMY_MAX_COUNT 400
18 #define ENEMY_TYPE_NONE 0
19 #define ENEMY_TYPE_MINION 1
20
21 typedef struct EnemyId
22 {
23 uint16_t index;
24 uint16_t generation;
25 } EnemyId;
26
27 typedef struct EnemyClassConfig
28 {
29 float speed;
30 float health;
31 float radius;
32 float maxAcceleration;
33 } EnemyClassConfig;
34
35 typedef struct Enemy
36 {
37 int16_t currentX, currentY;
38 int16_t nextX, nextY;
39 Vector2 simPosition;
40 Vector2 simVelocity;
41 uint16_t generation;
42 float startMovingTime;
43 float damage, futureDamage;
44 uint8_t enemyType;
45 uint8_t movePathCount;
46 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
47 } Enemy;
48
49 Enemy enemies[ENEMY_MAX_COUNT];
50 int enemyCount = 0;
51
52 EnemyClassConfig enemyClassConfigs[] = {
53 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
54 };
55
56 void EnemyInit()
57 {
58 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
59 {
60 enemies[i] = (Enemy){0};
61 }
62 enemyCount = 0;
63 }
64
65 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
66 {
67 return enemyClassConfigs[enemy->enemyType].speed;
68 }
69
70 float EnemyGetMaxHealth(Enemy *enemy)
71 {
72 return enemyClassConfigs[enemy->enemyType].health;
73 }
74
75 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
76 {
77 int16_t castleX = 0;
78 int16_t castleY = 0;
79 int16_t dx = castleX - currentX;
80 int16_t dy = castleY - currentY;
81 if (dx == 0 && dy == 0)
82 {
83 *nextX = currentX;
84 *nextY = currentY;
85 return 1;
86 }
87 if (abs(dx) > abs(dy))
88 {
89 *nextX = currentX + (dx > 0 ? 1 : -1);
90 *nextY = currentY;
91 }
92 else
93 {
94 *nextX = currentX;
95 *nextY = currentY + (dy > 0 ? 1 : -1);
96 }
97 return 0;
98 }
99
100
101 // this function predicts the movement of the unit for the next deltaT seconds
102 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
103 {
104 const float pointReachedDistance = 0.25f;
105 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
106 const float maxSimStepTime = 0.015625f;
107
108 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
109 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
110 int16_t nextX = enemy->nextX;
111 int16_t nextY = enemy->nextY;
112 Vector2 position = enemy->simPosition;
113 int passedCount = 0;
114 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
115 {
116 float stepTime = fminf(deltaT - t, maxSimStepTime);
117 Vector2 target = (Vector2){nextX, nextY};
118 float speed = Vector2Length(*velocity);
119 // draw the target position for debugging
120 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
121 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
122 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
123 {
124 // we reached the target position, let's move to the next waypoint
125 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
126 target = (Vector2){nextX, nextY};
127 // track how many waypoints we passed
128 passedCount++;
129 }
130
131 // acceleration towards the target
132 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
133 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
134 *velocity = Vector2Add(*velocity, acceleration);
135
136 // limit the speed to the maximum speed
137 if (speed > maxSpeed)
138 {
139 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
140 }
141
142 // move the enemy
143 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
144 }
145
146 if (waypointPassedCount)
147 {
148 (*waypointPassedCount) = passedCount;
149 }
150
151 return position;
152 }
153
154 void EnemyDraw()
155 {
156 for (int i = 0; i < enemyCount; i++)
157 {
158 Enemy enemy = enemies[i];
159 if (enemy.enemyType == ENEMY_TYPE_NONE)
160 {
161 continue;
162 }
163
164 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
165
166 if (enemy.movePathCount > 0)
167 {
168 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
169 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
170 }
171 for (int j = 1; j < enemy.movePathCount; j++)
172 {
173 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
174 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
175 DrawLine3D(p, q, GREEN);
176 }
177
178 switch (enemy.enemyType)
179 {
180 case ENEMY_TYPE_MINION:
181 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
182 break;
183 }
184 }
185 }
186
187 void EnemyUpdate()
188 {
189 const float castleX = 0;
190 const float castleY = 0;
191 const float maxPathDistance2 = 0.25f * 0.25f;
192
193 for (int i = 0; i < enemyCount; i++)
194 {
195 Enemy *enemy = &enemies[i];
196 if (enemy->enemyType == ENEMY_TYPE_NONE)
197 {
198 continue;
199 }
200
201 int waypointPassedCount = 0;
202 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
203 enemy->startMovingTime = gameTime.time;
204 // track path of unit
205 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
206 {
207 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
208 {
209 enemy->movePath[j] = enemy->movePath[j - 1];
210 }
211 enemy->movePath[0] = enemy->simPosition;
212 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
213 {
214 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
215 }
216 }
217
218 if (waypointPassedCount > 0)
219 {
220 enemy->currentX = enemy->nextX;
221 enemy->currentY = enemy->nextY;
222 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
223 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
224 {
225 // enemy reached the castle; remove it
226 enemy->enemyType = ENEMY_TYPE_NONE;
227 continue;
228 }
229 }
230 }
231
232 // handle collisions
233 for (int i = 0; i < enemyCount - 1; i++)
234 {
235 Enemy *enemyA = &enemies[i];
236 if (enemyA->enemyType == ENEMY_TYPE_NONE)
237 {
238 continue;
239 }
240 for (int j = i + 1; j < enemyCount; j++)
241 {
242 Enemy *enemyB = &enemies[j];
243 if (enemyB->enemyType == ENEMY_TYPE_NONE)
244 {
245 continue;
246 }
247 float distanceSqr = Vector2DistanceSqr(enemyA->simPosition, enemyB->simPosition);
248 float radiusA = enemyClassConfigs[enemyA->enemyType].radius;
249 float radiusB = enemyClassConfigs[enemyB->enemyType].radius;
250 float radiusSum = radiusA + radiusB;
251 if (distanceSqr < radiusSum * radiusSum && distanceSqr > 0.001f)
252 {
253 // collision
254 float distance = sqrtf(distanceSqr);
255 float overlap = radiusSum - distance;
256 // move the enemies apart, but softly; if we have a clog of enemies,
257 // moving them perfectly apart can cause them to jitter
258 float positionCorrection = overlap / 5.0f;
259 Vector2 direction = (Vector2){
260 (enemyB->simPosition.x - enemyA->simPosition.x) / distance * positionCorrection,
261 (enemyB->simPosition.y - enemyA->simPosition.y) / distance * positionCorrection};
262 enemyA->simPosition = Vector2Subtract(enemyA->simPosition, direction);
263 enemyB->simPosition = Vector2Add(enemyB->simPosition, direction);
264 }
265 }
266 }
267 }
268
269 EnemyId EnemyGetId(Enemy *enemy)
270 {
271 return (EnemyId){enemy - enemies, enemy->generation};
272 }
273
274 Enemy *EnemyTryResolve(EnemyId enemyId)
275 {
276 if (enemyId.index >= ENEMY_MAX_COUNT)
277 {
278 return 0;
279 }
280 Enemy *enemy = &enemies[enemyId.index];
281 if (enemy->generation != enemyId.generation || enemy->enemyType == ENEMY_TYPE_NONE)
282 {
283 return 0;
284 }
285 return enemy;
286 }
287
288 Enemy *EnemyTryAdd(uint8_t enemyType, int16_t currentX, int16_t currentY)
289 {
290 Enemy *spawn = 0;
291 for (int i = 0; i < enemyCount; i++)
292 {
293 Enemy *enemy = &enemies[i];
294 if (enemy->enemyType == ENEMY_TYPE_NONE)
295 {
296 spawn = enemy;
297 break;
298 }
299 }
300
301 if (enemyCount < ENEMY_MAX_COUNT && !spawn)
302 {
303 spawn = &enemies[enemyCount++];
304 }
305
306 if (spawn)
307 {
308 spawn->currentX = currentX;
309 spawn->currentY = currentY;
310 spawn->nextX = currentX;
311 spawn->nextY = currentY;
312 spawn->simPosition = (Vector2){currentX, currentY};
313 spawn->simVelocity = (Vector2){0, 0};
314 spawn->enemyType = enemyType;
315 spawn->startMovingTime = gameTime.time;
316 spawn->damage = 0.0f;
317 spawn->futureDamage = 0.0f;
318 spawn->generation++;
319 spawn->movePathCount = 0;
320 }
321
322 return spawn;
323 }
324
325 int EnemyAddDamage(Enemy *enemy, float damage)
326 {
327 enemy->damage += damage;
328 if (enemy->damage >= EnemyGetMaxHealth(enemy))
329 {
330 enemy->enemyType = ENEMY_TYPE_NONE;
331 return 1;
332 }
333
334 return 0;
335 }
336
337 Enemy* EnemyGetClosestToCastle(int16_t towerX, int16_t towerY, float range)
338 {
339 int16_t castleX = 0;
340 int16_t castleY = 0;
341 Enemy* closest = 0;
342 int16_t closestDistance = 0;
343 float range2 = range * range;
344 for (int i = 0; i < enemyCount; i++)
345 {
346 Enemy* enemy = &enemies[i];
347 if (enemy->enemyType == ENEMY_TYPE_NONE)
348 {
349 continue;
350 }
351 float maxHealth = EnemyGetMaxHealth(enemy);
352 if (enemy->futureDamage >= maxHealth)
353 {
354 // ignore enemies that will die soon
355 continue;
356 }
357 int16_t dx = castleX - enemy->currentX;
358 int16_t dy = castleY - enemy->currentY;
359 int16_t distance = abs(dx) + abs(dy);
360 if (!closest || distance < closestDistance)
361 {
362 float tdx = towerX - enemy->currentX;
363 float tdy = towerY - enemy->currentY;
364 float tdistance2 = tdx * tdx + tdy * tdy;
365 if (tdistance2 <= range2)
366 {
367 closest = enemy;
368 closestDistance = distance;
369 }
370 }
371 }
372 return closest;
373 }
374
375 int EnemyCount()
376 {
377 int count = 0;
378 for (int i = 0; i < enemyCount; i++)
379 {
380 if (enemies[i].enemyType != ENEMY_TYPE_NONE)
381 {
382 count++;
383 }
384 }
385 return count;
386 }
387
388 //# Projectiles
389 #define PROJECTILE_MAX_COUNT 1200
390 #define PROJECTILE_TYPE_NONE 0
391 #define PROJECTILE_TYPE_BULLET 1
392
393 typedef struct Projectile
394 {
395 uint8_t projectileType;
396 float shootTime;
397 float arrivalTime;
398 float damage;
399 Vector2 position;
400 Vector2 target;
401 Vector2 directionNormal;
402 EnemyId targetEnemy;
403 } Projectile;
404
405 Projectile projectiles[PROJECTILE_MAX_COUNT];
406 int projectileCount = 0;
407
408 void ProjectileInit()
409 {
410 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
411 {
412 projectiles[i] = (Projectile){0};
413 }
414 }
415
416 void ProjectileDraw()
417 {
418 for (int i = 0; i < projectileCount; i++)
419 {
420 Projectile projectile = projectiles[i];
421 if (projectile.projectileType == PROJECTILE_TYPE_NONE)
422 {
423 continue;
424 }
425 float transition = (gameTime.time - projectile.shootTime) / (projectile.arrivalTime - projectile.shootTime);
426 if (transition >= 1.0f)
427 {
428 continue;
429 }
430 Vector2 position = Vector2Lerp(projectile.position, projectile.target, transition);
431 float x = position.x;
432 float y = position.y;
433 float dx = projectile.directionNormal.x;
434 float dy = projectile.directionNormal.y;
435 for (float d = 1.0f; d > 0.0f; d -= 0.25f)
436 {
437 x -= dx * 0.1f;
438 y -= dy * 0.1f;
439 float size = 0.1f * d;
440 DrawCube((Vector3){x, 0.2f, y}, size, size, size, RED);
441 }
442 }
443 }
444
445 void ProjectileUpdate()
446 {
447 for (int i = 0; i < projectileCount; i++)
448 {
449 Projectile *projectile = &projectiles[i];
450 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
451 {
452 continue;
453 }
454 float transition = (gameTime.time - projectile->shootTime) / (projectile->arrivalTime - projectile->shootTime);
455 if (transition >= 1.0f)
456 {
457 projectile->projectileType = PROJECTILE_TYPE_NONE;
458 Enemy *enemy = EnemyTryResolve(projectile->targetEnemy);
459 if (enemy)
460 {
461 EnemyAddDamage(enemy, projectile->damage);
462 }
463 continue;
464 }
465 }
466 }
467
468 Projectile *ProjectileTryAdd(uint8_t projectileType, Enemy *enemy, Vector2 position, Vector2 target, float speed, float damage)
469 {
470 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
471 {
472 Projectile *projectile = &projectiles[i];
473 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
474 {
475 projectile->projectileType = projectileType;
476 projectile->shootTime = gameTime.time;
477 projectile->arrivalTime = gameTime.time + Vector2Distance(position, target) / speed;
478 projectile->damage = damage;
479 projectile->position = position;
480 projectile->target = target;
481 projectile->directionNormal = Vector2Normalize(Vector2Subtract(target, position));
482 projectile->targetEnemy = EnemyGetId(enemy);
483 projectileCount = projectileCount <= i ? i + 1 : projectileCount;
484 return projectile;
485 }
486 }
487 return 0;
488 }
489
490 //# Towers
491
492 #define TOWER_MAX_COUNT 400
493 #define TOWER_TYPE_NONE 0
494 #define TOWER_TYPE_BASE 1
495 #define TOWER_TYPE_GUN 2
496 #define TOWER_TYPE_WALL 3
497
498 typedef struct Tower
499 {
500 int16_t x, y;
501 uint8_t towerType;
502 float cooldown;
503 } Tower;
504
505 Tower towers[TOWER_MAX_COUNT];
506 int towerCount = 0;
507
508 void TowerInit()
509 {
510 for (int i = 0; i < TOWER_MAX_COUNT; i++)
511 {
512 towers[i] = (Tower){0};
513 }
514 towerCount = 0;
515 }
516
517 Tower *TowerGetAt(int16_t x, int16_t y)
518 {
519 for (int i = 0; i < towerCount; i++)
520 {
521 if (towers[i].x == x && towers[i].y == y)
522 {
523 return &towers[i];
524 }
525 }
526 return 0;
527 }
528
529 Tower *TowerTryAdd(uint8_t towerType, int16_t x, int16_t y)
530 {
531 if (towerCount >= TOWER_MAX_COUNT)
532 {
533 return 0;
534 }
535
536 Tower *tower = TowerGetAt(x, y);
537 if (tower)
538 {
539 return 0;
540 }
541
542 tower = &towers[towerCount++];
543 tower->x = x;
544 tower->y = y;
545 tower->towerType = towerType;
546 return tower;
547 }
548
549 void TowerDraw()
550 {
551 for (int i = 0; i < towerCount; i++)
552 {
553 Tower tower = towers[i];
554 DrawCube((Vector3){tower.x, 0.125f, tower.y}, 1.0f, 0.25f, 1.0f, GRAY);
555 switch (tower.towerType)
556 {
557 case TOWER_TYPE_BASE:
558 DrawCube((Vector3){tower.x, 0.4f, tower.y}, 0.8f, 0.8f, 0.8f, MAROON);
559 break;
560 case TOWER_TYPE_GUN:
561 DrawCube((Vector3){tower.x, 0.2f, tower.y}, 0.8f, 0.4f, 0.8f, DARKPURPLE);
562 break;
563 case TOWER_TYPE_WALL:
564 DrawCube((Vector3){tower.x, 0.5f, tower.y}, 1.0f, 1.0f, 1.0f, LIGHTGRAY);
565 break;
566 }
567 }
568 }
569
570 void TowerGunUpdate(Tower *tower)
571 {
572 if (tower->cooldown <= 0)
573 {
574 Enemy *enemy = EnemyGetClosestToCastle(tower->x, tower->y, 3.0f);
575 if (enemy)
576 {
577 tower->cooldown = 0.125f;
578 // shoot the enemy; determine future position of the enemy
579 float bulletSpeed = 1.0f;
580 float bulletDamage = 3.0f;
581 Vector2 velocity = enemy->simVelocity;
582 Vector2 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &velocity, 0);
583 Vector2 towerPosition = {tower->x, tower->y};
584 float eta = Vector2Distance(towerPosition, futurePosition) / bulletSpeed;
585 for (int i = 0; i < 8; i++) {
586 velocity = enemy->simVelocity;
587 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime + eta, &velocity, 0);
588 float distance = Vector2Distance(towerPosition, futurePosition);
589 float eta2 = distance / bulletSpeed;
590 if (fabs(eta - eta2) < 0.01f) {
591 break;
592 }
593 eta = (eta2 + eta) * 0.5f;
594 }
595 ProjectileTryAdd(PROJECTILE_TYPE_BULLET, enemy, towerPosition, futurePosition,
596 bulletSpeed, bulletDamage);
597 enemy->futureDamage += bulletDamage;
598 }
599 }
600 else
601 {
602 tower->cooldown -= gameTime.deltaTime;
603 }
604 }
605
606 void TowerUpdate()
607 {
608 for (int i = 0; i < towerCount; i++)
609 {
610 Tower *tower = &towers[i];
611 switch (tower->towerType)
612 {
613 case TOWER_TYPE_GUN:
614 TowerGunUpdate(tower);
615 break;
616 }
617 }
618 }
619
620 //# Game
621
622 float nextSpawnTime = 0.0f;
623
624 void InitGame()
625 {
626 TowerInit();
627 EnemyInit();
628 ProjectileInit();
629
630 TowerTryAdd(TOWER_TYPE_BASE, 0, 0);
631 TowerTryAdd(TOWER_TYPE_GUN, 2, 0);
632 TowerTryAdd(TOWER_TYPE_GUN, -2, 0);
633
634 for (int i = -2; i <= 2; i += 1)
635 {
636 TowerTryAdd(TOWER_TYPE_WALL, i, 2);
637 TowerTryAdd(TOWER_TYPE_WALL, i, -2);
638 }
639
640 EnemyTryAdd(ENEMY_TYPE_MINION, 5, 4);
641 }
642
643 void GameUpdate()
644 {
645 float dt = GetFrameTime();
646 // cap maximum delta time to 0.1 seconds to prevent large time steps
647 if (dt > 0.1f) dt = 0.1f;
648 gameTime.time += dt;
649 gameTime.deltaTime = dt;
650 EnemyUpdate();
651 TowerUpdate();
652 ProjectileUpdate();
653
654 // spawn a new enemy every second
655 if (gameTime.time >= nextSpawnTime && EnemyCount() < 50)
656 {
657 nextSpawnTime = gameTime.time + 0.2f;
658 // add a new enemy at the boundary of the map
659 int randValue = GetRandomValue(-5, 5);
660 int randSide = GetRandomValue(0, 3);
661 int16_t x = randSide == 0 ? -5 : randSide == 1 ? 5 : randValue;
662 int16_t y = randSide == 2 ? -5 : randSide == 3 ? 5 : randValue;
663 static int alternation = 0;
664 alternation += 1;
665 if (alternation % 3 == 0) {
666 EnemyTryAdd(ENEMY_TYPE_MINION, 0, -5);
667 }
668 else if (alternation % 3 == 1)
669 {
670 EnemyTryAdd(ENEMY_TYPE_MINION, 0, 5);
671 }
672 EnemyTryAdd(ENEMY_TYPE_MINION, x, y);
673 }
674 }
675
676 int main(void)
677 {
678 int screenWidth, screenHeight;
679 GetPreferredSize(&screenWidth, &screenHeight);
680 InitWindow(screenWidth, screenHeight, "Tower defense");
681 SetTargetFPS(30);
682
683 Camera3D camera = {0};
684 camera.position = (Vector3){0.0f, 10.0f, -0.5f};
685 camera.target = (Vector3){0.0f, 0.0f, -0.5f};
686 camera.up = (Vector3){0.0f, 0.0f, -1.0f};
687 camera.fovy = 12.0f;
688 camera.projection = CAMERA_ORTHOGRAPHIC;
689
690 InitGame();
691
692 while (!WindowShouldClose())
693 {
694 if (IsPaused()) {
695 // canvas is not visible in browser - do nothing
696 continue;
697 }
698 BeginDrawing();
699 ClearBackground(DARKBLUE);
700
701 BeginMode3D(camera);
702 DrawGrid(10, 1.0f);
703 TowerDraw();
704 EnemyDraw();
705 ProjectileDraw();
706 GameUpdate();
707 EndMode3D();
708
709 const char *title = "Tower defense tutorial";
710 int titleWidth = MeasureText(title, 20);
711 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f + 2, 5 + 2, 20, BLACK);
712 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f, 5, 20, WHITE);
713 EndDrawing();
714 }
715
716 CloseWindow();
717
718 return 0;
719 }
1 #ifndef TD_TUT_2_MAIN_H
2 #define TD_TUT_2_MAIN_H
3
4 #include <inttypes.h>
5
6 #include "raylib.h"
7 #include "preferred_size.h"
8
9 #endif
1 #include "raylib.h"
2 #include "preferred_size.h"
3
4 // Since the canvas size is not known at compile time, we need to query it at runtime;
5 // the following platform specific code obtains the canvas size and we will use this
6 // size as the preferred size for the window at init time. We're ignoring here the
7 // possibility of the canvas size changing during runtime - this would require to
8 // poll the canvas size in the game loop or establishing a callback to be notified
9
10 #ifdef PLATFORM_WEB
11 #include <emscripten.h>
12 EMSCRIPTEN_RESULT emscripten_get_element_css_size(const char *target, double *width, double *height);
13
14 void GetPreferredSize(int *screenWidth, int *screenHeight)
15 {
16 double canvasWidth, canvasHeight;
17 emscripten_get_element_css_size("#" CANVAS_NAME, &canvasWidth, &canvasHeight);
18 *screenWidth = (int)canvasWidth;
19 *screenHeight = (int)canvasHeight;
20 TraceLog(LOG_INFO, "preferred size for %s: %d %d", CANVAS_NAME, *screenWidth, *screenHeight);
21 }
22
23 int IsPaused()
24 {
25 const char *js = "(function(){\n"
26 " var canvas = document.getElementById(\"" CANVAS_NAME "\");\n"
27 " var rect = canvas.getBoundingClientRect();\n"
28 " var isVisible = (\n"
29 " rect.top >= 0 &&\n"
30 " rect.left >= 0 &&\n"
31 " rect.bottom <= (window.innerHeight || document.documentElement.clientHeight) &&\n"
32 " rect.right <= (window.innerWidth || document.documentElement.clientWidth)\n"
33 " );\n"
34 " return isVisible ? 0 : 1;\n"
35 "})()";
36 return emscripten_run_script_int(js);
37 }
38
39 #else
40 void GetPreferredSize(int *screenWidth, int *screenHeight)
41 {
42 *screenWidth = 600;
43 *screenHeight = 240;
44 }
45 int IsPaused()
46 {
47 return 0;
48 }
49 #endif
1 #ifndef PREFERRED_SIZE_H
2 #define PREFERRED_SIZE_H
3
4 void GetPreferredSize(int *screenWidth, int *screenHeight);
5 int IsPaused();
6
7 #endif
Drawing the wall was not difficult at all. But now we need to implement the path finding - which is certainly more challenging.
Path finding
This is probably going to be the most challenging part of the game, because I don't want to go the easy route either by using a library.
The naive approach would be to use a grid and A* path finding for every unit. This works for a few dozen units, but when we have hundreds, it can quickly become a bottleneck.
Instead, we'll implement a distance field for the map and use this to find the path. We can do this, because every enemy has the same target. When the map is modified, we'll simply recompute the distance field. We can even compute the distance field before every update.
Computing a distance field where every point on the grid has a distance value to the target not that much more expensive than doing a single A* path finding, but it allows us to find the path for every unit in constant time:
- Compute the distance field: Every cell has a simple distance value that represents the walking distance to the target.
- Always move on a descent: Each unit will simply check the neighboring cells and move to the one with the lowest distance value.
That's the entire path finding algorithm for each unit. A simple lookup of distance values - which could be even simplified, just storing the direction of the gradient in each cell for optimal performance.
Our first step is to compute the distance field and to display it. We start with the castle position and then we'll visit every neighboring cell and set the distance value to the current cell's value + 1. We'll repeat this until we've visited every cell:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 typedef struct GameTime
7 {
8 float time;
9 float deltaTime;
10 } GameTime;
11
12 GameTime gameTime = {0};
13
14 //# Pathfinding map
15 typedef struct PathfindingMap
16 {
17 int width, height;
18 float scale;
19 float *distances;
20 float maxDistance;
21 Matrix toMapSpace;
22 Matrix toWorldSpace;
23 } PathfindingMap;
24
25 // when we execute the pathfinding algorithm, we need to store the active nodes
26 // in a queue. Each node has a position, a distance from the start, and the
27 // position of the node that we came from (currently not used)
28 typedef struct PathfindingNode
29 {
30 int16_t x, y, fromX, fromY;
31 float distance;
32 } PathfindingNode;
33
34 // The queue is a simple array of nodes, we add nodes to the end and remove
35 // nodes from the front. We keep the array around to avoid unnecessary allocations
36 static PathfindingNode *pathfindingNodeQueue = 0;
37 static int pathfindingNodeQueueCount = 0;
38 static int pathfindingNodeQueueCapacity = 0;
39
40 // The pathfinding map stores the distances from the castle to each cell in the map.
41 PathfindingMap pathfindingMap = {0};
42
43 void PathfindingMapInit(int width, int height, Vector3 translate, float scale)
44 {
45 // transforming between map space and world space allows us to adapt
46 // position and scale of the map without changing the pathfinding data
47 pathfindingMap.toWorldSpace = MatrixTranslate(translate.x, translate.y, translate.z);
48 pathfindingMap.toWorldSpace = MatrixMultiply(pathfindingMap.toWorldSpace, MatrixScale(scale, scale, scale));
49 pathfindingMap.toMapSpace = MatrixInvert(pathfindingMap.toWorldSpace);
50 pathfindingMap.width = width;
51 pathfindingMap.height = height;
52 pathfindingMap.scale = scale;
53 pathfindingMap.distances = (float *)MemAlloc(width * height * sizeof(float));
54 for (int i = 0; i < width * height; i++)
55 {
56 pathfindingMap.distances[i] = -1.0f;
57 }
58 }
59
60 void PathFindingNodePush(int16_t x, int16_t y, int16_t fromX, int16_t fromY, float distance)
61 {
62 if (pathfindingNodeQueueCount >= pathfindingNodeQueueCapacity)
63 {
64 pathfindingNodeQueueCapacity = pathfindingNodeQueueCapacity == 0 ? 256 : pathfindingNodeQueueCapacity * 2;
65 // we use MemAlloc/MemRealloc to allocate memory for the queue
66 // I am not entirely sure if MemRealloc allows passing a null pointer
67 // so we check if the pointer is null and use MemAlloc in that case
68 if (pathfindingNodeQueue == 0)
69 {
70 pathfindingNodeQueue = (PathfindingNode *)MemAlloc(pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
71 }
72 else
73 {
74 pathfindingNodeQueue = (PathfindingNode *)MemRealloc(pathfindingNodeQueue, pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
75 }
76 }
77
78 PathfindingNode *node = &pathfindingNodeQueue[pathfindingNodeQueueCount++];
79 node->x = x;
80 node->y = y;
81 node->fromX = fromX;
82 node->fromY = fromY;
83 node->distance = distance;
84 }
85
86 PathfindingNode *PathFindingNodePop()
87 {
88 if (pathfindingNodeQueueCount == 0)
89 {
90 return 0;
91 }
92 // we return the first node in the queue; we want to return a pointer to the node
93 // so we can return 0 if the queue is empty.
94 // We should _not_ return a pointer to the element in the list, because the list
95 // may be reallocated and the pointer would become invalid. Or the
96 // popped element is overwritten by the next push operation.
97 // Using static here means that the variable is permanently allocated.
98 static PathfindingNode node;
99 node = pathfindingNodeQueue[0];
100 // we shift all nodes one position to the front
101 for (int i = 1; i < pathfindingNodeQueueCount; i++)
102 {
103 pathfindingNodeQueue[i - 1] = pathfindingNodeQueue[i];
104 }
105 --pathfindingNodeQueueCount;
106 return &node;
107 }
108
109 // transform a world position to a map position in the array;
110 // returns true if the position is inside the map
111 int PathFindingFromWorldToMapPosition(Vector3 worldPosition, int16_t *mapX, int16_t *mapY)
112 {
113 Vector3 mapPosition = Vector3Transform(worldPosition, pathfindingMap.toMapSpace);
114 *mapX = (int16_t)mapPosition.x;
115 *mapY = (int16_t)mapPosition.z;
116 return *mapX >= 0 && *mapX < pathfindingMap.width && *mapY >= 0 && *mapY < pathfindingMap.height;
117 }
118
119 void PathFindingMapUpdate()
120 {
121 const int castleX = 0, castleY = 0;
122 int16_t castleMapX, castleMapY;
123 if (!PathFindingFromWorldToMapPosition((Vector3){castleX, 0.0f, castleY}, &castleMapX, &castleMapY))
124 {
125 return;
126 }
127 int width = pathfindingMap.width, height = pathfindingMap.height;
128
129 // reset the distances to -1
130 for (int i = 0; i < width * height; i++)
131 {
132 pathfindingMap.distances[i] = -1.0f;
133 }
134
135 // we start at the castle and add the castle to the queue
136 pathfindingMap.maxDistance = 0.0f;
137 pathfindingNodeQueueCount = 0;
138 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
139 PathfindingNode *node = 0;
140 while ((node = PathFindingNodePop()))
141 {
142 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
143 {
144 continue;
145 }
146 int index = node->y * width + node->x;
147 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
148 {
149 continue;
150 }
151 pathfindingMap.distances[index] = node->distance;
152 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
153 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
154 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
155 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
156 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
157 }
158 }
159
160 void PathFindingMapDraw()
161 {
162 float cellSize = pathfindingMap.scale * 0.9f;
163 float highlightDistance = fmodf(GetTime() * 4.0f, pathfindingMap.maxDistance);
164 for (int x = 0; x < pathfindingMap.width; x++)
165 {
166 for (int y = 0; y < pathfindingMap.height; y++)
167 {
168 float distance = pathfindingMap.distances[y * pathfindingMap.width + x];
169 float colorV = distance < 0 ? 0 : fminf(distance / pathfindingMap.maxDistance, 1.0f);
170 Color color = distance < 0 ? BLUE : (Color){fminf(colorV, 1.0f) * 255, 0, 0, 255};
171 Vector3 position = Vector3Transform((Vector3){x, -0.25f, y}, pathfindingMap.toWorldSpace);
172 // animate the distance "wave" to show how the pathfinding algorithm expands
173 // from the castle
174 if (distance + 0.5f > highlightDistance && distance - 0.5f < highlightDistance)
175 {
176 color = YELLOW;
177 }
178 DrawCube(position, cellSize, 0.1f, cellSize, color);
179 }
180 }
181 }
182
183 //# Enemies
184
185 #define ENEMY_MAX_PATH_COUNT 8
186 #define ENEMY_MAX_COUNT 400
187 #define ENEMY_TYPE_NONE 0
188 #define ENEMY_TYPE_MINION 1
189
190 typedef struct EnemyId
191 {
192 uint16_t index;
193 uint16_t generation;
194 } EnemyId;
195
196 typedef struct EnemyClassConfig
197 {
198 float speed;
199 float health;
200 float radius;
201 float maxAcceleration;
202 } EnemyClassConfig;
203
204 typedef struct Enemy
205 {
206 int16_t currentX, currentY;
207 int16_t nextX, nextY;
208 Vector2 simPosition;
209 Vector2 simVelocity;
210 uint16_t generation;
211 float startMovingTime;
212 float damage, futureDamage;
213 uint8_t enemyType;
214 uint8_t movePathCount;
215 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
216 } Enemy;
217
218 Enemy enemies[ENEMY_MAX_COUNT];
219 int enemyCount = 0;
220
221 EnemyClassConfig enemyClassConfigs[] = {
222 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
223 };
224
225 void EnemyInit()
226 {
227 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
228 {
229 enemies[i] = (Enemy){0};
230 }
231 enemyCount = 0;
232 }
233
234 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
235 {
236 return enemyClassConfigs[enemy->enemyType].speed;
237 }
238
239 float EnemyGetMaxHealth(Enemy *enemy)
240 {
241 return enemyClassConfigs[enemy->enemyType].health;
242 }
243
244 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
245 {
246 int16_t castleX = 0;
247 int16_t castleY = 0;
248 int16_t dx = castleX - currentX;
249 int16_t dy = castleY - currentY;
250 if (dx == 0 && dy == 0)
251 {
252 *nextX = currentX;
253 *nextY = currentY;
254 return 1;
255 }
256 if (abs(dx) > abs(dy))
257 {
258 *nextX = currentX + (dx > 0 ? 1 : -1);
259 *nextY = currentY;
260 }
261 else
262 {
263 *nextX = currentX;
264 *nextY = currentY + (dy > 0 ? 1 : -1);
265 }
266 return 0;
267 }
268
269
270 // this function predicts the movement of the unit for the next deltaT seconds
271 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
272 {
273 const float pointReachedDistance = 0.25f;
274 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
275 const float maxSimStepTime = 0.015625f;
276
277 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
278 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
279 int16_t nextX = enemy->nextX;
280 int16_t nextY = enemy->nextY;
281 Vector2 position = enemy->simPosition;
282 int passedCount = 0;
283 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
284 {
285 float stepTime = fminf(deltaT - t, maxSimStepTime);
286 Vector2 target = (Vector2){nextX, nextY};
287 float speed = Vector2Length(*velocity);
288 // draw the target position for debugging
289 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
290 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
291 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
292 {
293 // we reached the target position, let's move to the next waypoint
294 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
295 target = (Vector2){nextX, nextY};
296 // track how many waypoints we passed
297 passedCount++;
298 }
299
300 // acceleration towards the target
301 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
302 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
303 *velocity = Vector2Add(*velocity, acceleration);
304
305 // limit the speed to the maximum speed
306 if (speed > maxSpeed)
307 {
308 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
309 }
310
311 // move the enemy
312 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
313 }
314
315 if (waypointPassedCount)
316 {
317 (*waypointPassedCount) = passedCount;
318 }
319
320 return position;
321 }
322
323 void EnemyDraw()
324 {
325 for (int i = 0; i < enemyCount; i++)
326 {
327 Enemy enemy = enemies[i];
328 if (enemy.enemyType == ENEMY_TYPE_NONE)
329 {
330 continue;
331 }
332
333 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
334
335 if (enemy.movePathCount > 0)
336 {
337 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
338 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
339 }
340 for (int j = 1; j < enemy.movePathCount; j++)
341 {
342 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
343 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
344 DrawLine3D(p, q, GREEN);
345 }
346
347 switch (enemy.enemyType)
348 {
349 case ENEMY_TYPE_MINION:
350 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
351 break;
352 }
353 }
354 }
355
356 void EnemyUpdate()
357 {
358 const float castleX = 0;
359 const float castleY = 0;
360 const float maxPathDistance2 = 0.25f * 0.25f;
361
362 for (int i = 0; i < enemyCount; i++)
363 {
364 Enemy *enemy = &enemies[i];
365 if (enemy->enemyType == ENEMY_TYPE_NONE)
366 {
367 continue;
368 }
369
370 int waypointPassedCount = 0;
371 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
372 enemy->startMovingTime = gameTime.time;
373 // track path of unit
374 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
375 {
376 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
377 {
378 enemy->movePath[j] = enemy->movePath[j - 1];
379 }
380 enemy->movePath[0] = enemy->simPosition;
381 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
382 {
383 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
384 }
385 }
386
387 if (waypointPassedCount > 0)
388 {
389 enemy->currentX = enemy->nextX;
390 enemy->currentY = enemy->nextY;
391 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
392 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
393 {
394 // enemy reached the castle; remove it
395 enemy->enemyType = ENEMY_TYPE_NONE;
396 continue;
397 }
398 }
399 }
400
401 // handle collisions
402 for (int i = 0; i < enemyCount - 1; i++)
403 {
404 Enemy *enemyA = &enemies[i];
405 if (enemyA->enemyType == ENEMY_TYPE_NONE)
406 {
407 continue;
408 }
409 for (int j = i + 1; j < enemyCount; j++)
410 {
411 Enemy *enemyB = &enemies[j];
412 if (enemyB->enemyType == ENEMY_TYPE_NONE)
413 {
414 continue;
415 }
416 float distanceSqr = Vector2DistanceSqr(enemyA->simPosition, enemyB->simPosition);
417 float radiusA = enemyClassConfigs[enemyA->enemyType].radius;
418 float radiusB = enemyClassConfigs[enemyB->enemyType].radius;
419 float radiusSum = radiusA + radiusB;
420 if (distanceSqr < radiusSum * radiusSum && distanceSqr > 0.001f)
421 {
422 // collision
423 float distance = sqrtf(distanceSqr);
424 float overlap = radiusSum - distance;
425 // move the enemies apart, but softly; if we have a clog of enemies,
426 // moving them perfectly apart can cause them to jitter
427 float positionCorrection = overlap / 5.0f;
428 Vector2 direction = (Vector2){
429 (enemyB->simPosition.x - enemyA->simPosition.x) / distance * positionCorrection,
430 (enemyB->simPosition.y - enemyA->simPosition.y) / distance * positionCorrection};
431 enemyA->simPosition = Vector2Subtract(enemyA->simPosition, direction);
432 enemyB->simPosition = Vector2Add(enemyB->simPosition, direction);
433 }
434 }
435 }
436 }
437
438 EnemyId EnemyGetId(Enemy *enemy)
439 {
440 return (EnemyId){enemy - enemies, enemy->generation};
441 }
442
443 Enemy *EnemyTryResolve(EnemyId enemyId)
444 {
445 if (enemyId.index >= ENEMY_MAX_COUNT)
446 {
447 return 0;
448 }
449 Enemy *enemy = &enemies[enemyId.index];
450 if (enemy->generation != enemyId.generation || enemy->enemyType == ENEMY_TYPE_NONE)
451 {
452 return 0;
453 }
454 return enemy;
455 }
456
457 Enemy *EnemyTryAdd(uint8_t enemyType, int16_t currentX, int16_t currentY)
458 {
459 Enemy *spawn = 0;
460 for (int i = 0; i < enemyCount; i++)
461 {
462 Enemy *enemy = &enemies[i];
463 if (enemy->enemyType == ENEMY_TYPE_NONE)
464 {
465 spawn = enemy;
466 break;
467 }
468 }
469
470 if (enemyCount < ENEMY_MAX_COUNT && !spawn)
471 {
472 spawn = &enemies[enemyCount++];
473 }
474
475 if (spawn)
476 {
477 spawn->currentX = currentX;
478 spawn->currentY = currentY;
479 spawn->nextX = currentX;
480 spawn->nextY = currentY;
481 spawn->simPosition = (Vector2){currentX, currentY};
482 spawn->simVelocity = (Vector2){0, 0};
483 spawn->enemyType = enemyType;
484 spawn->startMovingTime = gameTime.time;
485 spawn->damage = 0.0f;
486 spawn->futureDamage = 0.0f;
487 spawn->generation++;
488 spawn->movePathCount = 0;
489 }
490
491 return spawn;
492 }
493
494 int EnemyAddDamage(Enemy *enemy, float damage)
495 {
496 enemy->damage += damage;
497 if (enemy->damage >= EnemyGetMaxHealth(enemy))
498 {
499 enemy->enemyType = ENEMY_TYPE_NONE;
500 return 1;
501 }
502
503 return 0;
504 }
505
506 Enemy* EnemyGetClosestToCastle(int16_t towerX, int16_t towerY, float range)
507 {
508 int16_t castleX = 0;
509 int16_t castleY = 0;
510 Enemy* closest = 0;
511 int16_t closestDistance = 0;
512 float range2 = range * range;
513 for (int i = 0; i < enemyCount; i++)
514 {
515 Enemy* enemy = &enemies[i];
516 if (enemy->enemyType == ENEMY_TYPE_NONE)
517 {
518 continue;
519 }
520 float maxHealth = EnemyGetMaxHealth(enemy);
521 if (enemy->futureDamage >= maxHealth)
522 {
523 // ignore enemies that will die soon
524 continue;
525 }
526 int16_t dx = castleX - enemy->currentX;
527 int16_t dy = castleY - enemy->currentY;
528 int16_t distance = abs(dx) + abs(dy);
529 if (!closest || distance < closestDistance)
530 {
531 float tdx = towerX - enemy->currentX;
532 float tdy = towerY - enemy->currentY;
533 float tdistance2 = tdx * tdx + tdy * tdy;
534 if (tdistance2 <= range2)
535 {
536 closest = enemy;
537 closestDistance = distance;
538 }
539 }
540 }
541 return closest;
542 }
543
544 int EnemyCount()
545 {
546 int count = 0;
547 for (int i = 0; i < enemyCount; i++)
548 {
549 if (enemies[i].enemyType != ENEMY_TYPE_NONE)
550 {
551 count++;
552 }
553 }
554 return count;
555 }
556
557 //# Projectiles
558 #define PROJECTILE_MAX_COUNT 1200
559 #define PROJECTILE_TYPE_NONE 0
560 #define PROJECTILE_TYPE_BULLET 1
561
562 typedef struct Projectile
563 {
564 uint8_t projectileType;
565 float shootTime;
566 float arrivalTime;
567 float damage;
568 Vector2 position;
569 Vector2 target;
570 Vector2 directionNormal;
571 EnemyId targetEnemy;
572 } Projectile;
573
574 Projectile projectiles[PROJECTILE_MAX_COUNT];
575 int projectileCount = 0;
576
577 void ProjectileInit()
578 {
579 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
580 {
581 projectiles[i] = (Projectile){0};
582 }
583 }
584
585 void ProjectileDraw()
586 {
587 for (int i = 0; i < projectileCount; i++)
588 {
589 Projectile projectile = projectiles[i];
590 if (projectile.projectileType == PROJECTILE_TYPE_NONE)
591 {
592 continue;
593 }
594 float transition = (gameTime.time - projectile.shootTime) / (projectile.arrivalTime - projectile.shootTime);
595 if (transition >= 1.0f)
596 {
597 continue;
598 }
599 Vector2 position = Vector2Lerp(projectile.position, projectile.target, transition);
600 float x = position.x;
601 float y = position.y;
602 float dx = projectile.directionNormal.x;
603 float dy = projectile.directionNormal.y;
604 for (float d = 1.0f; d > 0.0f; d -= 0.25f)
605 {
606 x -= dx * 0.1f;
607 y -= dy * 0.1f;
608 float size = 0.1f * d;
609 DrawCube((Vector3){x, 0.2f, y}, size, size, size, RED);
610 }
611 }
612 }
613
614 void ProjectileUpdate()
615 {
616 for (int i = 0; i < projectileCount; i++)
617 {
618 Projectile *projectile = &projectiles[i];
619 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
620 {
621 continue;
622 }
623 float transition = (gameTime.time - projectile->shootTime) / (projectile->arrivalTime - projectile->shootTime);
624 if (transition >= 1.0f)
625 {
626 projectile->projectileType = PROJECTILE_TYPE_NONE;
627 Enemy *enemy = EnemyTryResolve(projectile->targetEnemy);
628 if (enemy)
629 {
630 EnemyAddDamage(enemy, projectile->damage);
631 }
632 continue;
633 }
634 }
635 }
636
637 Projectile *ProjectileTryAdd(uint8_t projectileType, Enemy *enemy, Vector2 position, Vector2 target, float speed, float damage)
638 {
639 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
640 {
641 Projectile *projectile = &projectiles[i];
642 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
643 {
644 projectile->projectileType = projectileType;
645 projectile->shootTime = gameTime.time;
646 projectile->arrivalTime = gameTime.time + Vector2Distance(position, target) / speed;
647 projectile->damage = damage;
648 projectile->position = position;
649 projectile->target = target;
650 projectile->directionNormal = Vector2Normalize(Vector2Subtract(target, position));
651 projectile->targetEnemy = EnemyGetId(enemy);
652 projectileCount = projectileCount <= i ? i + 1 : projectileCount;
653 return projectile;
654 }
655 }
656 return 0;
657 }
658
659 //# Towers
660
661 #define TOWER_MAX_COUNT 400
662 #define TOWER_TYPE_NONE 0
663 #define TOWER_TYPE_BASE 1
664 #define TOWER_TYPE_GUN 2
665 #define TOWER_TYPE_WALL 3
666
667 typedef struct Tower
668 {
669 int16_t x, y;
670 uint8_t towerType;
671 float cooldown;
672 } Tower;
673
674 Tower towers[TOWER_MAX_COUNT];
675 int towerCount = 0;
676
677 void TowerInit()
678 {
679 for (int i = 0; i < TOWER_MAX_COUNT; i++)
680 {
681 towers[i] = (Tower){0};
682 }
683 towerCount = 0;
684 }
685
686 Tower *TowerGetAt(int16_t x, int16_t y)
687 {
688 for (int i = 0; i < towerCount; i++)
689 {
690 if (towers[i].x == x && towers[i].y == y)
691 {
692 return &towers[i];
693 }
694 }
695 return 0;
696 }
697
698 Tower *TowerTryAdd(uint8_t towerType, int16_t x, int16_t y)
699 {
700 if (towerCount >= TOWER_MAX_COUNT)
701 {
702 return 0;
703 }
704
705 Tower *tower = TowerGetAt(x, y);
706 if (tower)
707 {
708 return 0;
709 }
710
711 tower = &towers[towerCount++];
712 tower->x = x;
713 tower->y = y;
714 tower->towerType = towerType;
715 return tower;
716 }
717
718 void TowerDraw()
719 {
720 for (int i = 0; i < towerCount; i++)
721 {
722 Tower tower = towers[i];
723 DrawCube((Vector3){tower.x, 0.125f, tower.y}, 1.0f, 0.25f, 1.0f, GRAY);
724 switch (tower.towerType)
725 {
726 case TOWER_TYPE_BASE:
727 DrawCube((Vector3){tower.x, 0.4f, tower.y}, 0.8f, 0.8f, 0.8f, MAROON);
728 break;
729 case TOWER_TYPE_GUN:
730 DrawCube((Vector3){tower.x, 0.2f, tower.y}, 0.8f, 0.4f, 0.8f, DARKPURPLE);
731 break;
732 case TOWER_TYPE_WALL:
733 DrawCube((Vector3){tower.x, 0.5f, tower.y}, 1.0f, 1.0f, 1.0f, LIGHTGRAY);
734 break;
735 }
736 }
737 }
738
739 void TowerGunUpdate(Tower *tower)
740 {
741 if (tower->cooldown <= 0)
742 {
743 Enemy *enemy = EnemyGetClosestToCastle(tower->x, tower->y, 3.0f);
744 if (enemy)
745 {
746 tower->cooldown = 0.125f;
747 // shoot the enemy; determine future position of the enemy
748 float bulletSpeed = 1.0f;
749 float bulletDamage = 3.0f;
750 Vector2 velocity = enemy->simVelocity;
751 Vector2 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &velocity, 0);
752 Vector2 towerPosition = {tower->x, tower->y};
753 float eta = Vector2Distance(towerPosition, futurePosition) / bulletSpeed;
754 for (int i = 0; i < 8; i++) {
755 velocity = enemy->simVelocity;
756 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime + eta, &velocity, 0);
757 float distance = Vector2Distance(towerPosition, futurePosition);
758 float eta2 = distance / bulletSpeed;
759 if (fabs(eta - eta2) < 0.01f) {
760 break;
761 }
762 eta = (eta2 + eta) * 0.5f;
763 }
764 ProjectileTryAdd(PROJECTILE_TYPE_BULLET, enemy, towerPosition, futurePosition,
765 bulletSpeed, bulletDamage);
766 enemy->futureDamage += bulletDamage;
767 }
768 }
769 else
770 {
771 tower->cooldown -= gameTime.deltaTime;
772 }
773 }
774
775 void TowerUpdate()
776 {
777 for (int i = 0; i < towerCount; i++)
778 {
779 Tower *tower = &towers[i];
780 switch (tower->towerType)
781 {
782 case TOWER_TYPE_GUN:
783 TowerGunUpdate(tower);
784 break;
785 }
786 }
787 }
788
789 //# Game
790
791 float nextSpawnTime = 0.0f;
792
793 void InitGame()
794 {
795 TowerInit();
796 EnemyInit();
797 ProjectileInit();
798 PathfindingMapInit(20, 20, (Vector3){-10.0f, 0.0f, -10.0f}, 1.0f);
799
800 TowerTryAdd(TOWER_TYPE_BASE, 0, 0);
801 TowerTryAdd(TOWER_TYPE_GUN, 2, 0);
802 TowerTryAdd(TOWER_TYPE_GUN, -2, 0);
803
804 for (int i = -2; i <= 2; i += 1)
805 {
806 TowerTryAdd(TOWER_TYPE_WALL, i, 2);
807 TowerTryAdd(TOWER_TYPE_WALL, i, -2);
808 }
809
810 EnemyTryAdd(ENEMY_TYPE_MINION, 5, 4);
811 }
812
813 void GameUpdate()
814 {
815 float dt = GetFrameTime();
816 // cap maximum delta time to 0.1 seconds to prevent large time steps
817 if (dt > 0.1f) dt = 0.1f;
818 gameTime.time += dt;
819 gameTime.deltaTime = dt;
820 PathFindingMapUpdate();
821 EnemyUpdate();
822 TowerUpdate();
823 ProjectileUpdate();
824
825 // spawn a new enemy every second
826 if (gameTime.time >= nextSpawnTime && EnemyCount() < 50)
827 {
828 nextSpawnTime = gameTime.time + 0.2f;
829 // add a new enemy at the boundary of the map
830 int randValue = GetRandomValue(-5, 5);
831 int randSide = GetRandomValue(0, 3);
832 int16_t x = randSide == 0 ? -5 : randSide == 1 ? 5 : randValue;
833 int16_t y = randSide == 2 ? -5 : randSide == 3 ? 5 : randValue;
834 static int alternation = 0;
835 alternation += 1;
836 if (alternation % 3 == 0) {
837 EnemyTryAdd(ENEMY_TYPE_MINION, 0, -5);
838 }
839 else if (alternation % 3 == 1)
840 {
841 EnemyTryAdd(ENEMY_TYPE_MINION, 0, 5);
842 }
843 EnemyTryAdd(ENEMY_TYPE_MINION, x, y);
844 }
845 }
846
847 int main(void)
848 {
849 int screenWidth, screenHeight;
850 GetPreferredSize(&screenWidth, &screenHeight);
851 InitWindow(screenWidth, screenHeight, "Tower defense");
852 SetTargetFPS(30);
853
854 Camera3D camera = {0};
855 camera.position = (Vector3){0.0f, 10.0f, -0.5f};
856 camera.target = (Vector3){0.0f, 0.0f, -0.5f};
857 camera.up = (Vector3){0.0f, 0.0f, -1.0f};
858 camera.fovy = 12.0f;
859 camera.projection = CAMERA_ORTHOGRAPHIC;
860
861 InitGame();
862
863 while (!WindowShouldClose())
864 {
865 if (IsPaused()) {
866 // canvas is not visible in browser - do nothing
867 continue;
868 }
869 BeginDrawing();
870 ClearBackground(DARKBLUE);
871
872 BeginMode3D(camera);
873 DrawGrid(10, 1.0f);
874 TowerDraw();
875 EnemyDraw();
876 ProjectileDraw();
877 PathFindingMapDraw();
878 GameUpdate();
879 EndMode3D();
880
881 const char *title = "Tower defense tutorial";
882 int titleWidth = MeasureText(title, 20);
883 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f + 2, 5 + 2, 20, BLACK);
884 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f, 5, 20, WHITE);
885 EndDrawing();
886 }
887
888 CloseWindow();
889
890 return 0;
891 }
1 #ifndef TD_TUT_2_MAIN_H
2 #define TD_TUT_2_MAIN_H
3
4 #include <inttypes.h>
5
6 #include "raylib.h"
7 #include "preferred_size.h"
8
9 #endif
1 #include "raylib.h"
2 #include "preferred_size.h"
3
4 // Since the canvas size is not known at compile time, we need to query it at runtime;
5 // the following platform specific code obtains the canvas size and we will use this
6 // size as the preferred size for the window at init time. We're ignoring here the
7 // possibility of the canvas size changing during runtime - this would require to
8 // poll the canvas size in the game loop or establishing a callback to be notified
9
10 #ifdef PLATFORM_WEB
11 #include <emscripten.h>
12 EMSCRIPTEN_RESULT emscripten_get_element_css_size(const char *target, double *width, double *height);
13
14 void GetPreferredSize(int *screenWidth, int *screenHeight)
15 {
16 double canvasWidth, canvasHeight;
17 emscripten_get_element_css_size("#" CANVAS_NAME, &canvasWidth, &canvasHeight);
18 *screenWidth = (int)canvasWidth;
19 *screenHeight = (int)canvasHeight;
20 TraceLog(LOG_INFO, "preferred size for %s: %d %d", CANVAS_NAME, *screenWidth, *screenHeight);
21 }
22
23 int IsPaused()
24 {
25 const char *js = "(function(){\n"
26 " var canvas = document.getElementById(\"" CANVAS_NAME "\");\n"
27 " var rect = canvas.getBoundingClientRect();\n"
28 " var isVisible = (\n"
29 " rect.top >= 0 &&\n"
30 " rect.left >= 0 &&\n"
31 " rect.bottom <= (window.innerHeight || document.documentElement.clientHeight) &&\n"
32 " rect.right <= (window.innerWidth || document.documentElement.clientWidth)\n"
33 " );\n"
34 " return isVisible ? 0 : 1;\n"
35 "})()";
36 return emscripten_run_script_int(js);
37 }
38
39 #else
40 void GetPreferredSize(int *screenWidth, int *screenHeight)
41 {
42 *screenWidth = 600;
43 *screenHeight = 240;
44 }
45 int IsPaused()
46 {
47 return 0;
48 }
49 #endif
1 #ifndef PREFERRED_SIZE_H
2 #define PREFERRED_SIZE_H
3
4 void GetPreferredSize(int *screenWidth, int *screenHeight);
5 int IsPaused();
6
7 #endif
We can see now the distance to the castle on the map, although it currently doesn't consider the obstacles. We'll add this in the next section - because that's a lot of new code again! But most of it is quite simple. Let's focus on the complicated part:
1 void PathFindingMapUpdate()
2 {
3 (...)
4
5 // we start at the castle and add the castle to the queue
6 pathfindingMap.maxDistance = 0.0f;
7 pathfindingNodeQueueCount = 0;
8 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
9 PathfindingNode *node = 0;
10 while ((node = PathFindingNodePop()))
11 {
12 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
13 {
14 continue;
15 }
16 int index = node->y * width + node->x;
17 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
18 {
19 continue;
20 }
21 pathfindingMap.distances[index] = node->distance;
22 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
23 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
24 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
25 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
26 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
27 }
28 }
This is the "magical" part of building the distance field: We start at the castle and add it to the queue. Then we pop the first element from the queue and visit all neighboring cells. If the distance value is already set and lower than the current distance, we skip the cell. Otherwise, we set the distance value and add the neighboring cells to the queue.
This is a simple breadth-first search algorithm that computes the distance field. The wave of yellow cells depicts pretty much how the algorithm expands the distance field.
Now we need to add the obstacles to the map and make sure that the path finding algorithm considers them:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 //# Declarations
7
8 #define TOWER_MAX_COUNT 400
9 #define TOWER_TYPE_NONE 0
10 #define TOWER_TYPE_BASE 1
11 #define TOWER_TYPE_GUN 2
12 #define TOWER_TYPE_WALL 3
13
14 typedef struct Tower
15 {
16 int16_t x, y;
17 uint8_t towerType;
18 float cooldown;
19 } Tower;
20
21 typedef struct GameTime
22 {
23 float time;
24 float deltaTime;
25 } GameTime;
26
27 GameTime gameTime = {0};
28
29 Tower towers[TOWER_MAX_COUNT];
30 int towerCount = 0;
31
32 //# Pathfinding map
33 typedef struct PathfindingMap
34 {
35 int width, height;
36 float scale;
37 float *distances;
38 long *towerIndex;
39 float maxDistance;
40 Matrix toMapSpace;
41 Matrix toWorldSpace;
42 } PathfindingMap;
43
44 // when we execute the pathfinding algorithm, we need to store the active nodes
45 // in a queue. Each node has a position, a distance from the start, and the
46 // position of the node that we came from (currently not used)
47 typedef struct PathfindingNode
48 {
49 int16_t x, y, fromX, fromY;
50 float distance;
51 } PathfindingNode;
52
53 // The queue is a simple array of nodes, we add nodes to the end and remove
54 // nodes from the front. We keep the array around to avoid unnecessary allocations
55 static PathfindingNode *pathfindingNodeQueue = 0;
56 static int pathfindingNodeQueueCount = 0;
57 static int pathfindingNodeQueueCapacity = 0;
58
59 // The pathfinding map stores the distances from the castle to each cell in the map.
60 PathfindingMap pathfindingMap = {0};
61
62 void PathfindingMapInit(int width, int height, Vector3 translate, float scale)
63 {
64 // transforming between map space and world space allows us to adapt
65 // position and scale of the map without changing the pathfinding data
66 pathfindingMap.toWorldSpace = MatrixTranslate(translate.x, translate.y, translate.z);
67 pathfindingMap.toWorldSpace = MatrixMultiply(pathfindingMap.toWorldSpace, MatrixScale(scale, scale, scale));
68 pathfindingMap.toMapSpace = MatrixInvert(pathfindingMap.toWorldSpace);
69 pathfindingMap.width = width;
70 pathfindingMap.height = height;
71 pathfindingMap.scale = scale;
72 pathfindingMap.distances = (float *)MemAlloc(width * height * sizeof(float));
73 for (int i = 0; i < width * height; i++)
74 {
75 pathfindingMap.distances[i] = -1.0f;
76 }
77
78 pathfindingMap.towerIndex = (long *)MemAlloc(width * height * sizeof(long));
79 }
80
81 void PathFindingNodePush(int16_t x, int16_t y, int16_t fromX, int16_t fromY, float distance)
82 {
83 if (pathfindingNodeQueueCount >= pathfindingNodeQueueCapacity)
84 {
85 pathfindingNodeQueueCapacity = pathfindingNodeQueueCapacity == 0 ? 256 : pathfindingNodeQueueCapacity * 2;
86 // we use MemAlloc/MemRealloc to allocate memory for the queue
87 // I am not entirely sure if MemRealloc allows passing a null pointer
88 // so we check if the pointer is null and use MemAlloc in that case
89 if (pathfindingNodeQueue == 0)
90 {
91 pathfindingNodeQueue = (PathfindingNode *)MemAlloc(pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
92 }
93 else
94 {
95 pathfindingNodeQueue = (PathfindingNode *)MemRealloc(pathfindingNodeQueue, pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
96 }
97 }
98
99 PathfindingNode *node = &pathfindingNodeQueue[pathfindingNodeQueueCount++];
100 node->x = x;
101 node->y = y;
102 node->fromX = fromX;
103 node->fromY = fromY;
104 node->distance = distance;
105 }
106
107 PathfindingNode *PathFindingNodePop()
108 {
109 if (pathfindingNodeQueueCount == 0)
110 {
111 return 0;
112 }
113 // we return the first node in the queue; we want to return a pointer to the node
114 // so we can return 0 if the queue is empty.
115 // We should _not_ return a pointer to the element in the list, because the list
116 // may be reallocated and the pointer would become invalid. Or the
117 // popped element is overwritten by the next push operation.
118 // Using static here means that the variable is permanently allocated.
119 static PathfindingNode node;
120 node = pathfindingNodeQueue[0];
121 // we shift all nodes one position to the front
122 for (int i = 1; i < pathfindingNodeQueueCount; i++)
123 {
124 pathfindingNodeQueue[i - 1] = pathfindingNodeQueue[i];
125 }
126 --pathfindingNodeQueueCount;
127 return &node;
128 }
129
130 // transform a world position to a map position in the array;
131 // returns true if the position is inside the map
132 int PathFindingFromWorldToMapPosition(Vector3 worldPosition, int16_t *mapX, int16_t *mapY)
133 {
134 Vector3 mapPosition = Vector3Transform(worldPosition, pathfindingMap.toMapSpace);
135 *mapX = (int16_t)mapPosition.x;
136 *mapY = (int16_t)mapPosition.z;
137 return *mapX >= 0 && *mapX < pathfindingMap.width && *mapY >= 0 && *mapY < pathfindingMap.height;
138 }
139
140 void PathFindingMapUpdate()
141 {
142 const int castleX = 0, castleY = 0;
143 int16_t castleMapX, castleMapY;
144 if (!PathFindingFromWorldToMapPosition((Vector3){castleX, 0.0f, castleY}, &castleMapX, &castleMapY))
145 {
146 return;
147 }
148 int width = pathfindingMap.width, height = pathfindingMap.height;
149
150 // reset the distances to -1
151 for (int i = 0; i < width * height; i++)
152 {
153 pathfindingMap.distances[i] = -1.0f;
154 }
155 // reset the tower indices
156 for (int i = 0; i < width * height; i++)
157 {
158 pathfindingMap.towerIndex[i] = -1;
159 }
160
161 for (int i = 0; i < towerCount; i++)
162 {
163 Tower *tower = &towers[i];
164 if (tower->towerType == TOWER_TYPE_NONE || tower->towerType == TOWER_TYPE_BASE)
165 {
166 continue;
167 }
168 int16_t mapX, mapY;
169 // technically, if the tower cell scale is not in sync with the pathfinding map scale,
170 // this would not work correctly and needs to be refined to allow towers covering multiple cells
171 // or having multiple towers in one cell; for simplicity, we assume that the tower covers exactly
172 // one cell. For now.
173 if (!PathFindingFromWorldToMapPosition((Vector3){tower->x, 0.0f, tower->y}, &mapX, &mapY))
174 {
175 continue;
176 }
177 int index = mapY * width + mapX;
178 pathfindingMap.towerIndex[index] = i;
179 }
180
181 // we start at the castle and add the castle to the queue
182 pathfindingMap.maxDistance = 0.0f;
183 pathfindingNodeQueueCount = 0;
184 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
185 PathfindingNode *node = 0;
186 while ((node = PathFindingNodePop()))
187 {
188 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
189 {
190 continue;
191 }
192 int index = node->y * width + node->x;
193 // we skip nodes that are blocked by towers
194 if (pathfindingMap.towerIndex[index] >= 0)
195 {
196 continue;
197 }
198 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
199 {
200 continue;
201 }
202 pathfindingMap.distances[index] = node->distance;
203 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
204 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
205 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
206 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
207 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
208 }
209 }
210
211 void PathFindingMapDraw()
212 {
213 float cellSize = pathfindingMap.scale * 0.9f;
214 float highlightDistance = fmodf(GetTime() * 4.0f, pathfindingMap.maxDistance);
215 for (int x = 0; x < pathfindingMap.width; x++)
216 {
217 for (int y = 0; y < pathfindingMap.height; y++)
218 {
219 float distance = pathfindingMap.distances[y * pathfindingMap.width + x];
220 float colorV = distance < 0 ? 0 : fminf(distance / pathfindingMap.maxDistance, 1.0f);
221 Color color = distance < 0 ? BLUE : (Color){fminf(colorV, 1.0f) * 255, 0, 0, 255};
222 Vector3 position = Vector3Transform((Vector3){x, -0.25f, y}, pathfindingMap.toWorldSpace);
223 // animate the distance "wave" to show how the pathfinding algorithm expands
224 // from the castle
225 if (distance + 0.5f > highlightDistance && distance - 0.5f < highlightDistance)
226 {
227 color = YELLOW;
228 }
229 DrawCube(position, cellSize, 0.1f, cellSize, color);
230 }
231 }
232 }
233
234 //# Enemies
235
236 #define ENEMY_MAX_PATH_COUNT 8
237 #define ENEMY_MAX_COUNT 400
238 #define ENEMY_TYPE_NONE 0
239 #define ENEMY_TYPE_MINION 1
240
241 typedef struct EnemyId
242 {
243 uint16_t index;
244 uint16_t generation;
245 } EnemyId;
246
247 typedef struct EnemyClassConfig
248 {
249 float speed;
250 float health;
251 float radius;
252 float maxAcceleration;
253 } EnemyClassConfig;
254
255 typedef struct Enemy
256 {
257 int16_t currentX, currentY;
258 int16_t nextX, nextY;
259 Vector2 simPosition;
260 Vector2 simVelocity;
261 uint16_t generation;
262 float startMovingTime;
263 float damage, futureDamage;
264 uint8_t enemyType;
265 uint8_t movePathCount;
266 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
267 } Enemy;
268
269 Enemy enemies[ENEMY_MAX_COUNT];
270 int enemyCount = 0;
271
272 EnemyClassConfig enemyClassConfigs[] = {
273 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
274 };
275
276 void EnemyInit()
277 {
278 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
279 {
280 enemies[i] = (Enemy){0};
281 }
282 enemyCount = 0;
283 }
284
285 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
286 {
287 return enemyClassConfigs[enemy->enemyType].speed;
288 }
289
290 float EnemyGetMaxHealth(Enemy *enemy)
291 {
292 return enemyClassConfigs[enemy->enemyType].health;
293 }
294
295 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
296 {
297 int16_t castleX = 0;
298 int16_t castleY = 0;
299 int16_t dx = castleX - currentX;
300 int16_t dy = castleY - currentY;
301 if (dx == 0 && dy == 0)
302 {
303 *nextX = currentX;
304 *nextY = currentY;
305 return 1;
306 }
307 if (abs(dx) > abs(dy))
308 {
309 *nextX = currentX + (dx > 0 ? 1 : -1);
310 *nextY = currentY;
311 }
312 else
313 {
314 *nextX = currentX;
315 *nextY = currentY + (dy > 0 ? 1 : -1);
316 }
317 return 0;
318 }
319
320
321 // this function predicts the movement of the unit for the next deltaT seconds
322 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
323 {
324 const float pointReachedDistance = 0.25f;
325 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
326 const float maxSimStepTime = 0.015625f;
327
328 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
329 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
330 int16_t nextX = enemy->nextX;
331 int16_t nextY = enemy->nextY;
332 Vector2 position = enemy->simPosition;
333 int passedCount = 0;
334 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
335 {
336 float stepTime = fminf(deltaT - t, maxSimStepTime);
337 Vector2 target = (Vector2){nextX, nextY};
338 float speed = Vector2Length(*velocity);
339 // draw the target position for debugging
340 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
341 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
342 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
343 {
344 // we reached the target position, let's move to the next waypoint
345 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
346 target = (Vector2){nextX, nextY};
347 // track how many waypoints we passed
348 passedCount++;
349 }
350
351 // acceleration towards the target
352 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
353 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
354 *velocity = Vector2Add(*velocity, acceleration);
355
356 // limit the speed to the maximum speed
357 if (speed > maxSpeed)
358 {
359 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
360 }
361
362 // move the enemy
363 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
364 }
365
366 if (waypointPassedCount)
367 {
368 (*waypointPassedCount) = passedCount;
369 }
370
371 return position;
372 }
373
374 void EnemyDraw()
375 {
376 for (int i = 0; i < enemyCount; i++)
377 {
378 Enemy enemy = enemies[i];
379 if (enemy.enemyType == ENEMY_TYPE_NONE)
380 {
381 continue;
382 }
383
384 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
385
386 if (enemy.movePathCount > 0)
387 {
388 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
389 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
390 }
391 for (int j = 1; j < enemy.movePathCount; j++)
392 {
393 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
394 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
395 DrawLine3D(p, q, GREEN);
396 }
397
398 switch (enemy.enemyType)
399 {
400 case ENEMY_TYPE_MINION:
401 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
402 break;
403 }
404 }
405 }
406
407 void EnemyUpdate()
408 {
409 const float castleX = 0;
410 const float castleY = 0;
411 const float maxPathDistance2 = 0.25f * 0.25f;
412
413 for (int i = 0; i < enemyCount; i++)
414 {
415 Enemy *enemy = &enemies[i];
416 if (enemy->enemyType == ENEMY_TYPE_NONE)
417 {
418 continue;
419 }
420
421 int waypointPassedCount = 0;
422 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
423 enemy->startMovingTime = gameTime.time;
424 // track path of unit
425 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
426 {
427 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
428 {
429 enemy->movePath[j] = enemy->movePath[j - 1];
430 }
431 enemy->movePath[0] = enemy->simPosition;
432 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
433 {
434 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
435 }
436 }
437
438 if (waypointPassedCount > 0)
439 {
440 enemy->currentX = enemy->nextX;
441 enemy->currentY = enemy->nextY;
442 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
443 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
444 {
445 // enemy reached the castle; remove it
446 enemy->enemyType = ENEMY_TYPE_NONE;
447 continue;
448 }
449 }
450 }
451
452 // handle collisions
453 for (int i = 0; i < enemyCount - 1; i++)
454 {
455 Enemy *enemyA = &enemies[i];
456 if (enemyA->enemyType == ENEMY_TYPE_NONE)
457 {
458 continue;
459 }
460 for (int j = i + 1; j < enemyCount; j++)
461 {
462 Enemy *enemyB = &enemies[j];
463 if (enemyB->enemyType == ENEMY_TYPE_NONE)
464 {
465 continue;
466 }
467 float distanceSqr = Vector2DistanceSqr(enemyA->simPosition, enemyB->simPosition);
468 float radiusA = enemyClassConfigs[enemyA->enemyType].radius;
469 float radiusB = enemyClassConfigs[enemyB->enemyType].radius;
470 float radiusSum = radiusA + radiusB;
471 if (distanceSqr < radiusSum * radiusSum && distanceSqr > 0.001f)
472 {
473 // collision
474 float distance = sqrtf(distanceSqr);
475 float overlap = radiusSum - distance;
476 // move the enemies apart, but softly; if we have a clog of enemies,
477 // moving them perfectly apart can cause them to jitter
478 float positionCorrection = overlap / 5.0f;
479 Vector2 direction = (Vector2){
480 (enemyB->simPosition.x - enemyA->simPosition.x) / distance * positionCorrection,
481 (enemyB->simPosition.y - enemyA->simPosition.y) / distance * positionCorrection};
482 enemyA->simPosition = Vector2Subtract(enemyA->simPosition, direction);
483 enemyB->simPosition = Vector2Add(enemyB->simPosition, direction);
484 }
485 }
486 }
487 }
488
489 EnemyId EnemyGetId(Enemy *enemy)
490 {
491 return (EnemyId){enemy - enemies, enemy->generation};
492 }
493
494 Enemy *EnemyTryResolve(EnemyId enemyId)
495 {
496 if (enemyId.index >= ENEMY_MAX_COUNT)
497 {
498 return 0;
499 }
500 Enemy *enemy = &enemies[enemyId.index];
501 if (enemy->generation != enemyId.generation || enemy->enemyType == ENEMY_TYPE_NONE)
502 {
503 return 0;
504 }
505 return enemy;
506 }
507
508 Enemy *EnemyTryAdd(uint8_t enemyType, int16_t currentX, int16_t currentY)
509 {
510 Enemy *spawn = 0;
511 for (int i = 0; i < enemyCount; i++)
512 {
513 Enemy *enemy = &enemies[i];
514 if (enemy->enemyType == ENEMY_TYPE_NONE)
515 {
516 spawn = enemy;
517 break;
518 }
519 }
520
521 if (enemyCount < ENEMY_MAX_COUNT && !spawn)
522 {
523 spawn = &enemies[enemyCount++];
524 }
525
526 if (spawn)
527 {
528 spawn->currentX = currentX;
529 spawn->currentY = currentY;
530 spawn->nextX = currentX;
531 spawn->nextY = currentY;
532 spawn->simPosition = (Vector2){currentX, currentY};
533 spawn->simVelocity = (Vector2){0, 0};
534 spawn->enemyType = enemyType;
535 spawn->startMovingTime = gameTime.time;
536 spawn->damage = 0.0f;
537 spawn->futureDamage = 0.0f;
538 spawn->generation++;
539 spawn->movePathCount = 0;
540 }
541
542 return spawn;
543 }
544
545 int EnemyAddDamage(Enemy *enemy, float damage)
546 {
547 enemy->damage += damage;
548 if (enemy->damage >= EnemyGetMaxHealth(enemy))
549 {
550 enemy->enemyType = ENEMY_TYPE_NONE;
551 return 1;
552 }
553
554 return 0;
555 }
556
557 Enemy* EnemyGetClosestToCastle(int16_t towerX, int16_t towerY, float range)
558 {
559 int16_t castleX = 0;
560 int16_t castleY = 0;
561 Enemy* closest = 0;
562 int16_t closestDistance = 0;
563 float range2 = range * range;
564 for (int i = 0; i < enemyCount; i++)
565 {
566 Enemy* enemy = &enemies[i];
567 if (enemy->enemyType == ENEMY_TYPE_NONE)
568 {
569 continue;
570 }
571 float maxHealth = EnemyGetMaxHealth(enemy);
572 if (enemy->futureDamage >= maxHealth)
573 {
574 // ignore enemies that will die soon
575 continue;
576 }
577 int16_t dx = castleX - enemy->currentX;
578 int16_t dy = castleY - enemy->currentY;
579 int16_t distance = abs(dx) + abs(dy);
580 if (!closest || distance < closestDistance)
581 {
582 float tdx = towerX - enemy->currentX;
583 float tdy = towerY - enemy->currentY;
584 float tdistance2 = tdx * tdx + tdy * tdy;
585 if (tdistance2 <= range2)
586 {
587 closest = enemy;
588 closestDistance = distance;
589 }
590 }
591 }
592 return closest;
593 }
594
595 int EnemyCount()
596 {
597 int count = 0;
598 for (int i = 0; i < enemyCount; i++)
599 {
600 if (enemies[i].enemyType != ENEMY_TYPE_NONE)
601 {
602 count++;
603 }
604 }
605 return count;
606 }
607
608 //# Projectiles
609 #define PROJECTILE_MAX_COUNT 1200
610 #define PROJECTILE_TYPE_NONE 0
611 #define PROJECTILE_TYPE_BULLET 1
612
613 typedef struct Projectile
614 {
615 uint8_t projectileType;
616 float shootTime;
617 float arrivalTime;
618 float damage;
619 Vector2 position;
620 Vector2 target;
621 Vector2 directionNormal;
622 EnemyId targetEnemy;
623 } Projectile;
624
625 Projectile projectiles[PROJECTILE_MAX_COUNT];
626 int projectileCount = 0;
627
628 void ProjectileInit()
629 {
630 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
631 {
632 projectiles[i] = (Projectile){0};
633 }
634 }
635
636 void ProjectileDraw()
637 {
638 for (int i = 0; i < projectileCount; i++)
639 {
640 Projectile projectile = projectiles[i];
641 if (projectile.projectileType == PROJECTILE_TYPE_NONE)
642 {
643 continue;
644 }
645 float transition = (gameTime.time - projectile.shootTime) / (projectile.arrivalTime - projectile.shootTime);
646 if (transition >= 1.0f)
647 {
648 continue;
649 }
650 Vector2 position = Vector2Lerp(projectile.position, projectile.target, transition);
651 float x = position.x;
652 float y = position.y;
653 float dx = projectile.directionNormal.x;
654 float dy = projectile.directionNormal.y;
655 for (float d = 1.0f; d > 0.0f; d -= 0.25f)
656 {
657 x -= dx * 0.1f;
658 y -= dy * 0.1f;
659 float size = 0.1f * d;
660 DrawCube((Vector3){x, 0.2f, y}, size, size, size, RED);
661 }
662 }
663 }
664
665 void ProjectileUpdate()
666 {
667 for (int i = 0; i < projectileCount; i++)
668 {
669 Projectile *projectile = &projectiles[i];
670 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
671 {
672 continue;
673 }
674 float transition = (gameTime.time - projectile->shootTime) / (projectile->arrivalTime - projectile->shootTime);
675 if (transition >= 1.0f)
676 {
677 projectile->projectileType = PROJECTILE_TYPE_NONE;
678 Enemy *enemy = EnemyTryResolve(projectile->targetEnemy);
679 if (enemy)
680 {
681 EnemyAddDamage(enemy, projectile->damage);
682 }
683 continue;
684 }
685 }
686 }
687
688 Projectile *ProjectileTryAdd(uint8_t projectileType, Enemy *enemy, Vector2 position, Vector2 target, float speed, float damage)
689 {
690 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
691 {
692 Projectile *projectile = &projectiles[i];
693 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
694 {
695 projectile->projectileType = projectileType;
696 projectile->shootTime = gameTime.time;
697 projectile->arrivalTime = gameTime.time + Vector2Distance(position, target) / speed;
698 projectile->damage = damage;
699 projectile->position = position;
700 projectile->target = target;
701 projectile->directionNormal = Vector2Normalize(Vector2Subtract(target, position));
702 projectile->targetEnemy = EnemyGetId(enemy);
703 projectileCount = projectileCount <= i ? i + 1 : projectileCount;
704 return projectile;
705 }
706 }
707 return 0;
708 }
709
710 //# Towers
711
712 void TowerInit()
713 {
714 for (int i = 0; i < TOWER_MAX_COUNT; i++)
715 {
716 towers[i] = (Tower){0};
717 }
718 towerCount = 0;
719 }
720
721 Tower *TowerGetAt(int16_t x, int16_t y)
722 {
723 for (int i = 0; i < towerCount; i++)
724 {
725 if (towers[i].x == x && towers[i].y == y)
726 {
727 return &towers[i];
728 }
729 }
730 return 0;
731 }
732
733 Tower *TowerTryAdd(uint8_t towerType, int16_t x, int16_t y)
734 {
735 if (towerCount >= TOWER_MAX_COUNT)
736 {
737 return 0;
738 }
739
740 Tower *tower = TowerGetAt(x, y);
741 if (tower)
742 {
743 return 0;
744 }
745
746 tower = &towers[towerCount++];
747 tower->x = x;
748 tower->y = y;
749 tower->towerType = towerType;
750 return tower;
751 }
752
753 void TowerDraw()
754 {
755 for (int i = 0; i < towerCount; i++)
756 {
757 Tower tower = towers[i];
758 DrawCube((Vector3){tower.x, 0.125f, tower.y}, 1.0f, 0.25f, 1.0f, GRAY);
759 switch (tower.towerType)
760 {
761 case TOWER_TYPE_BASE:
762 DrawCube((Vector3){tower.x, 0.4f, tower.y}, 0.8f, 0.8f, 0.8f, MAROON);
763 break;
764 case TOWER_TYPE_GUN:
765 DrawCube((Vector3){tower.x, 0.2f, tower.y}, 0.8f, 0.4f, 0.8f, DARKPURPLE);
766 break;
767 case TOWER_TYPE_WALL:
768 DrawCube((Vector3){tower.x, 0.5f, tower.y}, 1.0f, 1.0f, 1.0f, LIGHTGRAY);
769 break;
770 }
771 }
772 }
773
774 void TowerGunUpdate(Tower *tower)
775 {
776 if (tower->cooldown <= 0)
777 {
778 Enemy *enemy = EnemyGetClosestToCastle(tower->x, tower->y, 3.0f);
779 if (enemy)
780 {
781 tower->cooldown = 0.125f;
782 // shoot the enemy; determine future position of the enemy
783 float bulletSpeed = 1.0f;
784 float bulletDamage = 3.0f;
785 Vector2 velocity = enemy->simVelocity;
786 Vector2 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &velocity, 0);
787 Vector2 towerPosition = {tower->x, tower->y};
788 float eta = Vector2Distance(towerPosition, futurePosition) / bulletSpeed;
789 for (int i = 0; i < 8; i++) {
790 velocity = enemy->simVelocity;
791 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime + eta, &velocity, 0);
792 float distance = Vector2Distance(towerPosition, futurePosition);
793 float eta2 = distance / bulletSpeed;
794 if (fabs(eta - eta2) < 0.01f) {
795 break;
796 }
797 eta = (eta2 + eta) * 0.5f;
798 }
799 ProjectileTryAdd(PROJECTILE_TYPE_BULLET, enemy, towerPosition, futurePosition,
800 bulletSpeed, bulletDamage);
801 enemy->futureDamage += bulletDamage;
802 }
803 }
804 else
805 {
806 tower->cooldown -= gameTime.deltaTime;
807 }
808 }
809
810 void TowerUpdate()
811 {
812 for (int i = 0; i < towerCount; i++)
813 {
814 Tower *tower = &towers[i];
815 switch (tower->towerType)
816 {
817 case TOWER_TYPE_GUN:
818 TowerGunUpdate(tower);
819 break;
820 }
821 }
822 }
823
824 //# Game
825
826 float nextSpawnTime = 0.0f;
827
828 void InitGame()
829 {
830 TowerInit();
831 EnemyInit();
832 ProjectileInit();
833 PathfindingMapInit(20, 20, (Vector3){-10.0f, 0.0f, -10.0f}, 1.0f);
834
835 TowerTryAdd(TOWER_TYPE_BASE, 0, 0);
836 TowerTryAdd(TOWER_TYPE_GUN, 2, 0);
837 TowerTryAdd(TOWER_TYPE_GUN, -2, 0);
838
839 for (int i = -2; i <= 2; i += 1)
840 {
841 TowerTryAdd(TOWER_TYPE_WALL, i, 2);
842 TowerTryAdd(TOWER_TYPE_WALL, i, -2);
843 }
844
845 EnemyTryAdd(ENEMY_TYPE_MINION, 5, 4);
846 }
847
848 void GameUpdate()
849 {
850 float dt = GetFrameTime();
851 // cap maximum delta time to 0.1 seconds to prevent large time steps
852 if (dt > 0.1f) dt = 0.1f;
853 gameTime.time += dt;
854 gameTime.deltaTime = dt;
855 PathFindingMapUpdate();
856 EnemyUpdate();
857 TowerUpdate();
858 ProjectileUpdate();
859
860 // spawn a new enemy every second
861 if (gameTime.time >= nextSpawnTime && EnemyCount() < 50)
862 {
863 nextSpawnTime = gameTime.time + 0.2f;
864 // add a new enemy at the boundary of the map
865 int randValue = GetRandomValue(-5, 5);
866 int randSide = GetRandomValue(0, 3);
867 int16_t x = randSide == 0 ? -5 : randSide == 1 ? 5 : randValue;
868 int16_t y = randSide == 2 ? -5 : randSide == 3 ? 5 : randValue;
869 static int alternation = 0;
870 alternation += 1;
871 if (alternation % 3 == 0) {
872 EnemyTryAdd(ENEMY_TYPE_MINION, 0, -5);
873 }
874 else if (alternation % 3 == 1)
875 {
876 EnemyTryAdd(ENEMY_TYPE_MINION, 0, 5);
877 }
878 EnemyTryAdd(ENEMY_TYPE_MINION, x, y);
879 }
880 }
881
882 int main(void)
883 {
884 int screenWidth, screenHeight;
885 GetPreferredSize(&screenWidth, &screenHeight);
886 InitWindow(screenWidth, screenHeight, "Tower defense");
887 SetTargetFPS(30);
888
889 Camera3D camera = {0};
890 camera.position = (Vector3){0.0f, 10.0f, -0.5f};
891 camera.target = (Vector3){0.0f, 0.0f, -0.5f};
892 camera.up = (Vector3){0.0f, 0.0f, -1.0f};
893 camera.fovy = 12.0f;
894 camera.projection = CAMERA_ORTHOGRAPHIC;
895
896 InitGame();
897
898 while (!WindowShouldClose())
899 {
900 if (IsPaused()) {
901 // canvas is not visible in browser - do nothing
902 continue;
903 }
904 BeginDrawing();
905 ClearBackground(DARKBLUE);
906
907 BeginMode3D(camera);
908 DrawGrid(10, 1.0f);
909 TowerDraw();
910 EnemyDraw();
911 ProjectileDraw();
912 PathFindingMapDraw();
913 GameUpdate();
914 EndMode3D();
915
916 const char *title = "Tower defense tutorial";
917 int titleWidth = MeasureText(title, 20);
918 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f + 2, 5 + 2, 20, BLACK);
919 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f, 5, 20, WHITE);
920 EndDrawing();
921 }
922
923 CloseWindow();
924
925 return 0;
926 }
1 #ifndef TD_TUT_2_MAIN_H
2 #define TD_TUT_2_MAIN_H
3
4 #include <inttypes.h>
5
6 #include "raylib.h"
7 #include "preferred_size.h"
8
9 #endif
1 #include "raylib.h"
2 #include "preferred_size.h"
3
4 // Since the canvas size is not known at compile time, we need to query it at runtime;
5 // the following platform specific code obtains the canvas size and we will use this
6 // size as the preferred size for the window at init time. We're ignoring here the
7 // possibility of the canvas size changing during runtime - this would require to
8 // poll the canvas size in the game loop or establishing a callback to be notified
9
10 #ifdef PLATFORM_WEB
11 #include <emscripten.h>
12 EMSCRIPTEN_RESULT emscripten_get_element_css_size(const char *target, double *width, double *height);
13
14 void GetPreferredSize(int *screenWidth, int *screenHeight)
15 {
16 double canvasWidth, canvasHeight;
17 emscripten_get_element_css_size("#" CANVAS_NAME, &canvasWidth, &canvasHeight);
18 *screenWidth = (int)canvasWidth;
19 *screenHeight = (int)canvasHeight;
20 TraceLog(LOG_INFO, "preferred size for %s: %d %d", CANVAS_NAME, *screenWidth, *screenHeight);
21 }
22
23 int IsPaused()
24 {
25 const char *js = "(function(){\n"
26 " var canvas = document.getElementById(\"" CANVAS_NAME "\");\n"
27 " var rect = canvas.getBoundingClientRect();\n"
28 " var isVisible = (\n"
29 " rect.top >= 0 &&\n"
30 " rect.left >= 0 &&\n"
31 " rect.bottom <= (window.innerHeight || document.documentElement.clientHeight) &&\n"
32 " rect.right <= (window.innerWidth || document.documentElement.clientWidth)\n"
33 " );\n"
34 " return isVisible ? 0 : 1;\n"
35 "})()";
36 return emscripten_run_script_int(js);
37 }
38
39 #else
40 void GetPreferredSize(int *screenWidth, int *screenHeight)
41 {
42 *screenWidth = 600;
43 *screenHeight = 240;
44 }
45 int IsPaused()
46 {
47 return 0;
48 }
49 #endif
1 #ifndef PREFERRED_SIZE_H
2 #define PREFERRED_SIZE_H
3
4 void GetPreferredSize(int *screenWidth, int *screenHeight);
5 int IsPaused();
6
7 #endif
Thanks to the animated yellow cell coloring, we can see how the path finding algorithm respects the obstacles. The distance field is now correctly computed and we can use it when moving the enemies - although, this implementation turned out to be a little more complicated than I originally thought, more below; first, this is how it looks like:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 //# Declarations
7
8 #define TOWER_MAX_COUNT 400
9 #define TOWER_TYPE_NONE 0
10 #define TOWER_TYPE_BASE 1
11 #define TOWER_TYPE_GUN 2
12 #define TOWER_TYPE_WALL 3
13
14 typedef struct Tower
15 {
16 int16_t x, y;
17 uint8_t towerType;
18 float cooldown;
19 } Tower;
20
21 typedef struct GameTime
22 {
23 float time;
24 float deltaTime;
25 } GameTime;
26
27 GameTime gameTime = {0};
28
29 Tower towers[TOWER_MAX_COUNT];
30 int towerCount = 0;
31
32 //# Pathfinding map
33 typedef struct DeltaSrc
34 {
35 char x, y;
36 } DeltaSrc;
37
38 typedef struct PathfindingMap
39 {
40 int width, height;
41 float scale;
42 float *distances;
43 long *towerIndex;
44 DeltaSrc *deltaSrc;
45 float maxDistance;
46 Matrix toMapSpace;
47 Matrix toWorldSpace;
48 } PathfindingMap;
49
50 // when we execute the pathfinding algorithm, we need to store the active nodes
51 // in a queue. Each node has a position, a distance from the start, and the
52 // position of the node that we came from.
53 typedef struct PathfindingNode
54 {
55 int16_t x, y, fromX, fromY;
56 float distance;
57 } PathfindingNode;
58
59 // The queue is a simple array of nodes, we add nodes to the end and remove
60 // nodes from the front. We keep the array around to avoid unnecessary allocations
61 static PathfindingNode *pathfindingNodeQueue = 0;
62 static int pathfindingNodeQueueCount = 0;
63 static int pathfindingNodeQueueCapacity = 0;
64
65 // The pathfinding map stores the distances from the castle to each cell in the map.
66 PathfindingMap pathfindingMap = {0};
67
68 void PathfindingMapInit(int width, int height, Vector3 translate, float scale)
69 {
70 // transforming between map space and world space allows us to adapt
71 // position and scale of the map without changing the pathfinding data
72 pathfindingMap.toWorldSpace = MatrixTranslate(translate.x, translate.y, translate.z);
73 pathfindingMap.toWorldSpace = MatrixMultiply(pathfindingMap.toWorldSpace, MatrixScale(scale, scale, scale));
74 pathfindingMap.toMapSpace = MatrixInvert(pathfindingMap.toWorldSpace);
75 pathfindingMap.width = width;
76 pathfindingMap.height = height;
77 pathfindingMap.scale = scale;
78 pathfindingMap.distances = (float *)MemAlloc(width * height * sizeof(float));
79 for (int i = 0; i < width * height; i++)
80 {
81 pathfindingMap.distances[i] = -1.0f;
82 }
83
84 pathfindingMap.towerIndex = (long *)MemAlloc(width * height * sizeof(long));
85 pathfindingMap.deltaSrc = (DeltaSrc *)MemAlloc(width * height * sizeof(DeltaSrc));
86 }
87
88 float PathFindingGetDistance(int mapX, int mapY)
89 {
90 if (mapX < 0 || mapX >= pathfindingMap.width || mapY < 0 || mapY >= pathfindingMap.height)
91 {
92 // when outside the map, we return the manhattan distance to the castle (0,0)
93 return fabsf((float)mapX) + fabsf((float)mapY);
94 }
95
96 return pathfindingMap.distances[mapY * pathfindingMap.width + mapX];
97 }
98
99 void PathFindingNodePush(int16_t x, int16_t y, int16_t fromX, int16_t fromY, float distance)
100 {
101 if (pathfindingNodeQueueCount >= pathfindingNodeQueueCapacity)
102 {
103 pathfindingNodeQueueCapacity = pathfindingNodeQueueCapacity == 0 ? 256 : pathfindingNodeQueueCapacity * 2;
104 // we use MemAlloc/MemRealloc to allocate memory for the queue
105 // I am not entirely sure if MemRealloc allows passing a null pointer
106 // so we check if the pointer is null and use MemAlloc in that case
107 if (pathfindingNodeQueue == 0)
108 {
109 pathfindingNodeQueue = (PathfindingNode *)MemAlloc(pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
110 }
111 else
112 {
113 pathfindingNodeQueue = (PathfindingNode *)MemRealloc(pathfindingNodeQueue, pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
114 }
115 }
116
117 PathfindingNode *node = &pathfindingNodeQueue[pathfindingNodeQueueCount++];
118 node->x = x;
119 node->y = y;
120 node->fromX = fromX;
121 node->fromY = fromY;
122 node->distance = distance;
123 }
124
125 PathfindingNode *PathFindingNodePop()
126 {
127 if (pathfindingNodeQueueCount == 0)
128 {
129 return 0;
130 }
131 // we return the first node in the queue; we want to return a pointer to the node
132 // so we can return 0 if the queue is empty.
133 // We should _not_ return a pointer to the element in the list, because the list
134 // may be reallocated and the pointer would become invalid. Or the
135 // popped element is overwritten by the next push operation.
136 // Using static here means that the variable is permanently allocated.
137 static PathfindingNode node;
138 node = pathfindingNodeQueue[0];
139 // we shift all nodes one position to the front
140 for (int i = 1; i < pathfindingNodeQueueCount; i++)
141 {
142 pathfindingNodeQueue[i - 1] = pathfindingNodeQueue[i];
143 }
144 --pathfindingNodeQueueCount;
145 return &node;
146 }
147
148 // transform a world position to a map position in the array;
149 // returns true if the position is inside the map
150 int PathFindingFromWorldToMapPosition(Vector3 worldPosition, int16_t *mapX, int16_t *mapY)
151 {
152 Vector3 mapPosition = Vector3Transform(worldPosition, pathfindingMap.toMapSpace);
153 *mapX = (int16_t)mapPosition.x;
154 *mapY = (int16_t)mapPosition.z;
155 return *mapX >= 0 && *mapX < pathfindingMap.width && *mapY >= 0 && *mapY < pathfindingMap.height;
156 }
157
158 void PathFindingMapUpdate()
159 {
160 const int castleX = 0, castleY = 0;
161 int16_t castleMapX, castleMapY;
162 if (!PathFindingFromWorldToMapPosition((Vector3){castleX, 0.0f, castleY}, &castleMapX, &castleMapY))
163 {
164 return;
165 }
166 int width = pathfindingMap.width, height = pathfindingMap.height;
167
168 // reset the distances to -1
169 for (int i = 0; i < width * height; i++)
170 {
171 pathfindingMap.distances[i] = -1.0f;
172 }
173 // reset the tower indices
174 for (int i = 0; i < width * height; i++)
175 {
176 pathfindingMap.towerIndex[i] = -1;
177 }
178 // reset the delta src
179 for (int i = 0; i < width * height; i++)
180 {
181 pathfindingMap.deltaSrc[i].x = 0;
182 pathfindingMap.deltaSrc[i].y = 0;
183 }
184
185 for (int i = 0; i < towerCount; i++)
186 {
187 Tower *tower = &towers[i];
188 if (tower->towerType == TOWER_TYPE_NONE || tower->towerType == TOWER_TYPE_BASE)
189 {
190 continue;
191 }
192 int16_t mapX, mapY;
193 // technically, if the tower cell scale is not in sync with the pathfinding map scale,
194 // this would not work correctly and needs to be refined to allow towers covering multiple cells
195 // or having multiple towers in one cell; for simplicity, we assume that the tower covers exactly
196 // one cell. For now.
197 if (!PathFindingFromWorldToMapPosition((Vector3){tower->x, 0.0f, tower->y}, &mapX, &mapY))
198 {
199 continue;
200 }
201 int index = mapY * width + mapX;
202 pathfindingMap.towerIndex[index] = i;
203 }
204
205 // we start at the castle and add the castle to the queue
206 pathfindingMap.maxDistance = 0.0f;
207 pathfindingNodeQueueCount = 0;
208 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
209 PathfindingNode *node = 0;
210 while ((node = PathFindingNodePop()))
211 {
212 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
213 {
214 continue;
215 }
216 int index = node->y * width + node->x;
217 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
218 {
219 continue;
220 }
221
222 int deltaX = node->x - node->fromX;
223 int deltaY = node->y - node->fromY;
224 // even if the cell is blocked by a tower, we still may want to store the direction
225 // (though this might not be needed, IDK right now)
226 pathfindingMap.deltaSrc[index].x = (char) deltaX;
227 pathfindingMap.deltaSrc[index].y = (char) deltaY;
228
229 // we skip nodes that are blocked by towers
230 if (pathfindingMap.towerIndex[index] >= 0)
231 {
232 pathfindingMap.distances[index] = node->distance + 1.5f;
233 continue;
234 }
235 pathfindingMap.distances[index] = node->distance;
236 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
237 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
238 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
239 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
240 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
241 }
242 }
243
244 void PathFindingMapDraw()
245 {
246 float cellSize = pathfindingMap.scale * 0.9f;
247 float highlightDistance = fmodf(GetTime() * 4.0f, pathfindingMap.maxDistance);
248 for (int x = 0; x < pathfindingMap.width; x++)
249 {
250 for (int y = 0; y < pathfindingMap.height; y++)
251 {
252 float distance = pathfindingMap.distances[y * pathfindingMap.width + x];
253 float colorV = distance < 0 ? 0 : fminf(distance / pathfindingMap.maxDistance, 1.0f);
254 Color color = distance < 0 ? BLUE : (Color){fminf(colorV, 1.0f) * 255, 0, 0, 255};
255 Vector3 position = Vector3Transform((Vector3){x, -0.25f, y}, pathfindingMap.toWorldSpace);
256 // animate the distance "wave" to show how the pathfinding algorithm expands
257 // from the castle
258 if (distance + 0.5f > highlightDistance && distance - 0.5f < highlightDistance)
259 {
260 color = YELLOW;
261 }
262 DrawCube(position, cellSize, 0.1f, cellSize, color);
263 }
264 }
265 }
266
267 Vector2 PathFindingGetGradient(Vector3 world)
268 {
269 int16_t mapX, mapY;
270 if (PathFindingFromWorldToMapPosition(world, &mapX, &mapY))
271 {
272 DeltaSrc delta = pathfindingMap.deltaSrc[mapY * pathfindingMap.width + mapX];
273 return (Vector2){(float)-delta.x, (float)-delta.y};
274 }
275 // fallback to a simple gradient calculation
276 float n = PathFindingGetDistance(mapX, mapY - 1);
277 float s = PathFindingGetDistance(mapX, mapY + 1);
278 float w = PathFindingGetDistance(mapX - 1, mapY);
279 float e = PathFindingGetDistance(mapX + 1, mapY);
280 return (Vector2){w - e + 0.25f, n - s + 0.125f};
281 }
282
283 //# Enemies
284
285 #define ENEMY_MAX_PATH_COUNT 8
286 #define ENEMY_MAX_COUNT 400
287 #define ENEMY_TYPE_NONE 0
288 #define ENEMY_TYPE_MINION 1
289
290 typedef struct EnemyId
291 {
292 uint16_t index;
293 uint16_t generation;
294 } EnemyId;
295
296 typedef struct EnemyClassConfig
297 {
298 float speed;
299 float health;
300 float radius;
301 float maxAcceleration;
302 } EnemyClassConfig;
303
304 typedef struct Enemy
305 {
306 int16_t currentX, currentY;
307 int16_t nextX, nextY;
308 Vector2 simPosition;
309 Vector2 simVelocity;
310 uint16_t generation;
311 float startMovingTime;
312 float damage, futureDamage;
313 uint8_t enemyType;
314 uint8_t movePathCount;
315 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
316 } Enemy;
317
318 Enemy enemies[ENEMY_MAX_COUNT];
319 int enemyCount = 0;
320
321 EnemyClassConfig enemyClassConfigs[] = {
322 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
323 };
324
325 void EnemyInit()
326 {
327 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
328 {
329 enemies[i] = (Enemy){0};
330 }
331 enemyCount = 0;
332 }
333
334 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
335 {
336 return enemyClassConfigs[enemy->enemyType].speed;
337 }
338
339 float EnemyGetMaxHealth(Enemy *enemy)
340 {
341 return enemyClassConfigs[enemy->enemyType].health;
342 }
343
344 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
345 {
346 int16_t castleX = 0;
347 int16_t castleY = 0;
348 int16_t dx = castleX - currentX;
349 int16_t dy = castleY - currentY;
350 if (dx == 0 && dy == 0)
351 {
352 *nextX = currentX;
353 *nextY = currentY;
354 return 1;
355 }
356 Vector2 gradient = PathFindingGetGradient((Vector3){currentX, 0, currentY});
357
358 if (gradient.x == 0 && gradient.y == 0)
359 {
360 *nextX = currentX;
361 *nextY = currentY;
362 return 1;
363 }
364
365 if (fabsf(gradient.x) > fabsf(gradient.y))
366 {
367 *nextX = currentX + (int16_t)(gradient.x > 0.0f ? 1 : -1);
368 *nextY = currentY;
369 return 0;
370 }
371 *nextX = currentX;
372 *nextY = currentY + (int16_t)(gradient.y > 0.0f ? 1 : -1);
373 return 0;
374 }
375
376
377 // this function predicts the movement of the unit for the next deltaT seconds
378 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
379 {
380 const float pointReachedDistance = 0.25f;
381 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
382 const float maxSimStepTime = 0.015625f;
383
384 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
385 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
386 int16_t nextX = enemy->nextX;
387 int16_t nextY = enemy->nextY;
388 Vector2 position = enemy->simPosition;
389 int passedCount = 0;
390 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
391 {
392 float stepTime = fminf(deltaT - t, maxSimStepTime);
393 Vector2 target = (Vector2){nextX, nextY};
394 float speed = Vector2Length(*velocity);
395 // draw the target position for debugging
396 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
397 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
398 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
399 {
400 // we reached the target position, let's move to the next waypoint
401 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
402 target = (Vector2){nextX, nextY};
403 // track how many waypoints we passed
404 passedCount++;
405 }
406
407 // acceleration towards the target
408 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
409 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
410 *velocity = Vector2Add(*velocity, acceleration);
411
412 // limit the speed to the maximum speed
413 if (speed > maxSpeed)
414 {
415 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
416 }
417
418 // move the enemy
419 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
420 }
421
422 if (waypointPassedCount)
423 {
424 (*waypointPassedCount) = passedCount;
425 }
426
427 return position;
428 }
429
430 void EnemyDraw()
431 {
432 for (int i = 0; i < enemyCount; i++)
433 {
434 Enemy enemy = enemies[i];
435 if (enemy.enemyType == ENEMY_TYPE_NONE)
436 {
437 continue;
438 }
439
440 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
441
442 if (enemy.movePathCount > 0)
443 {
444 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
445 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
446 }
447 for (int j = 1; j < enemy.movePathCount; j++)
448 {
449 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
450 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
451 DrawLine3D(p, q, GREEN);
452 }
453
454 switch (enemy.enemyType)
455 {
456 case ENEMY_TYPE_MINION:
457 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
458 break;
459 }
460 }
461 }
462
463 void EnemyUpdate()
464 {
465 const float castleX = 0;
466 const float castleY = 0;
467 const float maxPathDistance2 = 0.25f * 0.25f;
468
469 for (int i = 0; i < enemyCount; i++)
470 {
471 Enemy *enemy = &enemies[i];
472 if (enemy->enemyType == ENEMY_TYPE_NONE)
473 {
474 continue;
475 }
476
477 int waypointPassedCount = 0;
478 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
479 enemy->startMovingTime = gameTime.time;
480 // track path of unit
481 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
482 {
483 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
484 {
485 enemy->movePath[j] = enemy->movePath[j - 1];
486 }
487 enemy->movePath[0] = enemy->simPosition;
488 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
489 {
490 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
491 }
492 }
493
494 if (waypointPassedCount > 0)
495 {
496 enemy->currentX = enemy->nextX;
497 enemy->currentY = enemy->nextY;
498 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
499 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
500 {
501 // enemy reached the castle; remove it
502 enemy->enemyType = ENEMY_TYPE_NONE;
503 continue;
504 }
505 }
506 }
507
508 // handle collisions
509 for (int i = 0; i < enemyCount - 1; i++)
510 {
511 Enemy *enemyA = &enemies[i];
512 if (enemyA->enemyType == ENEMY_TYPE_NONE)
513 {
514 continue;
515 }
516 for (int j = i + 1; j < enemyCount; j++)
517 {
518 Enemy *enemyB = &enemies[j];
519 if (enemyB->enemyType == ENEMY_TYPE_NONE)
520 {
521 continue;
522 }
523 float distanceSqr = Vector2DistanceSqr(enemyA->simPosition, enemyB->simPosition);
524 float radiusA = enemyClassConfigs[enemyA->enemyType].radius;
525 float radiusB = enemyClassConfigs[enemyB->enemyType].radius;
526 float radiusSum = radiusA + radiusB;
527 if (distanceSqr < radiusSum * radiusSum && distanceSqr > 0.001f)
528 {
529 // collision
530 float distance = sqrtf(distanceSqr);
531 float overlap = radiusSum - distance;
532 // move the enemies apart, but softly; if we have a clog of enemies,
533 // moving them perfectly apart can cause them to jitter
534 float positionCorrection = overlap / 5.0f;
535 Vector2 direction = (Vector2){
536 (enemyB->simPosition.x - enemyA->simPosition.x) / distance * positionCorrection,
537 (enemyB->simPosition.y - enemyA->simPosition.y) / distance * positionCorrection};
538 enemyA->simPosition = Vector2Subtract(enemyA->simPosition, direction);
539 enemyB->simPosition = Vector2Add(enemyB->simPosition, direction);
540 }
541 }
542 }
543 }
544
545 EnemyId EnemyGetId(Enemy *enemy)
546 {
547 return (EnemyId){enemy - enemies, enemy->generation};
548 }
549
550 Enemy *EnemyTryResolve(EnemyId enemyId)
551 {
552 if (enemyId.index >= ENEMY_MAX_COUNT)
553 {
554 return 0;
555 }
556 Enemy *enemy = &enemies[enemyId.index];
557 if (enemy->generation != enemyId.generation || enemy->enemyType == ENEMY_TYPE_NONE)
558 {
559 return 0;
560 }
561 return enemy;
562 }
563
564 Enemy *EnemyTryAdd(uint8_t enemyType, int16_t currentX, int16_t currentY)
565 {
566 Enemy *spawn = 0;
567 for (int i = 0; i < enemyCount; i++)
568 {
569 Enemy *enemy = &enemies[i];
570 if (enemy->enemyType == ENEMY_TYPE_NONE)
571 {
572 spawn = enemy;
573 break;
574 }
575 }
576
577 if (enemyCount < ENEMY_MAX_COUNT && !spawn)
578 {
579 spawn = &enemies[enemyCount++];
580 }
581
582 if (spawn)
583 {
584 spawn->currentX = currentX;
585 spawn->currentY = currentY;
586 spawn->nextX = currentX;
587 spawn->nextY = currentY;
588 spawn->simPosition = (Vector2){currentX, currentY};
589 spawn->simVelocity = (Vector2){0, 0};
590 spawn->enemyType = enemyType;
591 spawn->startMovingTime = gameTime.time;
592 spawn->damage = 0.0f;
593 spawn->futureDamage = 0.0f;
594 spawn->generation++;
595 spawn->movePathCount = 0;
596 }
597
598 return spawn;
599 }
600
601 int EnemyAddDamage(Enemy *enemy, float damage)
602 {
603 enemy->damage += damage;
604 if (enemy->damage >= EnemyGetMaxHealth(enemy))
605 {
606 enemy->enemyType = ENEMY_TYPE_NONE;
607 return 1;
608 }
609
610 return 0;
611 }
612
613 Enemy* EnemyGetClosestToCastle(int16_t towerX, int16_t towerY, float range)
614 {
615 int16_t castleX = 0;
616 int16_t castleY = 0;
617 Enemy* closest = 0;
618 int16_t closestDistance = 0;
619 float range2 = range * range;
620 for (int i = 0; i < enemyCount; i++)
621 {
622 Enemy* enemy = &enemies[i];
623 if (enemy->enemyType == ENEMY_TYPE_NONE)
624 {
625 continue;
626 }
627 float maxHealth = EnemyGetMaxHealth(enemy);
628 if (enemy->futureDamage >= maxHealth)
629 {
630 // ignore enemies that will die soon
631 continue;
632 }
633 int16_t dx = castleX - enemy->currentX;
634 int16_t dy = castleY - enemy->currentY;
635 int16_t distance = abs(dx) + abs(dy);
636 if (!closest || distance < closestDistance)
637 {
638 float tdx = towerX - enemy->currentX;
639 float tdy = towerY - enemy->currentY;
640 float tdistance2 = tdx * tdx + tdy * tdy;
641 if (tdistance2 <= range2)
642 {
643 closest = enemy;
644 closestDistance = distance;
645 }
646 }
647 }
648 return closest;
649 }
650
651 int EnemyCount()
652 {
653 int count = 0;
654 for (int i = 0; i < enemyCount; i++)
655 {
656 if (enemies[i].enemyType != ENEMY_TYPE_NONE)
657 {
658 count++;
659 }
660 }
661 return count;
662 }
663
664 //# Projectiles
665 #define PROJECTILE_MAX_COUNT 1200
666 #define PROJECTILE_TYPE_NONE 0
667 #define PROJECTILE_TYPE_BULLET 1
668
669 typedef struct Projectile
670 {
671 uint8_t projectileType;
672 float shootTime;
673 float arrivalTime;
674 float damage;
675 Vector2 position;
676 Vector2 target;
677 Vector2 directionNormal;
678 EnemyId targetEnemy;
679 } Projectile;
680
681 Projectile projectiles[PROJECTILE_MAX_COUNT];
682 int projectileCount = 0;
683
684 void ProjectileInit()
685 {
686 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
687 {
688 projectiles[i] = (Projectile){0};
689 }
690 }
691
692 void ProjectileDraw()
693 {
694 for (int i = 0; i < projectileCount; i++)
695 {
696 Projectile projectile = projectiles[i];
697 if (projectile.projectileType == PROJECTILE_TYPE_NONE)
698 {
699 continue;
700 }
701 float transition = (gameTime.time - projectile.shootTime) / (projectile.arrivalTime - projectile.shootTime);
702 if (transition >= 1.0f)
703 {
704 continue;
705 }
706 Vector2 position = Vector2Lerp(projectile.position, projectile.target, transition);
707 float x = position.x;
708 float y = position.y;
709 float dx = projectile.directionNormal.x;
710 float dy = projectile.directionNormal.y;
711 for (float d = 1.0f; d > 0.0f; d -= 0.25f)
712 {
713 x -= dx * 0.1f;
714 y -= dy * 0.1f;
715 float size = 0.1f * d;
716 DrawCube((Vector3){x, 0.2f, y}, size, size, size, RED);
717 }
718 }
719 }
720
721 void ProjectileUpdate()
722 {
723 for (int i = 0; i < projectileCount; i++)
724 {
725 Projectile *projectile = &projectiles[i];
726 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
727 {
728 continue;
729 }
730 float transition = (gameTime.time - projectile->shootTime) / (projectile->arrivalTime - projectile->shootTime);
731 if (transition >= 1.0f)
732 {
733 projectile->projectileType = PROJECTILE_TYPE_NONE;
734 Enemy *enemy = EnemyTryResolve(projectile->targetEnemy);
735 if (enemy)
736 {
737 EnemyAddDamage(enemy, projectile->damage);
738 }
739 continue;
740 }
741 }
742 }
743
744 Projectile *ProjectileTryAdd(uint8_t projectileType, Enemy *enemy, Vector2 position, Vector2 target, float speed, float damage)
745 {
746 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
747 {
748 Projectile *projectile = &projectiles[i];
749 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
750 {
751 projectile->projectileType = projectileType;
752 projectile->shootTime = gameTime.time;
753 projectile->arrivalTime = gameTime.time + Vector2Distance(position, target) / speed;
754 projectile->damage = damage;
755 projectile->position = position;
756 projectile->target = target;
757 projectile->directionNormal = Vector2Normalize(Vector2Subtract(target, position));
758 projectile->targetEnemy = EnemyGetId(enemy);
759 projectileCount = projectileCount <= i ? i + 1 : projectileCount;
760 return projectile;
761 }
762 }
763 return 0;
764 }
765
766 //# Towers
767
768 void TowerInit()
769 {
770 for (int i = 0; i < TOWER_MAX_COUNT; i++)
771 {
772 towers[i] = (Tower){0};
773 }
774 towerCount = 0;
775 }
776
777 Tower *TowerGetAt(int16_t x, int16_t y)
778 {
779 for (int i = 0; i < towerCount; i++)
780 {
781 if (towers[i].x == x && towers[i].y == y)
782 {
783 return &towers[i];
784 }
785 }
786 return 0;
787 }
788
789 Tower *TowerTryAdd(uint8_t towerType, int16_t x, int16_t y)
790 {
791 if (towerCount >= TOWER_MAX_COUNT)
792 {
793 return 0;
794 }
795
796 Tower *tower = TowerGetAt(x, y);
797 if (tower)
798 {
799 return 0;
800 }
801
802 tower = &towers[towerCount++];
803 tower->x = x;
804 tower->y = y;
805 tower->towerType = towerType;
806 return tower;
807 }
808
809 void TowerDraw()
810 {
811 for (int i = 0; i < towerCount; i++)
812 {
813 Tower tower = towers[i];
814 DrawCube((Vector3){tower.x, 0.125f, tower.y}, 1.0f, 0.25f, 1.0f, GRAY);
815 switch (tower.towerType)
816 {
817 case TOWER_TYPE_BASE:
818 DrawCube((Vector3){tower.x, 0.4f, tower.y}, 0.8f, 0.8f, 0.8f, MAROON);
819 break;
820 case TOWER_TYPE_GUN:
821 DrawCube((Vector3){tower.x, 0.2f, tower.y}, 0.8f, 0.4f, 0.8f, DARKPURPLE);
822 break;
823 case TOWER_TYPE_WALL:
824 DrawCube((Vector3){tower.x, 0.5f, tower.y}, 1.0f, 1.0f, 1.0f, LIGHTGRAY);
825 break;
826 }
827 }
828 }
829
830 void TowerGunUpdate(Tower *tower)
831 {
832 if (tower->cooldown <= 0)
833 {
834 Enemy *enemy = EnemyGetClosestToCastle(tower->x, tower->y, 3.0f);
835 if (enemy)
836 {
837 tower->cooldown = 0.125f;
838 // shoot the enemy; determine future position of the enemy
839 float bulletSpeed = 1.0f;
840 float bulletDamage = 3.0f;
841 Vector2 velocity = enemy->simVelocity;
842 Vector2 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &velocity, 0);
843 Vector2 towerPosition = {tower->x, tower->y};
844 float eta = Vector2Distance(towerPosition, futurePosition) / bulletSpeed;
845 for (int i = 0; i < 8; i++) {
846 velocity = enemy->simVelocity;
847 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime + eta, &velocity, 0);
848 float distance = Vector2Distance(towerPosition, futurePosition);
849 float eta2 = distance / bulletSpeed;
850 if (fabs(eta - eta2) < 0.01f) {
851 break;
852 }
853 eta = (eta2 + eta) * 0.5f;
854 }
855 ProjectileTryAdd(PROJECTILE_TYPE_BULLET, enemy, towerPosition, futurePosition,
856 bulletSpeed, bulletDamage);
857 enemy->futureDamage += bulletDamage;
858 }
859 }
860 else
861 {
862 tower->cooldown -= gameTime.deltaTime;
863 }
864 }
865
866 void TowerUpdate()
867 {
868 for (int i = 0; i < towerCount; i++)
869 {
870 Tower *tower = &towers[i];
871 switch (tower->towerType)
872 {
873 case TOWER_TYPE_GUN:
874 TowerGunUpdate(tower);
875 break;
876 }
877 }
878 }
879
880 //# Game
881
882 float nextSpawnTime = 0.0f;
883
884 void InitGame()
885 {
886 TowerInit();
887 EnemyInit();
888 ProjectileInit();
889 PathfindingMapInit(20, 20, (Vector3){-10.0f, 0.0f, -10.0f}, 1.0f);
890
891 TowerTryAdd(TOWER_TYPE_BASE, 0, 0);
892 TowerTryAdd(TOWER_TYPE_GUN, 2, 0);
893 TowerTryAdd(TOWER_TYPE_GUN, -2, 0);
894
895 for (int i = -2; i <= 2; i += 1)
896 {
897 TowerTryAdd(TOWER_TYPE_WALL, i, 2);
898 TowerTryAdd(TOWER_TYPE_WALL, i, -2);
899 }
900
901 EnemyTryAdd(ENEMY_TYPE_MINION, 5, 4);
902 }
903
904 void GameUpdate()
905 {
906 float dt = GetFrameTime();
907 // cap maximum delta time to 0.1 seconds to prevent large time steps
908 if (dt > 0.1f) dt = 0.1f;
909 gameTime.time += dt;
910 gameTime.deltaTime = dt;
911 PathFindingMapUpdate();
912 EnemyUpdate();
913 TowerUpdate();
914 ProjectileUpdate();
915
916 // spawn a new enemy every second
917 if (gameTime.time >= nextSpawnTime && EnemyCount() < 50)
918 {
919 nextSpawnTime = gameTime.time + 0.2f;
920 // add a new enemy at the boundary of the map
921 int randValue = GetRandomValue(-5, 5);
922 int randSide = GetRandomValue(0, 3);
923 int16_t x = randSide == 0 ? -5 : randSide == 1 ? 5 : randValue;
924 int16_t y = randSide == 2 ? -5 : randSide == 3 ? 5 : randValue;
925 static int alternation = 0;
926 alternation += 1;
927 if (alternation % 3 == 0) {
928 EnemyTryAdd(ENEMY_TYPE_MINION, 0, -5);
929 }
930 else if (alternation % 3 == 1)
931 {
932 EnemyTryAdd(ENEMY_TYPE_MINION, 0, 5);
933 }
934 EnemyTryAdd(ENEMY_TYPE_MINION, x, y);
935 }
936 }
937
938 int main(void)
939 {
940 int screenWidth, screenHeight;
941 GetPreferredSize(&screenWidth, &screenHeight);
942 InitWindow(screenWidth, screenHeight, "Tower defense");
943 SetTargetFPS(30);
944
945 Camera3D camera = {0};
946 camera.position = (Vector3){0.0f, 10.0f, -0.5f};
947 camera.target = (Vector3){0.0f, 0.0f, -0.5f};
948 camera.up = (Vector3){0.0f, 0.0f, -1.0f};
949 camera.fovy = 12.0f;
950 camera.projection = CAMERA_ORTHOGRAPHIC;
951
952 InitGame();
953
954 while (!WindowShouldClose())
955 {
956 if (IsPaused()) {
957 // canvas is not visible in browser - do nothing
958 continue;
959 }
960 BeginDrawing();
961 ClearBackground(DARKBLUE);
962
963 BeginMode3D(camera);
964 DrawGrid(10, 1.0f);
965 TowerDraw();
966 EnemyDraw();
967 ProjectileDraw();
968 PathFindingMapDraw();
969 GameUpdate();
970 EndMode3D();
971
972 const char *title = "Tower defense tutorial";
973 int titleWidth = MeasureText(title, 20);
974 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f + 2, 5 + 2, 20, BLACK);
975 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f, 5, 20, WHITE);
976 EndDrawing();
977 }
978
979 CloseWindow();
980
981 return 0;
982 }
1 #ifndef TD_TUT_2_MAIN_H
2 #define TD_TUT_2_MAIN_H
3
4 #include <inttypes.h>
5
6 #include "raylib.h"
7 #include "preferred_size.h"
8
9 #endif
1 #include "raylib.h"
2 #include "preferred_size.h"
3
4 // Since the canvas size is not known at compile time, we need to query it at runtime;
5 // the following platform specific code obtains the canvas size and we will use this
6 // size as the preferred size for the window at init time. We're ignoring here the
7 // possibility of the canvas size changing during runtime - this would require to
8 // poll the canvas size in the game loop or establishing a callback to be notified
9
10 #ifdef PLATFORM_WEB
11 #include <emscripten.h>
12 EMSCRIPTEN_RESULT emscripten_get_element_css_size(const char *target, double *width, double *height);
13
14 void GetPreferredSize(int *screenWidth, int *screenHeight)
15 {
16 double canvasWidth, canvasHeight;
17 emscripten_get_element_css_size("#" CANVAS_NAME, &canvasWidth, &canvasHeight);
18 *screenWidth = (int)canvasWidth;
19 *screenHeight = (int)canvasHeight;
20 TraceLog(LOG_INFO, "preferred size for %s: %d %d", CANVAS_NAME, *screenWidth, *screenHeight);
21 }
22
23 int IsPaused()
24 {
25 const char *js = "(function(){\n"
26 " var canvas = document.getElementById(\"" CANVAS_NAME "\");\n"
27 " var rect = canvas.getBoundingClientRect();\n"
28 " var isVisible = (\n"
29 " rect.top >= 0 &&\n"
30 " rect.left >= 0 &&\n"
31 " rect.bottom <= (window.innerHeight || document.documentElement.clientHeight) &&\n"
32 " rect.right <= (window.innerWidth || document.documentElement.clientWidth)\n"
33 " );\n"
34 " return isVisible ? 0 : 1;\n"
35 "})()";
36 return emscripten_run_script_int(js);
37 }
38
39 #else
40 void GetPreferredSize(int *screenWidth, int *screenHeight)
41 {
42 *screenWidth = 600;
43 *screenHeight = 240;
44 }
45 int IsPaused()
46 {
47 return 0;
48 }
49 #endif
1 #ifndef PREFERRED_SIZE_H
2 #define PREFERRED_SIZE_H
3
4 void GetPreferredSize(int *screenWidth, int *screenHeight);
5 int IsPaused();
6
7 #endif
The enemy behavior looks now exactly as expected: They swarm around the obstacles and take the shortest path to the castle. It does however not exactly work like I initially intended it to work: Instead of taking the descent of the distance field, I am storing now the direction from which the path finding algorithm reached that point.
The reason for this is that the gradient over the distance field is sometimes ambiguous: When a point is equally distant to two or more points, the descender would need to make a consistent decision which way to go - and this is not so easy to implement. So the most simple solution is to store the direction in each cell and let the enemies follow this direction.
Let's move on to the next problem: What if there is no way to the castle? Let's create this situation and then try to solve it:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 //# Declarations
7
8 #define TOWER_MAX_COUNT 400
9 #define TOWER_TYPE_NONE 0
10 #define TOWER_TYPE_BASE 1
11 #define TOWER_TYPE_GUN 2
12 #define TOWER_TYPE_WALL 3
13
14 typedef struct Tower
15 {
16 int16_t x, y;
17 uint8_t towerType;
18 float cooldown;
19 } Tower;
20
21 typedef struct GameTime
22 {
23 float time;
24 float deltaTime;
25 } GameTime;
26
27 GameTime gameTime = {0};
28
29 Tower towers[TOWER_MAX_COUNT];
30 int towerCount = 0;
31
32 //# Pathfinding map
33 typedef struct DeltaSrc
34 {
35 char x, y;
36 } DeltaSrc;
37
38 typedef struct PathfindingMap
39 {
40 int width, height;
41 float scale;
42 float *distances;
43 long *towerIndex;
44 DeltaSrc *deltaSrc;
45 float maxDistance;
46 Matrix toMapSpace;
47 Matrix toWorldSpace;
48 } PathfindingMap;
49
50 // when we execute the pathfinding algorithm, we need to store the active nodes
51 // in a queue. Each node has a position, a distance from the start, and the
52 // position of the node that we came from.
53 typedef struct PathfindingNode
54 {
55 int16_t x, y, fromX, fromY;
56 float distance;
57 } PathfindingNode;
58
59 // The queue is a simple array of nodes, we add nodes to the end and remove
60 // nodes from the front. We keep the array around to avoid unnecessary allocations
61 static PathfindingNode *pathfindingNodeQueue = 0;
62 static int pathfindingNodeQueueCount = 0;
63 static int pathfindingNodeQueueCapacity = 0;
64
65 // The pathfinding map stores the distances from the castle to each cell in the map.
66 PathfindingMap pathfindingMap = {0};
67
68 void PathfindingMapInit(int width, int height, Vector3 translate, float scale)
69 {
70 // transforming between map space and world space allows us to adapt
71 // position and scale of the map without changing the pathfinding data
72 pathfindingMap.toWorldSpace = MatrixTranslate(translate.x, translate.y, translate.z);
73 pathfindingMap.toWorldSpace = MatrixMultiply(pathfindingMap.toWorldSpace, MatrixScale(scale, scale, scale));
74 pathfindingMap.toMapSpace = MatrixInvert(pathfindingMap.toWorldSpace);
75 pathfindingMap.width = width;
76 pathfindingMap.height = height;
77 pathfindingMap.scale = scale;
78 pathfindingMap.distances = (float *)MemAlloc(width * height * sizeof(float));
79 for (int i = 0; i < width * height; i++)
80 {
81 pathfindingMap.distances[i] = -1.0f;
82 }
83
84 pathfindingMap.towerIndex = (long *)MemAlloc(width * height * sizeof(long));
85 pathfindingMap.deltaSrc = (DeltaSrc *)MemAlloc(width * height * sizeof(DeltaSrc));
86 }
87
88 float PathFindingGetDistance(int mapX, int mapY)
89 {
90 if (mapX < 0 || mapX >= pathfindingMap.width || mapY < 0 || mapY >= pathfindingMap.height)
91 {
92 // when outside the map, we return the manhattan distance to the castle (0,0)
93 return fabsf((float)mapX) + fabsf((float)mapY);
94 }
95
96 return pathfindingMap.distances[mapY * pathfindingMap.width + mapX];
97 }
98
99 void PathFindingNodePush(int16_t x, int16_t y, int16_t fromX, int16_t fromY, float distance)
100 {
101 if (pathfindingNodeQueueCount >= pathfindingNodeQueueCapacity)
102 {
103 pathfindingNodeQueueCapacity = pathfindingNodeQueueCapacity == 0 ? 256 : pathfindingNodeQueueCapacity * 2;
104 // we use MemAlloc/MemRealloc to allocate memory for the queue
105 // I am not entirely sure if MemRealloc allows passing a null pointer
106 // so we check if the pointer is null and use MemAlloc in that case
107 if (pathfindingNodeQueue == 0)
108 {
109 pathfindingNodeQueue = (PathfindingNode *)MemAlloc(pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
110 }
111 else
112 {
113 pathfindingNodeQueue = (PathfindingNode *)MemRealloc(pathfindingNodeQueue, pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
114 }
115 }
116
117 PathfindingNode *node = &pathfindingNodeQueue[pathfindingNodeQueueCount++];
118 node->x = x;
119 node->y = y;
120 node->fromX = fromX;
121 node->fromY = fromY;
122 node->distance = distance;
123 }
124
125 PathfindingNode *PathFindingNodePop()
126 {
127 if (pathfindingNodeQueueCount == 0)
128 {
129 return 0;
130 }
131 // we return the first node in the queue; we want to return a pointer to the node
132 // so we can return 0 if the queue is empty.
133 // We should _not_ return a pointer to the element in the list, because the list
134 // may be reallocated and the pointer would become invalid. Or the
135 // popped element is overwritten by the next push operation.
136 // Using static here means that the variable is permanently allocated.
137 static PathfindingNode node;
138 node = pathfindingNodeQueue[0];
139 // we shift all nodes one position to the front
140 for (int i = 1; i < pathfindingNodeQueueCount; i++)
141 {
142 pathfindingNodeQueue[i - 1] = pathfindingNodeQueue[i];
143 }
144 --pathfindingNodeQueueCount;
145 return &node;
146 }
147
148 // transform a world position to a map position in the array;
149 // returns true if the position is inside the map
150 int PathFindingFromWorldToMapPosition(Vector3 worldPosition, int16_t *mapX, int16_t *mapY)
151 {
152 Vector3 mapPosition = Vector3Transform(worldPosition, pathfindingMap.toMapSpace);
153 *mapX = (int16_t)mapPosition.x;
154 *mapY = (int16_t)mapPosition.z;
155 return *mapX >= 0 && *mapX < pathfindingMap.width && *mapY >= 0 && *mapY < pathfindingMap.height;
156 }
157
158 void PathFindingMapUpdate()
159 {
160 const int castleX = 0, castleY = 0;
161 int16_t castleMapX, castleMapY;
162 if (!PathFindingFromWorldToMapPosition((Vector3){castleX, 0.0f, castleY}, &castleMapX, &castleMapY))
163 {
164 return;
165 }
166 int width = pathfindingMap.width, height = pathfindingMap.height;
167
168 // reset the distances to -1
169 for (int i = 0; i < width * height; i++)
170 {
171 pathfindingMap.distances[i] = -1.0f;
172 }
173 // reset the tower indices
174 for (int i = 0; i < width * height; i++)
175 {
176 pathfindingMap.towerIndex[i] = -1;
177 }
178 // reset the delta src
179 for (int i = 0; i < width * height; i++)
180 {
181 pathfindingMap.deltaSrc[i].x = 0;
182 pathfindingMap.deltaSrc[i].y = 0;
183 }
184
185 for (int i = 0; i < towerCount; i++)
186 {
187 Tower *tower = &towers[i];
188 if (tower->towerType == TOWER_TYPE_NONE || tower->towerType == TOWER_TYPE_BASE)
189 {
190 continue;
191 }
192 int16_t mapX, mapY;
193 // technically, if the tower cell scale is not in sync with the pathfinding map scale,
194 // this would not work correctly and needs to be refined to allow towers covering multiple cells
195 // or having multiple towers in one cell; for simplicity, we assume that the tower covers exactly
196 // one cell. For now.
197 if (!PathFindingFromWorldToMapPosition((Vector3){tower->x, 0.0f, tower->y}, &mapX, &mapY))
198 {
199 continue;
200 }
201 int index = mapY * width + mapX;
202 pathfindingMap.towerIndex[index] = i;
203 }
204
205 // we start at the castle and add the castle to the queue
206 pathfindingMap.maxDistance = 0.0f;
207 pathfindingNodeQueueCount = 0;
208 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
209 PathfindingNode *node = 0;
210 while ((node = PathFindingNodePop()))
211 {
212 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
213 {
214 continue;
215 }
216 int index = node->y * width + node->x;
217 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
218 {
219 continue;
220 }
221
222 int deltaX = node->x - node->fromX;
223 int deltaY = node->y - node->fromY;
224 // even if the cell is blocked by a tower, we still may want to store the direction
225 // (though this might not be needed, IDK right now)
226 pathfindingMap.deltaSrc[index].x = (char) deltaX;
227 pathfindingMap.deltaSrc[index].y = (char) deltaY;
228
229 // we skip nodes that are blocked by towers
230 if (pathfindingMap.towerIndex[index] >= 0)
231 {
232 pathfindingMap.distances[index] = node->distance + 1.5f;
233 continue;
234 }
235 pathfindingMap.distances[index] = node->distance;
236 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
237 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
238 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
239 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
240 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
241 }
242 }
243
244 void PathFindingMapDraw()
245 {
246 float cellSize = pathfindingMap.scale * 0.9f;
247 float highlightDistance = fmodf(GetTime() * 4.0f, pathfindingMap.maxDistance);
248 for (int x = 0; x < pathfindingMap.width; x++)
249 {
250 for (int y = 0; y < pathfindingMap.height; y++)
251 {
252 float distance = pathfindingMap.distances[y * pathfindingMap.width + x];
253 float colorV = distance < 0 ? 0 : fminf(distance / pathfindingMap.maxDistance, 1.0f);
254 Color color = distance < 0 ? BLUE : (Color){fminf(colorV, 1.0f) * 255, 0, 0, 255};
255 Vector3 position = Vector3Transform((Vector3){x, -0.25f, y}, pathfindingMap.toWorldSpace);
256 // animate the distance "wave" to show how the pathfinding algorithm expands
257 // from the castle
258 if (distance + 0.5f > highlightDistance && distance - 0.5f < highlightDistance)
259 {
260 color = YELLOW;
261 }
262 DrawCube(position, cellSize, 0.1f, cellSize, color);
263 }
264 }
265 }
266
267 Vector2 PathFindingGetGradient(Vector3 world)
268 {
269 int16_t mapX, mapY;
270 if (PathFindingFromWorldToMapPosition(world, &mapX, &mapY))
271 {
272 DeltaSrc delta = pathfindingMap.deltaSrc[mapY * pathfindingMap.width + mapX];
273 return (Vector2){(float)-delta.x, (float)-delta.y};
274 }
275 // fallback to a simple gradient calculation
276 float n = PathFindingGetDistance(mapX, mapY - 1);
277 float s = PathFindingGetDistance(mapX, mapY + 1);
278 float w = PathFindingGetDistance(mapX - 1, mapY);
279 float e = PathFindingGetDistance(mapX + 1, mapY);
280 return (Vector2){w - e + 0.25f, n - s + 0.125f};
281 }
282
283 //# Enemies
284
285 #define ENEMY_MAX_PATH_COUNT 8
286 #define ENEMY_MAX_COUNT 400
287 #define ENEMY_TYPE_NONE 0
288 #define ENEMY_TYPE_MINION 1
289
290 typedef struct EnemyId
291 {
292 uint16_t index;
293 uint16_t generation;
294 } EnemyId;
295
296 typedef struct EnemyClassConfig
297 {
298 float speed;
299 float health;
300 float radius;
301 float maxAcceleration;
302 } EnemyClassConfig;
303
304 typedef struct Enemy
305 {
306 int16_t currentX, currentY;
307 int16_t nextX, nextY;
308 Vector2 simPosition;
309 Vector2 simVelocity;
310 uint16_t generation;
311 float startMovingTime;
312 float damage, futureDamage;
313 uint8_t enemyType;
314 uint8_t movePathCount;
315 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
316 } Enemy;
317
318 Enemy enemies[ENEMY_MAX_COUNT];
319 int enemyCount = 0;
320
321 EnemyClassConfig enemyClassConfigs[] = {
322 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
323 };
324
325 void EnemyInit()
326 {
327 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
328 {
329 enemies[i] = (Enemy){0};
330 }
331 enemyCount = 0;
332 }
333
334 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
335 {
336 return enemyClassConfigs[enemy->enemyType].speed;
337 }
338
339 float EnemyGetMaxHealth(Enemy *enemy)
340 {
341 return enemyClassConfigs[enemy->enemyType].health;
342 }
343
344 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
345 {
346 int16_t castleX = 0;
347 int16_t castleY = 0;
348 int16_t dx = castleX - currentX;
349 int16_t dy = castleY - currentY;
350 if (dx == 0 && dy == 0)
351 {
352 *nextX = currentX;
353 *nextY = currentY;
354 return 1;
355 }
356 Vector2 gradient = PathFindingGetGradient((Vector3){currentX, 0, currentY});
357
358 if (gradient.x == 0 && gradient.y == 0)
359 {
360 *nextX = currentX;
361 *nextY = currentY;
362 return 1;
363 }
364
365 if (fabsf(gradient.x) > fabsf(gradient.y))
366 {
367 *nextX = currentX + (int16_t)(gradient.x > 0.0f ? 1 : -1);
368 *nextY = currentY;
369 return 0;
370 }
371 *nextX = currentX;
372 *nextY = currentY + (int16_t)(gradient.y > 0.0f ? 1 : -1);
373 return 0;
374 }
375
376
377 // this function predicts the movement of the unit for the next deltaT seconds
378 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
379 {
380 const float pointReachedDistance = 0.25f;
381 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
382 const float maxSimStepTime = 0.015625f;
383
384 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
385 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
386 int16_t nextX = enemy->nextX;
387 int16_t nextY = enemy->nextY;
388 Vector2 position = enemy->simPosition;
389 int passedCount = 0;
390 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
391 {
392 float stepTime = fminf(deltaT - t, maxSimStepTime);
393 Vector2 target = (Vector2){nextX, nextY};
394 float speed = Vector2Length(*velocity);
395 // draw the target position for debugging
396 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
397 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
398 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
399 {
400 // we reached the target position, let's move to the next waypoint
401 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
402 target = (Vector2){nextX, nextY};
403 // track how many waypoints we passed
404 passedCount++;
405 }
406
407 // acceleration towards the target
408 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
409 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
410 *velocity = Vector2Add(*velocity, acceleration);
411
412 // limit the speed to the maximum speed
413 if (speed > maxSpeed)
414 {
415 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
416 }
417
418 // move the enemy
419 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
420 }
421
422 if (waypointPassedCount)
423 {
424 (*waypointPassedCount) = passedCount;
425 }
426
427 return position;
428 }
429
430 void EnemyDraw()
431 {
432 for (int i = 0; i < enemyCount; i++)
433 {
434 Enemy enemy = enemies[i];
435 if (enemy.enemyType == ENEMY_TYPE_NONE)
436 {
437 continue;
438 }
439
440 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
441
442 if (enemy.movePathCount > 0)
443 {
444 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
445 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
446 }
447 for (int j = 1; j < enemy.movePathCount; j++)
448 {
449 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
450 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
451 DrawLine3D(p, q, GREEN);
452 }
453
454 switch (enemy.enemyType)
455 {
456 case ENEMY_TYPE_MINION:
457 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
458 break;
459 }
460 }
461 }
462
463 void EnemyUpdate()
464 {
465 const float castleX = 0;
466 const float castleY = 0;
467 const float maxPathDistance2 = 0.25f * 0.25f;
468
469 for (int i = 0; i < enemyCount; i++)
470 {
471 Enemy *enemy = &enemies[i];
472 if (enemy->enemyType == ENEMY_TYPE_NONE)
473 {
474 continue;
475 }
476
477 int waypointPassedCount = 0;
478 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
479 enemy->startMovingTime = gameTime.time;
480 // track path of unit
481 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
482 {
483 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
484 {
485 enemy->movePath[j] = enemy->movePath[j - 1];
486 }
487 enemy->movePath[0] = enemy->simPosition;
488 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
489 {
490 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
491 }
492 }
493
494 if (waypointPassedCount > 0)
495 {
496 enemy->currentX = enemy->nextX;
497 enemy->currentY = enemy->nextY;
498 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
499 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
500 {
501 // enemy reached the castle; remove it
502 enemy->enemyType = ENEMY_TYPE_NONE;
503 continue;
504 }
505 }
506 }
507
508 // handle collisions
509 for (int i = 0; i < enemyCount - 1; i++)
510 {
511 Enemy *enemyA = &enemies[i];
512 if (enemyA->enemyType == ENEMY_TYPE_NONE)
513 {
514 continue;
515 }
516 for (int j = i + 1; j < enemyCount; j++)
517 {
518 Enemy *enemyB = &enemies[j];
519 if (enemyB->enemyType == ENEMY_TYPE_NONE)
520 {
521 continue;
522 }
523 float distanceSqr = Vector2DistanceSqr(enemyA->simPosition, enemyB->simPosition);
524 float radiusA = enemyClassConfigs[enemyA->enemyType].radius;
525 float radiusB = enemyClassConfigs[enemyB->enemyType].radius;
526 float radiusSum = radiusA + radiusB;
527 if (distanceSqr < radiusSum * radiusSum && distanceSqr > 0.001f)
528 {
529 // collision
530 float distance = sqrtf(distanceSqr);
531 float overlap = radiusSum - distance;
532 // move the enemies apart, but softly; if we have a clog of enemies,
533 // moving them perfectly apart can cause them to jitter
534 float positionCorrection = overlap / 5.0f;
535 Vector2 direction = (Vector2){
536 (enemyB->simPosition.x - enemyA->simPosition.x) / distance * positionCorrection,
537 (enemyB->simPosition.y - enemyA->simPosition.y) / distance * positionCorrection};
538 enemyA->simPosition = Vector2Subtract(enemyA->simPosition, direction);
539 enemyB->simPosition = Vector2Add(enemyB->simPosition, direction);
540 }
541 }
542 }
543 }
544
545 EnemyId EnemyGetId(Enemy *enemy)
546 {
547 return (EnemyId){enemy - enemies, enemy->generation};
548 }
549
550 Enemy *EnemyTryResolve(EnemyId enemyId)
551 {
552 if (enemyId.index >= ENEMY_MAX_COUNT)
553 {
554 return 0;
555 }
556 Enemy *enemy = &enemies[enemyId.index];
557 if (enemy->generation != enemyId.generation || enemy->enemyType == ENEMY_TYPE_NONE)
558 {
559 return 0;
560 }
561 return enemy;
562 }
563
564 Enemy *EnemyTryAdd(uint8_t enemyType, int16_t currentX, int16_t currentY)
565 {
566 Enemy *spawn = 0;
567 for (int i = 0; i < enemyCount; i++)
568 {
569 Enemy *enemy = &enemies[i];
570 if (enemy->enemyType == ENEMY_TYPE_NONE)
571 {
572 spawn = enemy;
573 break;
574 }
575 }
576
577 if (enemyCount < ENEMY_MAX_COUNT && !spawn)
578 {
579 spawn = &enemies[enemyCount++];
580 }
581
582 if (spawn)
583 {
584 spawn->currentX = currentX;
585 spawn->currentY = currentY;
586 spawn->nextX = currentX;
587 spawn->nextY = currentY;
588 spawn->simPosition = (Vector2){currentX, currentY};
589 spawn->simVelocity = (Vector2){0, 0};
590 spawn->enemyType = enemyType;
591 spawn->startMovingTime = gameTime.time;
592 spawn->damage = 0.0f;
593 spawn->futureDamage = 0.0f;
594 spawn->generation++;
595 spawn->movePathCount = 0;
596 }
597
598 return spawn;
599 }
600
601 int EnemyAddDamage(Enemy *enemy, float damage)
602 {
603 enemy->damage += damage;
604 if (enemy->damage >= EnemyGetMaxHealth(enemy))
605 {
606 enemy->enemyType = ENEMY_TYPE_NONE;
607 return 1;
608 }
609
610 return 0;
611 }
612
613 Enemy* EnemyGetClosestToCastle(int16_t towerX, int16_t towerY, float range)
614 {
615 int16_t castleX = 0;
616 int16_t castleY = 0;
617 Enemy* closest = 0;
618 int16_t closestDistance = 0;
619 float range2 = range * range;
620 for (int i = 0; i < enemyCount; i++)
621 {
622 Enemy* enemy = &enemies[i];
623 if (enemy->enemyType == ENEMY_TYPE_NONE)
624 {
625 continue;
626 }
627 float maxHealth = EnemyGetMaxHealth(enemy);
628 if (enemy->futureDamage >= maxHealth)
629 {
630 // ignore enemies that will die soon
631 continue;
632 }
633 int16_t dx = castleX - enemy->currentX;
634 int16_t dy = castleY - enemy->currentY;
635 int16_t distance = abs(dx) + abs(dy);
636 if (!closest || distance < closestDistance)
637 {
638 float tdx = towerX - enemy->currentX;
639 float tdy = towerY - enemy->currentY;
640 float tdistance2 = tdx * tdx + tdy * tdy;
641 if (tdistance2 <= range2)
642 {
643 closest = enemy;
644 closestDistance = distance;
645 }
646 }
647 }
648 return closest;
649 }
650
651 int EnemyCount()
652 {
653 int count = 0;
654 for (int i = 0; i < enemyCount; i++)
655 {
656 if (enemies[i].enemyType != ENEMY_TYPE_NONE)
657 {
658 count++;
659 }
660 }
661 return count;
662 }
663
664 //# Projectiles
665 #define PROJECTILE_MAX_COUNT 1200
666 #define PROJECTILE_TYPE_NONE 0
667 #define PROJECTILE_TYPE_BULLET 1
668
669 typedef struct Projectile
670 {
671 uint8_t projectileType;
672 float shootTime;
673 float arrivalTime;
674 float damage;
675 Vector2 position;
676 Vector2 target;
677 Vector2 directionNormal;
678 EnemyId targetEnemy;
679 } Projectile;
680
681 Projectile projectiles[PROJECTILE_MAX_COUNT];
682 int projectileCount = 0;
683
684 void ProjectileInit()
685 {
686 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
687 {
688 projectiles[i] = (Projectile){0};
689 }
690 }
691
692 void ProjectileDraw()
693 {
694 for (int i = 0; i < projectileCount; i++)
695 {
696 Projectile projectile = projectiles[i];
697 if (projectile.projectileType == PROJECTILE_TYPE_NONE)
698 {
699 continue;
700 }
701 float transition = (gameTime.time - projectile.shootTime) / (projectile.arrivalTime - projectile.shootTime);
702 if (transition >= 1.0f)
703 {
704 continue;
705 }
706 Vector2 position = Vector2Lerp(projectile.position, projectile.target, transition);
707 float x = position.x;
708 float y = position.y;
709 float dx = projectile.directionNormal.x;
710 float dy = projectile.directionNormal.y;
711 for (float d = 1.0f; d > 0.0f; d -= 0.25f)
712 {
713 x -= dx * 0.1f;
714 y -= dy * 0.1f;
715 float size = 0.1f * d;
716 DrawCube((Vector3){x, 0.2f, y}, size, size, size, RED);
717 }
718 }
719 }
720
721 void ProjectileUpdate()
722 {
723 for (int i = 0; i < projectileCount; i++)
724 {
725 Projectile *projectile = &projectiles[i];
726 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
727 {
728 continue;
729 }
730 float transition = (gameTime.time - projectile->shootTime) / (projectile->arrivalTime - projectile->shootTime);
731 if (transition >= 1.0f)
732 {
733 projectile->projectileType = PROJECTILE_TYPE_NONE;
734 Enemy *enemy = EnemyTryResolve(projectile->targetEnemy);
735 if (enemy)
736 {
737 EnemyAddDamage(enemy, projectile->damage);
738 }
739 continue;
740 }
741 }
742 }
743
744 Projectile *ProjectileTryAdd(uint8_t projectileType, Enemy *enemy, Vector2 position, Vector2 target, float speed, float damage)
745 {
746 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
747 {
748 Projectile *projectile = &projectiles[i];
749 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
750 {
751 projectile->projectileType = projectileType;
752 projectile->shootTime = gameTime.time;
753 projectile->arrivalTime = gameTime.time + Vector2Distance(position, target) / speed;
754 projectile->damage = damage;
755 projectile->position = position;
756 projectile->target = target;
757 projectile->directionNormal = Vector2Normalize(Vector2Subtract(target, position));
758 projectile->targetEnemy = EnemyGetId(enemy);
759 projectileCount = projectileCount <= i ? i + 1 : projectileCount;
760 return projectile;
761 }
762 }
763 return 0;
764 }
765
766 //# Towers
767
768 void TowerInit()
769 {
770 for (int i = 0; i < TOWER_MAX_COUNT; i++)
771 {
772 towers[i] = (Tower){0};
773 }
774 towerCount = 0;
775 }
776
777 Tower *TowerGetAt(int16_t x, int16_t y)
778 {
779 for (int i = 0; i < towerCount; i++)
780 {
781 if (towers[i].x == x && towers[i].y == y)
782 {
783 return &towers[i];
784 }
785 }
786 return 0;
787 }
788
789 Tower *TowerTryAdd(uint8_t towerType, int16_t x, int16_t y)
790 {
791 if (towerCount >= TOWER_MAX_COUNT)
792 {
793 return 0;
794 }
795
796 Tower *tower = TowerGetAt(x, y);
797 if (tower)
798 {
799 return 0;
800 }
801
802 tower = &towers[towerCount++];
803 tower->x = x;
804 tower->y = y;
805 tower->towerType = towerType;
806 return tower;
807 }
808
809 void TowerDraw()
810 {
811 for (int i = 0; i < towerCount; i++)
812 {
813 Tower tower = towers[i];
814 DrawCube((Vector3){tower.x, 0.125f, tower.y}, 1.0f, 0.25f, 1.0f, GRAY);
815 switch (tower.towerType)
816 {
817 case TOWER_TYPE_BASE:
818 DrawCube((Vector3){tower.x, 0.4f, tower.y}, 0.8f, 0.8f, 0.8f, MAROON);
819 break;
820 case TOWER_TYPE_GUN:
821 DrawCube((Vector3){tower.x, 0.2f, tower.y}, 0.8f, 0.4f, 0.8f, DARKPURPLE);
822 break;
823 case TOWER_TYPE_WALL:
824 DrawCube((Vector3){tower.x, 0.5f, tower.y}, 1.0f, 1.0f, 1.0f, LIGHTGRAY);
825 break;
826 }
827 }
828 }
829
830 void TowerGunUpdate(Tower *tower)
831 {
832 if (tower->cooldown <= 0)
833 {
834 Enemy *enemy = EnemyGetClosestToCastle(tower->x, tower->y, 3.0f);
835 if (enemy)
836 {
837 tower->cooldown = 0.125f;
838 // shoot the enemy; determine future position of the enemy
839 float bulletSpeed = 1.0f;
840 float bulletDamage = 3.0f;
841 Vector2 velocity = enemy->simVelocity;
842 Vector2 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &velocity, 0);
843 Vector2 towerPosition = {tower->x, tower->y};
844 float eta = Vector2Distance(towerPosition, futurePosition) / bulletSpeed;
845 for (int i = 0; i < 8; i++) {
846 velocity = enemy->simVelocity;
847 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime + eta, &velocity, 0);
848 float distance = Vector2Distance(towerPosition, futurePosition);
849 float eta2 = distance / bulletSpeed;
850 if (fabs(eta - eta2) < 0.01f) {
851 break;
852 }
853 eta = (eta2 + eta) * 0.5f;
854 }
855 ProjectileTryAdd(PROJECTILE_TYPE_BULLET, enemy, towerPosition, futurePosition,
856 bulletSpeed, bulletDamage);
857 enemy->futureDamage += bulletDamage;
858 }
859 }
860 else
861 {
862 tower->cooldown -= gameTime.deltaTime;
863 }
864 }
865
866 void TowerUpdate()
867 {
868 for (int i = 0; i < towerCount; i++)
869 {
870 Tower *tower = &towers[i];
871 switch (tower->towerType)
872 {
873 case TOWER_TYPE_GUN:
874 TowerGunUpdate(tower);
875 break;
876 }
877 }
878 }
879
880 //# Game
881
882 float nextSpawnTime = 0.0f;
883
884 void InitGame()
885 {
886 TowerInit();
887 EnemyInit();
888 ProjectileInit();
889 PathfindingMapInit(20, 20, (Vector3){-10.0f, 0.0f, -10.0f}, 1.0f);
890
891 TowerTryAdd(TOWER_TYPE_BASE, 0, 0);
892 TowerTryAdd(TOWER_TYPE_GUN, 2, 0);
893 TowerTryAdd(TOWER_TYPE_GUN, -2, 0);
894
895 for (int i = -2; i <= 2; i += 1)
896 {
897 TowerTryAdd(TOWER_TYPE_WALL, i, 2);
898 TowerTryAdd(TOWER_TYPE_WALL, i, -2);
899 TowerTryAdd(TOWER_TYPE_WALL, -2, i);
900 TowerTryAdd(TOWER_TYPE_WALL, 2, i);
901 }
902
903 EnemyTryAdd(ENEMY_TYPE_MINION, 5, 4);
904 }
905
906 void GameUpdate()
907 {
908 float dt = GetFrameTime();
909 // cap maximum delta time to 0.1 seconds to prevent large time steps
910 if (dt > 0.1f) dt = 0.1f;
911 gameTime.time += dt;
912 gameTime.deltaTime = dt;
913 PathFindingMapUpdate();
914 EnemyUpdate();
915 TowerUpdate();
916 ProjectileUpdate();
917
918 // spawn a new enemy every second
919 if (gameTime.time >= nextSpawnTime && EnemyCount() < 50)
920 {
921 nextSpawnTime = gameTime.time + 0.2f;
922 // add a new enemy at the boundary of the map
923 int randValue = GetRandomValue(-5, 5);
924 int randSide = GetRandomValue(0, 3);
925 int16_t x = randSide == 0 ? -5 : randSide == 1 ? 5 : randValue;
926 int16_t y = randSide == 2 ? -5 : randSide == 3 ? 5 : randValue;
927 static int alternation = 0;
928 alternation += 1;
929 if (alternation % 3 == 0) {
930 EnemyTryAdd(ENEMY_TYPE_MINION, 0, -5);
931 }
932 else if (alternation % 3 == 1)
933 {
934 EnemyTryAdd(ENEMY_TYPE_MINION, 0, 5);
935 }
936 EnemyTryAdd(ENEMY_TYPE_MINION, x, y);
937 }
938 }
939
940 int main(void)
941 {
942 int screenWidth, screenHeight;
943 GetPreferredSize(&screenWidth, &screenHeight);
944 InitWindow(screenWidth, screenHeight, "Tower defense");
945 SetTargetFPS(30);
946
947 Camera3D camera = {0};
948 camera.position = (Vector3){0.0f, 10.0f, -0.5f};
949 camera.target = (Vector3){0.0f, 0.0f, -0.5f};
950 camera.up = (Vector3){0.0f, 0.0f, -1.0f};
951 camera.fovy = 12.0f;
952 camera.projection = CAMERA_ORTHOGRAPHIC;
953
954 InitGame();
955
956 while (!WindowShouldClose())
957 {
958 if (IsPaused()) {
959 // canvas is not visible in browser - do nothing
960 continue;
961 }
962 BeginDrawing();
963 ClearBackground(DARKBLUE);
964
965 BeginMode3D(camera);
966 DrawGrid(10, 1.0f);
967 TowerDraw();
968 EnemyDraw();
969 ProjectileDraw();
970 PathFindingMapDraw();
971 GameUpdate();
972 EndMode3D();
973
974 const char *title = "Tower defense tutorial";
975 int titleWidth = MeasureText(title, 20);
976 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f + 2, 5 + 2, 20, BLACK);
977 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f, 5, 20, WHITE);
978 EndDrawing();
979 }
980
981 CloseWindow();
982
983 return 0;
984 }
1 #ifndef TD_TUT_2_MAIN_H
2 #define TD_TUT_2_MAIN_H
3
4 #include <inttypes.h>
5
6 #include "raylib.h"
7 #include "preferred_size.h"
8
9 #endif
1 #include "raylib.h"
2 #include "preferred_size.h"
3
4 // Since the canvas size is not known at compile time, we need to query it at runtime;
5 // the following platform specific code obtains the canvas size and we will use this
6 // size as the preferred size for the window at init time. We're ignoring here the
7 // possibility of the canvas size changing during runtime - this would require to
8 // poll the canvas size in the game loop or establishing a callback to be notified
9
10 #ifdef PLATFORM_WEB
11 #include <emscripten.h>
12 EMSCRIPTEN_RESULT emscripten_get_element_css_size(const char *target, double *width, double *height);
13
14 void GetPreferredSize(int *screenWidth, int *screenHeight)
15 {
16 double canvasWidth, canvasHeight;
17 emscripten_get_element_css_size("#" CANVAS_NAME, &canvasWidth, &canvasHeight);
18 *screenWidth = (int)canvasWidth;
19 *screenHeight = (int)canvasHeight;
20 TraceLog(LOG_INFO, "preferred size for %s: %d %d", CANVAS_NAME, *screenWidth, *screenHeight);
21 }
22
23 int IsPaused()
24 {
25 const char *js = "(function(){\n"
26 " var canvas = document.getElementById(\"" CANVAS_NAME "\");\n"
27 " var rect = canvas.getBoundingClientRect();\n"
28 " var isVisible = (\n"
29 " rect.top >= 0 &&\n"
30 " rect.left >= 0 &&\n"
31 " rect.bottom <= (window.innerHeight || document.documentElement.clientHeight) &&\n"
32 " rect.right <= (window.innerWidth || document.documentElement.clientWidth)\n"
33 " );\n"
34 " return isVisible ? 0 : 1;\n"
35 "})()";
36 return emscripten_run_script_int(js);
37 }
38
39 #else
40 void GetPreferredSize(int *screenWidth, int *screenHeight)
41 {
42 *screenWidth = 600;
43 *screenHeight = 240;
44 }
45 int IsPaused()
46 {
47 return 0;
48 }
49 #endif
1 #ifndef PREFERRED_SIZE_H
2 #define PREFERRED_SIZE_H
3
4 void GetPreferredSize(int *screenWidth, int *screenHeight);
5 int IsPaused();
6
7 #endif
As expected, the enemies are now not doing anything. There is no gradient to follow.
We need a strategy what to do, when there is no way to the castle. The most simple solution is to let the enemies destroy the obstacles! So instead of blocking the path, we modify the path finding algorithm to increase the distance value of the obstacle cells. This way, the enemies will ignore the obstacles as long as there is a way around them. But if there is no way around, they will destroy the obstacle and continue their way to the castle.
Let's say that a wall has a distance penalty of 8. That means that as long as the alternative route is shorter than 8, the enemies will take the alternative route, otherwise they will go for the wall. Let's implement this and open the way to the castle on just one side to watch what happens:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 //# Declarations
7
8 #define TOWER_MAX_COUNT 400
9 #define TOWER_TYPE_NONE 0
10 #define TOWER_TYPE_BASE 1
11 #define TOWER_TYPE_GUN 2
12 #define TOWER_TYPE_WALL 3
13
14 typedef struct Tower
15 {
16 int16_t x, y;
17 uint8_t towerType;
18 float cooldown;
19 } Tower;
20
21 typedef struct GameTime
22 {
23 float time;
24 float deltaTime;
25 } GameTime;
26
27 GameTime gameTime = {0};
28
29 Tower towers[TOWER_MAX_COUNT];
30 int towerCount = 0;
31
32 //# Pathfinding map
33 typedef struct DeltaSrc
34 {
35 char x, y;
36 } DeltaSrc;
37
38 typedef struct PathfindingMap
39 {
40 int width, height;
41 float scale;
42 float *distances;
43 long *towerIndex;
44 DeltaSrc *deltaSrc;
45 float maxDistance;
46 Matrix toMapSpace;
47 Matrix toWorldSpace;
48 } PathfindingMap;
49
50 // when we execute the pathfinding algorithm, we need to store the active nodes
51 // in a queue. Each node has a position, a distance from the start, and the
52 // position of the node that we came from.
53 typedef struct PathfindingNode
54 {
55 int16_t x, y, fromX, fromY;
56 float distance;
57 } PathfindingNode;
58
59 // The queue is a simple array of nodes, we add nodes to the end and remove
60 // nodes from the front. We keep the array around to avoid unnecessary allocations
61 static PathfindingNode *pathfindingNodeQueue = 0;
62 static int pathfindingNodeQueueCount = 0;
63 static int pathfindingNodeQueueCapacity = 0;
64
65 // The pathfinding map stores the distances from the castle to each cell in the map.
66 PathfindingMap pathfindingMap = {0};
67
68 void PathfindingMapInit(int width, int height, Vector3 translate, float scale)
69 {
70 // transforming between map space and world space allows us to adapt
71 // position and scale of the map without changing the pathfinding data
72 pathfindingMap.toWorldSpace = MatrixTranslate(translate.x, translate.y, translate.z);
73 pathfindingMap.toWorldSpace = MatrixMultiply(pathfindingMap.toWorldSpace, MatrixScale(scale, scale, scale));
74 pathfindingMap.toMapSpace = MatrixInvert(pathfindingMap.toWorldSpace);
75 pathfindingMap.width = width;
76 pathfindingMap.height = height;
77 pathfindingMap.scale = scale;
78 pathfindingMap.distances = (float *)MemAlloc(width * height * sizeof(float));
79 for (int i = 0; i < width * height; i++)
80 {
81 pathfindingMap.distances[i] = -1.0f;
82 }
83
84 pathfindingMap.towerIndex = (long *)MemAlloc(width * height * sizeof(long));
85 pathfindingMap.deltaSrc = (DeltaSrc *)MemAlloc(width * height * sizeof(DeltaSrc));
86 }
87
88 float PathFindingGetDistance(int mapX, int mapY)
89 {
90 if (mapX < 0 || mapX >= pathfindingMap.width || mapY < 0 || mapY >= pathfindingMap.height)
91 {
92 // when outside the map, we return the manhattan distance to the castle (0,0)
93 return fabsf((float)mapX) + fabsf((float)mapY);
94 }
95
96 return pathfindingMap.distances[mapY * pathfindingMap.width + mapX];
97 }
98
99 void PathFindingNodePush(int16_t x, int16_t y, int16_t fromX, int16_t fromY, float distance)
100 {
101 if (pathfindingNodeQueueCount >= pathfindingNodeQueueCapacity)
102 {
103 pathfindingNodeQueueCapacity = pathfindingNodeQueueCapacity == 0 ? 256 : pathfindingNodeQueueCapacity * 2;
104 // we use MemAlloc/MemRealloc to allocate memory for the queue
105 // I am not entirely sure if MemRealloc allows passing a null pointer
106 // so we check if the pointer is null and use MemAlloc in that case
107 if (pathfindingNodeQueue == 0)
108 {
109 pathfindingNodeQueue = (PathfindingNode *)MemAlloc(pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
110 }
111 else
112 {
113 pathfindingNodeQueue = (PathfindingNode *)MemRealloc(pathfindingNodeQueue, pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
114 }
115 }
116
117 PathfindingNode *node = &pathfindingNodeQueue[pathfindingNodeQueueCount++];
118 node->x = x;
119 node->y = y;
120 node->fromX = fromX;
121 node->fromY = fromY;
122 node->distance = distance;
123 }
124
125 PathfindingNode *PathFindingNodePop()
126 {
127 if (pathfindingNodeQueueCount == 0)
128 {
129 return 0;
130 }
131 // we return the first node in the queue; we want to return a pointer to the node
132 // so we can return 0 if the queue is empty.
133 // We should _not_ return a pointer to the element in the list, because the list
134 // may be reallocated and the pointer would become invalid. Or the
135 // popped element is overwritten by the next push operation.
136 // Using static here means that the variable is permanently allocated.
137 static PathfindingNode node;
138 node = pathfindingNodeQueue[0];
139 // we shift all nodes one position to the front
140 for (int i = 1; i < pathfindingNodeQueueCount; i++)
141 {
142 pathfindingNodeQueue[i - 1] = pathfindingNodeQueue[i];
143 }
144 --pathfindingNodeQueueCount;
145 return &node;
146 }
147
148 // transform a world position to a map position in the array;
149 // returns true if the position is inside the map
150 int PathFindingFromWorldToMapPosition(Vector3 worldPosition, int16_t *mapX, int16_t *mapY)
151 {
152 Vector3 mapPosition = Vector3Transform(worldPosition, pathfindingMap.toMapSpace);
153 *mapX = (int16_t)mapPosition.x;
154 *mapY = (int16_t)mapPosition.z;
155 return *mapX >= 0 && *mapX < pathfindingMap.width && *mapY >= 0 && *mapY < pathfindingMap.height;
156 }
157
158 void PathFindingMapUpdate()
159 {
160 const int castleX = 0, castleY = 0;
161 int16_t castleMapX, castleMapY;
162 if (!PathFindingFromWorldToMapPosition((Vector3){castleX, 0.0f, castleY}, &castleMapX, &castleMapY))
163 {
164 return;
165 }
166 int width = pathfindingMap.width, height = pathfindingMap.height;
167
168 // reset the distances to -1
169 for (int i = 0; i < width * height; i++)
170 {
171 pathfindingMap.distances[i] = -1.0f;
172 }
173 // reset the tower indices
174 for (int i = 0; i < width * height; i++)
175 {
176 pathfindingMap.towerIndex[i] = -1;
177 }
178 // reset the delta src
179 for (int i = 0; i < width * height; i++)
180 {
181 pathfindingMap.deltaSrc[i].x = 0;
182 pathfindingMap.deltaSrc[i].y = 0;
183 }
184
185 for (int i = 0; i < towerCount; i++)
186 {
187 Tower *tower = &towers[i];
188 if (tower->towerType == TOWER_TYPE_NONE || tower->towerType == TOWER_TYPE_BASE)
189 {
190 continue;
191 }
192 int16_t mapX, mapY;
193 // technically, if the tower cell scale is not in sync with the pathfinding map scale,
194 // this would not work correctly and needs to be refined to allow towers covering multiple cells
195 // or having multiple towers in one cell; for simplicity, we assume that the tower covers exactly
196 // one cell. For now.
197 if (!PathFindingFromWorldToMapPosition((Vector3){tower->x, 0.0f, tower->y}, &mapX, &mapY))
198 {
199 continue;
200 }
201 int index = mapY * width + mapX;
202 pathfindingMap.towerIndex[index] = i;
203 }
204
205 // we start at the castle and add the castle to the queue
206 pathfindingMap.maxDistance = 0.0f;
207 pathfindingNodeQueueCount = 0;
208 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
209 PathfindingNode *node = 0;
210 while ((node = PathFindingNodePop()))
211 {
212 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
213 {
214 continue;
215 }
216 int index = node->y * width + node->x;
217 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
218 {
219 continue;
220 }
221
222 int deltaX = node->x - node->fromX;
223 int deltaY = node->y - node->fromY;
224 // even if the cell is blocked by a tower, we still may want to store the direction
225 // (though this might not be needed, IDK right now)
226 pathfindingMap.deltaSrc[index].x = (char) deltaX;
227 pathfindingMap.deltaSrc[index].y = (char) deltaY;
228
229 // we skip nodes that are blocked by towers
230 if (pathfindingMap.towerIndex[index] >= 0)
231 {
232 node->distance += 8.0f;
233 }
234 pathfindingMap.distances[index] = node->distance;
235 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
236 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
237 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
238 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
239 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
240 }
241 }
242
243 void PathFindingMapDraw()
244 {
245 float cellSize = pathfindingMap.scale * 0.9f;
246 float highlightDistance = fmodf(GetTime() * 4.0f, pathfindingMap.maxDistance);
247 for (int x = 0; x < pathfindingMap.width; x++)
248 {
249 for (int y = 0; y < pathfindingMap.height; y++)
250 {
251 float distance = pathfindingMap.distances[y * pathfindingMap.width + x];
252 float colorV = distance < 0 ? 0 : fminf(distance / pathfindingMap.maxDistance, 1.0f);
253 Color color = distance < 0 ? BLUE : (Color){fminf(colorV, 1.0f) * 255, 0, 0, 255};
254 Vector3 position = Vector3Transform((Vector3){x, -0.25f, y}, pathfindingMap.toWorldSpace);
255 // animate the distance "wave" to show how the pathfinding algorithm expands
256 // from the castle
257 if (distance + 0.5f > highlightDistance && distance - 0.5f < highlightDistance)
258 {
259 color = YELLOW;
260 }
261 DrawCube(position, cellSize, 0.1f, cellSize, color);
262 }
263 }
264 }
265
266 Vector2 PathFindingGetGradient(Vector3 world)
267 {
268 int16_t mapX, mapY;
269 if (PathFindingFromWorldToMapPosition(world, &mapX, &mapY))
270 {
271 DeltaSrc delta = pathfindingMap.deltaSrc[mapY * pathfindingMap.width + mapX];
272 return (Vector2){(float)-delta.x, (float)-delta.y};
273 }
274 // fallback to a simple gradient calculation
275 float n = PathFindingGetDistance(mapX, mapY - 1);
276 float s = PathFindingGetDistance(mapX, mapY + 1);
277 float w = PathFindingGetDistance(mapX - 1, mapY);
278 float e = PathFindingGetDistance(mapX + 1, mapY);
279 return (Vector2){w - e + 0.25f, n - s + 0.125f};
280 }
281
282 //# Enemies
283
284 #define ENEMY_MAX_PATH_COUNT 8
285 #define ENEMY_MAX_COUNT 400
286 #define ENEMY_TYPE_NONE 0
287 #define ENEMY_TYPE_MINION 1
288
289 typedef struct EnemyId
290 {
291 uint16_t index;
292 uint16_t generation;
293 } EnemyId;
294
295 typedef struct EnemyClassConfig
296 {
297 float speed;
298 float health;
299 float radius;
300 float maxAcceleration;
301 } EnemyClassConfig;
302
303 typedef struct Enemy
304 {
305 int16_t currentX, currentY;
306 int16_t nextX, nextY;
307 Vector2 simPosition;
308 Vector2 simVelocity;
309 uint16_t generation;
310 float startMovingTime;
311 float damage, futureDamage;
312 uint8_t enemyType;
313 uint8_t movePathCount;
314 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
315 } Enemy;
316
317 Enemy enemies[ENEMY_MAX_COUNT];
318 int enemyCount = 0;
319
320 EnemyClassConfig enemyClassConfigs[] = {
321 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
322 };
323
324 void EnemyInit()
325 {
326 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
327 {
328 enemies[i] = (Enemy){0};
329 }
330 enemyCount = 0;
331 }
332
333 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
334 {
335 return enemyClassConfigs[enemy->enemyType].speed;
336 }
337
338 float EnemyGetMaxHealth(Enemy *enemy)
339 {
340 return enemyClassConfigs[enemy->enemyType].health;
341 }
342
343 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
344 {
345 int16_t castleX = 0;
346 int16_t castleY = 0;
347 int16_t dx = castleX - currentX;
348 int16_t dy = castleY - currentY;
349 if (dx == 0 && dy == 0)
350 {
351 *nextX = currentX;
352 *nextY = currentY;
353 return 1;
354 }
355 Vector2 gradient = PathFindingGetGradient((Vector3){currentX, 0, currentY});
356
357 if (gradient.x == 0 && gradient.y == 0)
358 {
359 *nextX = currentX;
360 *nextY = currentY;
361 return 1;
362 }
363
364 if (fabsf(gradient.x) > fabsf(gradient.y))
365 {
366 *nextX = currentX + (int16_t)(gradient.x > 0.0f ? 1 : -1);
367 *nextY = currentY;
368 return 0;
369 }
370 *nextX = currentX;
371 *nextY = currentY + (int16_t)(gradient.y > 0.0f ? 1 : -1);
372 return 0;
373 }
374
375
376 // this function predicts the movement of the unit for the next deltaT seconds
377 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
378 {
379 const float pointReachedDistance = 0.25f;
380 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
381 const float maxSimStepTime = 0.015625f;
382
383 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
384 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
385 int16_t nextX = enemy->nextX;
386 int16_t nextY = enemy->nextY;
387 Vector2 position = enemy->simPosition;
388 int passedCount = 0;
389 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
390 {
391 float stepTime = fminf(deltaT - t, maxSimStepTime);
392 Vector2 target = (Vector2){nextX, nextY};
393 float speed = Vector2Length(*velocity);
394 // draw the target position for debugging
395 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
396 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
397 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
398 {
399 // we reached the target position, let's move to the next waypoint
400 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
401 target = (Vector2){nextX, nextY};
402 // track how many waypoints we passed
403 passedCount++;
404 }
405
406 // acceleration towards the target
407 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
408 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
409 *velocity = Vector2Add(*velocity, acceleration);
410
411 // limit the speed to the maximum speed
412 if (speed > maxSpeed)
413 {
414 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
415 }
416
417 // move the enemy
418 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
419 }
420
421 if (waypointPassedCount)
422 {
423 (*waypointPassedCount) = passedCount;
424 }
425
426 return position;
427 }
428
429 void EnemyDraw()
430 {
431 for (int i = 0; i < enemyCount; i++)
432 {
433 Enemy enemy = enemies[i];
434 if (enemy.enemyType == ENEMY_TYPE_NONE)
435 {
436 continue;
437 }
438
439 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
440
441 if (enemy.movePathCount > 0)
442 {
443 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
444 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
445 }
446 for (int j = 1; j < enemy.movePathCount; j++)
447 {
448 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
449 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
450 DrawLine3D(p, q, GREEN);
451 }
452
453 switch (enemy.enemyType)
454 {
455 case ENEMY_TYPE_MINION:
456 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
457 break;
458 }
459 }
460 }
461
462 void EnemyUpdate()
463 {
464 const float castleX = 0;
465 const float castleY = 0;
466 const float maxPathDistance2 = 0.25f * 0.25f;
467
468 for (int i = 0; i < enemyCount; i++)
469 {
470 Enemy *enemy = &enemies[i];
471 if (enemy->enemyType == ENEMY_TYPE_NONE)
472 {
473 continue;
474 }
475
476 int waypointPassedCount = 0;
477 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
478 enemy->startMovingTime = gameTime.time;
479 // track path of unit
480 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
481 {
482 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
483 {
484 enemy->movePath[j] = enemy->movePath[j - 1];
485 }
486 enemy->movePath[0] = enemy->simPosition;
487 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
488 {
489 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
490 }
491 }
492
493 if (waypointPassedCount > 0)
494 {
495 enemy->currentX = enemy->nextX;
496 enemy->currentY = enemy->nextY;
497 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
498 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
499 {
500 // enemy reached the castle; remove it
501 enemy->enemyType = ENEMY_TYPE_NONE;
502 continue;
503 }
504 }
505 }
506
507 // handle collisions
508 for (int i = 0; i < enemyCount - 1; i++)
509 {
510 Enemy *enemyA = &enemies[i];
511 if (enemyA->enemyType == ENEMY_TYPE_NONE)
512 {
513 continue;
514 }
515 for (int j = i + 1; j < enemyCount; j++)
516 {
517 Enemy *enemyB = &enemies[j];
518 if (enemyB->enemyType == ENEMY_TYPE_NONE)
519 {
520 continue;
521 }
522 float distanceSqr = Vector2DistanceSqr(enemyA->simPosition, enemyB->simPosition);
523 float radiusA = enemyClassConfigs[enemyA->enemyType].radius;
524 float radiusB = enemyClassConfigs[enemyB->enemyType].radius;
525 float radiusSum = radiusA + radiusB;
526 if (distanceSqr < radiusSum * radiusSum && distanceSqr > 0.001f)
527 {
528 // collision
529 float distance = sqrtf(distanceSqr);
530 float overlap = radiusSum - distance;
531 // move the enemies apart, but softly; if we have a clog of enemies,
532 // moving them perfectly apart can cause them to jitter
533 float positionCorrection = overlap / 5.0f;
534 Vector2 direction = (Vector2){
535 (enemyB->simPosition.x - enemyA->simPosition.x) / distance * positionCorrection,
536 (enemyB->simPosition.y - enemyA->simPosition.y) / distance * positionCorrection};
537 enemyA->simPosition = Vector2Subtract(enemyA->simPosition, direction);
538 enemyB->simPosition = Vector2Add(enemyB->simPosition, direction);
539 }
540 }
541 }
542 }
543
544 EnemyId EnemyGetId(Enemy *enemy)
545 {
546 return (EnemyId){enemy - enemies, enemy->generation};
547 }
548
549 Enemy *EnemyTryResolve(EnemyId enemyId)
550 {
551 if (enemyId.index >= ENEMY_MAX_COUNT)
552 {
553 return 0;
554 }
555 Enemy *enemy = &enemies[enemyId.index];
556 if (enemy->generation != enemyId.generation || enemy->enemyType == ENEMY_TYPE_NONE)
557 {
558 return 0;
559 }
560 return enemy;
561 }
562
563 Enemy *EnemyTryAdd(uint8_t enemyType, int16_t currentX, int16_t currentY)
564 {
565 Enemy *spawn = 0;
566 for (int i = 0; i < enemyCount; i++)
567 {
568 Enemy *enemy = &enemies[i];
569 if (enemy->enemyType == ENEMY_TYPE_NONE)
570 {
571 spawn = enemy;
572 break;
573 }
574 }
575
576 if (enemyCount < ENEMY_MAX_COUNT && !spawn)
577 {
578 spawn = &enemies[enemyCount++];
579 }
580
581 if (spawn)
582 {
583 spawn->currentX = currentX;
584 spawn->currentY = currentY;
585 spawn->nextX = currentX;
586 spawn->nextY = currentY;
587 spawn->simPosition = (Vector2){currentX, currentY};
588 spawn->simVelocity = (Vector2){0, 0};
589 spawn->enemyType = enemyType;
590 spawn->startMovingTime = gameTime.time;
591 spawn->damage = 0.0f;
592 spawn->futureDamage = 0.0f;
593 spawn->generation++;
594 spawn->movePathCount = 0;
595 }
596
597 return spawn;
598 }
599
600 int EnemyAddDamage(Enemy *enemy, float damage)
601 {
602 enemy->damage += damage;
603 if (enemy->damage >= EnemyGetMaxHealth(enemy))
604 {
605 enemy->enemyType = ENEMY_TYPE_NONE;
606 return 1;
607 }
608
609 return 0;
610 }
611
612 Enemy* EnemyGetClosestToCastle(int16_t towerX, int16_t towerY, float range)
613 {
614 int16_t castleX = 0;
615 int16_t castleY = 0;
616 Enemy* closest = 0;
617 int16_t closestDistance = 0;
618 float range2 = range * range;
619 for (int i = 0; i < enemyCount; i++)
620 {
621 Enemy* enemy = &enemies[i];
622 if (enemy->enemyType == ENEMY_TYPE_NONE)
623 {
624 continue;
625 }
626 float maxHealth = EnemyGetMaxHealth(enemy);
627 if (enemy->futureDamage >= maxHealth)
628 {
629 // ignore enemies that will die soon
630 continue;
631 }
632 int16_t dx = castleX - enemy->currentX;
633 int16_t dy = castleY - enemy->currentY;
634 int16_t distance = abs(dx) + abs(dy);
635 if (!closest || distance < closestDistance)
636 {
637 float tdx = towerX - enemy->currentX;
638 float tdy = towerY - enemy->currentY;
639 float tdistance2 = tdx * tdx + tdy * tdy;
640 if (tdistance2 <= range2)
641 {
642 closest = enemy;
643 closestDistance = distance;
644 }
645 }
646 }
647 return closest;
648 }
649
650 int EnemyCount()
651 {
652 int count = 0;
653 for (int i = 0; i < enemyCount; i++)
654 {
655 if (enemies[i].enemyType != ENEMY_TYPE_NONE)
656 {
657 count++;
658 }
659 }
660 return count;
661 }
662
663 //# Projectiles
664 #define PROJECTILE_MAX_COUNT 1200
665 #define PROJECTILE_TYPE_NONE 0
666 #define PROJECTILE_TYPE_BULLET 1
667
668 typedef struct Projectile
669 {
670 uint8_t projectileType;
671 float shootTime;
672 float arrivalTime;
673 float damage;
674 Vector2 position;
675 Vector2 target;
676 Vector2 directionNormal;
677 EnemyId targetEnemy;
678 } Projectile;
679
680 Projectile projectiles[PROJECTILE_MAX_COUNT];
681 int projectileCount = 0;
682
683 void ProjectileInit()
684 {
685 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
686 {
687 projectiles[i] = (Projectile){0};
688 }
689 }
690
691 void ProjectileDraw()
692 {
693 for (int i = 0; i < projectileCount; i++)
694 {
695 Projectile projectile = projectiles[i];
696 if (projectile.projectileType == PROJECTILE_TYPE_NONE)
697 {
698 continue;
699 }
700 float transition = (gameTime.time - projectile.shootTime) / (projectile.arrivalTime - projectile.shootTime);
701 if (transition >= 1.0f)
702 {
703 continue;
704 }
705 Vector2 position = Vector2Lerp(projectile.position, projectile.target, transition);
706 float x = position.x;
707 float y = position.y;
708 float dx = projectile.directionNormal.x;
709 float dy = projectile.directionNormal.y;
710 for (float d = 1.0f; d > 0.0f; d -= 0.25f)
711 {
712 x -= dx * 0.1f;
713 y -= dy * 0.1f;
714 float size = 0.1f * d;
715 DrawCube((Vector3){x, 0.2f, y}, size, size, size, RED);
716 }
717 }
718 }
719
720 void ProjectileUpdate()
721 {
722 for (int i = 0; i < projectileCount; i++)
723 {
724 Projectile *projectile = &projectiles[i];
725 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
726 {
727 continue;
728 }
729 float transition = (gameTime.time - projectile->shootTime) / (projectile->arrivalTime - projectile->shootTime);
730 if (transition >= 1.0f)
731 {
732 projectile->projectileType = PROJECTILE_TYPE_NONE;
733 Enemy *enemy = EnemyTryResolve(projectile->targetEnemy);
734 if (enemy)
735 {
736 EnemyAddDamage(enemy, projectile->damage);
737 }
738 continue;
739 }
740 }
741 }
742
743 Projectile *ProjectileTryAdd(uint8_t projectileType, Enemy *enemy, Vector2 position, Vector2 target, float speed, float damage)
744 {
745 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
746 {
747 Projectile *projectile = &projectiles[i];
748 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
749 {
750 projectile->projectileType = projectileType;
751 projectile->shootTime = gameTime.time;
752 projectile->arrivalTime = gameTime.time + Vector2Distance(position, target) / speed;
753 projectile->damage = damage;
754 projectile->position = position;
755 projectile->target = target;
756 projectile->directionNormal = Vector2Normalize(Vector2Subtract(target, position));
757 projectile->targetEnemy = EnemyGetId(enemy);
758 projectileCount = projectileCount <= i ? i + 1 : projectileCount;
759 return projectile;
760 }
761 }
762 return 0;
763 }
764
765 //# Towers
766
767 void TowerInit()
768 {
769 for (int i = 0; i < TOWER_MAX_COUNT; i++)
770 {
771 towers[i] = (Tower){0};
772 }
773 towerCount = 0;
774 }
775
776 Tower *TowerGetAt(int16_t x, int16_t y)
777 {
778 for (int i = 0; i < towerCount; i++)
779 {
780 if (towers[i].x == x && towers[i].y == y)
781 {
782 return &towers[i];
783 }
784 }
785 return 0;
786 }
787
788 Tower *TowerTryAdd(uint8_t towerType, int16_t x, int16_t y)
789 {
790 if (towerCount >= TOWER_MAX_COUNT)
791 {
792 return 0;
793 }
794
795 Tower *tower = TowerGetAt(x, y);
796 if (tower)
797 {
798 return 0;
799 }
800
801 tower = &towers[towerCount++];
802 tower->x = x;
803 tower->y = y;
804 tower->towerType = towerType;
805 return tower;
806 }
807
808 void TowerDraw()
809 {
810 for (int i = 0; i < towerCount; i++)
811 {
812 Tower tower = towers[i];
813 DrawCube((Vector3){tower.x, 0.125f, tower.y}, 1.0f, 0.25f, 1.0f, GRAY);
814 switch (tower.towerType)
815 {
816 case TOWER_TYPE_BASE:
817 DrawCube((Vector3){tower.x, 0.4f, tower.y}, 0.8f, 0.8f, 0.8f, MAROON);
818 break;
819 case TOWER_TYPE_GUN:
820 DrawCube((Vector3){tower.x, 0.2f, tower.y}, 0.8f, 0.4f, 0.8f, DARKPURPLE);
821 break;
822 case TOWER_TYPE_WALL:
823 DrawCube((Vector3){tower.x, 0.5f, tower.y}, 1.0f, 1.0f, 1.0f, LIGHTGRAY);
824 break;
825 }
826 }
827 }
828
829 void TowerGunUpdate(Tower *tower)
830 {
831 if (tower->cooldown <= 0)
832 {
833 Enemy *enemy = EnemyGetClosestToCastle(tower->x, tower->y, 3.0f);
834 if (enemy)
835 {
836 tower->cooldown = 0.125f;
837 // shoot the enemy; determine future position of the enemy
838 float bulletSpeed = 1.0f;
839 float bulletDamage = 3.0f;
840 Vector2 velocity = enemy->simVelocity;
841 Vector2 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &velocity, 0);
842 Vector2 towerPosition = {tower->x, tower->y};
843 float eta = Vector2Distance(towerPosition, futurePosition) / bulletSpeed;
844 for (int i = 0; i < 8; i++) {
845 velocity = enemy->simVelocity;
846 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime + eta, &velocity, 0);
847 float distance = Vector2Distance(towerPosition, futurePosition);
848 float eta2 = distance / bulletSpeed;
849 if (fabs(eta - eta2) < 0.01f) {
850 break;
851 }
852 eta = (eta2 + eta) * 0.5f;
853 }
854 ProjectileTryAdd(PROJECTILE_TYPE_BULLET, enemy, towerPosition, futurePosition,
855 bulletSpeed, bulletDamage);
856 enemy->futureDamage += bulletDamage;
857 }
858 }
859 else
860 {
861 tower->cooldown -= gameTime.deltaTime;
862 }
863 }
864
865 void TowerUpdate()
866 {
867 for (int i = 0; i < towerCount; i++)
868 {
869 Tower *tower = &towers[i];
870 switch (tower->towerType)
871 {
872 case TOWER_TYPE_GUN:
873 TowerGunUpdate(tower);
874 break;
875 }
876 }
877 }
878
879 //# Game
880
881 float nextSpawnTime = 0.0f;
882
883 void InitGame()
884 {
885 TowerInit();
886 EnemyInit();
887 ProjectileInit();
888 PathfindingMapInit(20, 20, (Vector3){-10.0f, 0.0f, -10.0f}, 1.0f);
889
890 TowerTryAdd(TOWER_TYPE_BASE, 0, 0);
891 TowerTryAdd(TOWER_TYPE_GUN, 2, 0);
892
893 for (int i = -2; i <= 2; i += 1)
894 {
895 TowerTryAdd(TOWER_TYPE_WALL, i, 2);
896 TowerTryAdd(TOWER_TYPE_WALL, i, -2);
897 TowerTryAdd(TOWER_TYPE_WALL, -2, i);
898 }
899
900 EnemyTryAdd(ENEMY_TYPE_MINION, 5, 4);
901 }
902
903 void GameUpdate()
904 {
905 float dt = GetFrameTime();
906 // cap maximum delta time to 0.1 seconds to prevent large time steps
907 if (dt > 0.1f) dt = 0.1f;
908 gameTime.time += dt;
909 gameTime.deltaTime = dt;
910 PathFindingMapUpdate();
911 EnemyUpdate();
912 TowerUpdate();
913 ProjectileUpdate();
914
915 // spawn a new enemy every second
916 if (gameTime.time >= nextSpawnTime && EnemyCount() < 50)
917 {
918 nextSpawnTime = gameTime.time + 0.2f;
919 // add a new enemy at the boundary of the map
920 int randValue = GetRandomValue(-5, 5);
921 int randSide = GetRandomValue(0, 3);
922 int16_t x = randSide == 0 ? -5 : randSide == 1 ? 5 : randValue;
923 int16_t y = randSide == 2 ? -5 : randSide == 3 ? 5 : randValue;
924 static int alternation = 0;
925 alternation += 1;
926 if (alternation % 3 == 0) {
927 EnemyTryAdd(ENEMY_TYPE_MINION, 0, -5);
928 }
929 else if (alternation % 3 == 1)
930 {
931 EnemyTryAdd(ENEMY_TYPE_MINION, 0, 5);
932 }
933 EnemyTryAdd(ENEMY_TYPE_MINION, x, y);
934 }
935 }
936
937 int main(void)
938 {
939 int screenWidth, screenHeight;
940 GetPreferredSize(&screenWidth, &screenHeight);
941 InitWindow(screenWidth, screenHeight, "Tower defense");
942 SetTargetFPS(30);
943
944 Camera3D camera = {0};
945 camera.position = (Vector3){0.0f, 10.0f, -0.5f};
946 camera.target = (Vector3){0.0f, 0.0f, -0.5f};
947 camera.up = (Vector3){0.0f, 0.0f, -1.0f};
948 camera.fovy = 12.0f;
949 camera.projection = CAMERA_ORTHOGRAPHIC;
950
951 InitGame();
952
953 while (!WindowShouldClose())
954 {
955 if (IsPaused()) {
956 // canvas is not visible in browser - do nothing
957 continue;
958 }
959 BeginDrawing();
960 ClearBackground(DARKBLUE);
961
962 BeginMode3D(camera);
963 DrawGrid(10, 1.0f);
964 TowerDraw();
965 EnemyDraw();
966 ProjectileDraw();
967 PathFindingMapDraw();
968 GameUpdate();
969 EndMode3D();
970
971 const char *title = "Tower defense tutorial";
972 int titleWidth = MeasureText(title, 20);
973 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f + 2, 5 + 2, 20, BLACK);
974 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f, 5, 20, WHITE);
975 EndDrawing();
976 }
977
978 CloseWindow();
979
980 return 0;
981 }
1 #ifndef TD_TUT_2_MAIN_H
2 #define TD_TUT_2_MAIN_H
3
4 #include <inttypes.h>
5
6 #include "raylib.h"
7 #include "preferred_size.h"
8
9 #endif
1 #include "raylib.h"
2 #include "preferred_size.h"
3
4 // Since the canvas size is not known at compile time, we need to query it at runtime;
5 // the following platform specific code obtains the canvas size and we will use this
6 // size as the preferred size for the window at init time. We're ignoring here the
7 // possibility of the canvas size changing during runtime - this would require to
8 // poll the canvas size in the game loop or establishing a callback to be notified
9
10 #ifdef PLATFORM_WEB
11 #include <emscripten.h>
12 EMSCRIPTEN_RESULT emscripten_get_element_css_size(const char *target, double *width, double *height);
13
14 void GetPreferredSize(int *screenWidth, int *screenHeight)
15 {
16 double canvasWidth, canvasHeight;
17 emscripten_get_element_css_size("#" CANVAS_NAME, &canvasWidth, &canvasHeight);
18 *screenWidth = (int)canvasWidth;
19 *screenHeight = (int)canvasHeight;
20 TraceLog(LOG_INFO, "preferred size for %s: %d %d", CANVAS_NAME, *screenWidth, *screenHeight);
21 }
22
23 int IsPaused()
24 {
25 const char *js = "(function(){\n"
26 " var canvas = document.getElementById(\"" CANVAS_NAME "\");\n"
27 " var rect = canvas.getBoundingClientRect();\n"
28 " var isVisible = (\n"
29 " rect.top >= 0 &&\n"
30 " rect.left >= 0 &&\n"
31 " rect.bottom <= (window.innerHeight || document.documentElement.clientHeight) &&\n"
32 " rect.right <= (window.innerWidth || document.documentElement.clientWidth)\n"
33 " );\n"
34 " return isVisible ? 0 : 1;\n"
35 "})()";
36 return emscripten_run_script_int(js);
37 }
38
39 #else
40 void GetPreferredSize(int *screenWidth, int *screenHeight)
41 {
42 *screenWidth = 600;
43 *screenHeight = 240;
44 }
45 int IsPaused()
46 {
47 return 0;
48 }
49 #endif
1 #ifndef PREFERRED_SIZE_H
2 #define PREFERRED_SIZE_H
3
4 void GetPreferredSize(int *screenWidth, int *screenHeight);
5 int IsPaused();
6
7 #endif
I also removed the tower on the left side to give enemies the chance to get to the wall; and we can see that they are simply clipping through the wall. This is similar to another issue: When the enemies start squeezing through choke points, they also just clip through the walls - they don't care about the obstacles at all.
So the next step is to repulse the enemies from the obstacles:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 //# Declarations
7
8 #define TOWER_MAX_COUNT 400
9 #define TOWER_TYPE_NONE 0
10 #define TOWER_TYPE_BASE 1
11 #define TOWER_TYPE_GUN 2
12 #define TOWER_TYPE_WALL 3
13
14 typedef struct Tower
15 {
16 int16_t x, y;
17 uint8_t towerType;
18 float cooldown;
19 } Tower;
20
21 typedef struct GameTime
22 {
23 float time;
24 float deltaTime;
25 } GameTime;
26
27 GameTime gameTime = {0};
28
29 Tower towers[TOWER_MAX_COUNT];
30 int towerCount = 0;
31
32 //# Pathfinding map
33 typedef struct DeltaSrc
34 {
35 char x, y;
36 } DeltaSrc;
37
38 typedef struct PathfindingMap
39 {
40 int width, height;
41 float scale;
42 float *distances;
43 long *towerIndex;
44 DeltaSrc *deltaSrc;
45 float maxDistance;
46 Matrix toMapSpace;
47 Matrix toWorldSpace;
48 } PathfindingMap;
49
50 // when we execute the pathfinding algorithm, we need to store the active nodes
51 // in a queue. Each node has a position, a distance from the start, and the
52 // position of the node that we came from.
53 typedef struct PathfindingNode
54 {
55 int16_t x, y, fromX, fromY;
56 float distance;
57 } PathfindingNode;
58
59 // The queue is a simple array of nodes, we add nodes to the end and remove
60 // nodes from the front. We keep the array around to avoid unnecessary allocations
61 static PathfindingNode *pathfindingNodeQueue = 0;
62 static int pathfindingNodeQueueCount = 0;
63 static int pathfindingNodeQueueCapacity = 0;
64
65 // The pathfinding map stores the distances from the castle to each cell in the map.
66 PathfindingMap pathfindingMap = {0};
67
68 void PathfindingMapInit(int width, int height, Vector3 translate, float scale)
69 {
70 // transforming between map space and world space allows us to adapt
71 // position and scale of the map without changing the pathfinding data
72 pathfindingMap.toWorldSpace = MatrixTranslate(translate.x, translate.y, translate.z);
73 pathfindingMap.toWorldSpace = MatrixMultiply(pathfindingMap.toWorldSpace, MatrixScale(scale, scale, scale));
74 pathfindingMap.toMapSpace = MatrixInvert(pathfindingMap.toWorldSpace);
75 pathfindingMap.width = width;
76 pathfindingMap.height = height;
77 pathfindingMap.scale = scale;
78 pathfindingMap.distances = (float *)MemAlloc(width * height * sizeof(float));
79 for (int i = 0; i < width * height; i++)
80 {
81 pathfindingMap.distances[i] = -1.0f;
82 }
83
84 pathfindingMap.towerIndex = (long *)MemAlloc(width * height * sizeof(long));
85 pathfindingMap.deltaSrc = (DeltaSrc *)MemAlloc(width * height * sizeof(DeltaSrc));
86 }
87
88 float PathFindingGetDistance(int mapX, int mapY)
89 {
90 if (mapX < 0 || mapX >= pathfindingMap.width || mapY < 0 || mapY >= pathfindingMap.height)
91 {
92 // when outside the map, we return the manhattan distance to the castle (0,0)
93 return fabsf((float)mapX) + fabsf((float)mapY);
94 }
95
96 return pathfindingMap.distances[mapY * pathfindingMap.width + mapX];
97 }
98
99 void PathFindingNodePush(int16_t x, int16_t y, int16_t fromX, int16_t fromY, float distance)
100 {
101 if (pathfindingNodeQueueCount >= pathfindingNodeQueueCapacity)
102 {
103 pathfindingNodeQueueCapacity = pathfindingNodeQueueCapacity == 0 ? 256 : pathfindingNodeQueueCapacity * 2;
104 // we use MemAlloc/MemRealloc to allocate memory for the queue
105 // I am not entirely sure if MemRealloc allows passing a null pointer
106 // so we check if the pointer is null and use MemAlloc in that case
107 if (pathfindingNodeQueue == 0)
108 {
109 pathfindingNodeQueue = (PathfindingNode *)MemAlloc(pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
110 }
111 else
112 {
113 pathfindingNodeQueue = (PathfindingNode *)MemRealloc(pathfindingNodeQueue, pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
114 }
115 }
116
117 PathfindingNode *node = &pathfindingNodeQueue[pathfindingNodeQueueCount++];
118 node->x = x;
119 node->y = y;
120 node->fromX = fromX;
121 node->fromY = fromY;
122 node->distance = distance;
123 }
124
125 PathfindingNode *PathFindingNodePop()
126 {
127 if (pathfindingNodeQueueCount == 0)
128 {
129 return 0;
130 }
131 // we return the first node in the queue; we want to return a pointer to the node
132 // so we can return 0 if the queue is empty.
133 // We should _not_ return a pointer to the element in the list, because the list
134 // may be reallocated and the pointer would become invalid. Or the
135 // popped element is overwritten by the next push operation.
136 // Using static here means that the variable is permanently allocated.
137 static PathfindingNode node;
138 node = pathfindingNodeQueue[0];
139 // we shift all nodes one position to the front
140 for (int i = 1; i < pathfindingNodeQueueCount; i++)
141 {
142 pathfindingNodeQueue[i - 1] = pathfindingNodeQueue[i];
143 }
144 --pathfindingNodeQueueCount;
145 return &node;
146 }
147
148 // transform a world position to a map position in the array;
149 // returns true if the position is inside the map
150 int PathFindingFromWorldToMapPosition(Vector3 worldPosition, int16_t *mapX, int16_t *mapY)
151 {
152 Vector3 mapPosition = Vector3Transform(worldPosition, pathfindingMap.toMapSpace);
153 *mapX = (int16_t)mapPosition.x;
154 *mapY = (int16_t)mapPosition.z;
155 return *mapX >= 0 && *mapX < pathfindingMap.width && *mapY >= 0 && *mapY < pathfindingMap.height;
156 }
157
158 void PathFindingMapUpdate()
159 {
160 const int castleX = 0, castleY = 0;
161 int16_t castleMapX, castleMapY;
162 if (!PathFindingFromWorldToMapPosition((Vector3){castleX, 0.0f, castleY}, &castleMapX, &castleMapY))
163 {
164 return;
165 }
166 int width = pathfindingMap.width, height = pathfindingMap.height;
167
168 // reset the distances to -1
169 for (int i = 0; i < width * height; i++)
170 {
171 pathfindingMap.distances[i] = -1.0f;
172 }
173 // reset the tower indices
174 for (int i = 0; i < width * height; i++)
175 {
176 pathfindingMap.towerIndex[i] = -1;
177 }
178 // reset the delta src
179 for (int i = 0; i < width * height; i++)
180 {
181 pathfindingMap.deltaSrc[i].x = 0;
182 pathfindingMap.deltaSrc[i].y = 0;
183 }
184
185 for (int i = 0; i < towerCount; i++)
186 {
187 Tower *tower = &towers[i];
188 if (tower->towerType == TOWER_TYPE_NONE || tower->towerType == TOWER_TYPE_BASE)
189 {
190 continue;
191 }
192 int16_t mapX, mapY;
193 // technically, if the tower cell scale is not in sync with the pathfinding map scale,
194 // this would not work correctly and needs to be refined to allow towers covering multiple cells
195 // or having multiple towers in one cell; for simplicity, we assume that the tower covers exactly
196 // one cell. For now.
197 if (!PathFindingFromWorldToMapPosition((Vector3){tower->x, 0.0f, tower->y}, &mapX, &mapY))
198 {
199 continue;
200 }
201 int index = mapY * width + mapX;
202 pathfindingMap.towerIndex[index] = i;
203 }
204
205 // we start at the castle and add the castle to the queue
206 pathfindingMap.maxDistance = 0.0f;
207 pathfindingNodeQueueCount = 0;
208 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
209 PathfindingNode *node = 0;
210 while ((node = PathFindingNodePop()))
211 {
212 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
213 {
214 continue;
215 }
216 int index = node->y * width + node->x;
217 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
218 {
219 continue;
220 }
221
222 int deltaX = node->x - node->fromX;
223 int deltaY = node->y - node->fromY;
224 // even if the cell is blocked by a tower, we still may want to store the direction
225 // (though this might not be needed, IDK right now)
226 pathfindingMap.deltaSrc[index].x = (char) deltaX;
227 pathfindingMap.deltaSrc[index].y = (char) deltaY;
228
229 // we skip nodes that are blocked by towers
230 if (pathfindingMap.towerIndex[index] >= 0)
231 {
232 node->distance += 8.0f;
233 }
234 pathfindingMap.distances[index] = node->distance;
235 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
236 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
237 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
238 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
239 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
240 }
241 }
242
243 void PathFindingMapDraw()
244 {
245 float cellSize = pathfindingMap.scale * 0.9f;
246 float highlightDistance = fmodf(GetTime() * 4.0f, pathfindingMap.maxDistance);
247 for (int x = 0; x < pathfindingMap.width; x++)
248 {
249 for (int y = 0; y < pathfindingMap.height; y++)
250 {
251 float distance = pathfindingMap.distances[y * pathfindingMap.width + x];
252 float colorV = distance < 0 ? 0 : fminf(distance / pathfindingMap.maxDistance, 1.0f);
253 Color color = distance < 0 ? BLUE : (Color){fminf(colorV, 1.0f) * 255, 0, 0, 255};
254 Vector3 position = Vector3Transform((Vector3){x, -0.25f, y}, pathfindingMap.toWorldSpace);
255 // animate the distance "wave" to show how the pathfinding algorithm expands
256 // from the castle
257 if (distance + 0.5f > highlightDistance && distance - 0.5f < highlightDistance)
258 {
259 color = BLACK;
260 }
261 DrawCube(position, cellSize, 0.1f, cellSize, color);
262 }
263 }
264 }
265
266 Vector2 PathFindingGetGradient(Vector3 world)
267 {
268 int16_t mapX, mapY;
269 if (PathFindingFromWorldToMapPosition(world, &mapX, &mapY))
270 {
271 DeltaSrc delta = pathfindingMap.deltaSrc[mapY * pathfindingMap.width + mapX];
272 return (Vector2){(float)-delta.x, (float)-delta.y};
273 }
274 // fallback to a simple gradient calculation
275 float n = PathFindingGetDistance(mapX, mapY - 1);
276 float s = PathFindingGetDistance(mapX, mapY + 1);
277 float w = PathFindingGetDistance(mapX - 1, mapY);
278 float e = PathFindingGetDistance(mapX + 1, mapY);
279 return (Vector2){w - e + 0.25f, n - s + 0.125f};
280 }
281
282 //# Enemies
283
284 #define ENEMY_MAX_PATH_COUNT 8
285 #define ENEMY_MAX_COUNT 400
286 #define ENEMY_TYPE_NONE 0
287 #define ENEMY_TYPE_MINION 1
288
289 typedef struct EnemyId
290 {
291 uint16_t index;
292 uint16_t generation;
293 } EnemyId;
294
295 typedef struct EnemyClassConfig
296 {
297 float speed;
298 float health;
299 float radius;
300 float maxAcceleration;
301 } EnemyClassConfig;
302
303 typedef struct Enemy
304 {
305 int16_t currentX, currentY;
306 int16_t nextX, nextY;
307 Vector2 simPosition;
308 Vector2 simVelocity;
309 uint16_t generation;
310 float startMovingTime;
311 float damage, futureDamage;
312 uint8_t enemyType;
313 uint8_t movePathCount;
314 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
315 } Enemy;
316
317 Enemy enemies[ENEMY_MAX_COUNT];
318 int enemyCount = 0;
319
320 EnemyClassConfig enemyClassConfigs[] = {
321 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
322 };
323
324 void EnemyInit()
325 {
326 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
327 {
328 enemies[i] = (Enemy){0};
329 }
330 enemyCount = 0;
331 }
332
333 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
334 {
335 return enemyClassConfigs[enemy->enemyType].speed;
336 }
337
338 float EnemyGetMaxHealth(Enemy *enemy)
339 {
340 return enemyClassConfigs[enemy->enemyType].health;
341 }
342
343 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
344 {
345 int16_t castleX = 0;
346 int16_t castleY = 0;
347 int16_t dx = castleX - currentX;
348 int16_t dy = castleY - currentY;
349 if (dx == 0 && dy == 0)
350 {
351 *nextX = currentX;
352 *nextY = currentY;
353 return 1;
354 }
355 Vector2 gradient = PathFindingGetGradient((Vector3){currentX, 0, currentY});
356
357 if (gradient.x == 0 && gradient.y == 0)
358 {
359 *nextX = currentX;
360 *nextY = currentY;
361 return 1;
362 }
363
364 if (fabsf(gradient.x) > fabsf(gradient.y))
365 {
366 *nextX = currentX + (int16_t)(gradient.x > 0.0f ? 1 : -1);
367 *nextY = currentY;
368 return 0;
369 }
370 *nextX = currentX;
371 *nextY = currentY + (int16_t)(gradient.y > 0.0f ? 1 : -1);
372 return 0;
373 }
374
375
376 // this function predicts the movement of the unit for the next deltaT seconds
377 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
378 {
379 const float pointReachedDistance = 0.25f;
380 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
381 const float maxSimStepTime = 0.015625f;
382
383 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
384 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
385 int16_t nextX = enemy->nextX;
386 int16_t nextY = enemy->nextY;
387 Vector2 position = enemy->simPosition;
388 int passedCount = 0;
389 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
390 {
391 float stepTime = fminf(deltaT - t, maxSimStepTime);
392 Vector2 target = (Vector2){nextX, nextY};
393 float speed = Vector2Length(*velocity);
394 // draw the target position for debugging
395 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
396 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
397 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
398 {
399 // we reached the target position, let's move to the next waypoint
400 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
401 target = (Vector2){nextX, nextY};
402 // track how many waypoints we passed
403 passedCount++;
404 }
405
406 // acceleration towards the target
407 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
408 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
409 *velocity = Vector2Add(*velocity, acceleration);
410
411 // limit the speed to the maximum speed
412 if (speed > maxSpeed)
413 {
414 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
415 }
416
417 // move the enemy
418 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
419 }
420
421 if (waypointPassedCount)
422 {
423 (*waypointPassedCount) = passedCount;
424 }
425
426 return position;
427 }
428
429 void EnemyDraw()
430 {
431 for (int i = 0; i < enemyCount; i++)
432 {
433 Enemy enemy = enemies[i];
434 if (enemy.enemyType == ENEMY_TYPE_NONE)
435 {
436 continue;
437 }
438
439 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
440
441 if (enemy.movePathCount > 0)
442 {
443 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
444 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
445 }
446 for (int j = 1; j < enemy.movePathCount; j++)
447 {
448 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
449 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
450 DrawLine3D(p, q, GREEN);
451 }
452
453 switch (enemy.enemyType)
454 {
455 case ENEMY_TYPE_MINION:
456 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
457 break;
458 }
459 }
460 }
461
462 void EnemyUpdate()
463 {
464 const float castleX = 0;
465 const float castleY = 0;
466 const float maxPathDistance2 = 0.25f * 0.25f;
467
468 for (int i = 0; i < enemyCount; i++)
469 {
470 Enemy *enemy = &enemies[i];
471 if (enemy->enemyType == ENEMY_TYPE_NONE)
472 {
473 continue;
474 }
475
476 int waypointPassedCount = 0;
477 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
478 enemy->startMovingTime = gameTime.time;
479 // track path of unit
480 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
481 {
482 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
483 {
484 enemy->movePath[j] = enemy->movePath[j - 1];
485 }
486 enemy->movePath[0] = enemy->simPosition;
487 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
488 {
489 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
490 }
491 }
492
493 if (waypointPassedCount > 0)
494 {
495 enemy->currentX = enemy->nextX;
496 enemy->currentY = enemy->nextY;
497 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
498 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
499 {
500 // enemy reached the castle; remove it
501 enemy->enemyType = ENEMY_TYPE_NONE;
502 continue;
503 }
504 }
505 }
506
507 // handle collisions between enemies
508 for (int i = 0; i < enemyCount - 1; i++)
509 {
510 Enemy *enemyA = &enemies[i];
511 if (enemyA->enemyType == ENEMY_TYPE_NONE)
512 {
513 continue;
514 }
515 for (int j = i + 1; j < enemyCount; j++)
516 {
517 Enemy *enemyB = &enemies[j];
518 if (enemyB->enemyType == ENEMY_TYPE_NONE)
519 {
520 continue;
521 }
522 float distanceSqr = Vector2DistanceSqr(enemyA->simPosition, enemyB->simPosition);
523 float radiusA = enemyClassConfigs[enemyA->enemyType].radius;
524 float radiusB = enemyClassConfigs[enemyB->enemyType].radius;
525 float radiusSum = radiusA + radiusB;
526 if (distanceSqr < radiusSum * radiusSum && distanceSqr > 0.001f)
527 {
528 // collision
529 float distance = sqrtf(distanceSqr);
530 float overlap = radiusSum - distance;
531 // move the enemies apart, but softly; if we have a clog of enemies,
532 // moving them perfectly apart can cause them to jitter
533 float positionCorrection = overlap / 5.0f;
534 Vector2 direction = (Vector2){
535 (enemyB->simPosition.x - enemyA->simPosition.x) / distance * positionCorrection,
536 (enemyB->simPosition.y - enemyA->simPosition.y) / distance * positionCorrection};
537 enemyA->simPosition = Vector2Subtract(enemyA->simPosition, direction);
538 enemyB->simPosition = Vector2Add(enemyB->simPosition, direction);
539 }
540 }
541 }
542
543 // handle collisions between enemies and towers
544 for (int i = 0; i < enemyCount; i++)
545 {
546 Enemy *enemy = &enemies[i];
547 if (enemy->enemyType == ENEMY_TYPE_NONE)
548 {
549 continue;
550 }
551 float enemyRadius = enemyClassConfigs[enemy->enemyType].radius;
552 // linear search over towers; could be optimized by using path finding tower map,
553 // but for now, we keep it simple
554 for (int j = 0; j < towerCount; j++)
555 {
556 Tower *tower = &towers[j];
557 if (tower->towerType == TOWER_TYPE_NONE)
558 {
559 continue;
560 }
561 float distanceSqr = Vector2DistanceSqr(enemy->simPosition, (Vector2){tower->x, tower->y});
562 float radius = enemyRadius + 2.0f;
563 if (distanceSqr > radius * radius)
564 {
565 continue;
566 }
567 // potential collision; square / circle intersection
568 float dx = tower->x - enemy->simPosition.x;
569 float dy = tower->y - enemy->simPosition.y;
570 float absDx = fabsf(dx);
571 float absDy = fabsf(dy);
572 if (absDx <= 0.5f && absDx <= absDy) {
573 // vertical collision; push the enemy out horizontally
574 float overlap = enemyRadius + 0.5f - absDy;
575 if (overlap < 0.0f)
576 {
577 continue;
578 }
579 float direction = dy > 0.0f ? -1.0f : 1.0f;
580 enemy->simPosition.y += direction * overlap;
581 }
582 else if (absDy <= 0.5f && absDy <= absDx)
583 {
584 // horizontal collision; push the enemy out vertically
585 float overlap = enemyRadius + 0.5f - absDx;
586 if (overlap < 0.0f)
587 {
588 continue;
589 }
590 float direction = dx > 0.0f ? -1.0f : 1.0f;
591 enemy->simPosition.x += direction * overlap;
592 }
593 else
594 {
595 // possible collision with a corner
596 float cornerDX = dx > 0.0f ? -0.5f : 0.5f;
597 float cornerDY = dy > 0.0f ? -0.5f : 0.5f;
598 float cornerX = tower->x + cornerDX;
599 float cornerY = tower->y + cornerDY;
600 DrawCube((Vector3){cornerX, 0.2f, cornerY}, 0.1f, 2.0f, 0.1f, PINK);
601 float cornerDistanceSqr = Vector2DistanceSqr(enemy->simPosition, (Vector2){cornerX, cornerY});
602 if (cornerDistanceSqr > radius * radius)
603 {
604 continue;
605 }
606 // push the enemy out along the diagonal
607 float cornerDistance = sqrtf(cornerDistanceSqr);
608 float overlap = enemyRadius - cornerDistance;
609 float directionX = cornerDistance > 0.0f ? (cornerX - enemy->simPosition.x) / cornerDistance : -cornerDX;
610 float directionY = cornerDistance > 0.0f ? (cornerY - enemy->simPosition.y) / cornerDistance : -cornerDY;
611 enemy->simPosition.x -= directionX * overlap;
612 enemy->simPosition.y -= directionY * overlap;
613 }
614 }
615 }
616 }
617
618 EnemyId EnemyGetId(Enemy *enemy)
619 {
620 return (EnemyId){enemy - enemies, enemy->generation};
621 }
622
623 Enemy *EnemyTryResolve(EnemyId enemyId)
624 {
625 if (enemyId.index >= ENEMY_MAX_COUNT)
626 {
627 return 0;
628 }
629 Enemy *enemy = &enemies[enemyId.index];
630 if (enemy->generation != enemyId.generation || enemy->enemyType == ENEMY_TYPE_NONE)
631 {
632 return 0;
633 }
634 return enemy;
635 }
636
637 Enemy *EnemyTryAdd(uint8_t enemyType, int16_t currentX, int16_t currentY)
638 {
639 Enemy *spawn = 0;
640 for (int i = 0; i < enemyCount; i++)
641 {
642 Enemy *enemy = &enemies[i];
643 if (enemy->enemyType == ENEMY_TYPE_NONE)
644 {
645 spawn = enemy;
646 break;
647 }
648 }
649
650 if (enemyCount < ENEMY_MAX_COUNT && !spawn)
651 {
652 spawn = &enemies[enemyCount++];
653 }
654
655 if (spawn)
656 {
657 spawn->currentX = currentX;
658 spawn->currentY = currentY;
659 spawn->nextX = currentX;
660 spawn->nextY = currentY;
661 spawn->simPosition = (Vector2){currentX, currentY};
662 spawn->simVelocity = (Vector2){0, 0};
663 spawn->enemyType = enemyType;
664 spawn->startMovingTime = gameTime.time;
665 spawn->damage = 0.0f;
666 spawn->futureDamage = 0.0f;
667 spawn->generation++;
668 spawn->movePathCount = 0;
669 }
670
671 return spawn;
672 }
673
674 int EnemyAddDamage(Enemy *enemy, float damage)
675 {
676 enemy->damage += damage;
677 if (enemy->damage >= EnemyGetMaxHealth(enemy))
678 {
679 enemy->enemyType = ENEMY_TYPE_NONE;
680 return 1;
681 }
682
683 return 0;
684 }
685
686 Enemy* EnemyGetClosestToCastle(int16_t towerX, int16_t towerY, float range)
687 {
688 int16_t castleX = 0;
689 int16_t castleY = 0;
690 Enemy* closest = 0;
691 int16_t closestDistance = 0;
692 float range2 = range * range;
693 for (int i = 0; i < enemyCount; i++)
694 {
695 Enemy* enemy = &enemies[i];
696 if (enemy->enemyType == ENEMY_TYPE_NONE)
697 {
698 continue;
699 }
700 float maxHealth = EnemyGetMaxHealth(enemy);
701 if (enemy->futureDamage >= maxHealth)
702 {
703 // ignore enemies that will die soon
704 continue;
705 }
706 int16_t dx = castleX - enemy->currentX;
707 int16_t dy = castleY - enemy->currentY;
708 int16_t distance = abs(dx) + abs(dy);
709 if (!closest || distance < closestDistance)
710 {
711 float tdx = towerX - enemy->currentX;
712 float tdy = towerY - enemy->currentY;
713 float tdistance2 = tdx * tdx + tdy * tdy;
714 if (tdistance2 <= range2)
715 {
716 closest = enemy;
717 closestDistance = distance;
718 }
719 }
720 }
721 return closest;
722 }
723
724 int EnemyCount()
725 {
726 int count = 0;
727 for (int i = 0; i < enemyCount; i++)
728 {
729 if (enemies[i].enemyType != ENEMY_TYPE_NONE)
730 {
731 count++;
732 }
733 }
734 return count;
735 }
736
737 //# Projectiles
738 #define PROJECTILE_MAX_COUNT 1200
739 #define PROJECTILE_TYPE_NONE 0
740 #define PROJECTILE_TYPE_BULLET 1
741
742 typedef struct Projectile
743 {
744 uint8_t projectileType;
745 float shootTime;
746 float arrivalTime;
747 float damage;
748 Vector2 position;
749 Vector2 target;
750 Vector2 directionNormal;
751 EnemyId targetEnemy;
752 } Projectile;
753
754 Projectile projectiles[PROJECTILE_MAX_COUNT];
755 int projectileCount = 0;
756
757 void ProjectileInit()
758 {
759 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
760 {
761 projectiles[i] = (Projectile){0};
762 }
763 }
764
765 void ProjectileDraw()
766 {
767 for (int i = 0; i < projectileCount; i++)
768 {
769 Projectile projectile = projectiles[i];
770 if (projectile.projectileType == PROJECTILE_TYPE_NONE)
771 {
772 continue;
773 }
774 float transition = (gameTime.time - projectile.shootTime) / (projectile.arrivalTime - projectile.shootTime);
775 if (transition >= 1.0f)
776 {
777 continue;
778 }
779 Vector2 position = Vector2Lerp(projectile.position, projectile.target, transition);
780 float x = position.x;
781 float y = position.y;
782 float dx = projectile.directionNormal.x;
783 float dy = projectile.directionNormal.y;
784 for (float d = 1.0f; d > 0.0f; d -= 0.25f)
785 {
786 x -= dx * 0.1f;
787 y -= dy * 0.1f;
788 float size = 0.1f * d;
789 DrawCube((Vector3){x, 0.2f, y}, size, size, size, RED);
790 }
791 }
792 }
793
794 void ProjectileUpdate()
795 {
796 for (int i = 0; i < projectileCount; i++)
797 {
798 Projectile *projectile = &projectiles[i];
799 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
800 {
801 continue;
802 }
803 float transition = (gameTime.time - projectile->shootTime) / (projectile->arrivalTime - projectile->shootTime);
804 if (transition >= 1.0f)
805 {
806 projectile->projectileType = PROJECTILE_TYPE_NONE;
807 Enemy *enemy = EnemyTryResolve(projectile->targetEnemy);
808 if (enemy)
809 {
810 EnemyAddDamage(enemy, projectile->damage);
811 }
812 continue;
813 }
814 }
815 }
816
817 Projectile *ProjectileTryAdd(uint8_t projectileType, Enemy *enemy, Vector2 position, Vector2 target, float speed, float damage)
818 {
819 for (int i = 0; i < PROJECTILE_MAX_COUNT; i++)
820 {
821 Projectile *projectile = &projectiles[i];
822 if (projectile->projectileType == PROJECTILE_TYPE_NONE)
823 {
824 projectile->projectileType = projectileType;
825 projectile->shootTime = gameTime.time;
826 projectile->arrivalTime = gameTime.time + Vector2Distance(position, target) / speed;
827 projectile->damage = damage;
828 projectile->position = position;
829 projectile->target = target;
830 projectile->directionNormal = Vector2Normalize(Vector2Subtract(target, position));
831 projectile->targetEnemy = EnemyGetId(enemy);
832 projectileCount = projectileCount <= i ? i + 1 : projectileCount;
833 return projectile;
834 }
835 }
836 return 0;
837 }
838
839 //# Towers
840
841 void TowerInit()
842 {
843 for (int i = 0; i < TOWER_MAX_COUNT; i++)
844 {
845 towers[i] = (Tower){0};
846 }
847 towerCount = 0;
848 }
849
850 Tower *TowerGetAt(int16_t x, int16_t y)
851 {
852 for (int i = 0; i < towerCount; i++)
853 {
854 if (towers[i].x == x && towers[i].y == y)
855 {
856 return &towers[i];
857 }
858 }
859 return 0;
860 }
861
862 Tower *TowerTryAdd(uint8_t towerType, int16_t x, int16_t y)
863 {
864 if (towerCount >= TOWER_MAX_COUNT)
865 {
866 return 0;
867 }
868
869 Tower *tower = TowerGetAt(x, y);
870 if (tower)
871 {
872 return 0;
873 }
874
875 tower = &towers[towerCount++];
876 tower->x = x;
877 tower->y = y;
878 tower->towerType = towerType;
879 return tower;
880 }
881
882 void TowerDraw()
883 {
884 for (int i = 0; i < towerCount; i++)
885 {
886 Tower tower = towers[i];
887 DrawCube((Vector3){tower.x, 0.125f, tower.y}, 1.0f, 0.25f, 1.0f, GRAY);
888 switch (tower.towerType)
889 {
890 case TOWER_TYPE_BASE:
891 DrawCube((Vector3){tower.x, 0.4f, tower.y}, 0.8f, 0.8f, 0.8f, MAROON);
892 break;
893 case TOWER_TYPE_GUN:
894 DrawCube((Vector3){tower.x, 0.2f, tower.y}, 0.8f, 0.4f, 0.8f, DARKPURPLE);
895 break;
896 case TOWER_TYPE_WALL:
897 DrawCube((Vector3){tower.x, 0.5f, tower.y}, 1.0f, 1.0f, 1.0f, LIGHTGRAY);
898 break;
899 }
900 }
901 }
902
903 void TowerGunUpdate(Tower *tower)
904 {
905 if (tower->cooldown <= 0)
906 {
907 Enemy *enemy = EnemyGetClosestToCastle(tower->x, tower->y, 3.0f);
908 if (enemy)
909 {
910 tower->cooldown = 0.125f;
911 // shoot the enemy; determine future position of the enemy
912 float bulletSpeed = 1.0f;
913 float bulletDamage = 3.0f;
914 Vector2 velocity = enemy->simVelocity;
915 Vector2 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &velocity, 0);
916 Vector2 towerPosition = {tower->x, tower->y};
917 float eta = Vector2Distance(towerPosition, futurePosition) / bulletSpeed;
918 for (int i = 0; i < 8; i++) {
919 velocity = enemy->simVelocity;
920 futurePosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime + eta, &velocity, 0);
921 float distance = Vector2Distance(towerPosition, futurePosition);
922 float eta2 = distance / bulletSpeed;
923 if (fabs(eta - eta2) < 0.01f) {
924 break;
925 }
926 eta = (eta2 + eta) * 0.5f;
927 }
928 ProjectileTryAdd(PROJECTILE_TYPE_BULLET, enemy, towerPosition, futurePosition,
929 bulletSpeed, bulletDamage);
930 enemy->futureDamage += bulletDamage;
931 }
932 }
933 else
934 {
935 tower->cooldown -= gameTime.deltaTime;
936 }
937 }
938
939 void TowerUpdate()
940 {
941 for (int i = 0; i < towerCount; i++)
942 {
943 Tower *tower = &towers[i];
944 switch (tower->towerType)
945 {
946 case TOWER_TYPE_GUN:
947 TowerGunUpdate(tower);
948 break;
949 }
950 }
951 }
952
953 //# Game
954
955 float nextSpawnTime = 0.0f;
956
957 void InitGame()
958 {
959 TowerInit();
960 EnemyInit();
961 ProjectileInit();
962 PathfindingMapInit(20, 20, (Vector3){-10.0f, 0.0f, -10.0f}, 1.0f);
963
964 TowerTryAdd(TOWER_TYPE_BASE, 0, 0);
965 TowerTryAdd(TOWER_TYPE_GUN, 2, 0);
966
967 TowerTryAdd(TOWER_TYPE_WALL, 2, 2);
968 // for (int i = -2; i <= 2; i += 1)
969 // {
970 // TowerTryAdd(TOWER_TYPE_WALL, i, 2);
971 // TowerTryAdd(TOWER_TYPE_WALL, i, -2);
972 // TowerTryAdd(TOWER_TYPE_WALL, -2, i);
973 // }
974
975 EnemyTryAdd(ENEMY_TYPE_MINION, 5, 4);
976 }
977
978 void GameUpdate()
979 {
980 float dt = GetFrameTime();
981 // cap maximum delta time to 0.1 seconds to prevent large time steps
982 if (dt > 0.1f) dt = 0.1f;
983 gameTime.time += dt;
984 gameTime.deltaTime = dt;
985 PathFindingMapUpdate();
986 EnemyUpdate();
987 TowerUpdate();
988 ProjectileUpdate();
989
990 // spawn a new enemy every second
991 if (gameTime.time >= nextSpawnTime && EnemyCount() < 1)
992 {
993 nextSpawnTime = gameTime.time + 0.2f;
994 // add a new enemy at the boundary of the map
995 int randValue = GetRandomValue(-5, 5);
996 int randSide = GetRandomValue(0, 3);
997 int16_t x = randSide == 0 ? -5 : randSide == 1 ? 5 : randValue;
998 int16_t y = randSide == 2 ? -5 : randSide == 3 ? 5 : randValue;
999 static int alternation = 0;
1000 alternation += 1;
1001 if (alternation % 3 == 0) {
1002 EnemyTryAdd(ENEMY_TYPE_MINION, 0, -5);
1003 }
1004 else if (alternation % 3 == 1)
1005 {
1006 EnemyTryAdd(ENEMY_TYPE_MINION, 0, 5);
1007 }
1008 EnemyTryAdd(ENEMY_TYPE_MINION, x, y);
1009 }
1010 }
1011
1012 int main(void)
1013 {
1014 int screenWidth, screenHeight;
1015 GetPreferredSize(&screenWidth, &screenHeight);
1016 InitWindow(screenWidth, screenHeight, "Tower defense");
1017 SetTargetFPS(30);
1018
1019 Camera3D camera = {0};
1020 camera.position = (Vector3){0.0f, 10.0f, -0.5f};
1021 camera.target = (Vector3){0.0f, 0.0f, -0.5f};
1022 camera.up = (Vector3){0.0f, 0.0f, -1.0f};
1023 camera.fovy = 12.0f;
1024 camera.projection = CAMERA_ORTHOGRAPHIC;
1025
1026 InitGame();
1027
1028 while (!WindowShouldClose())
1029 {
1030 if (IsPaused()) {
1031 // canvas is not visible in browser - do nothing
1032 continue;
1033 }
1034 BeginDrawing();
1035 ClearBackground(DARKBLUE);
1036
1037 BeginMode3D(camera);
1038 DrawGrid(10, 1.0f);
1039 TowerDraw();
1040 EnemyDraw();
1041 ProjectileDraw();
1042 PathFindingMapDraw();
1043 GameUpdate();
1044 EndMode3D();
1045
1046 const char *title = "Tower defense tutorial";
1047 int titleWidth = MeasureText(title, 20);
1048 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f + 2, 5 + 2, 20, BLACK);
1049 DrawText(title, (GetScreenWidth() - titleWidth) * 0.5f, 5, 20, WHITE);
1050 EndDrawing();
1051 }
1052
1053 CloseWindow();
1054
1055 return 0;
1056 }
1 #ifndef TD_TUT_2_MAIN_H
2 #define TD_TUT_2_MAIN_H
3
4 #include <inttypes.h>
5
6 #include "raylib.h"
7 #include "preferred_size.h"
8
9 #endif
1 #include "raylib.h"
2 #include "preferred_size.h"
3
4 // Since the canvas size is not known at compile time, we need to query it at runtime;
5 // the following platform specific code obtains the canvas size and we will use this
6 // size as the preferred size for the window at init time. We're ignoring here the
7 // possibility of the canvas size changing during runtime - this would require to
8 // poll the canvas size in the game loop or establishing a callback to be notified
9
10 #ifdef PLATFORM_WEB
11 #include <emscripten.h>
12 EMSCRIPTEN_RESULT emscripten_get_element_css_size(const char *target, double *width, double *height);
13
14 void GetPreferredSize(int *screenWidth, int *screenHeight)
15 {
16 double canvasWidth, canvasHeight;
17 emscripten_get_element_css_size("#" CANVAS_NAME, &canvasWidth, &canvasHeight);
18 *screenWidth = (int)canvasWidth;
19 *screenHeight = (int)canvasHeight;
20 TraceLog(LOG_INFO, "preferred size for %s: %d %d", CANVAS_NAME, *screenWidth, *screenHeight);
21 }
22
23 int IsPaused()
24 {
25 const char *js = "(function(){\n"
26 " var canvas = document.getElementById(\"" CANVAS_NAME "\");\n"
27 " var rect = canvas.getBoundingClientRect();\n"
28 " var isVisible = (\n"
29 " rect.top >= 0 &&\n"
30 " rect.left >= 0 &&\n"
31 " rect.bottom <= (window.innerHeight || document.documentElement.clientHeight) &&\n"
32 " rect.right <= (window.innerWidth || document.documentElement.clientWidth)\n"
33 " );\n"
34 " return isVisible ? 0 : 1;\n"
35 "})()";
36 return emscripten_run_script_int(js);
37 }
38
39 #else
40 void GetPreferredSize(int *screenWidth, int *screenHeight)
41 {
42 *screenWidth = 600;
43 *screenHeight = 240;
44 }
45 int IsPaused()
46 {
47 return 0;
48 }
49 #endif
1 #ifndef PREFERRED_SIZE_H
2 #define PREFERRED_SIZE_H
3
4 void GetPreferredSize(int *screenWidth, int *screenHeight);
5 int IsPaused();
6
7 #endif
This ... isn't quite right. The result above shows buggy behavior; I removed the walls except for one and the single enemy that approaches the wall gets sucked towards it and is then stuck at the bottom left corner. The problem is the square-circle collision test in line 590.
I don't want to hide the fact that working out these problems is a large part of working on such games. It's frustrating, but it's rewarding when it works. I don't want to showcase all debugging steps I am using, but one you can see above: I am drawing the corner of collision as pink rectangle. Visualizing the problematic values is often a good way to find out what's going on. In this case, I can simply draw such information any time I want, because the game update loop is executed inside the drawing phase.
Anyway, let's fix the problem... First, observe the behavior:
Observing the behavior gives clues on what is happening: In line 562, I am checking if the enemy is close enough to the wall to consider running more expensive tests. I deliberately use a too large threshold to trigger this behavior so I can observe this behavior better.
There is a phase where the enemy gets away from the wall before getting stuck on the left bottom corner. This happens because when the enemy is leaving the corner area, the if check in line 572 is active, and this part works fine.
But when the enemy enters the next corner sector, it again gets sucked in and is no longer able to escape. This happens in the block starting at line 595. We can also see that the purple corner is correctly selected. This is the corner that we want to check for collision.
What we can also see is, that the enemy is sucked to the corner before the corner is even reached. The bug here is hidden in "radius * radius". Bad naming: It's not the radius of the enemy, but the combined radius of the enemy and the wall's assumed bounding circle! So renaming the variable to "combinedRadius" is one fix. Replacing the combined radius value with the enemy's radius (we only want to see if the corner is inside the enemy's circle) should fix this: Since the following code uses the correct enemy radius (line 608, calculating the overlap), the result is that the overlap is a large negative value - causing the suck-in effect.
Let's test this and reenable the walls:
1 #include "td-tut-2-main.h"
2 #include <raymath.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 //# Declarations
7
8 #define TOWER_MAX_COUNT 400
9 #define TOWER_TYPE_NONE 0
10 #define TOWER_TYPE_BASE 1
11 #define TOWER_TYPE_GUN 2
12 #define TOWER_TYPE_WALL 3
13
14 typedef struct Tower
15 {
16 int16_t x, y;
17 uint8_t towerType;
18 float cooldown;
19 } Tower;
20
21 typedef struct GameTime
22 {
23 float time;
24 float deltaTime;
25 } GameTime;
26
27 GameTime gameTime = {0};
28
29 Tower towers[TOWER_MAX_COUNT];
30 int towerCount = 0;
31
32 //# Pathfinding map
33 typedef struct DeltaSrc
34 {
35 char x, y;
36 } DeltaSrc;
37
38 typedef struct PathfindingMap
39 {
40 int width, height;
41 float scale;
42 float *distances;
43 long *towerIndex;
44 DeltaSrc *deltaSrc;
45 float maxDistance;
46 Matrix toMapSpace;
47 Matrix toWorldSpace;
48 } PathfindingMap;
49
50 // when we execute the pathfinding algorithm, we need to store the active nodes
51 // in a queue. Each node has a position, a distance from the start, and the
52 // position of the node that we came from.
53 typedef struct PathfindingNode
54 {
55 int16_t x, y, fromX, fromY;
56 float distance;
57 } PathfindingNode;
58
59 // The queue is a simple array of nodes, we add nodes to the end and remove
60 // nodes from the front. We keep the array around to avoid unnecessary allocations
61 static PathfindingNode *pathfindingNodeQueue = 0;
62 static int pathfindingNodeQueueCount = 0;
63 static int pathfindingNodeQueueCapacity = 0;
64
65 // The pathfinding map stores the distances from the castle to each cell in the map.
66 PathfindingMap pathfindingMap = {0};
67
68 void PathfindingMapInit(int width, int height, Vector3 translate, float scale)
69 {
70 // transforming between map space and world space allows us to adapt
71 // position and scale of the map without changing the pathfinding data
72 pathfindingMap.toWorldSpace = MatrixTranslate(translate.x, translate.y, translate.z);
73 pathfindingMap.toWorldSpace = MatrixMultiply(pathfindingMap.toWorldSpace, MatrixScale(scale, scale, scale));
74 pathfindingMap.toMapSpace = MatrixInvert(pathfindingMap.toWorldSpace);
75 pathfindingMap.width = width;
76 pathfindingMap.height = height;
77 pathfindingMap.scale = scale;
78 pathfindingMap.distances = (float *)MemAlloc(width * height * sizeof(float));
79 for (int i = 0; i < width * height; i++)
80 {
81 pathfindingMap.distances[i] = -1.0f;
82 }
83
84 pathfindingMap.towerIndex = (long *)MemAlloc(width * height * sizeof(long));
85 pathfindingMap.deltaSrc = (DeltaSrc *)MemAlloc(width * height * sizeof(DeltaSrc));
86 }
87
88 float PathFindingGetDistance(int mapX, int mapY)
89 {
90 if (mapX < 0 || mapX >= pathfindingMap.width || mapY < 0 || mapY >= pathfindingMap.height)
91 {
92 // when outside the map, we return the manhattan distance to the castle (0,0)
93 return fabsf((float)mapX) + fabsf((float)mapY);
94 }
95
96 return pathfindingMap.distances[mapY * pathfindingMap.width + mapX];
97 }
98
99 void PathFindingNodePush(int16_t x, int16_t y, int16_t fromX, int16_t fromY, float distance)
100 {
101 if (pathfindingNodeQueueCount >= pathfindingNodeQueueCapacity)
102 {
103 pathfindingNodeQueueCapacity = pathfindingNodeQueueCapacity == 0 ? 256 : pathfindingNodeQueueCapacity * 2;
104 // we use MemAlloc/MemRealloc to allocate memory for the queue
105 // I am not entirely sure if MemRealloc allows passing a null pointer
106 // so we check if the pointer is null and use MemAlloc in that case
107 if (pathfindingNodeQueue == 0)
108 {
109 pathfindingNodeQueue = (PathfindingNode *)MemAlloc(pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
110 }
111 else
112 {
113 pathfindingNodeQueue = (PathfindingNode *)MemRealloc(pathfindingNodeQueue, pathfindingNodeQueueCapacity * sizeof(PathfindingNode));
114 }
115 }
116
117 PathfindingNode *node = &pathfindingNodeQueue[pathfindingNodeQueueCount++];
118 node->x = x;
119 node->y = y;
120 node->fromX = fromX;
121 node->fromY = fromY;
122 node->distance = distance;
123 }
124
125 PathfindingNode *PathFindingNodePop()
126 {
127 if (pathfindingNodeQueueCount == 0)
128 {
129 return 0;
130 }
131 // we return the first node in the queue; we want to return a pointer to the node
132 // so we can return 0 if the queue is empty.
133 // We should _not_ return a pointer to the element in the list, because the list
134 // may be reallocated and the pointer would become invalid. Or the
135 // popped element is overwritten by the next push operation.
136 // Using static here means that the variable is permanently allocated.
137 static PathfindingNode node;
138 node = pathfindingNodeQueue[0];
139 // we shift all nodes one position to the front
140 for (int i = 1; i < pathfindingNodeQueueCount; i++)
141 {
142 pathfindingNodeQueue[i - 1] = pathfindingNodeQueue[i];
143 }
144 --pathfindingNodeQueueCount;
145 return &node;
146 }
147
148 // transform a world position to a map position in the array;
149 // returns true if the position is inside the map
150 int PathFindingFromWorldToMapPosition(Vector3 worldPosition, int16_t *mapX, int16_t *mapY)
151 {
152 Vector3 mapPosition = Vector3Transform(worldPosition, pathfindingMap.toMapSpace);
153 *mapX = (int16_t)mapPosition.x;
154 *mapY = (int16_t)mapPosition.z;
155 return *mapX >= 0 && *mapX < pathfindingMap.width && *mapY >= 0 && *mapY < pathfindingMap.height;
156 }
157
158 void PathFindingMapUpdate()
159 {
160 const int castleX = 0, castleY = 0;
161 int16_t castleMapX, castleMapY;
162 if (!PathFindingFromWorldToMapPosition((Vector3){castleX, 0.0f, castleY}, &castleMapX, &castleMapY))
163 {
164 return;
165 }
166 int width = pathfindingMap.width, height = pathfindingMap.height;
167
168 // reset the distances to -1
169 for (int i = 0; i < width * height; i++)
170 {
171 pathfindingMap.distances[i] = -1.0f;
172 }
173 // reset the tower indices
174 for (int i = 0; i < width * height; i++)
175 {
176 pathfindingMap.towerIndex[i] = -1;
177 }
178 // reset the delta src
179 for (int i = 0; i < width * height; i++)
180 {
181 pathfindingMap.deltaSrc[i].x = 0;
182 pathfindingMap.deltaSrc[i].y = 0;
183 }
184
185 for (int i = 0; i < towerCount; i++)
186 {
187 Tower *tower = &towers[i];
188 if (tower->towerType == TOWER_TYPE_NONE || tower->towerType == TOWER_TYPE_BASE)
189 {
190 continue;
191 }
192 int16_t mapX, mapY;
193 // technically, if the tower cell scale is not in sync with the pathfinding map scale,
194 // this would not work correctly and needs to be refined to allow towers covering multiple cells
195 // or having multiple towers in one cell; for simplicity, we assume that the tower covers exactly
196 // one cell. For now.
197 if (!PathFindingFromWorldToMapPosition((Vector3){tower->x, 0.0f, tower->y}, &mapX, &mapY))
198 {
199 continue;
200 }
201 int index = mapY * width + mapX;
202 pathfindingMap.towerIndex[index] = i;
203 }
204
205 // we start at the castle and add the castle to the queue
206 pathfindingMap.maxDistance = 0.0f;
207 pathfindingNodeQueueCount = 0;
208 PathFindingNodePush(castleMapX, castleMapY, castleMapX, castleMapY, 0.0f);
209 PathfindingNode *node = 0;
210 while ((node = PathFindingNodePop()))
211 {
212 if (node->x < 0 || node->x >= width || node->y < 0 || node->y >= height)
213 {
214 continue;
215 }
216 int index = node->y * width + node->x;
217 if (pathfindingMap.distances[index] >= 0 && pathfindingMap.distances[index] <= node->distance)
218 {
219 continue;
220 }
221
222 int deltaX = node->x - node->fromX;
223 int deltaY = node->y - node->fromY;
224 // even if the cell is blocked by a tower, we still may want to store the direction
225 // (though this might not be needed, IDK right now)
226 pathfindingMap.deltaSrc[index].x = (char) deltaX;
227 pathfindingMap.deltaSrc[index].y = (char) deltaY;
228
229 // we skip nodes that are blocked by towers
230 if (pathfindingMap.towerIndex[index] >= 0)
231 {
232 node->distance += 8.0f;
233 }
234 pathfindingMap.distances[index] = node->distance;
235 pathfindingMap.maxDistance = fmaxf(pathfindingMap.maxDistance, node->distance);
236 PathFindingNodePush(node->x, node->y + 1, node->x, node->y, node->distance + 1.0f);
237 PathFindingNodePush(node->x, node->y - 1, node->x, node->y, node->distance + 1.0f);
238 PathFindingNodePush(node->x + 1, node->y, node->x, node->y, node->distance + 1.0f);
239 PathFindingNodePush(node->x - 1, node->y, node->x, node->y, node->distance + 1.0f);
240 }
241 }
242
243 void PathFindingMapDraw()
244 {
245 float cellSize = pathfindingMap.scale * 0.9f;
246 float highlightDistance = fmodf(GetTime() * 4.0f, pathfindingMap.maxDistance);
247 for (int x = 0; x < pathfindingMap.width; x++)
248 {
249 for (int y = 0; y < pathfindingMap.height; y++)
250 {
251 float distance = pathfindingMap.distances[y * pathfindingMap.width + x];
252 float colorV = distance < 0 ? 0 : fminf(distance / pathfindingMap.maxDistance, 1.0f);
253 Color color = distance < 0 ? BLUE : (Color){fminf(colorV, 1.0f) * 255, 0, 0, 255};
254 Vector3 position = Vector3Transform((Vector3){x, -0.25f, y}, pathfindingMap.toWorldSpace);
255 // animate the distance "wave" to show how the pathfinding algorithm expands
256 // from the castle
257 if (distance + 0.5f > highlightDistance && distance - 0.5f < highlightDistance)
258 {
259 color = BLACK;
260 }
261 DrawCube(position, cellSize, 0.1f, cellSize, color);
262 }
263 }
264 }
265
266 Vector2 PathFindingGetGradient(Vector3 world)
267 {
268 int16_t mapX, mapY;
269 if (PathFindingFromWorldToMapPosition(world, &mapX, &mapY))
270 {
271 DeltaSrc delta = pathfindingMap.deltaSrc[mapY * pathfindingMap.width + mapX];
272 return (Vector2){(float)-delta.x, (float)-delta.y};
273 }
274 // fallback to a simple gradient calculation
275 float n = PathFindingGetDistance(mapX, mapY - 1);
276 float s = PathFindingGetDistance(mapX, mapY + 1);
277 float w = PathFindingGetDistance(mapX - 1, mapY);
278 float e = PathFindingGetDistance(mapX + 1, mapY);
279 return (Vector2){w - e + 0.25f, n - s + 0.125f};
280 }
281
282 //# Enemies
283
284 #define ENEMY_MAX_PATH_COUNT 8
285 #define ENEMY_MAX_COUNT 400
286 #define ENEMY_TYPE_NONE 0
287 #define ENEMY_TYPE_MINION 1
288
289 typedef struct EnemyId
290 {
291 uint16_t index;
292 uint16_t generation;
293 } EnemyId;
294
295 typedef struct EnemyClassConfig
296 {
297 float speed;
298 float health;
299 float radius;
300 float maxAcceleration;
301 } EnemyClassConfig;
302
303 typedef struct Enemy
304 {
305 int16_t currentX, currentY;
306 int16_t nextX, nextY;
307 Vector2 simPosition;
308 Vector2 simVelocity;
309 uint16_t generation;
310 float startMovingTime;
311 float damage, futureDamage;
312 uint8_t enemyType;
313 uint8_t movePathCount;
314 Vector2 movePath[ENEMY_MAX_PATH_COUNT];
315 } Enemy;
316
317 Enemy enemies[ENEMY_MAX_COUNT];
318 int enemyCount = 0;
319
320 EnemyClassConfig enemyClassConfigs[] = {
321 [ENEMY_TYPE_MINION] = {.health = 3.0f, .speed = 1.0f, .radius = 0.25f, .maxAcceleration = 1.0f},
322 };
323
324 void EnemyInit()
325 {
326 for (int i = 0; i < ENEMY_MAX_COUNT; i++)
327 {
328 enemies[i] = (Enemy){0};
329 }
330 enemyCount = 0;
331 }
332
333 float EnemyGetCurrentMaxSpeed(Enemy *enemy)
334 {
335 return enemyClassConfigs[enemy->enemyType].speed;
336 }
337
338 float EnemyGetMaxHealth(Enemy *enemy)
339 {
340 return enemyClassConfigs[enemy->enemyType].health;
341 }
342
343 int EnemyGetNextPosition(int16_t currentX, int16_t currentY, int16_t *nextX, int16_t *nextY)
344 {
345 int16_t castleX = 0;
346 int16_t castleY = 0;
347 int16_t dx = castleX - currentX;
348 int16_t dy = castleY - currentY;
349 if (dx == 0 && dy == 0)
350 {
351 *nextX = currentX;
352 *nextY = currentY;
353 return 1;
354 }
355 Vector2 gradient = PathFindingGetGradient((Vector3){currentX, 0, currentY});
356
357 if (gradient.x == 0 && gradient.y == 0)
358 {
359 *nextX = currentX;
360 *nextY = currentY;
361 return 1;
362 }
363
364 if (fabsf(gradient.x) > fabsf(gradient.y))
365 {
366 *nextX = currentX + (int16_t)(gradient.x > 0.0f ? 1 : -1);
367 *nextY = currentY;
368 return 0;
369 }
370 *nextX = currentX;
371 *nextY = currentY + (int16_t)(gradient.y > 0.0f ? 1 : -1);
372 return 0;
373 }
374
375
376 // this function predicts the movement of the unit for the next deltaT seconds
377 Vector2 EnemyGetPosition(Enemy *enemy, float deltaT, Vector2 *velocity, int *waypointPassedCount)
378 {
379 const float pointReachedDistance = 0.25f;
380 const float pointReachedDistance2 = pointReachedDistance * pointReachedDistance;
381 const float maxSimStepTime = 0.015625f;
382
383 float maxAcceleration = enemyClassConfigs[enemy->enemyType].maxAcceleration;
384 float maxSpeed = EnemyGetCurrentMaxSpeed(enemy);
385 int16_t nextX = enemy->nextX;
386 int16_t nextY = enemy->nextY;
387 Vector2 position = enemy->simPosition;
388 int passedCount = 0;
389 for (float t = 0.0f; t < deltaT; t += maxSimStepTime)
390 {
391 float stepTime = fminf(deltaT - t, maxSimStepTime);
392 Vector2 target = (Vector2){nextX, nextY};
393 float speed = Vector2Length(*velocity);
394 // draw the target position for debugging
395 DrawCubeWires((Vector3){target.x, 0.2f, target.y}, 0.1f, 0.4f, 0.1f, RED);
396 Vector2 lookForwardPos = Vector2Add(position, Vector2Scale(*velocity, speed));
397 if (Vector2DistanceSqr(target, lookForwardPos) <= pointReachedDistance2)
398 {
399 // we reached the target position, let's move to the next waypoint
400 EnemyGetNextPosition(nextX, nextY, &nextX, &nextY);
401 target = (Vector2){nextX, nextY};
402 // track how many waypoints we passed
403 passedCount++;
404 }
405
406 // acceleration towards the target
407 Vector2 unitDirection = Vector2Normalize(Vector2Subtract(target, lookForwardPos));
408 Vector2 acceleration = Vector2Scale(unitDirection, maxAcceleration * stepTime);
409 *velocity = Vector2Add(*velocity, acceleration);
410
411 // limit the speed to the maximum speed
412 if (speed > maxSpeed)
413 {
414 *velocity = Vector2Scale(*velocity, maxSpeed / speed);
415 }
416
417 // move the enemy
418 position = Vector2Add(position, Vector2Scale(*velocity, stepTime));
419 }
420
421 if (waypointPassedCount)
422 {
423 (*waypointPassedCount) = passedCount;
424 }
425
426 return position;
427 }
428
429 void EnemyDraw()
430 {
431 for (int i = 0; i < enemyCount; i++)
432 {
433 Enemy enemy = enemies[i];
434 if (enemy.enemyType == ENEMY_TYPE_NONE)
435 {
436 continue;
437 }
438
439 Vector2 position = EnemyGetPosition(&enemy, gameTime.time - enemy.startMovingTime, &enemy.simVelocity, 0);
440
441 if (enemy.movePathCount > 0)
442 {
443 Vector3 p = {enemy.movePath[0].x, 0.2f, enemy.movePath[0].y};
444 DrawLine3D(p, (Vector3){position.x, 0.2f, position.y}, GREEN);
445 }
446 for (int j = 1; j < enemy.movePathCount; j++)
447 {
448 Vector3 p = {enemy.movePath[j - 1].x, 0.2f, enemy.movePath[j - 1].y};
449 Vector3 q = {enemy.movePath[j].x, 0.2f, enemy.movePath[j].y};
450 DrawLine3D(p, q, GREEN);
451 }
452
453 switch (enemy.enemyType)
454 {
455 case ENEMY_TYPE_MINION:
456 DrawCubeWires((Vector3){position.x, 0.2f, position.y}, 0.4f, 0.4f, 0.4f, GREEN);
457 break;
458 }
459 }
460 }
461
462 void EnemyUpdate()
463 {
464 const float castleX = 0;
465 const float castleY = 0;
466 const float maxPathDistance2 = 0.25f * 0.25f;
467
468 for (int i = 0; i < enemyCount; i++)
469 {
470 Enemy *enemy = &enemies[i];
471 if (enemy->enemyType == ENEMY_TYPE_NONE)
472 {
473 continue;
474 }
475
476 int waypointPassedCount = 0;
477 enemy->simPosition = EnemyGetPosition(enemy, gameTime.time - enemy->startMovingTime, &enemy->simVelocity, &waypointPassedCount);
478 enemy->startMovingTime = gameTime.time;
479 // track path of unit
480 if (enemy->movePathCount == 0 || Vector2DistanceSqr(enemy->simPosition, enemy->movePath[0]) > maxPathDistance2)
481 {
482 for (int j = ENEMY_MAX_PATH_COUNT - 1; j > 0; j--)
483 {
484 enemy->movePath[j] = enemy->movePath[j - 1];
485 }
486 enemy->movePath[0] = enemy->simPosition;
487 if (++enemy->movePathCount > ENEMY_MAX_PATH_COUNT)
488 {
489 enemy->movePathCount = ENEMY_MAX_PATH_COUNT;
490 }
491 }
492
493 if (waypointPassedCount > 0)
494 {
495 enemy->currentX = enemy->nextX;
496 enemy->currentY = enemy->nextY;
497 if (EnemyGetNextPosition(enemy->currentX, enemy->currentY, &enemy->nextX, &enemy->nextY) &&
498 Vector2DistanceSqr(enemy->simPosition, (Vector2){castleX, castleY}) <= 0.25f * 0.25f)
499 {
500 // enemy reached the castle; remove it
501 enemy->enemyType = ENEMY_TYPE_NONE;
502 continue;
503 }
504 }
505 }
506
507 // handle collisions between enemies
508 for (int i = 0; i < enemyCount - 1; i++)
509 {