quadtre: Fix nearest neighborhood search

[sdl-planets] / quadtree.c

diff --git a/quadtree.c b/quadtree.c
index 5412b8031cf2fe3007aa8a350105473931a5ca50..72973c8bba7ae35049f087057790db577719edb6 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -353,6 +353,15 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
        vector_sub(&nearest->pos, pos, &tmp);
        distance = vector_abs(&tmp);
 
+       if (tree != nearest) {
+               vector_sub(&tree->pos, pos, &tmp);
+               dist = vector_abs(&tmp);
+               if (dist < distance) {
+                       nearest = tree;
+                       distance = dist;
+               }
+       }
+
        if (!is_within(&nearest->pos, corner)) {
                if (debug)
                        printf("Discarding nearest %p "