pathfind

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

• type Pathfinder
  • func NewPathfinder(polygons [][]image.Point) *Pathfinder
  • func (p *Pathfinder) Path(start, dest image.Point) []image.Point
  • func (p *Pathfinder) VisibilityGraph() map[image.Point][]image.Point

Examples

• Pathfinder.Path

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.