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:
for tile_node in open:
if tile_node.location == successor.location and tile_node.f < successor.f:
for tile_node in closed:
if tile_node.location == successor.location and tile_node.f < successor.f:
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
``````
Godot version 3.4.2
in Engine

Well using a dictionary will not be fast enough for this but to be honest I would suggest you look into the A* class in godot.

Documentation here

https://docs.godotengine.org/ko/latest/classes/class_astar.html

basically you are trying to recreate a function which already exists in godot. The A* class in godot can do the pathfinding for you.

by (3,328 points)
selected

Yes fully agree with you.

You've heard it said a million times before and will say it once more. `Do not reinvent the wheel`. Build upon it.

The A* class can be extended to accommodate all you have above.

It's also obvious why it gets slower as you extend outward as aStar calculates all possible nodes

Wonderful, thank you so much for providing this info! Not only will this work much better, but I'm sure it'll help me clean up my code, haha!

Honestly, I would like to understand the algorithm better, personally, and would like to look into how I can optimize what I've got, but for now this class is definitely a better alternative. Thank you!

Understand the need for speed and you're walking down a road others have already walked before.
Depending on your end goal there are a couple of tricks you can use for optimization.

• Break the path up into smaller from-to positions
• Use obstacles and precalculate boundaries
• Use a chunk system or divide using sets

It's good to look under the hood but the time it takes to tear things apart you could have finished more projects