Back to the cards

A* at 0.12x

Win: 1st of about 90, DigiPen

My part
Individual entry
When
Jun 2026
Made with
C++20, AVX2 SIMD, WebAssembly

…microseconds for this search, measured in your browser

Loading my C++…

Draw walls with your mouse or finger. Drag the two dots to move the start and the goal.

The grid above is my actual code

The search above is not a JavaScript demo written for this site. It’s the two C++ files that I submitted, compiled to WebAssembly without any changes, so when you draw walls it’s my entry that finds the path.

The assignment was built on a framework provided by the class. The framework isn’t my work, so none of it is used here, and only the pathfinding code that I wrote is running.

The challenge

DigiPen ran an A* pathfinding challenge where the goal was to make the search as fast as possible. About 90 students entered and my entry placed 1st, at 0.12x of the baseline runtime and 20% faster than second place.

In the speed test, which runs 100 paths on a 40x40 map, my fastest run was 274 microseconds for all 100 paths, which is under 3 microseconds per path. I spent about 120 hours on it.

How I made it fast

  • Integer costs. A straight step costs 1024 and a diagonal costs 1448, so there is no floating point in the search loop.
  • An 8-byte node. Each node is a 32-bit cost and one word that packs the parent, row, column and a closed bit, so there is no separate closed list. A 40x40 map is 1,600 nodes, which is 12.8 KB and stays in the cache.
  • No clearing between searches. Each node carries a generation number, and a node whose number doesn’t match the current search is treated as untouched. The nodes are only actually cleared once every 256 searches.
  • A bucketed open list. Nodes go into buckets by cost, so a push is O(1) and a pop takes the head of the lowest bucket without sorting. An AVX2 compare checks eight buckets at a time to find the next non-empty one.
  • Eight neighbours at once. With the octile heuristic, AVX2 computes the heuristic for all eight neighbours together, and the neighbour loop is fully unrolled.
  • Precomputing per map. When the map changes I precompute which neighbours each cell can reach, and which of those are never worth taking given the direction the search arrived from. I also label the connected regions, so an unreachable goal is rejected before the search starts. You can see this above by walling off the goal.
  • Compile-time options. The heuristic and the other settings are template parameters, so the search loop has no branches for them.

Running in a browser

It’s slower here than it was natively. WebAssembly only has 128-bit SIMD, so every 256-bit AVX2 instruction becomes two, and the memory prefetching does nothing at all. The time shown above is measured in your browser.