generated from BattlesnakeOfficial/starter-snake-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
voronoi.go
116 lines (106 loc) · 2.94 KB
/
voronoi.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package game
type pair struct {
id SnakeId
index uint16
}
type voronoiResult struct {
Score map[SnakeId]int8
FoodDepth map[SnakeId]int
}
func Voronoi(game *FastBoard, player SnakeId) voronoiResult {
// create queue of indices
queue := []pair{}
// create map of visited indices
visited := make(map[uint16]SnakeId)
// create map of scores for indices
scores := make(map[SnakeId]int8)
depth := 0
food := make(map[SnakeId]int)
depthMark := pair{id: SnakeId(0), index: 0}
mark := SnakeId(0)
//
// add snake heads to queue
// mark snake heads as visited
for id, head := range game.Heads {
food[id] = -1
if game.IsSnakeAlive(id) {
p := pair{id, head}
queue = append(queue, p)
visited[head] = id
}
}
// add depth mark to queue
queue = append(queue, depthMark)
//
// while the queue is not empty
for len(queue) > 0 {
//fmt.Println(queue)
//fmt.Println(scores)
//for y := int(game.height - 1); y >= 0; y-- {
//var line string
//for x := 0; x < int(game.width); x++ {
//p := Point{X: int8(x), Y: int8(y)}
//index := pointToIndex(p, game.width)
//part := ""
//if id, ok := visited[index]; ok {
//part = fmt.Sprintf(" _%d ", id)
//} else {
//part = game.tileToString(index)
//}
//line = line + part
//}
//fmt.Println(line)
//}
// dequeue index
var current pair
current, queue = queue[0], queue[1:]
//
// if index is depth mark
if current == depthMark {
// increase depth count by 1
depth += 1
// add depth mark to queue
queue = append(queue, depthMark)
//
// if front of queue is a depth mark
if queue[0] == depthMark {
// end (we have searched all tiles)
//
break
}
} else { // else
// if this index is already marked, skip out
if id, ok := visited[current.index]; ok && id == mark {
continue
}
// loop through neighbors of index
neighbors := game.GetNeighbors(current.index)
for _, neighbor := range neighbors {
nIndex := IndexInDirection(neighbor, current.index, game.Width, game.Height, game.isWrapped)
if game.IsTileFood(nIndex) && food[current.id] == -1 {
food[current.id] = depth
}
// if neighbor is in visited map
if other, ok := visited[nIndex]; ok {
// if visited map is not a mark and the visited snake does not equal the snake for the current index
if other != mark && other != current.id {
// reduce the score for this neighbor by one
scores[other] -= 1
// set the visited map to mark for this neighbor
visited[nIndex] = mark
}
//
} else {
// increase the score for this neighbor by 1
scores[current.id] += 1
// add neighbor to visited map
p := pair{id: current.id, index: nIndex}
visited[nIndex] = current.id
// add neighbor to the queue
queue = append(queue, p)
}
}
}
}
return voronoiResult{Score: scores, FoodDepth: food}
}