/
MovementCalculator.gd
415 lines (351 loc) · 15.4 KB
/
MovementCalculator.gd
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
extends Reference
# Movement Calculator for units
# Calculates which tiles you can move, attack and heal
# Calculates using A* which is the shortest path to the target cell
class_name MovementCalculator
# Reference
var battlefield
# BFS
var queue = []
# Constructor
func _init(battlefield):
self.battlefield = battlefield
# Calculate Movement Blue Squares
func calculatePossibleMoves(Unit, AllTiles) -> void:
# Clear the allowed tiles before calculation
Unit.UnitMovementStats.allowedMovement.clear()
Unit.UnitMovementStats.allowedAttackRange.clear()
Unit.UnitMovementStats.allowedHealRange.clear()
# Reset Grid values
reset_grid_values()
reset_parent_tile_values()
# Process Move Tiles
processTile(Unit.UnitMovementStats.currentTile, Unit.UnitMovementStats, Unit.UnitMovementStats.movementSteps, Unit)
# Process Attack tiles -> Find a better way of optimizing this
processAttackTile(Unit)
# Process Heal Tiles -> Find better way of optimizaing this
processHealingTile(Unit)
# Turn on the tiles
turn_on_all_tiles(Unit, AllTiles)
# Turn on tiles for enemies only
func highlight_enemy_movement_range(Unit, AllTiles) -> void:
# Calculate the move
calculatePossibleMoves(Unit, AllTiles)
# Turn off the tiles
turn_off_all_tiles(Unit, AllTiles)
# Light all the blue tiles -> Change this later to check if the unit has a healing ability and turn on green tiles
for blueTile in Unit.UnitMovementStats.allowedMovement:
AllTiles[blueTile.getPosition().x][blueTile.getPosition().y].get_node("MovementRangeRect").turnOn("Purple")
for redTile in Unit.UnitMovementStats.allowedAttackRange:
AllTiles[redTile.getPosition().x][redTile.getPosition().y].get_node("MovementRangeRect").turnOn("Purple")
for greenTile in Unit.UnitMovementStats.allowedHealRange:
AllTiles[greenTile.getPosition().x][greenTile.getPosition().y].get_node("MovementRangeRect").turnOn("Purple")
# Process all the tiles to find what is movable to
func processTile(initialTile, unit_movement, moveSteps, unit):
# Set parent tile
initialTile.parentTile = initialTile
# Add first tile to the queue
queue.append([moveSteps, initialTile])
# Process queue until it is empty
while !queue.empty():
# Pop the first tile
var tile_to_check = queue.pop_front()
# Add tile to allowed movement and set visited status to true
unit_movement.allowedMovement.append(tile_to_check[1])
# tile_to_check[1].isVisited = true
# Get the next cost
for adjTile in tile_to_check[1].adjCells:
var next_cost = tile_to_check[0] - adjTile.movementCost - getPenaltyCost(unit, unit_movement, adjTile)
if next_cost >= 0 && !adjTile.isVisited:
# Is the tile occupied? -> Tile is not occupied, process right away
if adjTile.occupyingUnit == null:
adjTile.parentTile = tile_to_check[1]
adjTile.isVisited = true
queue.append([next_cost, adjTile])
else:
# Tile is occupied -> Check if it's an ally (or enemy for enemy)
if adjTile.occupyingUnit.UnitMovementStats.is_ally == unit_movement.is_ally:
adjTile.parentTile = tile_to_check[1]
adjTile.isVisited = true
queue.append([next_cost, adjTile])
# Process Attackable Range
func processAttackTile(Unit):
# Reset values
reset_grid_values()
var new_queue = []
# Get tiles
var moveSteps = (Unit.UnitInventory.MAX_ATTACK_RANGE - 1)
if moveSteps == -1:
return
for blueTile in Unit.UnitMovementStats.allowedMovement:
for adjTile in blueTile.adjCells:
if !Unit.UnitMovementStats.allowedMovement.has(adjTile):
new_queue.append([moveSteps, adjTile])
# BFS Search for attack tiles
while !new_queue.empty():
var check_tile = new_queue.pop_front()
if !Unit.UnitMovementStats.allowedAttackRange.has(check_tile[1]):
Unit.UnitMovementStats.allowedAttackRange.append(check_tile[1])
check_tile[1].isVisited = true
# Get the next cost
for adjTile in check_tile[1].adjCells:
var next_cost = check_tile[0] - 1
# Do not process tiles that we have already seen or if we cannot get there or if the movement already has this
if next_cost >= 0 && !adjTile.isVisited && !Unit.UnitMovementStats.allowedMovement.has(adjTile):
new_queue.append([next_cost, adjTile])
# Process Healing Range
func processHealingTile(Unit):
# Reset values
reset_grid_values()
var new_queue = []
# Get tiles
var moveSteps = (Unit.UnitInventory.MAX_HEAL_RANGE - 1)
if moveSteps == -1:
return
for blueTile in Unit.UnitMovementStats.allowedMovement:
for adjTile in blueTile.adjCells:
if !Unit.UnitMovementStats.allowedMovement.has(adjTile):
new_queue.append([moveSteps, adjTile])
# BFS Search for attack tiles
while !new_queue.empty():
var check_tile = new_queue.pop_front()
if !Unit.UnitMovementStats.allowedAttackRange.has(check_tile[1]) && !Unit.UnitMovementStats.allowedHealRange.has(check_tile[1]):
Unit.UnitMovementStats.allowedHealRange.append(check_tile[1])
check_tile[1].isVisited = true
# Get the next cost
for adjTile in check_tile[1].adjCells:
var next_cost = check_tile[0] - 1
# Do not process tiles that we have already seen or if we cannot get there or if the movement already has this
if next_cost >= 0 && !adjTile.isVisited && !Unit.UnitMovementStats.allowedMovement.has(adjTile):
new_queue.append([next_cost, adjTile])
# Returns the penalty cost associated with the unit's class for moving across different tiles
func getPenaltyCost(Unit, Unit_Movement, cell) -> int:
# Flying units can get through
if Unit.UnitStats.pegasus:
if cell.movementCost < 1000:
return (cell.movementCost - 1) * -1
else:
return 0
# Everyone else
var cell_type = cell.tileName
match cell_type:
"Plain", "Road", "Bridge", "Throne":
return Unit_Movement.defaultPenalty
"Mountain", "Cliff":
return Unit_Movement.mountainPenalty
"Hill":
return Unit_Movement.hillPenalty
"Forest":
return Unit_Movement.forestPenalty
"Fortress":
return Unit_Movement.fortressPenalty
"Village":
return Unit_Movement.buildingPenalty
"River":
return Unit_Movement.riverPenalty
"Ruins":
return Unit_Movement.ruinsPenalty
"Sea":
return Unit_Movement.seaPenalty
_:
# fall through
return 0
# Turn on all tiles
func turn_on_all_tiles(Unit, AllTiles) -> void:
# Light all the blue tiles -> Change this later to check if the unit has a healing ability and turn on green tiles
for blueTile in Unit.UnitMovementStats.allowedMovement:
AllTiles[blueTile.getPosition().x][blueTile.getPosition().y].get_node("MovementRangeRect").turnOn("Blue")
for redTile in Unit.UnitMovementStats.allowedAttackRange:
AllTiles[redTile.getPosition().x][redTile.getPosition().y].get_node("MovementRangeRect").turnOn("Red")
for greenTile in Unit.UnitMovementStats.allowedHealRange:
AllTiles[greenTile.getPosition().x][greenTile.getPosition().y].get_node("MovementRangeRect").turnOn("Green")
# Turn off all tiles
func turn_off_all_tiles(Unit, AllTiles) -> void:
# Turn off blue
for blueTile in Unit.UnitMovementStats.allowedMovement:
AllTiles[blueTile.getPosition().x][blueTile.getPosition().y].get_node("MovementRangeRect").turnOff("Blue")
# Turn off Red -> TO DO
for redTile in Unit.UnitMovementStats.allowedAttackRange:
AllTiles[redTile.getPosition().x][redTile.getPosition().y].get_node("MovementRangeRect").turnOff("Red")
# Turn off Green -> TO DO
for greenTile in Unit.UnitMovementStats.allowedHealRange:
AllTiles[greenTile.getPosition().x][greenTile.getPosition().y].get_node("MovementRangeRect").turnOff("Green")
# Turn off only purple
func turn_off_purple(Unit, AllTiles) -> void:
# Turn off blue
for blueTile in Unit.UnitMovementStats.allowedMovement:
AllTiles[blueTile.getPosition().x][blueTile.getPosition().y].get_node("MovementRangeRect").turnOff("Purple")
# Turn off Red -> TO DO
for redTile in Unit.UnitMovementStats.allowedAttackRange:
AllTiles[redTile.getPosition().x][redTile.getPosition().y].get_node("MovementRangeRect").turnOff("Purple")
# Turn off Green -> TO DO
for greenTile in Unit.UnitMovementStats.allowedHealRange:
AllTiles[greenTile.getPosition().x][greenTile.getPosition().y].get_node("MovementRangeRect").turnOff("Purple")
# Find the shortest path to the target destination | No A* algorithm | Player version only
func get_path_to_destination(Unit, target_destination, AllTiles):
# Create the pathfinding queue directly?
create_pathfinding_queue(target_destination, Unit)
## Find the shortest path to the target destination | This uses the A* algorithm | Player Version
#func get_path_to_destination(Unit, target_destination, AllTiles):
# # Clear Tile statistics first
# for tile_array in AllTiles:
# for tile in tile_array:
# tile.parentTile = null
# tile.hCost = 0
# tile.gCost = 0
# tile.fCost = 0
#
# # Clear Queue for the unit
# Unit.UnitMovementStats.movement_queue.clear()
#
# # Hashset and Priority Queue to hold all the tiles needed
# var closed_list = HashSet.new()
# var open_list = PriorityQueue.new()
#
# # Get Current Tile
# var current_tile = Unit.UnitMovementStats.currentTile
#
# # Add the current cell we are starting on to this list
# open_list.add_first(Unit.UnitMovementStats.currentTile)
#
# # Process Tiles until the open list is empty
# while !open_list.is_empty():
# # Remove the first tile in the list and add it to the closed list
# current_tile = open_list.pop_front()
# closed_list.add(current_tile)
#
# # Check if we have reached our destination
# if current_tile == target_destination:
# break
#
# # Process Adj Tiles
# for adjCell in current_tile.adjCells:
# # Do not process unwalkable tiles or we can't go there
# if adjCell.movementCost >= 101 || closed_list.contains(adjCell) || !Unit.UnitMovementStats.allowedMovement.has(adjCell):
# continue
#
# # Calculate Heuristic costs
# var movement_cost_to_neighbor = current_tile.gCost + adjCell.movementCost + getPenaltyCost(Unit, Unit.UnitMovementStats, adjCell)
# if movement_cost_to_neighbor < adjCell.gCost || !open_list.contains(adjCell):
# adjCell.gCost = movement_cost_to_neighbor
# adjCell.hCost = calculate_hCost(adjCell, target_destination, Unit, AllTiles)
# adjCell.parentTile = current_tile
#
# # Add to the open List
# if !open_list.contains(adjCell):
# open_list.add_first(adjCell)
#
# # Create the Pathfinding Queue
# create_pathfinding_queue(target_destination, Unit)
# Find the shortest path to the target destination | AI Version | Use this for cinematic purposes too
func get_path_to_destination_AI(Unit, target_destination, AllTiles):
# Clear Tile statistics first
for tile_array in AllTiles:
for tile in tile_array:
# tile.parentTile = null
tile.hCost = 0
tile.gCost = 0
# Clear Queue for the unit
Unit.UnitMovementStats.movement_queue.clear()
# Hashset and Priority Queue to hold all the tiles needed
var closed_list = HashSet.new()
var open_list = PriorityQueue.new()
# Get Current Tile
var current_tile = Unit.UnitMovementStats.currentTile
# Add the current cell we are starting on to this list
open_list.add_first(Unit.UnitMovementStats.currentTile)
# Process Tiles until the open list is empty
while !open_list.is_empty():
# Remove the first tile in the list and add it to the closed list
current_tile = open_list.pop_front()
closed_list.add(current_tile)
# Check if we have reached our destination
if current_tile == target_destination:
break
# Process Adj Tiles
for adjCell in current_tile.adjCells:
# Do not process unwalkable tiles or we can't go there
if Unit.has_node("AI"):
if adjCell.movementCost >= 100 || closed_list.contains(adjCell):
continue
else:
if adjCell.movementCost >= 101 || closed_list.contains(adjCell):
continue
# Calculate Heuristic costs
var movement_cost_to_neighbor = current_tile.gCost + adjCell.movementCost + getPenaltyCost(Unit, Unit.UnitMovementStats, adjCell)
if movement_cost_to_neighbor < adjCell.gCost || !open_list.contains(adjCell):
adjCell.gCost = movement_cost_to_neighbor
adjCell.hCost = calculate_hCost(adjCell, target_destination, Unit, AllTiles)
adjCell.parentTile = current_tile
# Add to the open List
if !open_list.contains(adjCell):
open_list.add_first(adjCell)
# Create the Pathfinding Queue
create_pathfinding_queue(target_destination, Unit)
# Calculates the H Costs based on how far you need to go
func calculate_hCost(initial_tile, destination_tile, unit, all_tiles) -> int:
var MovementStats = unit.UnitMovementStats
var starting_NodeX = initial_tile.getPosition().x
var starting_NodeY = initial_tile.getPosition().y
var total_vertical_cost = 0
var total_horizontal_cost = 0
# Caculate all the tiles using manhattan distance how far you need to go to get to the target destination
# North South
var vertical_movement
if initial_tile.getPosition().y - destination_tile.getPosition().y < 0:
vertical_movement = -1
for i in range(destination_tile.getPosition().y, initial_tile.getPosition().y, vertical_movement):
total_vertical_cost += all_tiles[starting_NodeX][i].movementCost + getPenaltyCost(unit, MovementStats, all_tiles[starting_NodeX][i])
elif initial_tile.getPosition().y - destination_tile.getPosition().y > 0:
vertical_movement = 1
for i in range(initial_tile.getPosition().y, destination_tile.getPosition().y, vertical_movement):
total_vertical_cost += all_tiles[starting_NodeX][i].movementCost + getPenaltyCost(unit, MovementStats, all_tiles[starting_NodeX][i])
elif initial_tile.getPosition().y - destination_tile.getPosition().y == 0:
total_vertical_cost = 0
# West East
var horizontal_movement
if initial_tile.getPosition().x - destination_tile.getPosition().x < 0:
horizontal_movement = -1
for i in range(destination_tile.getPosition().x, initial_tile.getPosition().x, horizontal_movement):
total_horizontal_cost += all_tiles[i][starting_NodeY].movementCost + getPenaltyCost(unit, MovementStats, all_tiles[i][starting_NodeY])
elif initial_tile.getPosition().x - destination_tile.getPosition().x > 0:
horizontal_movement = 1
for i in range(initial_tile.getPosition().x, destination_tile.getPosition().x, horizontal_movement):
total_horizontal_cost += all_tiles[i][starting_NodeY].movementCost + getPenaltyCost(unit, MovementStats, all_tiles[i][starting_NodeY])
elif initial_tile.getPosition().x - destination_tile.getPosition().x == 0:
total_horizontal_cost = 0
return total_horizontal_cost + total_vertical_cost
# Create the pathfinding queue needed for the unit to move there
func create_pathfinding_queue(destination_cell, unit) -> void:
# Get the Queue
var MovementStatsQueue = unit.UnitMovementStats.movement_queue
# Set next cell
var next_cell = destination_cell
var starting_cell = unit.UnitMovementStats.currentTile
# Work backwards until we find the destination cell
while next_cell != starting_cell:
MovementStatsQueue.push_front(next_cell)
next_cell = next_cell.parentTile
# Check if move is valid
func check_if_move_is_valid(destination_cell, unit) -> bool:
# Cell is not part of the allowed moveset
if !unit.UnitMovementStats.allowedMovement.has(destination_cell):
return false
# Is the cell not occupied by yourself?
if destination_cell.occupyingUnit != null && destination_cell.occupyingUnit != unit:
return false
return true
# Reset grid values
func reset_grid_values():
# Reset the Grid Values
for tile_array in battlefield.grid:
for tile in tile_array:
#tile.parentTile = null
tile.isVisited = false
# Reset Parent tiles
func reset_parent_tile_values():
# Reset the Grid Values
for tile_array in battlefield.grid:
for tile in tile_array:
tile.parentTile = null
#tile.isVisited = false