Godot3: Performance tips for GDScript

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


today I wanted to write down a simple pathfinder in GDScript. So I implemented a simple BFS which runs in O(|V| + |E|), which basicly means that it runs pretty fast compared to AStar etc., but after I have implemented it in GDScript, I noticed that the performace is incredibly bad. For example, on a 50x50 Grid it takes from (0,0) to (23,7) 37ms which means, I can’t run it at runtime without stuttering. So I wonder if somebody has any tips to improve my Version or maybe I have a bug in my implementation? Here is my Code:

func getNeightbours(var index):
	var result 	= []
	var tile	= self.grid_system.getDataFromGrid(index)

	if(tile["area"] != null):
		return result

	var half_size = Constants.MAX_GRID_SIZE / 2.0

	if(tile["edge_w"] == null and index.x+1 <  half_size): result.append(index + Constants.EDGE_TO_VECTOR["edge_w"])
	if(tile["edge_e"] == null and index.x-1 >=-half_size): result.append(index + Constants.EDGE_TO_VECTOR["edge_e"])
	if(tile["edge_n"] == null and index.z+1 <  half_size): result.append(index + Constants.EDGE_TO_VECTOR["edge_n"])
	if(tile["edge_s"] == null and index.z-1 >=-half_size): result.append(index + Constants.EDGE_TO_VECTOR["edge_s"])

	return result

func getPathTo(var start_index, var end_index):
	var result 	= null

	if(self.grid_system.isInGridBounds(start_index) == false or self.grid_system.isInGridBounds(end_index) == false):
		return result
	var visited				= {}
	var openlist			= [[start_index, null]]
	var current_index		= null
	var neighbours			= null

	var success				= false
	var index_position		= 0
	while(index_position < openlist.size()):
		current_index = openlist[index_position]
		if(current_index[0] == end_index):
			success = true
		visited[current_index[0]]	= true
		neighbours 					= self.getNeightbours(current_index[0])

		for i in range(neighbours.size()):
			if(visited.has(neighbours[i]) == false):
				openlist.append([neighbours[i], index_position])
				visited[neighbours[i]] = true

		index_position	= index_position + 1
	if(success == true):
		result		= []
		var current = current_index
		while(current[1] != null):
			current = openlist[current[1]]

	return result

Note: I already took out the “pop_front” from the openlist-Column since it took out a lot of performance aswell and I’m using a Vector3 cause the pathfinding is on a plane in 3D.

Thanks for any help.

all i can say to you is DO NOT RECALCULATE EVERY FRAME(or try to recalculate across multiple scenes so it will not stutter and lag the game)

rustyStriker | 2018-03-07 19:29

Well that wasn’t the plan anyway, but it would still be good if there is a way to decrease the runtime of this algorithms, since this is for pathfinding and it could bring the game to stutter if multiple objects rely on it. I remember implementing this algorithm in LUA some time ago and it ran perfectly fine on a much larger grid than 50x50

Nophlock | 2018-03-07 20:14

Well, you could try timing each line, which you suspect to cause bad performance. Something like:

var start = OS.get_ticks_msec()
print(OS.get_ticks_msec() - start)

If your algorithm takes 37 milliseconds to finish, there definitely should be some lines that cause significant delay, which should yield more than 0 in timing.

KoBeWi | 2018-03-08 17:42

This is exactly what I did and it turned out, that creating a new array or make some function calls, eats up a lot of performance. After I had changed that, so that the getNeightbours function was basicly inlined and used 2 arrays instead of one, I got down to 14ms. This is quite an improvement compared with what I started, but still not usable by any means. So I decided to give the builtins AStar class a go and now it runs at a non measureable millisecond-time which is just crazy if you think about the fact, that AStar runs in O(n*log(n)) when implemented with a heap, which I just assume for Godots implementation.
Anyway I hope that GDScript gets some performance improvements in the near future.

Nophlock | 2018-03-08 19:24