Jump to content
  • Advertisement
  • 08/11/17 09:04 PM
    Sign in to follow this  

    Using DOT to Debug Data Structures

    General and Gameplay Programming
       (1 review)

    TheComet

    In this article, I'd like to share a method I used to help visually debug tree-like data structures by leveraging the DOT format and Graphviz. This may be useful to you if you ever end up having to work with low-level data structures and no way to visually see what your code is doing.

    The Problem

    During the early stages of development of my inverse kinematics library (which, at the time of writing, is in its alpha stages and not quite ready for general use yet), I was working on an algorithm which takes a scene graph as its input and generates an optimised structure consisting of a tree of "chains", specifically designed for use with an IK solver.

    The transformation is not that easy to explain in words, but here is an illustration of before (a) and after (b) (please excuse my MSPaint skills; I'm a programmer, not an artist):

    1.png.14527fd00d931285c428f1928818ef93.png

    You can see here that each end effector in the scene graph specifies a "chain length" parameter, which tells the solver how many parent nodes are affected. Since the IK solver works most efficiently on single chains of nodes, it makes sense to break down the scene graph into multiple chains which the solver can then process sequentially. This is illustrated in (b). Notice how chain 1 (red) becomes isolated from the rest of the tree after processing, because its end effector only specified a length of 1. Also notice how in the new structure each chain consists of only a sequence of nodes with no branches.

    The algorithm had to be able to handle a few weird edge cases, such as:

    • What happens when you place an effector on a node that has multiple children?
    • What happens when there are multiple end effectors in a chain?
    • What happens when an end effector specifies a chain length that doesn't quite join up with the rest of the tree?

    This of course meant it was harder to test and make sure it was working correctly. I did of course write a suite of unit tests using Google's testing framework, but I wanted more: I wanted to have the ability to visually look at what my algorithm was generating, and I wanted to do this without having to use some fancy 3D engine.

    Inroducing: DOT and Graphviz

    DOT is a simple graph description language. Graphviz is a set of open source tools for generating graphics from DOT descriptions. For example, the following DOT code:

    graph testgraph {
        a -- b;
        b -- c;
        b -- d;
    }

    Compiled with dot as follows:

    dot -Tpdf testgraph.dot -o testgraph.pdf

    Produces the following graphic:

    2.png.3252fa7a3f9e72d5d94560c63d1ad932.png

    DOT is quite a powerful language. It's possible to specify colours, shapes, multiple connections between nodes, and much more! Read up on the format specification for more information.

    In only a few lines of code I was able to iterate the optimised chain tree and serialise it to DOT. This is what the example tree I drew in MSPaint looks like after it is broken down by my algorithm and exported to DOT:

    3.png.a086849bf37d2d09b8a62102bf905a2c.png

    Things to note:

    • The black edges show the connections between the original tree.
    • The red edges show how the chains are connected (just like in the first figure (b))
    • Effector nodes are coloured blue
    • Nodes that mark the start or end of a chain are square. You can see for example that node 6 is square because it has two child chains, but node 2 is not square because it's in the middle of the second chain.

    And just like that I had a powerful way to quickly spot errors in my algorithm. Using python and watchdog I wrote a simple script that would monitor the DOT file for changes and automatically compile it to PDF. Thus, every time I ran my program the graphic would update immediately on my second monitor so I could inspect it.

    Another Example

    In another application I wrote, I implemented an intrusive profiler which would dynamically build a tree from the callgraph and store timing information in each node. I thought it would be cool to also dump this tree to DOT format and see what it looked like. Note that in this case I didn't use the "dot" command line tool, instead I used "neato" (this is also part of the Graphviz package). Neato has a different layout algorithm based on physical constraints, which in this case produces much nicer graphs than "dot":

    4.thumb.png.01c5665c8b19103584fcb2b93d565786.png

    I find it quite beautiful to look at. What you see here is a visual representation of how much time was spent where in the program. Nodes that are red are "hot" (meaning lots of time was spent in them) and nodes that are blue are "cold" (nearly no time was spent in them).

    If you zoom in a little bit you can also see that I exported some of the profiler parameters of each function.

    5.png.48db060a3bcc93f56b91bef35d448cc3.png

    While this does provide a very nice birds eye view of where your program needs optimising, I would of course recommend using proper profiling tools to further analyse the slow functions.

    In conclusion

    Due to the simplicity of the DOT language, it's trivial to write an exporter for it, so if you ever find yourself fiddling with low level data structures, consider dumping them to DOT and visualising them. I found this to be extremely helpful during development of my IK library.



      Report Article
    Sign in to follow this  


    User Feedback


    Hey, I've looked into your ik library and it seems awesome. How stable it is, besides alpha, is it ready to use? And do you anticipate if the API is going to have significant changes in the future?

    Share this comment


    Link to comment
    Share on other sites

    Hi!

    It's fairly stable at this point (as in, it doesn't crash, there are no memory leaks, it correctly calculates results in every situation).

    The biggest API change in the near future will be that positions and rotations are specified in local space rather than in global space (which is currently the case). Other than that I don't see the API changing.

    Functionally, the way it was designed introduces some major flaws (none of which you will not run into if you don't try to solve nested trees with multiple end effectors). I'm still working on getting those fixed.

    Edited by TheComet

    Share this comment


    Link to comment
    Share on other sites


    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Game Developer Survey

    completed-task.png

    We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a $15 incentive for your time and insights. Click here to start!

    Take me to the survey!

  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Advertisement
  • Popular Now

  • Similar Content

    • By KrokoStudio
      Hello guys!
      This is the first game of our studio and we just released it on Play Store. Lighty Ghost is a little game where you need to touch the walls while avoiding to touch the spikes. The longer you stay alive, the bigger your score is. The little detail is the "green lights" multiplicators that encourage you to take risks in order to have bigger score. We already planned to launch on iOS when our account will be validated and to integrate a leaderboard (certainly based on facebook accounts) to compare with your friends in a version 2.
      We need advices to make the "green lights" multiplicators more understandable in the game. A lot of people think for the moment it is poison. Moreover, when you take a multiplicator, the next one will multiply by 2 again until you reach x16 which is the maximum. We tried to make it understand by adding the bubbles on top of our character and make the tail bigger each time. Do you have advices on that?
      Same for the gems, it is to buy characters. An idea to improve the understanding of this part?
      Thanks guys!
       
      Lighty_Ghost_-_Play_Store_-_EN.mp4
    • By JeremyAlessi
      In episode #2, Jeremy adds some formatting by covering the news, reflecting on the inspiration for PixelFest, and delving into an important developer lesson; that period of time everyone faces when they have to decide whether to play a game or make a game with their time.
      https://youtu.be/fvaG_pIIUYM
       

      View full story
    • By JeremyAlessi
      In episode #2, Jeremy adds some formatting by covering the news, reflecting on the inspiration for PixelFest, and delving into an important developer lesson; that period of time everyone faces when they have to decide whether to play a game or make a game with their time.
      https://youtu.be/fvaG_pIIUYM
       
    • By nsmadsen
      In this episode of Madsen's Musings, I discuss what to call yourself when first getting started as an audio professional.
      Wanna learn more about me or my work?  Go here: https://madsenstudios.com/
      Subscribe to my YouTube channel or follow me here on GameDev.net to see all the latest updates.
      A transcript is provided below the video.
      Okay, so this is a really quick mini-vlog, but I watched an interview with CLA today - Chris Lord-Alge.  It was a really good interview for the most part, I enjoyed it: lots of really good quotes and tidbits of information in there, but here's one thing I did not enjoy - or one thing where I perhaps understand what CLA is saying but I don't totally buy into or agree to it, and that is the notion of... he was basically ranting about the fact that people call themselves mixing engineers, and he felt like he had to earn that.  
      He used the analogy of the military saying "you're not a General, you're a Private", you're just starting out, don't call yourself a mixing engineer, and I get the fact that he's talking about back in the day the way it worked is you had to work up different things: you're an assistant, you had to do this type of prep, and then you shut up, and you stood back, and you let the professionals do certain things that they were doing whether they are the engineer or the producer, or they're the mixing/mastering engineer, whatever it is - they had a very structured path or progression you went up through and you didn't just say "I'm a mixing engineer".
      So I get what he's saying, and to a degree I agree with it, but I also feel like there's a danger to saying you have to reach a certain threshold before you can say you're X, Y, or Z.  A perfect analogy is I play saxophone - I have two degrees in it, so can I say that I'm a saxophonist if I don't play at the same level as a Jeff Coffin, a Bob Reynolds, you know, a Joshua Redmond, a Branford Marsalis?  I don't play on the same level as those guys, so does that make me not a saxophonist?  I think it makes me a saxophonist in work in progress.  A saxophonist working towards something.  
      So I don't ever want to have that mentality of you're not a composer if you have not reached X or Y.  Maybe CLA, Chris Lord-Alge is trying to get at is if you haven't gone through and mastered all these other elements and you're just saying you're a mixer, then yeah, maybe pare back a little bit, but I also see that we're all works in progress, and I hope we're all continually advancing and growing, and learning and getting better.
      So that's just a little short tidbit, I hope it's helpful and encouraging.  Go out there, learn your stuff, always be a lifetime student, but at the same time don't be scared to say that you are X, Y and Z.  I don't know, I mean, that doesn't make sense.  I personally offer mixing as one of my services, but I also don't claim to be at the same level as a Chris Lord-Alge, or any of those people.  I'm still intermediate - and it shows in my price point too - it shows on my credit list, so I don't know - I'm kind of rambling, but that's something to think about.
      [Parting remarks]
    • By linus_e
      I am really annoyed at how slow GitLab became in my last project, looking for something more scalable for the next one. Using LFS is not an option unfortunately. Does anyone have any recommendations for working with large repos on other tools (Bitbucket, CodeCommit, ...)?
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!