I'm only just learning pathfinding. I have followed the instructions at GeeksForGeeks and gotten the following code working for printing the fastest path to a given point. The issue is that it works and is instant for any close-by tiles, but for for anything starting at around 12 tiles away and further, it starts to slow down significantly and anything much further just makes Godot stop responding...
Can someone a little smarter than me help me figure out what the slow down is and how I can optimize this code?
Basically, I have a tilemap with coordinates starting at (0, 0) at the top left. On the map, when I click anywhere with my mouse, I have a function called get_tile that returns the tile coordinates for the tile clicked on. As you can see, find_path is supposed to then return the quickest path from (0, 0) to the tile clicked on. As per the Geeks for Geeks article, g is the movement cost from (0, 0) to the node, h is the movement cost from the node to the destination, and f is the sum of the two.
I'm using a dictionary to represent each tile node because I had problems with building a class.
How can I speed things up for greater distances?
extends Node2D
func _input(event):
if event.is_action_pressed("click"):
print(find_path(Vector2(0, 0), get_tile(event.position)))
func find_path(starting_pos, ending_pos):
var open = []
var closed = []
var root = {}
construct_tile_node(root, null, starting_pos, ending_pos)
open.append(root)
while open.size() > 0:
var lowest_f = open[0]
for tile_node in open:
if tile_node.f < lowest_f.f:
lowest_f = tile_node
var q = open.pop_at(open.find(lowest_f, 0))
var successors = get_tile_node_successors(q, ending_pos)
for successor in successors:
if successor.location == ending_pos:
return pull_path_coordinates(successor)
else:
var add_to_open = true
for tile_node in open:
if tile_node.location == successor.location and tile_node.f < successor.f:
add_to_open = false
if add_to_open:
for tile_node in closed:
if tile_node.location == successor.location and tile_node.f < successor.f:
add_to_open = false
if add_to_open:
open.append(successor)
closed.append(q)
return null
func construct_tile_node(dict, parent, location, ending_pos):
dict.parent = parent
dict.location = location
if parent != null:
dict.g = Game.Utils.sharp_distance(parent.location, location) + parent.g
dict.h = Game.Utils.sharp_distance(location, ending_pos)
dict.f = dict.g + dict.h
else:
dict.g = 0
dict.h = 0
dict.f = 0
func get_tile_node_successors(tile_node, ending_pos):
var temp_nodes = []
var successors = []
temp_nodes.append(tile_node.location - Vector2(1, 0))
temp_nodes.append(tile_node.location + Vector2(1, 0))
temp_nodes.append(tile_node.location - Vector2(0, 1))
temp_nodes.append(tile_node.location + Vector2(0, 1))
for tile_position in temp_nodes:
if Game.is_in_bounds(tile_position):
var new_tile_node = {}
construct_tile_node(new_tile_node, tile_node, tile_position, ending_pos)
successors.append(new_tile_node)
return successors
func pull_path_coordinates(leaf_node):
var path = []
while true:
path.append(leaf_node.location)
if leaf_node.parent == null:
break
leaf_node = leaf_node.parent
path.invert()
return path