/
ai.go
80 lines (65 loc) · 2.85 KB
/
ai.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
// Copyright © 2014-2018 Galvanized Logic Inc.
// Use is governed by a BSD-style license found in the LICENSE file.
// Package ai provides support for autonomous application unit behaviour.
// This is an experimental package that currently provides A-star and flow
// field path finding algorihms as well as a behaviour tree implementation.
//
// Package ai is provided as part of the vu (virtual universe) 3D engine.
package ai
// More information at:
// https://web.cs.ship.edu/~djmoon/gaming/gaming-notes/ai-movement.pdf
// http://www.raywenderlich.com/24824/introduction-to-ai-programming-for-games
// http://www.hobbygamedev.com/articles/vol8/real-time-videogame-ai/
// http://www.ramalila.net/Adventures/AI/RealTime.html
// Graph is a set of linked points that works with an A* pathing algorithm.
// A graph can be a grids or a set of waypoints or navigation meshes.
type Graph interface {
// Neighbours returns the locations that can be reached
// from the current location. The returned data may be
// overwritten the next time this method is called.
Neighbours(at Point) []Point
// Cost for travelling from a to b. Used to value the move from
// the current location to the next location. Lower cost is better.
// Impassable areas have very high costs.
Cost(a, b Point) float64
// Estimate travel cost from a to b. Used to estimate cost
// from current location to the goal. Lower cost is better.
// Estimates that approximate the final path cost are best.
Estimate(a, b Point) float64
}
// Point is a specific location in a Graph.
// Points with the same ID have the same location.
type Point interface {
ID() int64 // Unique identifier for a location.
}
// =============================================================================
// Utility classes to attach a priority to a given location.
// priorityPoint wraps a location with a priority value used for sorting.
// May be moved to a interal package.
type priorityPoint struct {
Priority float64 // Used to sort PriorityPoints.
Point Point // Route location.
}
// PriorityPointHeap is a min-heap of PriorityPoint.
// Based on example from https://golang.org/pkg/container/heap/
type priorityPointHeap []priorityPoint
// Len implements sort.Interface.
func (h priorityPointHeap) Len() int { return len(h) }
// Less implements sort.Interface.
func (h priorityPointHeap) Less(i, j int) bool { return h[i].Priority < h[j].Priority }
// Swap implements sort.Interface.
func (h priorityPointHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
// Push implements heap.Interface.
func (h *priorityPointHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the
// slice's length, not just its contents.
*h = append(*h, x.(priorityPoint))
}
// Pop implements heap.Interface.
func (h *priorityPointHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}