A* Pathfinding Optimization

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By YangTegap

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)
	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)
				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:
	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
		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)
	return successors

func pull_path_coordinates(leaf_node):
	var path = []
	while true:
		if leaf_node.parent == null:
		leaf_node = leaf_node.parent
	return path
:bust_in_silhouette: Reply From: Gluon

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


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