From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Sun, 18 Apr 2010 10:24:56 +0000 (+0300)
Subject: move_planet: Optimize the tree topology change detection
X-Git-Url: http://git.itanic.dy.fi/?p=sdl-planets;a=commitdiff_plain;h=ccdad280e06765f7d7262075d8ef408ce1fad1ca

move_planet: Optimize the tree topology change detection

This change avoids repositioning unnecessary the nodes within the
tree.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
---

diff --git a/planet.c b/planet.c
index 330f82a..2482dd9 100644
--- a/planet.c
+++ b/planet.c
@@ -302,6 +302,9 @@ void planet_move_iterator(struct quadtree *node, struct quadtree_iterator *it)
 {
 	struct quadtree *parent;
 
+	if (node == it->head)
+		return;
+
 	parent = quadtree_del(node, &planet_ops);
 	quadtree_add(parent, node, &planet_ops);
 }
@@ -342,17 +345,18 @@ struct planet *move_planet(struct planet *p, const double time)
 		return tree_to_planet(tree_parent);
 	}
 
-	/*
-	 * Now, search the subtree for any crossed children and move
-	 * them into correct place within the tree.
-	 */
-	it.qt_iterator.head = &p->tree;
-	it.limit[0] = p->pos;
-	it.limit[1] = new_pos;
-	it.qt_iterator.direction = planet_search_when_moving;
-	it.qt_iterator.callback = planet_move_iterator;
-	walk_quadtree(&it.qt_iterator);
-
+	if(p->tree.children) {
+		/*
+		 * Now, search the subtree for any crossed children and move
+		 * them into correct place within the tree.
+		 */
+		it.qt_iterator.head = &p->tree;
+		it.limit[0] = p->pos;
+		it.limit[1] = new_pos;
+		it.qt_iterator.direction = planet_search_when_moving;
+		it.qt_iterator.callback = planet_move_iterator;
+		walk_quadtree(&it.qt_iterator);
+	}
 	p->pos = new_pos;
 
 	return tree_to_planet(quadtree_find_parent(&p->tree));