README
¶
pathfind
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
Demo
go run github.com/fzipp/pathfind/cmd/pathfinddemo@latest
https://user-images.githubusercontent.com/598327/228644017-a9800747-a096-46ae-befe-d725da18205a.mp4
Example Code
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)]
License
This project is free and open source software licensed under the BSD 3-Clause License.
Documentation
¶
Overview ¶
Package pathfind finds the shortest path between two points constrained by a set of polygons.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Pathfinder ¶
type Pathfinder struct {
// contains filtered or unexported fields
}
A Pathfinder is created and initialized with a set of polygons via NewPathfinder. Its Path method finds the shortest path between two points in this polygon set.
func NewPathfinder ¶
func NewPathfinder(polygons [][]image.Point) *Pathfinder
NewPathfinder creates a Pathfinder instance and initializes it with a set of polygons.
A polygon is represented by a slice of points, i.e. []image.Point, describing the vertices of the polygon. Thus [][]image.Point is a slice of polygons, i.e. the set of polygons.
Each polygon in the polygon set designates either an area that is accessible for path finding or a hole inside such an area, i.e. an obstacle. Nested polygons alternate between accessible area and inaccessible hole:
- Polygons at the first level are area polygons.
- Polygons contained inside an area polygon are holes.
- Polygons contained inside a hole are area polygons again.
func (*Pathfinder) Path ¶
func (p *Pathfinder) Path(start, dest image.Point) []image.Point
Path finds the shortest path from start to dest within the bounds of the polygons the Pathfinder was initialized with. If dest is outside the polygon set it will be clamped to the nearest polygon edge. The function returns nil if no path exists because start is outside the polygon set.
Example ¶
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)]
func (*Pathfinder) VisibilityGraph ¶
func (p *Pathfinder) VisibilityGraph() map[image.Point][]image.Point
VisibilityGraph returns the calculated visibility graph from the last Path call. It is only available after Path was called, otherwise nil.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
cmd
|
|
|
pathfinddemo
Module
|
|
|
internal
|
|
|
poly
Package poly provides types and functions for working with polygons in support of the pathfind package.
|
Package poly provides types and functions for working with polygons in support of the pathfind package. |