Алгоритм волновой трассировки

Статья в вики.

Поле с препятствиями

Поле представляет из себя прямоугольную матрицу [][]float32.

Ячейку свободная для прохода задаем значением 0 (wave.Empty). Препятствия задаем значением -1 (wave.Obstacle).

field := wave.NewField([][]float32{
    {0, 0, -1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, -1, 0, 0, 0, 0, 0, 0, 0},
    {-1, 0, 0, 0, -1, 0, 0, 0, 0, 0},
    {0, -1, -1, -1, 0, -1, 0, 0, 0, 0},
    {0, -1, 0, 0, 0, 0, -1, 0, 0, 0},
    {0, -1, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
}, )

Примеры

Получить кратчайший путь.

field := NewField([][]float32{
    {0, 0, -1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, -1, 0, 0, 0, 0, 0, 0, 0},
    {-1, 0, 0, 0, -1, 0, 0, 0, 0, 0},
    {0, -1, -1, -1, 0, -1, 0, 0, 0, 0},
    {0, -1, 0, 0, 0, 0, -1, 0, 0, 0},
    {0, -1, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
})

p, ok := Search(field, image.ZP, image.Point{X: 0, Y: 3})
if ok {
    fmt.Println("Путь найден", p)
} else {
    fmt.Println("Путь не найден")
}