From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Sun, 11 Apr 2010 09:13:55 +0000 (+0300)
Subject: planet.c: Optimize moving of planets within thetree
X-Git-Url: http://git.itanic.dy.fi/?p=sdl-planets;a=commitdiff_plain;h=adba740739f3a5b9ec3e97149714111532d6964e

planet.c: Optimize moving of planets within thetree

If there is no changes in the tree topology when a planet is moved,
there is no need to do any tree operations. This will decrease tree
maintenance overhead especially with large trees.

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

diff --git a/planet.c b/planet.c
index da83d3a..de0e49f 100644
--- a/planet.c
+++ b/planet.c
@@ -207,17 +207,97 @@ struct planet *merge_planets(struct planet *a, struct planet *b)
 	return a;
 }
 
+static int planet_search_when_moving(struct quadtree *node,
+				     struct quadtree_iterator *itr)
+{
+	struct planet *p = tree_to_planet(node);
+	struct planet_search_iterator *it = qt_itr_to_planet_itr(itr);
+	int direction = 0, i;
+	int up = 0, left = 0, right = 0, down = 0;
+
+	for (i = 0; i < 2; i++) {
+		if (it->limit[i].x < p->pos.x)
+			left = 1;
+		else
+			right = 1;
+		if (it->limit[i].y < p->pos.y)
+			up = 1;
+		else
+			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;
+	if ((left && right) || (up && down))
+		direction |= QUADTREE_SELF;
+
+	return direction;
+}
+
+void planet_move_iterator(struct quadtree *node, struct quadtree_iterator *it)
+{
+	struct quadtree *parent;
+
+	parent = quadtree_del(node, planet_spatial_compare);
+	quadtree_add(parent, node, planet_spatial_compare);
+}
+
 struct planet *move_planet(struct planet *p, const double time)
 {
-	struct vector tmp;
-	struct quadtree *tree_parent;
+	struct vector tmp, new_pos;
+	struct quadtree *parent, *tree_parent;
+	struct planet *pa;
+	struct planet_search_iterator it;
+
+	int modify = 0;
 
 	vector_scale(&p->speed, time, &tmp);
-	vector_add(&p->pos, &tmp, &p->pos);
+	vector_add(&p->pos, &tmp, &new_pos);
+
+	/* Check if we have crossed any of the parents */
+	parent = p->tree.parent;
+	while (parent) {
+		pa = tree_to_planet(parent);
+		if (p->pos.x < pa->pos.x && new_pos.x > pa->pos.x)
+			modify = 1;
+		if (p->pos.x > pa->pos.x && new_pos.x < pa->pos.x)
+			modify = 1;
+		if (p->pos.y < pa->pos.y && new_pos.y > pa->pos.y)
+			modify = 1;
+		if (p->pos.y > pa->pos.y && new_pos.y < pa->pos.y)
+			modify = 1;
+
+		if (!modify) {
+			parent = parent->parent;
+			continue;
+		}
+
+		tree_parent = quadtree_del(&p->tree, planet_spatial_compare);
+		p->pos = new_pos;
+		quadtree_add(tree_parent, &p->tree, planet_spatial_compare);
+		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);
+
+	p->pos = new_pos;
 
-	tree_parent = quadtree_del(&p->tree, planet_spatial_compare);
-	quadtree_add(tree_parent, &p->tree, planet_spatial_compare);
-	return tree_to_planet(tree_parent);
+	return tree_to_planet(quadtree_find_parent(&p->tree));
 }
 
 void print_planet(const struct planet *p)