As I promised to myself this morning I finally made the pathfinding and collision detection / avoidance work! It’s not yet perfect, but basically functional. Here comes a new screenshot:

The implementation relies on a 2D grid (visualized by blue and gray lines) and A* search. The search itself also uses an array based binary heap for finding the lowest cost nodes. The heuristic used to calculate the shortest path uses the Manhattan distance. The red quads represent blocked grid cells. The yellow lines represent paths of different units.

Usually the game is running smoothly at 60 fps. However currently the paths are not cached and also not otherwise optimized so that every unit recalculates it’s path way too often, which results in the lower framerate. Meanwhile I implemented caching which alone already fixed the framerate drops.

As soon as everything works perfectly I will publish the code here.