Skip to content

Pathfinding and Collision Avoidance Progress

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:

Functional Pathfinding

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: