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)
}
if !avail(grid, dst) {
supposed to beif !available(grid, dst) {
? \$\endgroup\$ – rolfl Dec 28 '15 at 15:08avail
) and it compiled fine here both withgo build
andgo run
.go version go1.3.3 linux/386
from Debian Jessie repos (which provides Google's toolchain AFAIK). \$\endgroup\$ – Alex Dec 29 '15 at 6:57func foo(p Pos)
doesn't and cannot modifyp
) \$\endgroup\$ – Adam Smith Dec 30 '15 at 0:13