From 187ba4c5a884aaecd97febcdfaaa76466820be07 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?R=C3=A9mi=20Verschelde?= Date: Tue, 9 Jun 2020 10:26:21 +0200 Subject: AStar: Make get_closest_point() deterministic for equidistant points Closes godotengine/godot-docs#3667. Supersedes #39405. --- core/math/a_star.cpp | 14 +++++++++----- doc/classes/AStar.xml | 3 ++- doc/classes/AStar2D.xml | 3 ++- 3 files changed, 13 insertions(+), 7 deletions(-) diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp index 580a7cf7bb..30f712b2c3 100644 --- a/core/math/a_star.cpp +++ b/core/math/a_star.cpp @@ -280,10 +280,16 @@ int AStar::get_closest_point(const Vector3 &p_point, bool p_include_disabled) co continue; // Disabled points should not be considered. } + // Keep the closest point's ID, and in case of multiple closest IDs, + // the smallest one (makes it deterministic). real_t d = p_point.distance_squared_to((*it.value)->pos); - if (closest_id < 0 || d < closest_dist) { + int id = *(it.key); + if (d <= closest_dist) { + if (d == closest_dist && id > closest_id) { // Keep lowest ID. + continue; + } closest_dist = d; - closest_id = *(it.key); + closest_id = id; } } @@ -291,7 +297,6 @@ int AStar::get_closest_point(const Vector3 &p_point, bool p_include_disabled) co } Vector3 AStar::get_closest_position_in_segment(const Vector3 &p_point) const { - bool found = false; real_t closest_dist = 1e20; Vector3 closest_point; @@ -311,10 +316,9 @@ Vector3 AStar::get_closest_position_in_segment(const Vector3 &p_point) const { Vector3 p = Geometry3D::get_closest_point_to_segment(p_point, segment); real_t d = p_point.distance_squared_to(p); - if (!found || d < closest_dist) { + if (d < closest_dist) { closest_point = p; closest_dist = d; - found = true; } } diff --git a/doc/classes/AStar.xml b/doc/classes/AStar.xml index e930abba87..2695e86f47 100644 --- a/doc/classes/AStar.xml +++ b/doc/classes/AStar.xml @@ -131,7 +131,8 @@ - Returns the ID of the closest point to [code]to_position[/code], optionally taking disabled points into account. Returns -1 if there are no points in the points pool. + Returns the ID of the closest point to [code]to_position[/code], optionally taking disabled points into account. Returns [code]-1[/code] if there are no points in the points pool. + [b]Note:[/b] If several points are the closest to [code]to_position[/code], the one with the smallest ID will be returned, ensuring a deterministic result. diff --git a/doc/classes/AStar2D.xml b/doc/classes/AStar2D.xml index 16fa05041e..622d336ef6 100644 --- a/doc/classes/AStar2D.xml +++ b/doc/classes/AStar2D.xml @@ -114,7 +114,8 @@ - Returns the ID of the closest point to [code]to_position[/code], optionally taking disabled points into account. Returns -1 if there are no points in the points pool. + Returns the ID of the closest point to [code]to_position[/code], optionally taking disabled points into account. Returns [code]-1[/code] if there are no points in the points pool. + [b]Note:[/b] If several points are the closest to [code]to_position[/code], the one with the smallest ID will be returned, ensuring a deterministic result. -- cgit v1.2.3