-
Notifications
You must be signed in to change notification settings - Fork 0
/
finder.js
109 lines (87 loc) · 3.26 KB
/
finder.js
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
'use strict'
var Queue = require('js-priority-queue')
module.exports = Finder
function Finder() {
// methods the user must overwrite:
this.nodeToPrimitive = function (a) { throw 'Overwrite this method!' }
this.getNeighbors = function (node) { throw 'Overwrite this method!' }
this.getMovementCost = function (a, b) { throw 'Overwrite this method!' }
this.getHeuristic = function (a, b) { throw 'Overwrite this method!' }
// core functionality
this.findPath = function (start, goal) {
var pstart = this.nodeToPrimitive(start)
var pgoal = this.nodeToPrimitive(goal)
// init data structures, open start node
var open = new Queue({ comparator: compareNodes })
var visited = {}
var startNode = new Node(start, 0, 0, true, false)
open.queue(startNode)
visited[pstart] = startNode
while (open.length > 0) {
// get open node with lowest f
var curr = open.dequeue()
// node might have been removed from OPEN while it was queued
while (curr && !curr.open) curr = open.dequeue()
// exit conditions
if (!curr || !curr.open) break
var pcurr = this.nodeToPrimitive(curr.data)
if (pcurr === pgoal) break
curr.open = false
curr.closed = true
// iterate neighbors, visit or refresh if current cost is lower than previous
var nabs = this.getNeighbors(curr.data)
for (var i = 0; i < nabs.length; i++) {
var ndata = nabs[i]
var move = this.getMovementCost(curr.data, ndata)
if (move < 0) continue // impassable barrier
var cost = curr.g + move
var pneighbor = this.nodeToPrimitive(ndata)
var nnode = visited[pneighbor]
if (nnode) {
if (cost < nnode.g) {
nnode.open = true
nnode.closed = false
nnode.g = cost
nnode.f = cost + this.getHeuristic(ndata, goal)
nnode.parent = curr
open.queue(nnode)
}
} else {
var h = this.getHeuristic(ndata, goal)
var f = cost + h
var newnode = new Node(ndata, f, cost, true, false, curr)
visited[pneighbor] = newnode
open.queue(newnode)
}
}
}
// build reversed path from goal to start
var path = []
var pnode = visited[pgoal]
if (pnode && pnode.parent) {
path.push(pnode.data)
while (pnode.parent) {
pnode = pnode.parent
path.push(pnode.data)
}
}
// reverse it, clean up and exit
var rpath = []
while (path.length) rpath.push(path.pop())
open.clear()
open = null
visited = null
return rpath
}
}
function Node(data, f, g, open, closed, parent) {
this.f = +f
this.g = +g
this.open = !!open
this.closed = !!closed
this.parent = parent || null
this.data = data
}
function compareNodes(a, b) {
return a.f - b.f
}