Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to use the shortest path A* (A-Star) algorithm of golang". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "golang how to use the shortest path A* (A-Star) algorithm"!

Golang practice

A* (A-Star) algorithm A* (A-Star) algorithm is also an algorithm for solving the shortest path problem in the graph, which is developed from the Dixstra algorithm. The A* algorithm considers not only the distance from the start point to the alternate vertex, but also the estimated distance from the current vertex to the end point. The closer the estimated distance value is to the actual value from the current vertex to the end point, the higher the search efficiency of the A* algorithm. When the estimated distance is less than the actual distance, the correct answer can be obtained. A * algorithm is often used to calculate the action route of the enemy chasing the player in game programming. Excerpt from [Japan] Ishida Baohui; Miyazaki Shoichi scene

In the following picture, in a game, the map is grid-shaped, we are at S point, the enemy is at G point, and the blank area is inaccessible areas such as lakes / woods:

Now we need to pursue the enemy, so we need to calculate the shortest route from S point to G point. The A* algorithm is based on the Dikstra algorithm. The difference is that both the measurement weight and the estimated weight need to be considered when calculating the weights of candidate nodes. In this scene, the straight line distance from S point to G point coordinate is used as the estimated weight. The function of estimating weight is like a rope pulling a kite, so that each selected candidate node is as far as possible to the end point.

Process flow

Given several vertices and several edges between vertices, find the minimum weight path from the specified starting point srcNode to the specified end point dstNode.

Set the weight of srcNode to 0 and the weight of other vertices to infinity

Calculate the estimated distance from all nodes to the dstNode node, using the straight line distance of the x _ focus y coordinates as the estimated value

Node. Total weight = node. Measure weight + node. Estimated weight

Send the srcNode node to the candidate heap

The for candidate heap is not empty:

From the candidate heap pop vertex node, node is the candidate node with the lowest total weight.

If node.id = = dstNode.id, the loop ends

Iterate through all the edges starting from node, and update the measured weight of the end point of the edge to to min (to. Measuring weight, node. Measure weight + edge. Weight)

If to. Measurement weight > node. Measure weight + edge. Weight, indicating that the update is valid

If the update is valid, determine whether the to is in the heap, if so, float to maintain the heap order, otherwise, push the to node into the candidate heap

Determine whether the measurement weight of dstNode is updated (! = infinity). If so, it means that there is a shortest path.

Reverse find the shortest path:

Set current node current = end point

Push node current enters the path queue

Traverse the edge with the end point of current to find the starting point of the eligible node: edge. Measurement weight = current. Measure weight-edge. Weight

Push node node enters the path queue

Loop 1-4 until current = = srcNode, search is complete

Design

INode: Vertex interface that supports xy coordinates and estimated weights

ILine: side interface

IPathFinder: shortest path lookup algorithm interface

IComparator: Vertex comparison interface

IHeap: Vertex heap interface

TNode: vertices, implementing INode

TLine: edge, implementing ILine

TNodeWeightComparator: weight-based vertex comparator to implement IComparator interface

TArrayHeap: implementation of the heap

TAStarPathFinder: the implementation of the A* algorithm, which uses the straight line distance of xy coordinates as the estimated weight

Unit testing

A_star_finder_test.go

Package graphimport ("fmt"strings"testing") import astar "learning/gooop/graph/a_star" func Test_AStarFinder (t * testing.T) {fnAssertTrue: = func (b bool) Msg string) {if! b {t.Fatal (msg)}} / / set vertices nodes: = [] astar.INode {astar.NewNode ("11", 1,1), astar.NewNode ("21", 2,1), astar.NewNode ("31") 3,1), astar.NewNode ("12", 1,2), astar.NewNode ("32", 3,2), astar.NewNode ("13", 1,3), astar.NewNode ("33", 3,3), astar.NewNode ("43", 4,3), astar.NewNode ("53", 5,3) Astar.NewNode ("63", 6,3), astar.NewNode ("73", 7,3), astar.NewNode ("14", 1,4), astar.NewNode ("34", 3,4), astar.NewNode ("74", 7,4), astar.NewNode ("15", 1,5) Astar.NewNode ("35", 3,5), astar.NewNode ("55", 5,5), astar.NewNode ("65", 6,5), astar.NewNode ("75", 7,5), astar.NewNode ("16", 1,6), astar.NewNode ("36", 3,6) Astar.NewNode ("56", 5,6), astar.NewNode ("17", 1,7), astar.NewNode ("27", 2,7), astar.NewNode ("37", 3,7), astar.NewNode ("47", 4,7), astar.NewNode ("57", 5,7) Astar.NewNode ("67", 6, 7), astar.NewNode ("77", 7, 7),} / / create edges for adjacent points var lines [] astar.ILine mapNodes: = make (map [string] astar.INode, len (nodes)) for _, it: = range nodes {k: = fmt.Sprintf ("% vForce% v" It.GetX (), it.GetY () mapNodes [k] = it} for _, it: = range nodes {if up,ok: = mapNodes [fmt.Sprintf ("% v% v", it.GetX (), it.GetY ()-1)] Ok {lines = append (lines, astar.NewLine (it.ID (), up.ID (), 1), astar.NewLine (up.ID (), it.ID (), 1)} if down,ok: = mapNodes [fmt.Sprintf ("% v% v", it.GetX (), it.GetY () + 1)] Ok {lines = append (lines, astar.NewLine (it.ID (), down.ID (), 1), astar.NewLine (down.ID (), it.ID (), 1)} if left,ok: = mapNodes [fmt.Sprintf ("% v% v", it.GetX ()-1, it.GetY ())] Ok {lines = append (lines, astar.NewLine (it.ID (), left.ID (), 1), astar.NewLine (left.ID (), it.ID (), 1)} if right,ok: = mapNodes [fmt.Sprintf ("% v% v", it.GetX () + 1, it.GetY ())] Ok {lines = append (lines, astar.NewLine (it.ID (), right.ID (), 1), astar.NewLine (right.ID (), it.ID (), 1)}} / / a* algorithm to find the shortest path ok,path: = astar.AStarPathFinder.FindPath (nodes, lines, "33") "77") if! ok {t.Fatal ("failed to find min path")} fnPathToString: = func (nodes [] astar.INode) string {items: = make ([] string, len (nodes)) for istring it: = range nodes {items [I] = fmt.Sprintf ("% s") It)} return strings.Join (items, "")} pathString: = fnPathToString (path) t.Log (pathString) fnAssertTrue (pathString = = "33 (0,6) 34 (1x 5) 35 (2x 4) 36 (3x 4) 37 (4x 4) 47 (5x 3) 57 (6x 2) 67 (7x 1) 77 (8x 0)" "incorrect path")} Test output $go test-v a_star_finder_test.go = = RUN Test_AStarFinder a_star_finder_test.go:96: 33 (0,6) 34 (1x 5) 35 (2x 4) 36 (3x 4) 37 (4x 4) 47 (5x 3) 57 (6x 2) 67 (7v 1) 77 (8x 0)-PASS: Test_AStarFinder (0.00s) PASSok command-line-arguments 0.002sINode.go

Vertex interface that supports xy coordinates and estimated weights

Package a_startype INode interface {ID () string GetX () int GetY () int SetX (int) SetY (int) SetEstimatedWeight (int) SetMeasuredWeight (int) GetMeasuredWeight () int GetTotalWeight () int} const MaxWeight = int (0x7fffffff_00000000) ILine.go

Side interface

Package a_startype ILine interface {From () string To () string Weight () int} IPathFinder.go

Shortest path search algorithm interface

Package a_startype IPathFinder interface {FindPath (nodes [] INode, lines [] ILine, from string, to string) (bool, [] INode)} IComparator.go

Vertex comparison interface

Package a_startype IComparator interface {Less (an interface {}, b interface {}) bool} IHeap.go

Vertex heap interface

Package a_startype IHeap interface {Size () int IsEmpty () bool IsNotEmpty () bool Push (node interface {}) Pop () (bool, interface {}) IndexOf (node interface {}) int ShiftUp (I int)} tNode.go

Vertex, implementing INode

Package a_starimport "fmt" type tNode struct {id string x int y int measuredWeight int estimatedWeight int} func NewNode (id string, x int, y int) INode {return & tNode {id,x, y, MaxWeight,0 } func (me * tNode) ID () string {return me.id} func (me * tNode) GetX () int {return me.x} func (me * tNode) GetY () int {return me.y} func (me * tNode) SetX (x int) {me.x = x} func (me * tNode) SetY (y int) {me.y = y} func (me * tNode) SetEstimatedWeight ( W int) {me.estimatedWeight = w} func (me * tNode) SetMeasuredWeight (w int) {me.measuredWeight = w} func (me * tNode) GetMeasuredWeight () int {return me.measuredWeight} func (me * tNode) GetTotalWeight () int {return me.estimatedWeight + me.measuredWeight} func (me * tNode) String () string {return fmt.Sprintf ("% s (% vested% v)" Me.id, me.measuredWeight, me.estimatedWeight)} tLine.go

Edge, implementing ILine

Package a_startype tLine struct {from string to string weight int} func NewLine (from string, to string, weight int) ILine {return & tLine {from,to,weight,}} func (me * tLine) From () string {return me.from} func (me * tLine) To () string {return me.to} func (me * tLine) Weight () int {return me.weight} tNodeWeightComparator.go

A vertex comparator based on weight to realize IComparator interface

Package a_starimport "errors" type tNodeWeightComparator struct {} func newNodeWeightComparator () IComparator {return & tNodeWeightComparator {} func (me * tNodeWeightComparator) Less (an interface {}, b interface {}) bool {if a = = nil | | b = = nil {panic (gNullArgumentError)} N1: = a. (INode) N2: = b. (INode) return n1.GetTotalWeight () = MaxWeight {return false Nil} path: = [] INode {dstNode} current: = dstNode maxRound: = len (lines) for Current! = srcNode & & maxRound > 0 MaxRound-- {linkedLines, _: = mapToLines [current.ID ()] for _, line: = range linkedLines {from _: = mapNodes [line.From ()] if from.GetMeasuredWeight () = = current.GetMeasuredWeight ()-line.Weight () {current = from path = append (path From)} if current! = srcNode {return false, nil} me.reverse (path) return true, path} func (me * tAStarPathFinder) distance (x0, y0, x1) Y1 int) int {dx: = x0-x1 dy: = y0-y1 return int (math.Round (math.Sqrt (float64 (dx * dx + dy * dy)} func (me * tAStarPathFinder) reverse (nodes [] INode) {for iMagne j: = 0, len (nodes)-1 I

< j;i,j=i+1,j-1 { nodes[i], nodes[j] = nodes[j], nodes[i] }}func (me *tAStarPathFinder) updateMeasuredWeight(from INode, to INode, line ILine) bool { w := me.min(from.GetMeasuredWeight() + line.Weight(), to.GetMeasuredWeight()) if to.GetMeasuredWeight() >

W {to.SetMeasuredWeight (w) return true} return false} func (me * tAStarPathFinder) min (a, b int) int {if a

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.