The fastest wayfinding in Go without allocations and SMS

What’s with the asterisk?

To turn greedy BFS into A* we will need a few changes:

Two generation maps instead of one

Min heap instead of bucket queue

Slightly different heuristics for p

In the case of an asterisk, the algorithm will take into account the cost of moving (it costs us nothing).

The code there is incredibly similar, but I recommend doing the implementation in separate functions, this way you can avoid unnecessary branches and/or indirection.

How to choose between asterisk and greedy bfs for your task? Almost always A* would be the preferred option, but greedy bfs is slightly faster and requires less working memory.

Greedy BFS finds a near-optimal path quite often, although a very complex maze may frustrate it. In cases where star and greedy BFS both find optimal paths, they are usually different. Using this in the game, you can create less predictable routes for units: build some routes through A*and the other through greedy BFS.

If we take examples from my favorite article, then greedy BFS should lose in the example below. However, my greedy BFS works slightly differently and, in my tests, performs quite well. In just a couple of tests, greedy BFS built a less optimal route than A*:

We win in benchmarks

Using all the recipes above, we collect your pathfinding library.

pathing is about 2000 times faster than the paths library!

A* It works noticeably slower than greedy BFS, but is still faster than other implementations.

Now the allocations:

Since all the data structures I use support full memory reuse, there will be no allocations between path constructions. The path object also does not require the involvement of an allocator.

It turned out thousands of times faster and without allocations (zero alloc). It was worth it.

conclusions

Algorithms are important, but so is implementation. Sometimes a series of micro-optimizations leads to a phenomenal effect.

My pathfinding library has two main limitations:

Maximum path length – 56 steps

One terrain map can only have 4 types of tiles (2 bits)

However, you can live with them:

Partial paths can be combined into one

Separate enums for biomes may delay the problem

Did you like the article? In our Go game development community always fun! Join us, we will create toys in our favorite programming language together.