A* Go application

Question

I've written a generic implementation of the A* algorithm as a first Go program, since I had implemented that both in C and in Python before and Go reminds me a bit of both. I'm looking for general commentary on bad practices, specially concerning the following:

References

I don't think I've ever seen a struct being passed by value in C, though I can think of some use cases. In Python, class instances are also "passed by reference". Is that the way to go with Go? The lack of const makes it tempting to pass something like Pos by value, though I guess in a function like astar that might not be a good idea, as there can be a lot of iterations and I guess the copy overhead would add up.

Slices

According to the docs I should think of them as "a pointer to a struct containing a pointer to an array and a length", and the array has its length embedded in the type. So should I even be using slices in here? Shouldn't I just use an array, growing it as I go?

Ranges

I'm using them like a for i in x in Python, though I read a copy is created in each iteration. Then again, with a large number of iterations isn't that a bit costly? Perhaps I should be using a C-like for i = 0; ... loop instead?

General advice is also appreciated. I understand the code is a bit lengthy, I'm not asking for any in-depth analysis though, just an overview.

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

Your code clearly states:

Src: 0, 0
Dst: 0, 5
Excpeted answer: {(0,0), (1,1), (2,2), (2,3), (2,4), (1,5), (0,5)}

But, when I run your code, I get:

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

Everything in reverse order. It is clear that your back-track to reverse the path taken is appending each point to the ans slice, instead of inserting each point at the beginning - and getting things in the right order.

Having said that, the append is probably the right solution, but a slice reversal afterwards would be better.

Your current back-track function is:

/* 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
}

I would instead make that:

/* 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
}

Notice how I put the loop conditions in to the for-loop, which makes your out-of-loop in variable now in-scope for the loop. Also, I renamed it to ok to conform to common practice in go.

Then, I use the simple swap mechanism in go to reverse the ans slice.

Code Style

You have a number of convention-breaking habits in your code. For example, the following:

/* For internal use */
func _reconstruct_path(came_from map[Pos]Pos, cur Pos) []Pos {

Function names in go should not have any underscores in them, and should be MixedCase (for exported functions) or mixedCase for internal functions. This is true for variable names as well.

The underscore _ or blank identifier has a special meaning in Go, and should be avoided in names.

That declaration should be:

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

When running your code through the go lint-checker, it reported a number of problems in addition to the above (though the above code is what prompted me to run the lint checker):

astar.go:10:3: don't use ALL_CAPS in Go names; use CamelCase
astar.go:11:3: don't use ALL_CAPS in Go names; use CamelCase
astar.go:12:3: don't use ALL_CAPS in Go names; use CamelCase
astar.go:16:1: comment on exported type Obj should be of the form "Obj ..." (with optional leading article)
astar.go:21:1: comment on exported type Coord should be of the form "Coord ..." (with optional leading article)
astar.go:27:1: comment on exported type Pos should be of the form "Pos ..." (with optional leading article)
astar.go:33:1: comment on exported type Grid should be of the form "Grid ..." (with optional leading article)
astar.go:36:1: comment on exported const MAX_PATHFINDING_STEPS should be of the form "MAX_PATHFINDING_STEPS ..."
astar.go:37:7: don't use ALL_CAPS in Go names; use CamelCase
astar.go:60:3: don't use underscores in Go names; var to_be_visited should be toBeVisited
astar.go:61:3: don't use underscores in Go names; var came_from should be cameFrom
astar.go:62:3: don't use underscores in Go names; var d_src should be dSrc
astar.go:63:3: don't use underscores in Go names; var d_dst should be dDst
astar.go:77:9: don't use underscores in Go names; var temp_gscore should be tempGscore
astar.go:89:10: if block ends with a return statement, so drop this else and outdent its block
astar.go:97:11: should omit type Coord from declaration of var min; it will be inferred from the right-hand side
astar.go:108:6: don't use underscores in Go names; func _reconstruct_path should be _reconstructPath
astar.go:108:24: don't use underscores in Go names; func parameter came_from should be cameFrom

Running the code fmt on your code also made a difference - mostly in the spaces/tabs situation - go uses tabs.... for better or worse, always.

Naming

One item that had me confused for a bit, is this code:

type Coord int64;

You define a "coordinate" as a single int64 - but, a coordinate is at least a 2 dimensional thing..... right? What you have there, is a distance. You call it a distance in some places, but in other places it makes the code funny... for example, here we have a function called mdistance which returns a Coord... ??? ...:

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

You have been overly enthusiastic in your type declaration for Coord, I think, and it should just be removed. Also, there's no real reason to make it an int64. A simple int will do fine - and you're probably on a 64-bit platform anyway.