Graph (and Tree) algorithms in Go.
Featuring:
- Uniform Cost Search (UCS or Dijkstra’s Algorithm)
- A* (Astar)
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Beam search (BS)
- Chokudai search (DFS version of Beam)
- Monte Carlo Tree Search (MCTS)
- Minimax (depth-limited Negamax with alpha-beta pruning)
Consider this code unstable. Copy and paste what you need into your own code for stability!
The pathfinding directory contains algorithms that find the shortest path from
start to goal.
The optimization directory contains algorithms that find an optimal solution
to a problem that doesn't have a single clear goal.
The adversarial directory contains algorithms that require an opponent.
The bitset directory contains functions wrapping common bitwise operations.
- Don't use
for _, copy := range, usefor i := rangeorfor i := 0; i < len(things); i++. - Don't use
map, use arrays/slices: Amortized lookups add up. - Pool objects by making a big array
var pool = make([]Thing, 1_000_000), grab items likething := &pool[cursor]; cursor++ - Turn off Garbage Collection once most things are pooled
debug.SetGCPercent(-1) - Once GC is off, prefer objects on the stack (
Thing{}) not the heap (&Thing{}) - Use the built-in benchmark and profiling functionality to find slow spots
- For even more performance turn arrays into bitsets. If multiple values are possible on the same position, then use multiple uints as "layers" of the grid.