Is this a suitable "pathfinding" algorithm for a tower defense game?

Question

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.

Answer 1

Like some have said, you should test it.

Realize that you'll likely be looping over all your enemies and doing multiple more complicated calculations for other aspects of the game, and until this starts causing you trouble, don't prematurely optimize it.

That being said, if you find that you have so many enemies that making this seemingly similar calculation takes too long, you can think about precomputing all of the positions along your paths ahead of time and then map each enemy to the precomputed locations each frame instead (assuming all your paths stay the same for the duration of a level). The trade off here is space vs speed. If you do the calculation for all paths earlier in the game, you can then use a simpler function that only does a lookup based on some key. Your mapping function would do some kind of array or map lookup.