# A* Pathfinding Optimization

Attention Topic was automatically imported from the old Question2Answer platform.

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
``````

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.

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

Wakatta | 2022-05-23 16:34

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!

YangTegap | 2022-05-23 19:29

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

Wakatta | 2022-05-23 20:12