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:

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:

The enemy approaching the wall and getting sucked to the corner

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   {
510     Enemy *enemyA = &enemies[i];
511     if (enemyA->enemyType == ENEMY_TYPE_NONE)
512     {