A* Go申请

Question

我编写了一个A*算法的通用实现，作为第一个Go程序，因为我以前在C和Python中都实现了这一点，Go让我想起了这两个方面。我正在寻找关于不良做法的一般性评论，特别是关于以下方面的评论：

参考资料

我想我从未见过在C中通过值传递一个结构，尽管我可以想到一些用例。在Python中，类实例也是“通过引用传递”的。这就是我们该走的路吗？由于缺少const，所以很容易按值传递类似Pos的内容，尽管我认为在astar这样的函数中，这可能不是一个好主意，因为可能会有很多迭代，而且我猜复制开销会增加。

片

根据文档，我应该把它们看作是“指向包含指向数组和长度的指针的结构的指针”，并且数组的长度嵌入到类型中。所以我应该在这里用切片吗？我是不是应该用一个数组，在我走的时候扩大它？

Ranges

我使用它们就像使用Python中的for i in x一样，尽管我在每次迭代中都会创建一个副本。再说一遍，有大量的迭代，这难道不是有点费钱吗？也许我应该使用类似C的for i = 0; ...循环来代替？

一般的建议也是值得赞赏的。我知道代码有点长，我并不要求任何深入的分析，只是一个概述。

package main

import "fmt"

// TODO separate things in packages

/* Error codes */
const (
  SUCCESS int = iota
  INTERNAL_ERROR
  NO_PATH
  TOO_FAR
  UNAVAILABLE
)

/* Define any object here */
type Obj struct {
  attr int8
}

/*
  Define the positional/distances type to be used in geo funcitons. This can be
  any numerical type, signed or unsigned, integer or real.
*/
type Coord int64;

/* Define any N-dimentional position struct here */
type Pos struct {
  y Coord
  x Coord
}

/* A grid represented by a hash table of the form { position : object } */
type Grid map[Pos]Obj

/* Don't A* if dst further than this, and stop iteration after this */
const MAX_PATHFINDING_STEPS Coord = 6000

/*
  Returns the positions in the shortest path between src and dst and an error
  code.

  grid    : { pos : obj }
  src      : source position
  dst      : destination position
  distance : returns the numeric distance between two positions
  nbors    : returns the available positions around a position
  avail    : tells if a position is available on the given grid
 */
func astar(grid Grid, src, dst *Pos, distance func(*Pos, *Pos)Coord, nbors func(Grid, *Pos, func(Grid, *Pos)bool)[]Pos, avail func(Grid, *Pos)bool) ([]Pos, int) {
  var path []Pos;
  if !avail(grid, dst) {
    return path, UNAVAILABLE
  }
  if distance(src, dst) > MAX_PATHFINDING_STEPS{
    return path, TOO_FAR
  }
  /* Hash table for O(1) search and deletion, the value is not used */
  visited := make(map[Pos]int8)
  to_be_visited := map[Pos]int8{ *src : 0 }
  came_from := make(map[Pos]Pos)
  d_src := map[Pos]Coord{ *src : 0 }
  d_dst := map[Pos]Coord{ *src : distance(src, dst) }
  for len(to_be_visited) > 0 && Coord(len(visited)) < MAX_PATHFINDING_STEPS {
    src = _argmin(d_dst)
    if distance(src, dst) == 0 {
      path = _reconstruct_path(came_from, *dst)
      return path, SUCCESS
    }
    delete(to_be_visited, *src)
    delete(d_dst, *src)
    visited[*src] = 0
    for _, nbor := range nbors(grid, src, avail) {
      _, hasbeenvisited := visited[nbor]
      if !hasbeenvisited {
        _, tobevisited := to_be_visited[nbor]
        temp_gscore := d_src[*src] + distance(&nbor, src)
        if !tobevisited || temp_gscore < d_src[nbor] {
          came_from[nbor] = *src
          d_src[nbor] = temp_gscore
          d_dst[nbor] = d_src[nbor] + distance(&nbor, src)
          to_be_visited[nbor] = 0
        }
      }
    }
  }
  if len(to_be_visited) > 0 {
    return path, TOO_FAR
  } else {
    return path, NO_PATH
  }
}

/* For internal use, returns the &position with the least distance */
func _argmin(distances map[Pos]Coord) *Pos {
  var ans *Pos
  var min Coord = MAX_PATHFINDING_STEPS
  for spot, distance := range distances {
    if distance < min {
      min = distance
      ans = &spot
    }
  }
  return ans
}

/* For internal use */
func _reconstruct_path(came_from map[Pos]Pos, cur Pos) []Pos {
  ans := []Pos{cur}
  in := true
  for in {
    cur = came_from[cur]
    ans = append(ans, cur)
    _, in = came_from[cur]
  }
  return ans
}

/*
  The following functions provide the necessary arguments to do A* on a 2D grid
  (tiled map) with taxicab geometry (Manhattan distance)
*/

/*
  A position is available on the grid if it's coordinates are within the grid
  and there is no object ocupying them
*/
func available(grid Grid, pos *Pos)bool {
  // TODO for now this is hard coded
  if pos.x < 0 || pos.y < 0 || pos.x > 5 || pos.y > 2 {
    return false
  }
  _, ans := grid[*pos]
  return !ans
}

/* Exact copy of abs.go, except with Coord type */
func abs(x Coord) Coord {
  switch {
  case x < 0:
    return -x
  case x == 0:
    return 0 // return correctly abs(-0)
  }
  return x
}

/* Manhattan distance */
func mdistance(a, b *Pos) Coord {
  return abs(a.y - b.y) + abs(a.x - b.x)
}

/* The (at most 8) available positions around a spot in a grid */
func nbors(grid Grid, spot *Pos, avail func(Grid, *Pos)bool) []Pos {
  var ans []Pos;
  var i, j Coord
  // TODO assumes pos is signed and doesn't check for under/overflow
  for i = -1; i < 2; i++ {
    for j = -1; j < 2; j++ {
      nbor := Pos{spot.y + i, spot.x + j}
      if avail(grid, &nbor) {
        ans = append(ans, nbor)
      }
    }
  }
  return ans
}

func main() {
  /* Create the game map (ht pos : obj) */
  m := make(map[Pos]Obj)
  /*
    Map:

       012345
      0 #  # 0
      1# ### 1
      2#     2
       012345

    Src: 0, 0
    Dst: 0, 5
    Excpeted answer: {(0,0), (1,1), (2,2), (2,3), (2,4), (1,5), (0,5)}
  */
  m[Pos{0,1}] = Obj{0}
  m[Pos{0,4}] = Obj{0}
  m[Pos{1,0}] = Obj{0}
  m[Pos{1,2}] = Obj{0}
  m[Pos{1,3}] = Obj{0}
  m[Pos{1,4}] = Obj{0}
  m[Pos{2,0}] = Obj{0}
  path, rc := astar(m, &Pos{0,0}, &Pos{0,5}, mdistance, nbors, available)
  fmt.Println(rc)
  fmt.Println(path)
}

Answer 1

Bug

您的代码明确指出：

Src: 0，0 Dst: 0，5异常答案：{(0,0)，(1,1)，(2,2)，(2,3)，(2,4)，(1,5)，(0,5)}

但是，当我运行你的代码时，我得到：

[{0 5} {1 5} {2 4} {2 3} {2 2} {1 1} {0 0}]

一切都是相反的。很明显，倒转路径的回头路是将每个点附加到ans切片中，而不是在开始时插入每个点--并以正确的顺序进行处理。

话虽如此，追加可能是正确的解决方案，但之后再进行切片反转会更好。

你目前的回溯功能是：

内部使用的/* */ func _reconstruct_path(came_from map位置Pos，cur Pos) []Pos { ans := []Pos{ cur } in := true For {cur= came_from库尔 ans = append( ans，cur) _，in = came_from库尔 }返回ans}

相反，我要这样说：

/* For internal use */
func _reconstruct_path(came_from map[Pos]Pos, cur Pos) []Pos {
  ans := []Pos{cur}
  for cur, ok := came_from[cur]; ok; cur, ok = came_from[cur] {
    ans = append(ans, cur)
  }

  sz := len(ans)
  for i := sz / 2; i >= 0; i-- {
    ans[i], ans[sz - i - 1] = ans[sz - i - 1], ans[i]
  }

  return ans
}

请注意我是如何将循环条件放入for -循环中的，这使得您的出环in变量现在处于循环的范围内。另外，我将它重命名为ok，以符合go中的常见实践。

然后，我使用go中的简单交换机制来反转ans切片。

码样式

你的代码中有很多打破惯例的习惯。例如，以下内容：

内部使用/* */ func _reconstruct_path(came_from map位置Pos，cur Pos) []Pos {

go中的函数名不应该包含任何下划线，并且应该是MixedCase (用于导出函数)或mixedCase (用于内部函数)。对于变量名称也是如此。

下划线_或blank identifier在Go中有特殊的含义，应该在名称中避免使用。

该宣言应包括：

func reconstructPath(cameFrom map[Pos]Pos, cur Pos) []Pos {

当通过go lint检查器运行您的代码时，它报告了除上述问题之外的一些问题(尽管上面的代码是促使我运行lint检查器的原因)：

astar.go:10:3:在Go名称中不要使用ALL_CAPS；使用CamelCase astar.go:11:3:不要在Go名称中使用ALL_CAPS；使用CamelCase astar.go:12:3:不要在Go名称中使用ALL_CAPS；使用CamelCase astar.go:16:1:注释导出类型Obj的形式应该是"Obj .“。astar.go:21:1:关于导出类型Coord的注释应该是"Coord .“形式。astar.go:27:1:关于导出类型Pos的注释应该是"Pos .“形式。(带有可选的前面文章) astar.go:33:1:关于导出类型的网格的注释应该是"Grid .(带有可选的前面文章) astar.go:36:1:关于导出的MAX_PATHFINDING_STEPS的注释应该是"MAX_PATHFINDING_STEPS .“形式。astar.go:37:7:在Go名称中不要使用ALL_CAPS；使用CamelCase astar.go:60:3:不要在Go名称中使用下划线；var to_be_visited应该是toBeVisited astar.go:61:3:不要在Go名称中使用下划线；var came_from应该是cameFrom astar.go:62:3:不要在Go名称中使用下划线；var d_src应该是dSrc astar.go:63:3:不要在Go名称中使用下划线；var d_dst应该是dDst astar.go:77:9:在Go名称中不要使用下划线；var temp_gscore应该是tempGscore astar.go:89:10:如果块以返回语句结尾，那么删除它，然后删除它的块astar.go:97:11:应该从var min的声明中省略Coord类型；它将从右边的astar.go:108:6:不要在Go名称中使用下划线来推断；func _reconstruct_path应该是_reconstructPath astar.go:108:24:不要在Go名称中使用下划线；函数参数came_from应该是cameFrom

在代码上运行code fmt也会产生影响--主要是在空格/制表符的情况下-- go使用选项卡.无论是好是坏，总是。

命名

有一点让我感到困惑的是，这段代码：

Coord int64型；

你把一个“坐标”定义为一个单一的int64 --但是，一个坐标至少是一个二维的东西……对吗？你所拥有的是一段距离。你在某些地方称它为距离，但在另一些地方，它使代码变得有趣.例如，这里有一个名为mdistance的函数，它返回一个Coord？.：

/*曼哈顿距离*/ func mdistance(a，b *Pos) Coord {返回abs(a.y - b.y) +abs(A.X-b.x)}

我认为，您对Coord的类型声明过于热情，应该删除它。而且，没有真正的理由让它成为int64。一个简单的int会做得很好，而且您可能是在64位平台上。