AStar#connect_points(p1, p2, bidirectional) does not check if points are already connected

[alimalkhalifa]

Godot version: 3.0.3

Similar Issues that helped debug, but not specifically about this issue:
#8691
#19311

OS/device including version: Windows 10

Issue description: When adding points, AStar#connect_points() does not check if the points are already connected, and would create error conditions by making multiple connections. Also the case if bidirectional flag is on and you connect two points as such:

AStar.connect_points(p1, p2, true)
AStar.connect_points(p2, p1, true)

This causes error messages when running AStar#find_point_path(), but behaves properly in game.
The error message that is produced is:

0:00:06:0484 - Condition ' p_elem->_root ' is true.
----------
Type:Error
Description: 
Time: 0:00:06:0484
C Error: Condition ' p_elem->_root ' is true.
C Source: core/self_list.h:46
C Function: add

May be mitigated by putting this in code:

if not p2 in astar.get_point_connections(p1):
    astar.connect_points(p1, p2, false)

However, this feels like something that would be much, much faster to do in the core, and seems like something every use case of AStar will require.

Steps to reproduce: Run this script:

func reproduce_error():
	for x in range(8):
		for y in range(8):
			astar.add_point(x, y, 0)
	for x in range(8):
		for y in range(8):
			var point = astar.get_closest_point(Vector3(x, y, 0))
			var point_pos = astar.get_point_position(point)
			for dx in range(-1, 2):
				for dy in range (-1, 2):
					var point2 = astar.get_closest_point(Vector3(x + (dx*0.51), y + (dy*0.51), 0))
					var point2_pos = astar.get_point_position(p)
					if point != point2 and (point_pos - point2_pos).length() <= 1.42 and not point2 in astar.get_point_connections(point):
						astar.connect_points(point, point2, false)
	var point_path = astar.get_point_path(from_point, to_point)
	return path

Minimal reproduction project: No need for a project, as can be reproduced in above script.

[akien-mga]

Is this still reproducible in the current master branch / recent 3.1 builds?

[alimalkhalifa]

Fixed Script:

extends Node2D

func _ready():
	reproduce_error(Vector3(1,1,0), Vector3(3,3,0))

func reproduce_error(from_point, to_point):
	var astar = AStar.new()
	for x in range(8):
		for y in range(8):
			astar.add_point(x + y*8, Vector3(x,y,0) , 1)
	for x in range(8):
		for y in range(8):
			var point = astar.get_closest_point(Vector3(x, y, 0))
			var point_pos = astar.get_point_position(point)
			for dx in range(-1, 2):
				for dy in range (-1, 2):
					var point2 = astar.get_closest_point(Vector3(x + (dx*0.51), y + (dy*0.51), 0))
					var point2_pos = astar.get_point_position(point2)
					if point != point2 and (point_pos - point2_pos).length() <= 1.42 and not point2 in astar.get_point_connections(point):
						astar.connect_points(point, point2, true)
	var point_path = astar.get_point_path(astar.get_closest_point(from_point), astar.get_closest_point(to_point))
	var connections = astar.get_point_connections(astar.get_closest_point(from_point))
	print("Points connected to (1,1):")
	print(connections)
	print("Expecting 8 connections, found %d connections" % connections.size())
	print("Path from (1,1) to (3,3):")
	print(point_path)
	print("--DONE--")

Result:

Points connected to (1,1):
[1, 16, 17, 2, 10, 18, 8, 0]
Expecting 8 connections, found 8 connections
Path from (1,1) to (3,3):
[(1, 1, 0), (2, 2, 0), (3, 3, 0)]
--DONE--

Seems its resolved. Confirm @akien-mga ?

[akien-mga]

Thanks, it seems to work fine for me too.