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 )

Twitter picture

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

Facebook photo

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

Connecting to %s


  • Just realized one different that might be important... one of them is a contenteditable 1 day ago
  • @nextjs At least it's consistent in browsers. So I know the mistake must be somewhere in my styles or DOM... 1 day ago
  • I'm having a weird issue where the SSR version of my @nextjs page looks slightly different than the CSR version, be…… 1 day ago
  • RT @KialoEdu: 2022 was a busy year for us here at Kialo Edu: we spent most of our time making great new features for you! Check out our r… 6 days ago
  • loving @LastOfUsHBO - really cool seeing it come together in such a well made tv series after having played all the games. 1 week ago


%d bloggers like this: