-
Notifications
You must be signed in to change notification settings - Fork 0
/
pathfinding.ms
139 lines (114 loc) · 2.88 KB
/
pathfinding.ms
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
import "coreUtils"
import "reverseList"
ensureImport "Point"
isEqual = function(point, goal)
return (point.x == goal.x and point.y == goal.y)
end function
findPointInList = function(arr, point)
if not point isa Point then
print "FindPoint invalid argument"
return null
end if
if not arr isa list then
print "FindPoint invalid argument"
return null
end if
for el in arr
if isEqual(el, point) then
return el
end if
end for
return null
end function
isPassable = function(x, y)
tile = farm.tile(x, y)
if tile == null then
return true
end if
//if animal or player is on path add tile and wait for it to move
bool = (tile.passable == 1 or
tile.type == "Character" or
tile.type == "BotObject") and
tile.type != "Building"
return bool
end function
findMinFIndex = function(array)
//search in reverse!!!
index = array.len - 1
for i in range(array.len - 2, 0)
if array[i].f < array[index].f then
index = i
end if
end for
return index
end function
globals.findPath = function(origin, goal)
if not (origin isa Point and goal isa Point) then
print "Argument must be Point"
return []
end if
if goal.x < 0 or goal.x > farm.width then
print "Invalid goal x"
return []
end if
if goal.y < 0 or goal.y > farm.height then
print "Invalid goal y"
return []
end if
if not isPassable(goal.x, goal.y) then
print "can't reach goal"
return []
end if
if isEqual(origin, goal) then
return []
end if
closedList = []
openList = [origin]
while openList
yield
index = findMinFIndex(openList)
currentPoint = openList[index]
openList.remove(index)
closedList.push(currentPoint)
neighbours = currentPoint.getNeighbours
for neighbour in neighbours
if not isPassable(neighbour.x, neighbour.y) then
closedList.push(neighbour)
continue
end if
if findPointInList(closedList, neighbour) != null then
continue
end if
neighbour.calculateF(currentPoint, goal)
element = findPointInList(openList, neighbour)
if element != null then
if element.f < neighbour.f then
continue
end if
end if
neighbour.parent = currentPoint
if isEqual(neighbour, goal) then
return createPath(origin, neighbour)
end if
openList.push(neighbour)
end for
end while
return []
end function
createPath = function(origin, goal)
if not (origin isa Point and goal isa Point) then
print "createPath invalid argument"
return []
end if
path = []
currentPoint = goal
while not isEqual(currentPoint, origin)
path.push(currentPoint)
currentPoint = currentPoint.parent
if currentPoint == null then
return []
end if
end while
path.push(origin)
return path.reverse
end function