Package pathfind finds the shortest path between two points in a polygon set.
The algorithm works as follows:
- determine all concave polygon vertices
- add start and end points
- build a visibility graph
- use the A* search algorithm (package astar) on the visibility graph to find the shortest path
go run github.com/fzipp/pathfind/cmd/pathfinddemo@latest
pathfind.mp4
package main
import (
"fmt"
"image"
"github.com/fzipp/pathfind"
)
func main() {
// (0,0) >---+ +-----------+ (50,0)
// | s | | >---+ |
// | +---+ | | d |
// | +---+ |
// (0,20) +-------------------+ (50,20)
//
// s = start, d = destination
polygons := [][]image.Point{
// Outer shape
{
image.Pt(0, 0),
image.Pt(10, 0),
image.Pt(10, 10),
image.Pt(20, 10),
image.Pt(20, 0),
image.Pt(50, 0),
image.Pt(50, 20),
image.Pt(0, 20),
},
// Inner rectangle ("hole")
{
image.Pt(30, 5),
image.Pt(40, 5),
image.Pt(40, 15),
image.Pt(30, 15),
},
}
start := image.Pt(5, 5)
destination := image.Pt(45, 10)
pathfinder := pathfind.NewPathfinder(polygons)
path := pathfinder.Path(start, destination)
fmt.Println(path)
}Output:
[(5,5) (10,10) (30,15) (40,15) (45,10)]
This project is free and open source software licensed under the BSD 3-Clause License.