The most obvious bug here was that the "modify" variable was
uninitialized, thus the search for crossed parents resulted always
true for the very first parent. Therefore, every time a node was
moved, the tree was rebalanced below the node.
Fixing the uninitialzed variable bug revealed other problems in the
crossed subnodes search, which was broken too. This patch modifies the
crossed subnode search a slight. It will now return true if it finds
any subnode that the movement would cross, stopping the search
instantly as soon as such node is found.
If either crossed parent or subnode is found, the node is removed and
added back to the tree in order to ensure it will be put in the
correct place.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 20 Jul 2011 12:47:55 +0000 (15:47 +0300)]
merge_planets: Remove planet from linked lists before merging
The planet needs to be remove from all linked lists before they are
being merged together. If merging takes place while both nodes are in
the same quad tree, the tree logic might collapse due to two nodes
sharing the same identical coordinates.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Tue, 19 Jul 2011 18:40:33 +0000 (21:40 +0300)]
quadtree: Optimize distance calculation
All of the distance values needed here are only used for comparing
between different distances. The actual distance itself is not used at
all. Thus, the distance calculation can be optimized by leaving out
all of the square root calculations and the end result is still the
same.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Tue, 19 Jul 2011 17:16:36 +0000 (20:16 +0300)]
vector.h: Introduce vector_abs_squared()
This function is identical to vector_abs but it returns the squared
distance instead. The advantage of this function is that the one
square root calculation canb e omitted. If the actual distance is not
important, this function is faster than the one which returns the
absolute distance.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
There is no need to go through the entire tree in case one leaf node
has a minimal change in it. As long as we have gone high enough in the
tree that there is no more any changes to the corner vectors, we can
stop walking the tree up. According to perf measurements, this
optimization reduces the tree area recalculation overhead about 50%.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Tue, 19 Jul 2011 16:32:37 +0000 (19:32 +0300)]
quadtre: Fix nearest neighborhood search
The search was missing a check whether the current node is the
nearest. Obviously without this check we never found anything else
except the initial node as the nearest node.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 13 Jul 2011 16:59:05 +0000 (19:59 +0300)]
quadtree: Reduce excess stats calculation
There is no need to explicitly recalculate the tree stats when a node
is moved from one place from the into another. As the node is added to
the tree, the stats are being recalculated automatically.
When the node is merely moved within the tree and the tree topology
doesn't change, it is sufficient to only recalculate the tree area
statistics. When some other usage is implemented for the tree
statistics, the need for more accurate statistics might change.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 13 Jul 2011 16:53:08 +0000 (19:53 +0300)]
quadtree: Unlink parent when rebalancing a subtree
There is no need to keep the one way link to the parent while the
subtree is being rebalanced. Removing this link optimizes the
rebalancing process by stopping the stats recalculation from
propagating into the parent tree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 13 Jul 2011 16:43:10 +0000 (19:43 +0300)]
quadtree: Remove redundant validity test
The sole purpose of this test wast to see whether the subtree was
removed correctly. If such condition exists, the failure will be
caught in the quadtree_del function. This test should be removed since
it causes unnecessary runtime overhead also on the non-debug build.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 13 Jul 2011 16:04:52 +0000 (19:04 +0300)]
quadtree: Add better nearest neighborhood search
This one attempts to leave majority of the tree unchecked while
searching for the nearest neighborhood, but ensures still that the
nearest node is always found.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 9 Jul 2011 09:07:34 +0000 (12:07 +0300)]
quadtree: Use tree corners from the tree itself
Now that we have the tree corner points stored in the each three node
itself, we can use those corner points when rebalancing the tree. This
allows also removing great deal of clumsy and hard to understand code.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Fri, 8 Jul 2011 09:51:36 +0000 (12:51 +0300)]
quadtree: Add subtree area into tree statistics
Two corner coordinates are stored into each quadtree nodes. These
corner coordinates indicate the area where all the subnodes of the
tree are located in.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Fri, 8 Jul 2011 10:03:21 +0000 (13:03 +0300)]
quadtree: Move quadtree_recalculate_parent_stats() out from the header
This function is not called anywhere outside of the quadtree.c, so
there is no really point in keeping it in the header. Furthermore,
this is one quite big function to keep inlined. Make it an ordinary
static function instead and let the compiler decide whether it should
be inlined or not.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Fri, 8 Jul 2011 08:49:32 +0000 (11:49 +0300)]
quadtree: Document subtree indexing
As stupid as it might sound, I forgot how the subtrees are indexed in
spatially. Therefore it might make sense to simply document even the
trivial things in the header file to avoid future confusion.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
If we move planet in the quadtree, we must call quadtree_move() in
order to keep the tree sorted. As the tree ordering might change, the
merge planet must also return the possibly new parent node of the
tree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Mon, 6 Dec 2010 09:09:36 +0000 (11:09 +0200)]
Makefile: Reduce wildcard usage
Having wildcards in the Makefile is error prone in situations where
there are unrelated files in the source tree that are not related to
the actual project. For example, if some source files have been
renamed and there are leftover .*.o.d files that still contain the old
source files. Then make will incorrectly determine that some old files
would still be needed even though they are not part of the project any
more.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 30 Oct 2010 16:57:19 +0000 (19:57 +0300)]
Move position vector from planet to quadtree
Moving the position information inside the quadtree structure will
make it eventually much easier to do varios tree operations within the
quadtree code. Most of the quadtree callback functions can be moved
inside the quadtree code. This patch implements just the first part of
the change, moving the coordinates inside quadtree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sun, 13 Jun 2010 13:04:57 +0000 (16:04 +0300)]
main.c: Skip simulation when time step is zero
When user has set the simulation speed to zero, there is no need to
run the simulation at all, as it won't be changing anyway. This makes
it possible to run excessively large simulations and occassionally
freeze the simulation. Then, for example, inspecting the tree topology
(if draw_lines variable is enabled) becomes easier without need to
worry about slow camera movement.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 24 Apr 2010 11:00:49 +0000 (14:00 +0300)]
quadtree: Try to keep the tree in better balance.
When a tree node is removed, we now attempt to add the detached
subtree in more optimized order to the new tree. This is done so that
we walk down the detached tree and add a new node to the main tree
always when the tree is one quarter'th smaller than the previous node
that was added.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 24 Apr 2010 10:59:14 +0000 (13:59 +0300)]
quadtree_add: Zero child pointers when a new node is added
Since we don't support adding an entire subtree, it is better to zero
out the child pointers to ensure there are no leftover child nodes
that might corrupt the tree integrity.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sun, 11 Apr 2010 15:05:13 +0000 (18:05 +0300)]
Introduce struct quadree_ops
Store all related function pointers (so far only the comparison) in
one structure. This will make it easier to add function pointers that
are needed in various quadtree operations.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sun, 11 Apr 2010 09:13:55 +0000 (12:13 +0300)]
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>
Timo Kokkonen [Mon, 5 Apr 2010 16:33:53 +0000 (19:33 +0300)]
main loop: Fade correctly when simulation runs fast
There was a bug that buffer fade amount was relative to the time it
took to run one simulation step, not relatively to the time interval
between two drawn frame. This patch fixes the issue.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Mon, 5 Apr 2010 12:43:43 +0000 (15:43 +0300)]
quadtree: Be more careful when deleting a node from the tree
Before attempting to move nodes back to the main tree, detach the
subtree completely from the main tree. When detaching individual nodes
from the tree, also ensure that each node has its old children
removed.
If these measures are not taken into account, loops will form in the
tree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Mon, 5 Apr 2010 09:19:26 +0000 (12:19 +0300)]
quadtree: Implement node removing
Removing a node from a quadtree is a tricky process. The node might
have multiple children which all need to be repositioned in the
remainig tree, which propably requires a recursive recreation of the
entire (sub)tree. If the given node happens to be the root node of the
tree, a new root needs to be selected for the remaining tree.
This kind of tree manipulation might have significant impact on the
balance of the tree. On the contrary, as massive tree reorganization
might be required, this is a good opportunity to rebalance the
(sub)tree. The introduced implementation does not address any
balancing issues at all.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 3 Apr 2010 10:02:44 +0000 (13:02 +0300)]
fade_buf: Optimizations
Since most of the buffer is usually black, we can skip the fading
entirely on those words that are already null. Only when the buffer
contains something to fade, individual color values are being
substracted.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Fri, 2 Apr 2010 09:59:03 +0000 (12:59 +0300)]
setup_planet: Concentrate the mass mostly in the middle of the system
This will increase the stability of the created planetar system. Most
of the central planets collapse into one large object, which will keep
most of the system more stable.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 31 Mar 2010 16:54:29 +0000 (19:54 +0300)]
main loop: Separate simulation time from true time
This allows simulation and other actions, such as camera movements, to
use different time steps. Now camera will move the same speed
regardless of the simulation time (eg. very low fps scenarios).
Furthermore, the maximum time step value is always respected and won't
be exceeded even though user adjusts the simulation speed to higher.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 31 Mar 2010 16:42:41 +0000 (19:42 +0300)]
gettime fixes
Return microseconds instead of nanoseconds. Also return value is now
delta from the first call to gettime instead of the absolute value of
the monotonic clock.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
projects / sdl-planets / log