jps

README

Jps

Golang implementation of Jump point search . Jump point search minimizes A* execution time by jumping nodes which won't be contributing in optimizing path. Detailed explaination available at - https://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-icaps14.pdf

Usage

package main

import (
	"fmt"

	"github.com/ankurjha7/jps"
)

func main() {

	grid := [][]uint8{
		{0, 1, 0, 0, 0},
		{0, 0, 1, 0, 0},
		{1, 1, 1, 1, 0},
		{0, 0, 0, 0, 0},
	}
	start := jps.GetNode(0, 0)
	end := jps.GetNode(3, 2)
	path, err := jps.AStarWithJump(grid, start, end, 1)
	if err == nil {
		fmt.Printf("Path is : ")
		for _, node := range path.Nodes {
			fmt.Printf("%d %d -> ", node.GetRow(), node.GetCol())
		}
		fmt.Printf("\nTotal distance %f", path.Weight)
	}

}

References

A python version of code which served as a reference for this is available at - https://github.com/ViktorRubenko/Jump-Point-Search

Documentation

Index

• type Node
  • func GetNode(row, col int) Node
  • func (node *Node) GetCol() int
  • func (node *Node) GetRow() int
• type Path
  • func AStarWithJump(matrix [][]uint8, start Node, goal Node, hchoice int) (*Path, error)

Types

type Node

type Node struct {
	// contains filtered or unexported fields
}

func GetNode

func GetNode(row, col int) Node

GetNode returns node object for a row,columns value

func (*Node) GetCol

func (node *Node) GetCol() int

GetCol returns column value for a node. in terms of x and y this is x

func (*Node) GetRow

func (node *Node) GetRow() int

GetRow returns row value for a node . in terms of x and y this is y

type Path

type Path struct {
	Nodes  []Node
	Weight float64
}

Path struct to hold the shortest path result

func AStarWithJump

func AStarWithJump(matrix [][]uint8, start Node, goal Node, hchoice int) (*Path, error)

AStarWithJump astar implementation with neighbours filtered by jump point search .