"All memory allocations are in use" error when looping through a large Astar object whilst calling get_point_position() or get_point_connections().

[KnightNine]

Godot version

3.3.4

System information

Windows 10, Intel i7-8850H

Issue description

If you decide to add a large enough number of points (my test is with around 100,000) to an Astar object then try to loop through all the points and call the object's get_point_position() or get_point_connections() functions you will receive this error every loop:

ERROR: All memory pool allocations are in use.
   At: ./core/pool_vector.h:530
ERROR: set: Index p_index = -1 is out of bounds (size() = 0).
   At: ./core/pool_vector.h:494

the error printing every loop slows this down to a snail's pace considering the number of points.

Further Experimentation:

(hopefully useful though not exactly "brief")

Strangely enough get_point_position() and get_point_connections() being called on this +100,000 point Astar object doesn't seem to trigger the error at all, the issue is only present when I loop through a large enough number of the points while call these functions, like this:

        var point_data = {}
        var t = 0
	
	while t < 100000:
		var point_index = t
		var pos = astar_obj.get_point_position(point_index)
		var connections = astar_obj.get_point_connections(point_index)
		point_data[point_index] = [pos,connections]
		t+=1

But looping through a lesser number of points works fine. (i.e. while t < 100, works)

Or if i decide to print something within the loop, no error is shown:

        var point_data = {}
        var t = 0
	
	while t < 100000:
		var point_index = t
		var pos = astar_obj.get_point_position(point_index)
		var connections = astar_obj.get_point_connections(point_index)
		point_data[point_index] = [pos,connections]
		t+=1
		#this fixes the issue but also slows down the loop for the same reason as the error
		print([pos,connections])

Or if i remove the point_data dictionary's data collection from the loop, no error is shown. (i.e. removing this line: "point_data[point_index] = [pos,connections]")
(i also tried converting point_data to an array, it makes no difference)

I then tried converting the point_data to a string and collected the data by appending it to the string like so:
point_data += var2str([pos,connections])+"," , this worked surprisingly but I can't attest to how efficient repeated calls to var2str() are.

So the issue isn't even the Astar object breaking entirely due to having a large number points but rather breaking in response to being looped through and its data being collected by an array or dictionary.
I'm also not sure what other Astar object functions might be subject to this issue.

Steps to reproduce

You can use this script to reproduce the error:

func _ready():
	var astar_obj = AStar.new()
	var x = 0
	
	while x < 100000:
		astar_obj.add_point(x,Vector3(x,x,x))
		#simply connecting to the previous point
		if x>0:
			astar_obj.connect_points(x-1,x)
		x+=1
	
	var point_data = {}
	
	var points = astar_obj.get_points()
	
	var t = 0
	
	while t < 100000:
		var point_index = t
		var pos = astar_obj.get_point_position(point_index)
		var connections = astar_obj.get_point_connections(point_index)
		point_data[point_index] = [pos,connections]
		t+=1
	
	
	print(point_data)

Minimal reproduction project

No response

[Calinou]

Duplicate of #18094 and #37154 (same cause).

Try checking if this still occurs with #54263 too.

[KnightNine]

@Calinou is there a way to circumvent this issue without modifying godot? Speed isn't a necessity.

        var point_data = {}
	
	var all_points_stored = false
	var p_max_allocs_loop = 0
	while !all_points_stored:

		var i = p_max_allocs_loop * 65534
		while i < 65534 * (p_max_allocs_loop + 1) && i < points.size():

			var point_index = points[i]
			var pos = astar_obj.get_point_position(point_index)
			var connections = astar_obj.get_point_connections(point_index)
			point_data[point_index] = [pos,connections]
                        i+=1
		if i >= points.size():
			all_points_stored = true

		p_max_allocs_loop+=1

this just has the same issue. 😥

[Calinou]

is there a way to circumvent this issue without modifying godot?

You could write an A* implementation in GDScript that doesn't rely on Pool*Array for large amounts of items. That said, depending on the number of platforms you want to target, I think recompiling the editor and export templates with my PR included might be less work.