Some different approach..

diff --git a/quadtree.c b/quadtree.c
index 4c183c803c9f30684dbba4e02cc439d0bebe2a4c..4b0a0e3354eb3d8cd67d5a106934f0f31af68c8b 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -327,14 +327,42 @@ static int is_within(struct vector *pos, struct vector *corner)
        return 0;
 }
 
+static int quadrants_to_search(struct quadtree *node, struct vector *corner)
+{
+       int direction = 0, i;
+       int up = 0, left = 0, right = 0, down = 0;
+
+       for (i = 0; i < 2; i++) {
+               if (corner[i].x <= node->pos.x)
+                       left = 1;
+               else if (corner[i].x >= node->pos.x)
+                       right = 1;
+               if (corner[i].y <= node->pos.y)
+                       up = 1;
+               else if (corner[i].y >= node->pos.y)
+                       down = 1;
+       }
+
+       if (left || up)
+               direction |= QUADTREE_UPLEFT;
+       if (right || up)
+               direction |= QUADTREE_UPRIGHT;
+       if (left || down)
+               direction |= QUADTREE_DOWNLEFT;
+       if (right || down)
+               direction |= QUADTREE_DOWNRIGHT;
+
+       return direction;
+}
+
 static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
                                        struct vector *pos,
                                        struct vector *corner)
 {
        struct vector tmp;
-       struct quadtree *parent = tree;
+       struct quadtree *nearest = tree, *node;
        double distance, dist;
-       int ret;
+       int ret, i, directions;
 
        if (!is_within(pos, corner)) {
                if (debug) {
@@ -351,42 +379,49 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
        vector_sub(pos, &tree->pos, &tmp);
        distance = vector_abs(&tmp);
 
-       printf("Starting from parent %p (%f %f), target (%f %f)\n", tree,
-               tree->pos.x, tree->pos.y, pos->x, pos->y);
+       directions = quadrants_to_search(tree, corner);
 
-       while (1) {
+       printf("Starting from parent %p (%f %f), target (%f %f), %x\n", tree,
+               tree->pos.x, tree->pos.y, pos->x, pos->y, directions);
 
-               ret = quadtree_compare_coord(&tree->pos, pos);
+       for (i = 0; i < 4; i++) {
+               if (!tree->child[i])
+                       continue;
 
-               printf("Compared: %d\n", ret);
+/*
+               if (!(directions & (1 << i)))
+                       continue;
+*/
+               node = quadtree_find_nearest(tree->child[i], pos, corner);
 
-               if (tree->child[ret]) {
-                       tree = tree->child[ret];
+               if (!node)
                        continue;
+
+               vector_sub(pos, &node->pos, &tmp);
+               dist = vector_abs(&tmp);
+
+               printf("%p: (%f %f)dist: %f, distance: %f\n",
+                       node, node->pos.x, node->pos.y,
+                       dist, distance);
+               if (dist < distance) {
+                       nearest = node;
+                       distance = dist;
+
+                       printf("Choosing nearest\n");
                }
-               printf("break\n");
-               break;
        }
 
-       if (!is_within(&tree->pos, corner)) {
+       if (!is_within(&nearest->pos, corner)) {
                if (debug)
                        printf("Node %p (%f %f) is not within "
                                "search window (%f %f) (%f %f)\n",
-                               tree, tree->pos.x, tree->pos.y,
+                               nearest, nearest->pos.x, nearest->pos.y,
                                corner[0].x, corner[0].y,
                                corner[1].x, corner[1].y);
                return NULL;
        }
 
-       vector_sub(pos, &tree->pos, &tmp);
-       dist = vector_abs(&tmp);
-
-       printf("dist: %f, distance: %f\n", dist, distance);
-       if (dist < distance)
-               return tree;
-
-       printf("Return parent\n");
-       return parent;
+       return nearest;
 }
 
 static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree,
@@ -405,7 +440,7 @@ static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree,
                return nearest;
 
        if (debug)
-               printf("Avoiding parent node %p\n", tree);
+               printf("Avoiding parent or NULL node %p\n", nearest);
 
        /*
         * oops, we don't want to pick the parent node, let's choose