-
Notifications
You must be signed in to change notification settings - Fork 1
/
astar.gd
185 lines (150 loc) · 6.53 KB
/
astar.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
extends TileMap
const BASE_LINE_WIDTH = 3.0
const DRAW_COLOR = Color.white
# The Tilemap node doesn't have clear bounds so we're defining the map's limits here.
export(Vector2) var map_size = Vector2.ONE * 16
# The path start and end variables use setter methods.
# You can find them at the bottom of the script.
var path_start_position = Vector2() setget _set_path_start_position
var path_end_position = Vector2() setget _set_path_end_position
var _point_path = []
# You can only create an AStar node from code, not from the Scene tab.
onready var astar_node = AStar.new()
# get_used_cells_by_id is a method from the TileMap node.
# Here the id 0 corresponds to the grey tile, the obstacles.
onready var obstacles = get_used_cells_by_id(0)
onready var _half_cell_size = cell_size / 2
func _ready():
var walkable_cells_list = astar_add_walkable_cells(obstacles)
astar_connect_walkable_cells(walkable_cells_list)
func _draw():
if not _point_path:
return
var point_start = _point_path[0]
var point_end = _point_path[len(_point_path) - 1]
set_cell(point_start.x, point_start.y, 1)
set_cell(point_end.x, point_end.y, 2)
var last_point = map_to_world(Vector2(point_start.x, point_start.y)) + _half_cell_size
for index in range(1, len(_point_path)):
var current_point = map_to_world(Vector2(_point_path[index].x, _point_path[index].y)) + _half_cell_size
draw_line(last_point, current_point, DRAW_COLOR, BASE_LINE_WIDTH, true)
draw_circle(current_point, BASE_LINE_WIDTH * 2.0, DRAW_COLOR)
last_point = current_point
# Click and Shift force the start and end position of the path to update,
# and the node to redraw everything.
#func _input(event):
# if event.is_action_pressed('click') and Input.is_key_pressed(KEY_SHIFT):
# # To call the setter method from this script we have to use the explicit self.
# self.path_start_position = world_to_map(get_global_mouse_position())
# elif event.is_action_pressed('click'):
# self.path_end_position = world_to_map(get_global_mouse_position())
# Loops through all cells within the map's bounds and
# adds all points to the astar_node, except the obstacles.
func astar_add_walkable_cells(obstacle_list = []):
var points_array = []
for y in range(map_size.y):
for x in range(map_size.x):
var point = Vector2(x, y)
if point in obstacle_list:
continue
points_array.append(point)
# The AStar class references points with indices.
# Using a function to calculate the index from a point's coordinates
# ensures we always get the same index with the same input point.
var point_index = calculate_point_index(point)
# AStar works for both 2d and 3d, so we have to convert the point
# coordinates from and to Vector3s.
astar_node.add_point(point_index, Vector3(point.x, point.y, 0.0))
return points_array
# Once you added all points to the AStar node, you've got to connect them.
# The points don't have to be on a grid: you can use this class
# to create walkable graphs however you'd like.
# It's a little harder to code at first, but works for 2d, 3d,
# orthogonal grids, hex grids, tower defense games...
func astar_connect_walkable_cells(points_array):
for point in points_array:
var point_index = calculate_point_index(point)
# For every cell in the map, we check the one to the top, right.
# left and bottom of it. If it's in the map and not an obstalce.
# We connect the current point with it.
var points_relative = PoolVector2Array([
point + Vector2.RIGHT,
point + Vector2.LEFT,
point + Vector2.DOWN,
point + Vector2.UP,
])
for point_relative in points_relative:
var point_relative_index = calculate_point_index(point_relative)
if is_outside_map_bounds(point_relative):
continue
if not astar_node.has_point(point_relative_index):
continue
# Note the 3rd argument. It tells the astar_node that we want the
# connection to be bilateral: from point A to B and B to A.
# If you set this value to false, it becomes a one-way path.
# As we loop through all points we can set it to false.
astar_node.connect_points(point_index, point_relative_index, false)
# This is a variation of the method above.
# It connects cells horizontally, vertically AND diagonally.
func astar_connect_walkable_cells_diagonal(points_array):
for point in points_array:
var point_index = calculate_point_index(point)
for local_y in range(3):
for local_x in range(3):
var point_relative = Vector2(point.x + local_x - 1, point.y + local_y - 1)
var point_relative_index = calculate_point_index(point_relative)
if point_relative == point or is_outside_map_bounds(point_relative):
continue
if not astar_node.has_point(point_relative_index):
continue
astar_node.connect_points(point_index, point_relative_index, true)
func calculate_point_index(point):
return point.x + map_size.x * point.y
func clear_previous_path_drawing():
if not _point_path:
return
var point_start = _point_path[0]
var point_end = _point_path[len(_point_path) - 1]
set_cell(point_start.x, point_start.y, -1)
set_cell(point_end.x, point_end.y, -1)
func is_outside_map_bounds(point):
return point.x < 0 or point.y < 0 or point.x >= map_size.x or point.y >= map_size.y
func get_astar_path(world_start, world_end):
self.path_start_position = world_to_map(world_start)
self.path_end_position = world_to_map(world_end)
_recalculate_path()
var path_world = []
for point in _point_path:
var point_world = map_to_world(Vector2(point.x, point.y)) + _half_cell_size
path_world.append(point_world)
return path_world
func _recalculate_path():
clear_previous_path_drawing()
var start_point_index = calculate_point_index(path_start_position)
var end_point_index = calculate_point_index(path_end_position)
# This method gives us an array of points. Note you need the start and
# end points' indices as input.
_point_path = astar_node.get_point_path(start_point_index, end_point_index)
# Redraw the lines and circles from the start to the end point.
update()
# Setters for the start and end path values.
func _set_path_start_position(value):
if value in obstacles:
return
if is_outside_map_bounds(value):
return
set_cell(path_start_position.x, path_start_position.y, -1)
set_cell(value.x, value.y, 1)
path_start_position = value
if path_end_position and path_end_position != path_start_position:
_recalculate_path()
func _set_path_end_position(value):
if value in obstacles:
return
if is_outside_map_bounds(value):
return
set_cell(path_start_position.x, path_start_position.y, -1)
set_cell(value.x, value.y, 2)
path_end_position = value
if path_start_position != value:
_recalculate_path()