 |
Attention | Topic was automatically imported from the old Question2Answer platform. |
 |
Asked By | Nophlock |
Hello,
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
break
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):
result.push_front(current[0])
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()
some_susicious_call()
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