Merge branch 'master' into dirty_work

Conflicts:
planet.c
quadtree.c

Makefile: Better output beautifier

This is better code and makes prettier output

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

Makefile: More advanced dependency tracking

Inspired by: http://mad-scientist.net/make/autodep.html#norule

Ensure that dependency tracking does not get confused even if some
dependencies (header files for example) are renamed or deleted.

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

planet.c: merge_planet: Keep quadtree spatially sorted

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>

planet.c: Use the quadtree_move function from quadtree lib

This will remove the duplicate functionality from the planet.c

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

quadtree: Add quadtree_move() function

This function will do necessary steps to keep the tree in correct
spatial order when a node is moved.

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

quadtree: Fix compiler warnings

quadtree.c:370: warning: unused variable ‘ret’

Trivial remove

quadtree.c: In function ‘quadtree_find_nearest’:
quadtree.c:369: warning: ‘distance’ may be used uninitialized in this function

This variable will not be used uninitialized, but the compiler warning
is trivial to fix with simply initializing the variable with zero.

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

quadtree: Implement proper rebalancing

Select nodes in predetermined spatial order that will produce well
balanced tree.

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

quadtree: validator: Catch missing leaf node

This patch will make the validator to catch error when a leaf node has
a pointer to a parent which does not have pointer back to the leaf
node.

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

quadtree: tree validator: Add spatial validation

This will catch errors when the tree is not in spatial order.

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

quadtree.c: Print line number when trap is caught

This helps debugging

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

quadtree.c: Compare vectors, not quadtrees

Factor out the vector comparison into a separate function. That way it
is more useful if plain vector comparison is needed.

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

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>

Make the tree gravitation calculation work better

planet.c: Always remove the smallest planet

As we are not allowed to just move nodes in the quadtree (that might
lead crossing of branch boundaries), we will try to only remove the
smaller planet and add everything else to the larger planet.

Remove explicit debug prints

Does not appear to crash anymore

Some different approach..

Refactor and debug

some more debug

A lot of fixes here and there

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

Add debug and improve tree validation

quadtree.c: Fix a lot of bugs

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

Optimized quadtree, non-working version

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

Merge branch 'master' into HEAD

Conflicts:
main.c
planet.c

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

Merge branch 'master' of git://itanic.dy.fi/sdl-planets

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

Move quadtree comparison code inside quadtree.c

The .compare function can also be removed now from the quadtree_ops
structure.

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

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>

quadtree: Suppress compiler warning

Use correct printf arguments

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

main.c: Use getopt_long() for reading cmd line arguments

This makes it easier to read various different command line arguments.

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

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>

does not crash anymore

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

Continuing..

Work in proggress, will crash and burn

merge_planets: Calculate new color for the remaining planet

Another optimization try..

Merge branch 'master' into work

Conflicts:
planet.c
planet.h
quadtree.c

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>

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>

quadtree.c: Improve debuggin capabilities

-Flush out prints immedeatly. This will ensure prints get out even
 though execution is halted to a breakpoint.

-Add some extra debug messages

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

Better optimization perhaps

continuing..

poll_events: Add support for stopping the simulation

This makes it possible to for example inspect the tree structure in a
stopped simulation.

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

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>

planet.c: Add support for drawing the planet tree structure

A line will be drawn from a planet parent to the child node. Local
variable is used to enable line drawing at compile time.

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

Optimization, work in proggress..

draw_planet: Add support for drawing the tree area

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

planet.c: Make line drawing conditional

When repositioning a subtree, move nodes in random order

Revert "Revert "Revert "Try to optimze"""

This reverts commit df41bc01e2d3ffd9be2bfba023c97c5aabcefc4e.

Revert "Draw also the area planet tree affects"

This reverts commit d2cff17ba1c765f580a23be9da2236648a0f6586.

oops, fix bug..

draw_planet: Separate circle drawing into its own function

It is easier to draw circles elsewhere in the code if the circle
drawing is separated.

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

quadtree: quadtree_del: Fix tree integrity bug

When a root node is deleted and new tree is built under the new root,
the new root node needs to have its parent set to null.

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

planet: Add tree statistics

The total mass and area of the subtree tree is calculated.

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

quadtree: Allow updating other than just quadtree stats

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

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>

Draw also the area planet tree affects

Separate circle drawing into its own function

Revert "Revert "Try to optimze""

This reverts commit 1ae3efb2dde3e86ab4cfcbaea15222ab65389787.

Remove excess status prints

Optimize tree handling

Draw lines

main.c: Prune planets correctly

Print different stats

quadtree: Fix bugs

Revert "Try to optimze"

This reverts commit 66ec6620125badde86f08fabb0a99226da922ee6.

Conflicts:

quadtree.c

some more stuff

Crash and burn

planet: Add tree statistics

The total mass and area of the subtree tree is calculated.

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

quadtree: Allow updating other than just quadtree stats

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

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>

Try to optimze

Merge branch 'master' into work

sync with master

quadtree: Fix minor coding convention issue

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

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>

Seems to be working..

move_planet: Remove debug code

This was not supposed to be there after debugging was finished.

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

continuing..

Crash and burn

main.c: Print tree statistics

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

quadtree: Collect tree statistics

Tree depth and child count is collected and kept up to date.

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

Merge branch 'master' into work

Stats appear to be working

main.c: Do not allow creating zero planets

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

add stats, incomplete..

Makefile: Enable DEBUG definition in debug build

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

quadtree: Fix style issues

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

main.c: Use quadtrees to draw only visible planets

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

planets: Add support for spatial search from quadtree

This can be used to for example draw only visible planets on the
screen.

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

planets: Add quadtrees in use

The tree is used and kept sorted, but it is not used for anything
useful yet.

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

Merge branch 'master' into quadtree

quadtree: Pass quadtree iterator structure to the callback functions

This is better than plain void pointer, since now the iterator can be
embedded as part of some other struct. This simplifies the design.

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

.gitignore: Add debug-planet

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

Makefile: Add debug-planet to the clean target

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

Makefile: rename debug target to obey naming convention

The main target is called sdl-planet, so the debug target should be
called then as debug-planet.

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

Merge branch 'master' of git://itanic.dy.fi/sdl-planets

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>

quadtree: Obey naming conventions

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