Pathfinding to a moving target in evolving terrain
In this post, I'm going to describe how I used direction fields to introduce fast and dynamic pathfinding to a browser game. I recently published a free browser game, developed in Unity, called Build + Brawl . In Build + Brawl , the player moves their character to avoid swarms of approaching enemies. The environment contains impassable obstacles — some generated at random, some placed by the player — that the enemies must route around as they approach the player. There are off-the-shelf solutions for pathfinding in general using algorithms like A* [1]; however, there were a few quirks to Build + Brawl that pushed me to roll my own solution: There may be hundreds of enemies routing to the player at once. The enemies all start from different, randomized positions. The player character can move. The player can add or remove obstacles during the game. The game must run in realtime, without lag, single-threaded, in the browser. Running A* worked fine in a high-r...