Created
November 12, 2009 16:09
-
-
Save bellbind/233013 to your computer and use it in GitHub Desktop.
[Go] Example for astar.go gist:233012
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 8g astar.go | |
| // 8g -I . astar_main.go | |
| // 8l -o astar_main astar_main.go astar.go | |
| package main | |
| import "fmt" | |
| import "math" | |
| import "strings" | |
| import "astar" | |
| type loc struct { | |
| x, y int; | |
| } | |
| func (pos *loc) Equals(obj astar.Location) bool { | |
| o := obj.(*loc); | |
| return pos.x == o.x && pos.y == o.y; | |
| } | |
| func (pos *loc) ToKey() string { | |
| return fmt.Sprintf("%v", pos); | |
| } | |
| func main() { | |
| dungeonData := [...]string { | |
| "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", | |
| "OS O O O O O", | |
| "O O O O O O O OOOO GO", | |
| "O O O O OOOO O O OOOO", | |
| "OO OOOOOOOOOOOOOOO O O O O", | |
| "O O O O O", | |
| "O OOO O O OOOOOOOOO O", | |
| "O OO O OOOO O O OO O", | |
| "O O O O O O O O", | |
| "O OOO O O O O O", | |
| "O O O O O", | |
| "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO", | |
| }; | |
| dungeon := make([][]string, len(dungeonData)); | |
| for i, l := range dungeonData { | |
| dungeon[i] = strings.Split(l, "", 0); | |
| } | |
| findCh := func(ch string) *loc { | |
| for i, l := range dungeon { | |
| for j, c := range l { | |
| if ch == c { return &loc{i, j}; } | |
| } | |
| } | |
| return nil; | |
| }; | |
| start := findCh("S"); | |
| goal := findCh("G"); | |
| nexts := func(pos astar.Location) <-chan astar.Location { | |
| ch := make(chan astar.Location); | |
| go func() { | |
| p := pos.(*loc); | |
| x := p.x; | |
| y := p.y; | |
| wall := "O"; | |
| if dungeon[x - 1][y] != wall { | |
| ch <- &loc{x - 1, y}; | |
| } | |
| if dungeon[x + 1][y] != wall { | |
| ch <- &loc{x + 1, y}; | |
| } | |
| if dungeon[x][y - 1] != wall { | |
| ch <- &loc{x, y - 1}; | |
| } | |
| if dungeon[x][y + 1] != wall { | |
| ch <- &loc{x, y + 1}; | |
| } | |
| if dungeon[x - 1][y - 1] != wall { | |
| ch <- &loc{x - 1, y - 1}; | |
| } | |
| if dungeon[x + 1][y - 1] != wall { | |
| ch <- &loc{x + 1, y - 1}; | |
| } | |
| if dungeon[x - 1][y + 1] != wall { | |
| ch <- &loc{x - 1, y + 1}; | |
| } | |
| if dungeon[x + 1][y + 1] != wall { | |
| ch <- &loc{x + 1, y + 1}; | |
| } | |
| close(ch); | |
| }(); | |
| return ch; | |
| }; | |
| dist := func(p1 *loc, p2 *loc) float64 { | |
| return math.Sqrt( | |
| math.Pow(float64(p2.x - p1.x), 2.0) + | |
| math.Pow(float64(p2.y - p1.y), 2.0)); | |
| }; | |
| heulistic := func(pos astar.Location) float64 { | |
| p := pos.(*loc); | |
| return dist(p, goal); | |
| }; | |
| distance := func(path []astar.Location) float64 { | |
| result := float64(0.0); | |
| cur := path[0].(*loc); | |
| for _, n := range path[1:len(path)] { | |
| next := n.(*loc); | |
| result += dist(cur, next); | |
| cur = next; | |
| } | |
| return result; | |
| }; | |
| renderPath := func(path []astar.Location) string { | |
| buf := make([][]string, len(dungeonData)); | |
| for i, _ := range dungeonData { | |
| buf[i] = strings.Split(dungeonData[i], "", 0); | |
| } | |
| for _, pos := range path { | |
| p := pos.(*loc); | |
| buf[p.x][p.y] = "*"; | |
| } | |
| s := path[0].(*loc); | |
| buf[s.x][s.y] = "s"; | |
| g := path[len(path) - 1].(*loc); | |
| buf[g.x][g.y] = "g"; | |
| result := make([]string, len(buf)); | |
| for i, l := range buf { | |
| result[i] = strings.Join(l, ""); | |
| } | |
| return strings.Join(result, "\n"); | |
| }; | |
| path := astar.AStar(start, goal, nexts, distance, heulistic); | |
| fmt.Printf("%s\n", renderPath(path)); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment