Skip to content

A very fast & zero-allocation, grid-based, pathfinding library for Go.

License

Notifications You must be signed in to change notification settings

quasilyte/pathing

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

51 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

quasilyte/pathing

Build Status PkgGoDev

A very fast & zero-allocation, grid-based, pathfinding library for Go.

Overview

This library has several things that make it much faster than the alternatives. Some of them are fundamental, and some of them are just a side-effect of the goal I was pursuing for myself.

Some of the limitations you may want to know about before using this library:

  1. Its max path length per BuildPath() is limited
  2. Only 4 tile kinds per Grid are supported

Both of these limitations can be worked around:

  1. Connect the partial results to traverse a bigger map
  2. Use different "layers" for different biomes

To learn more about this library and its internals, see this presentation.

When to use this library?

  • You need a very fast pathfinding
  • You can live with the limitations listed above

If you answer "yes" to both, consider using this library.

Some games that use this library:

Quick Start

$ go get github.com/quasilyte/pathing

This is a simplified example. See the full example if you want to learn more.

func main() {
	// Grid is a "map" that stores cell info.
	const cellSize = 40
	g := pathing.NewGrid(pathing.GridConfig{
		// A 5x4 map.
		WorldWidth:  5 * cellSize,
		WorldHeight: 4 * cellSize,
		CellWidth:   cellSize,
		CellHeight:  cellSize,
	})

	// We'll use Greedy BFS pathfinder (A* is also available).
	bfs := pathing.NewGreedyBFS(pathing.GreedyBFSConfig{})

	// Tile kinds are needed to interpret the cell values.
	// Let's define some.
	const (
		tilePlain = iota
		tileForest
		tileMountain
	)

	// Grid map cells contain "tile tags"; these are basically
	// a tile enum values that should fit the 2 bits (max 4 tags per Grid).
	// The default tag is 0 (tilePlain).
	// Let's add some forests and mountains.
	//
	// The result map layout will look like this:
	// . . m . . | [m] - mountain
	// . . f . . | [f] - forest
	// . . f . . | [.] - plain
	// . . . . .
	g.SetCellTile(pathing.GridCoord{X: 2, Y: 0}, tileMountain)
	g.SetCellTile(pathing.GridCoord{X: 2, Y: 1}, tileForest)
	g.SetCellTile(pathing.GridCoord{X: 2, Y: 2}, tileForest)

	// Now we need to tell the pathfinding library how to interpret
	// these tiles. For instance, which tiles are passable and not.
	// We do that by using layers. I'll define two layers here
	// to show you how it's possible to interpret the grid differently
	// depending on the layer.
	normalLayer := pathing.MakeGridLayer([4]uint8{
		tilePlain:    1, // passable
		tileMountain: 0, // not passable
		tileForest:   0, // not passable
	})
	flyingLayer := pathing.MakeGridLayer([4]uint8{
		tilePlain:    1,
		tileMountain: 1,
		tileForest:   1,
	})

	// Our map with markers will look like this:
	// . . m . . | [m] - mountain
	// . A f B . | [f] - forest
	// . . f . . | [.] - plain
	// . . . . . | [A] - start, [B] - finish
	startPos := pathing.GridCoord{X: 1, Y: 1}
	finishPos := pathing.GridCoord{X: 3, Y: 1}

	// Let's build a normal path first, for a non-flying unit.
	p := bfs.BuildPath(g, startPos, finishPos, normalLayer)

	// The path reads as: Down, Down, Right, Right, Up, Up.
	fmt.Println(p.Steps.String(), "- normal layer path")

	// You can iterate the path.
	for p.Steps.HasNext() {
		fmt.Println("> step:", p.Steps.Next())
	}

	// A flying unit can go in a straight line.
	p = bfs.BuildPath(g, startPos, finishPos, flyingLayer)
	fmt.Println(p.Steps.String(), "- flying layer path")
}

Some terminology hints:

  • Grid - a compact matrix that holds the "tile tags"
  • GridCoord - an {X,Y} object that addresses the grid cell
  • Pos - a world coordinate that can be mapped to a grid
  • Tile (or a tile tag) - a enum-like value that represents a tile kind
  • GridLayer - translates the tag into a pathing value cost (where 0 means "blocked")

Note that it's possible to convert between the GridCoord and world positions via the Grid type API.

Greedy BFS paths quality

This library provides both greedy best-first search as well as A* algorithms.

You may be concerned about the Greedy BFS vs A* results. Due to a couple of tricks I used during the implementation, an unexpected thing happened: some of the paths are actually better than you would expect from a Greedy BFS.

A* (21 steps) Greedy BFS (27 steps) This library's BFS (21 steps)

This library worked well enough for me even without A*. You still may want to use A* if you need to have different movement costs for tiles.

In general, A* always build an optimal path and can handle cost-based pathfinding. Greedy BFS requires less memory and works faster.

Benchmarks & Performance

See _bench folder to reproduce the results.

# If you're using Linux+Intel processor, consider doing this
# to reduce the noise and make your results more stable:
$ echo "1" | sudo tee /sys/devices/system/cpu/intel_pstate/no_turbo

# Running and analyzing the benchmarks:
$ cd _bench
$ go test -bench=. -benchmem -count=10 | results.txt
$ benchstat results.txt

Time - ns/op:

Library no_wall simple_wall multi_wall
quasilyte/pathing BFS 3525 6353 16927
quasilyte/pathing A* 20140 35846 44756
fzipp/astar 948367 1554290 1842812
beefsack/go-astar 453939 939300 1032581
kelindar/tile 107632 ns 169613 ns 182342 ns
s0rg/grid 1816039 1154117 1189989
SolarLune/paths 6588751 5158604 6114856

Allocations - allocs/op:

Library no_wall simple_wall multi_wall
quasilyte/pathing BFS 0 0 0
quasilyte/pathing A* 0 0 0
fzipp/astar 2008 3677 3600
beefsack/go-astar 529 1347 1557
kelindar/tile 3 3 3
s0rg/grid 2976 1900 1759
SolarLune/paths 7199 6368 7001

Allocations - bytes/op:

Library no_wall simple_wall multi_wall
quasilyte/pathing BFS 0 0 0
quasilyte/pathing A* 0 0 0
fzipp/astar 337336 511908 722690
beefsack/go-astar 43653 93122 130731
tile 123118 32950 65763
s0rg/grid 996889 551976 740523
SolarLune/paths 235168 194768 230416

I hope that my contribution to this lineup will increase the competition, so we get better Go gamedev libraries in the future.

Some of my findings that can make these libraries faster:

  • Never use container/heap; use a generic non-interface version
  • Better yet, try a bucket priority queue instead of minheap
  • Do not use map, prefer something that allows a memory re-use
  • The sparse-dense is a good structure to consider
  • The generations array is also a good option
  • Allocating the result path slice is expensive; consider deltas (2 bits per step)
  • Interface method calls are slow for a hot loop
  • Try to be cache-friendly; everything that can be packed should be packed
  • Not every game needs A*, don't underestimate the power of a simpler (and faster) algorithm

If you want to learn more details, look at my library implementation and/or see these slides.