# Is this a suitable “pathfinding” algorithm for a tower defense game?

Note: I put "pathfinding" in quotes because I'm not sure if it's the proper term for this.

My goal is to create a 2D tower defense game with HTML5/JavaScript. It's mostly for learning purposes, so I'm trying to come up with solutions myself before looking how others did it.

One of my first questions was: How do I get enemies to follow a path? After thinking about it for a while, I came up with an idea which I think might be a bit counter-intuitive. It appears to work perfectly in testing, but I'm not sure if I should do it this way because I couldn't find any similar examples. Although that may just be because I'm not sure how to search for it.

The general idea works like this:

• The map has a path, which the enemies follow. The path is an array of waypoints (each with X and Y coordinates) which are implicitly connected in sequence by straight lines. So the length of the path can be measured by adding the distances between consecutive waypoints.
• Each enemy's position is represented by a single number, which refers to how far they are on the path (i.e. their progress). There's also a field for their two-dimensional position on the map (needed for rendering), which is initially empty.
• Every frame, the algorithm recalculates and updates each enemy's 2D-position. This is done by taking its 1D-position, checking which waypoint was the last one the enemy passed, and then calculatig the correct position between that waypoint and the next (even if they're at an angle).

The reason I like this idea is that each number between 0 and the length of the path corresponds exactly to one single point on the path. That way it should be impossible for objects to glitch out of bounds or be rendered at the wrong place. It also makes finding the first or last enemy in a given range a trivial task.

My main concern so far is performance. Running this calculation for each enemy on every frame seems rather time-consuming, especially if the map gets filled with enemies, towers and projectiles later on. Are there any other problems with this approach?

In case my description doesn't tell you enough, here's what my code looks like:

posOnMap(pos) {
if (typeof pos !== 'number') throw TypeError('pos is NaN');
if (pos < 0) return new V2(map.path[0].x, map.path[0].y);
if (pos >= map.pathLength) return new V2(map.path[map.path.length - 1].x, map.path[map.path.length - 1].y);

var last, next, offset, len = 0;
for (var i = 0; i < map.path.length - 1; i++) {
offset = len;
len += V2.distance(map.path[i], map.path[i + 1]);
if (len > pos) {
last = map.path[i];
next = map.path[i + 1];
break;
}
}
var posRel = pos - offset;
var dist = V2.distance(last, next);
var fraction = posRel / dist;
return new V2(last.x + (next.x - last.x) * fraction, last.y + (next.y - last.y) * fraction);
}


map.path is the path array, as described above. So map.path.length is the total number of waypoints, while map.pathLength is the length of the path in in-game units.

• "running this calculation for each enemy on every frame seems rather time-consuming" - did you test that? You should always strive for testing performance problems like that, before prematurely optimizing. – Kromster says support Monica May 26 '17 at 11:07
• What you've described is a form of spline-following, with a piecewise linear spline. It's a very standard approach. You can speed it up in a few ways, like caching the segment length info to avoid unnecessary recalculation, or having each agent remember which segment it's in so you don't need to search the whole segment list each frame. As Kromster says though, profile first to see if this is even a problem worth worrying about. Your time might be better spent working on other game features instead of building the perfect splines. – DMGregory May 26 '17 at 11:46
• Also, for future reference: when you have code that's already working correctly and meeting your needs, and you don't have any specific problem to solve, you just want feedback on code quality & optimization, there's a dedicated exchange for that: the Code Review StackExchange – DMGregory May 26 '17 at 14:11
• @DMGregory I was thinking about that, I just thought it should be asked here since it's specifically related to game development. I'll keep it in mind next time though. – Andii May 26 '17 at 14:31