122 lines
2.7 KiB
Swift
122 lines
2.7 KiB
Swift
struct Graph {
|
|
public var vertices: [Vertex]
|
|
public var dist: [Vertex: Int]
|
|
public var prev: [Vertex: (Vertex, Vertex)]
|
|
|
|
public init(numberOfNodes: Int) {
|
|
vertices = []
|
|
dist = [:]
|
|
prev = [:]
|
|
vertices.reserveCapacity(numberOfNodes)
|
|
dist.reserveCapacity(numberOfNodes)
|
|
prev.reserveCapacity(numberOfNodes)
|
|
}
|
|
|
|
public mutating func populate(_ board: Board) {
|
|
vertices.removeAll()
|
|
dist.removeAll()
|
|
prev.removeAll()
|
|
|
|
guard board.mySnake != nil else {
|
|
return
|
|
}
|
|
|
|
for y in 0..<board.height {
|
|
for x in 0..<board.width {
|
|
let vertex = Vertex(x, y)
|
|
|
|
guard !board.occupiedSpaces.contains(vertex) else {
|
|
continue
|
|
}
|
|
|
|
vertices.append(vertex)
|
|
}
|
|
}
|
|
}
|
|
|
|
public mutating func dijkstra(_ board: Board) -> [(Vertex, Vertex)]? {
|
|
guard let snake = board.mySnake,
|
|
let source = snake.body.first?.vertex
|
|
else {
|
|
return nil
|
|
}
|
|
|
|
var queue: Set<Vertex> = []
|
|
for vertex in vertices {
|
|
dist[vertex] = Int.max
|
|
queue.insert(vertex)
|
|
}
|
|
|
|
dist[source] = 0
|
|
|
|
while !queue.isEmpty {
|
|
guard let vertex = queue.min(by: { dist[$0, default: Int.max] < dist[$1, default: Int.max] }),
|
|
let distance = dist[vertex]
|
|
else {
|
|
break
|
|
}
|
|
|
|
if distance == Int.max {
|
|
break
|
|
}
|
|
|
|
queue.remove(vertex)
|
|
|
|
for dir in Vertex.cardinals {
|
|
_ = pathCheck(board, vertex, dir: dir, distance: distance, cost: 1)
|
|
/*
|
|
// this is kind of broken
|
|
guard pathCheck(board, vertex, dir: dir, distance: distance, cost: 1),
|
|
snake.body.count > 5 else {
|
|
continue
|
|
}
|
|
_ = pathCheck(board, vertex, dir: dir + dir, distance: distance, cost: 1)
|
|
*/
|
|
}
|
|
}
|
|
|
|
for apple in board.apples.sorted(by: {
|
|
source.distance(target: $0, size: board.size) < source.distance(target: $1, size: board.size)
|
|
|| Int.random(in: 0..<10000) == 5000 // 0.01% chance for chaos for when two Np85 bots are in a loop with each other
|
|
}) {
|
|
var s: [(Vertex, Vertex)] = []
|
|
var u = prev[apple]
|
|
|
|
guard u != nil else {
|
|
continue
|
|
}
|
|
|
|
s.append((apple, Vertex.zero))
|
|
while let vertex = u {
|
|
s.append(vertex)
|
|
u = prev[vertex.0]
|
|
}
|
|
|
|
return s
|
|
}
|
|
|
|
return nil
|
|
}
|
|
|
|
mutating func pathCheck(_ board: Board, _ vertex: Vertex, dir: Vertex, distance: Int, cost: Int)
|
|
-> Bool
|
|
{
|
|
let position = (vertex + dir) % board.size
|
|
guard !board.occupiedSpaces.contains(position) else {
|
|
return false
|
|
}
|
|
|
|
guard let edgeDist = dist[position] else {
|
|
return false
|
|
}
|
|
|
|
let alt = distance + cost
|
|
if alt < edgeDist {
|
|
dist[position] = alt
|
|
prev[position] = (vertex, dir)
|
|
}
|
|
|
|
return true
|
|
}
|
|
}
|