benchmark_test.go

// SPDX-License-Identifier: MIT
// Copyright (c) 2026 MaIII Themd

package dijkstra

import (
	"fmt"
	"testing"
)

// buildGrid returns a side x side 4-connected unit-weight grid graph.
// Vertices are named "r<row>c<col>". Used to benchmark a realistic
// spatial pathfinding workload (e.g. a robot map).
func buildGrid(side int) *StGraph {
	var g StGraph
	name := func(r, c int) string { return fmt.Sprintf("r%dc%d", r, c) }
	for r := 0; r < side; r++ {
		for c := 0; c < side; c++ {
			var edges []StEdge
			if r > 0 {
				edges = append(edges, StEdge{ToVertexName: name(r-1, c), Weight: 1})
			}
			if r < side-1 {
				edges = append(edges, StEdge{ToVertexName: name(r+1, c), Weight: 1})
			}
			if c > 0 {
				edges = append(edges, StEdge{ToVertexName: name(r, c-1), Weight: 1})
			}
			if c < side-1 {
				edges = append(edges, StEdge{ToVertexName: name(r, c+1), Weight: 1})
			}
			g.VertexAdd(name(r, c), float64(c), float64(r), 0, edges...)
		}
	}
	return &g
}

// BenchmarkScale exercises larger grids (1k / 10k / 25.6k vertices) so
// speed and allocation changes at scale are visible. It measures a full
// single-source Dijkstra (corner goal) and a goal-directed A* (mid
// goal) on each grid.
func BenchmarkScale(b *testing.B) {
	for _, side := range []int{32, 100, 160} { // 1024, 10000, 25600
		g := buildGrid(side)
		corner := fmt.Sprintf("r%dc%d", side-1, side-1)
		mid := fmt.Sprintf("r%dc%d", side/4, side/4)
		b.Run(fmt.Sprintf("V=%d/dijkstra-corner", side*side), func(b *testing.B) {
			b.ReportAllocs()
			for i := 0; i < b.N; i++ {
				if ok, _ := g.DijkstraSearch("r0c0", corner); !ok {
					b.Fatal("no path")
				}
			}
		})
		b.Run(fmt.Sprintf("V=%d/astar-mid", side*side), func(b *testing.B) {
			b.ReportAllocs()
			for i := 0; i < b.N; i++ {
				if ok, _ := g.AStarSearch("r0c0", mid); !ok {
					b.Fatal("no path")
				}
			}
		})
	}
}

func BenchmarkDijkstraSearch(b *testing.B) {
	for _, side := range []int{7, 14, 32} {
		g := buildGrid(side)
		from, to := "r0c0", fmt.Sprintf("r%dc%d", side-1, side-1)
		b.Run(fmt.Sprintf("V=%d", side*side), func(b *testing.B) {
			b.ReportAllocs()
			for i := 0; i < b.N; i++ {
				if ok, _ := g.DijkstraSearch(from, to); !ok {
					b.Fatal("expected a path across the grid")
				}
			}
		})
	}
}