Jump to content

  • Log In with Google      Sign In   
  • Create Account


How to debug the complex data structure and algrithms such like quadtree, BSP, octree?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 Baesky   Members   -  Reputation: 126

Like
0Likes
Like

Posted 19 September 2013 - 11:45 PM

Hi, recently i worte my own implements of quadtree, but i encountered some bug in my algrithm. I found it difficult to debug the bug because the algrithm and data structure is complex than others.

I wanna known how to debuging in this situation if you were me?

Thanks advance!



Sponsor:

#2 HappyCoder   Members   -  Reputation: 2224

Like
3Likes
Like

Posted 20 September 2013 - 12:16 AM

I don't know of any easy answers. But a few things come to mind. First, find a scenerio where you can duplicate the bug evertime. The fewer steps the better. Then drill down with a debugger viewing intermediate values and making sure they match expected output. Also, having some way to visualize the quadtree is usefull, drawing it out to the screen for example.

Another thing to concider is to make automated tests. When you write the tests make then simple but be sure to cover common occurences. For a quadtree, make a test for when the object being added intersects multiple quadrants. Make a test that overflows a quadrant so it has to be split. Making automated test helps you think of corner cases to thouroghly test your algorithm in small parts so you can have more confidence it works as a whole.

#3 rozz666   Members   -  Reputation: 599

Like
2Likes
Like

Posted 20 September 2013 - 04:46 AM

I would split the algorithm into the smallest pieces that are reasonable and unit test every possible scenario. Then the only bugs that could occur would be integration errors, which I would cover with module tests.



#4 RobTheBloke   Crossbones+   -  Reputation: 2295

Like
3Likes
Like

Posted 20 September 2013 - 04:49 AM

Unit test *everything*. Some debug rendering *may* be useful, but only as a tool to help decide what to test next.....

A GUI based editor might be useful (i.e. tree view window, with attribute editor listing information about each node in the tree). That won't help you find problems in the implementation though, just as a tools to inspect the data... 


Edited by RobTheBloke, 20 September 2013 - 04:51 AM.


#5 unbird   Crossbones+   -  Reputation: 4813

Like
2Likes
Like

Posted 20 September 2013 - 06:41 AM

I occasionally find log-files useful to track down bugs. E.g. for big loops or structures dumping temp vars or debug calculations in tabular form is IMO easier too inspect than repeatedly run-break with an interactive debugger.
 
Currently I (ab)use a D3D11 append buffer to "log" debug values from compute shader wink.png

#6 radioteeth   Prime Members   -  Reputation: 914

Like
2Likes
Like

Posted 20 September 2013 - 10:54 AM

I work with tree structures by starting very small, one level with a node and just its children. I see how everything operates there, and then start making the tree deeper, to make sure any recursion doesn't start throwing things off.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS