Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 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
  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Popular Now

  • Similar Content

    • By 999PING
      I'm very often facing one small problem when trying to learn some new stuff - hard to choose what to learn next.
      Even if the problem seems to be small it has a very huge impact on the final result I think. And because Game Programming offers so much to learn, I'm always feeling that I'm missing something important and wasting my time learning something not important or unneeded. Or usually, I'm afraid to focus on something specific and huge for a long time, because I think that I'll spend all my time on that particular filed and will not be able to solve another problem.
       
      So I've tried to fit all my thoughts in this questions.
      1) Are you trying to cover all the aspects of Game Programming? Or you trying to focus on some specific aspects like physics, animations, or networking etc.
      2) What is your way to find a new theory or whatever else for your learning process? (Manuals, Courses, Books, Documentation? etc.)
      3) When you trying to learn while practicing, are you search for learning because of a problem that appears, or because you wants to try new things? How do you choose this new thing? And finally, Which of this two approaches was the best for you if any?
       
      Not actually in the scope of the topic, but I'm also very interested to hear your thoughts on this.
      What is Game Programming for you? How would you describe what should Game Programmer able to solve?
    • By supermikhail
      You click on objects in the world and get their name and how it's pronounced, in Russian which is my native language.
      That's pretty much it. Basically I want to be 100% sure that I can accomplish the project. The problem is, as a player, would I want to buy it? I myself am poor and consequently very selective with my entertainment spending. Which means, it'd be too lean an offering for me.
      On the other hand, I more or less believe that there are... enough "suckers" out there who'd pick up anything with "language learning" in description... To put it plainly.
      I guess that's the short of it. I don't know if that last intuition of mine is correct. And if it is, I don't actually want to scam people. But I don't want to promise something that I don't know that I'll be able to deliver, like... voice recognition or anything as useful and preposterous. Or even a story. I've never written for games. I've never designed a puzzle. All of which would probably add all the value necessary, but more likely just show me my limits.
      I suppose you could say "make a prototype". And I know I won't enjoy playing it, simply because, well, Russian is my native language and I like challenge. But I'd enjoy making it, and I like the idea of using videogames for studying languages.
      Any thoughts to help my conscience, more or less?
    • By Septopus
      Okay, looking for some constructive feedback/criticism here... 
      What follows is the code of my c# UDP Socket Class.  I've written this based on a number of online examples and a few distant memories from the past, so I really have no idea how "bad" the code is/could be in a 100+ concurrent connection scenario(my dev environment is just two machines at the moment)...  It works, I know that, it is fairly stable(I can't break it when using it normally), and it behaves how I believe I want it to. 
      It is a dual purpose class for handling both Servers and Clients.  It uses an asynchronous receive and synchronous send(I may switch to async send if it proves beneficial later on).  My servers use Client sockets to communicate with each other and to perform internal connection tests in a multiple server, "single shard" type environment.  I'll be devising some heavy load testing methods a little further down the line, but I'm hoping to fish out most of the major gotchas before I get there.
      So, please, let me know how to fix it up if it smells terribly to you, or if not, that's even better...
      Sorry for the large code dump, but THANKS for checking it out!
      using System; using System.Collections.Generic; using System.Net; using System.Net.Sockets; using System.Text; using UWAvatarServerData; namespace UWAvatarServer { public class UDPSocket : IDisposable { //Some simple string length counters and averages to get a rough idea of generated traffic. public int sndMax = 0; public MovingAverage sndAvg = new MovingAverage(); public int csndMax = 0; public MovingAverage csndAvg = new MovingAverage(); public int rcvMax = 0; public MovingAverage rcvAvg = new MovingAverage(); //Constant for configuring the prevention of ICMP connection resets private const int SIO_UDP_CONNRESET = -1744830452; //UDP socket private Socket _socket = new Socket(AddressFamily.InterNetwork, SocketType.Dgram, ProtocolType.Udp); //Buffer Size Constant private const int bufSize = 8 * 1024; //Raw string data from client packets private Dictionary<EndPoint, Queue<string>> messageDictionary; //Queue for holding raw string data from server packets when in client mode. private Queue<string> cQ; //Referece to the data store used by the server(for access to the current game time clock) private UWDataStore dataStore; //Time code storage for last sent/received messages private double lastSentMessage = 0; private double lastReceivedMessage = 0; //Boolean to determine which mode we're in so received messages get put in the right place. private bool clientMode = false; //Max string lenght allowed by the servers. private int maxMessageLength = 1450; //IDisposable stuff public void Dispose() { Dispose(true); GC.SuppressFinalize(this); } protected virtual void Dispose(bool disposing) { if (disposing) { // free managed resources if (_socket != null) { _socket.Dispose(); _socket = null; } } } //State class for async receive. public class State { public byte[] buffer = new byte[bufSize]; public EndPoint epFrom = new IPEndPoint(IPAddress.Any, 0); } //Server "Mode" public UDPSocket(Dictionary<EndPoint, Queue<string>> msgsDict, UWDataStore DATASTORE) { clientMode = false; messageDictionary = msgsDict; dataStore = DATASTORE; lastSentMessage = dataStore.UWServerSeconds; } //Client "Mode" public UDPSocket(Queue<string> mq, UWDataStore DATASTORE) { clientMode = true; cQ = mq; dataStore = DATASTORE; lastSentMessage = dataStore.UWServerSeconds; } public void CloseSocket() { _socket.Close(); } //Internal connection status checking public int SendHowStale() { if (lastSentMessage == 0) lastSentMessage = dataStore.UWServerSeconds; return (int)(dataStore.UWServerSeconds - lastSentMessage); } //Internal connection status checking public int ReceiveHowStale() { if (lastReceivedMessage == 0) lastReceivedMessage = dataStore.UWServerSeconds; return (int)(dataStore.UWServerSeconds - lastReceivedMessage); } //Start/Bind a Server. public void Server(string address, int port) { //In case restarting uncleanly, dunno if this actually does anything.. _socket.SetSocketOption(SocketOptionLevel.IP, SocketOptionName.ReuseAddress, true); //Ensure all async packets contain endpoint info and etc. _socket.SetSocketOption(SocketOptionLevel.IP, SocketOptionName.PacketInformation, true); //Ignore ICMP port unreachable exceptions. _socket.IOControl((IOControlCode)SIO_UDP_CONNRESET, new byte[] { 0, 0, 0, 0 }, null); //Bind to port. if (address == "all") { _socket.Bind(new IPEndPoint(IPAddress.Any, port)); } else { _socket.Bind(new IPEndPoint(IPAddress.Parse(address), port)); } //Start receive callback process. Receive(); } //Setup a Client to Server socket. public void Client(string address, int port) { //Dunno if these two options do anything for client sockets, but they don't seem to break anything. _socket.SetSocketOption(SocketOptionLevel.IP, SocketOptionName.PacketInformation, true); _socket.IOControl((IOControlCode)SIO_UDP_CONNRESET, new byte[] { 0, 0, 0, 0 }, null); _socket.Connect(IPAddress.Parse(address), port); //Start receive callback. Receive(); } //ServerSend sends to any EndPoint from THIS server. public void ServerSend(string text, EndPoint ep) { try { byte[] data = Encoding.ASCII.GetBytes(text); _socket.SendTo(data, ep); lastSentMessage = dataStore.UWServerSeconds; if (text.Length > sndMax) sndMax = text.Length; sndAvg.ComputeAverage((float)text.Length); //Console.WriteLine("TO NET: " + text); } catch (Exception ex) { Console.WriteLine("ServerSend Exception: " + ex.Message); } } //Client Send only sends to the connected Server. public void cSend(string text) { try { byte[] data = Encoding.ASCII.GetBytes(text); _socket.Send(data); lastSentMessage = dataStore.UWServerSeconds; if (text.Length > sndMax) sndMax = text.Length; sndAvg.ComputeAverage((float)text.Length); //Console.WriteLine("TO NET: " + text); } catch (Exception ex) { Console.WriteLine("cSend Exception: " + ex.Message); } } //Setup Async Callback private void Receive() { try { State so = new State(); _socket.BeginReceiveFrom(so.buffer, 0, bufSize, SocketFlags.None, ref so.epFrom, new AsyncCallback(_Receive), so); } catch (Exception) { } } //Receive Callback private void _Receive(IAsyncResult ar) { try { State so = (State)ar.AsyncState; int bytes = _socket.EndReceiveFrom(ar, ref so.epFrom); lastReceivedMessage = dataStore.UWServerSeconds; string smessage = Encoding.ASCII.GetString(so.buffer, 0, bytes); //Console.WriteLine("FROM NET: " + text); if (smessage.Length < maxMessageLength) { if (smessage.Length > rcvMax) rcvMax = smessage.Length; rcvAvg.ComputeAverage((float)smessage.Length); if (clientMode) { cQ.Enqueue(smessage); } else { if (!messageDictionary.ContainsKey(so.epFrom)) { messageDictionary.Add(so.epFrom, new Queue<string> { }); } messageDictionary[so.epFrom].Enqueue(smessage); } } _socket.BeginReceiveFrom(so.buffer, 0, bufSize, SocketFlags.None, ref so.epFrom, new AsyncCallback(_Receive), so); } catch (Exception) { } } } } Generally speaking I use it as such:
      public static bool running = true; static void UDPServer() { using (s = new UDPSocket(MessageDictionary, UWDataStore)) { s.Server("all", 37373); while(running) { //Servery Stuff Goes Here. //Like reiteratively dequeuing the Message Dictionary Queues and processing/replying to all commands/etc... } } } All processing of individual messages from clients is handled with Task.Factory tasks, and a reference to the server's socket varible (s), and the client's EndPoint is sent along the ride for use in replying to clients.  There's no game logic and there are no client replies that happen directly from within the UDP server's main while loop, mostly just connection status checking and reorganizing of the Message Queues into Tasks.
      Thanks again for making it this far.
    • By Iris_Technologies
      Suppose i don't have any linker at hand but i am calling an exported function from a C++ DLL Windows, i.e. sqrt from mvcrt14.dll, how would i get just and only just the Relative Virtual Address of sqrt from that dll to simulate what linker does and convert this call to a call to such RVA on the hexcoded generated .exe file? 
      Either, how would i read the RVA of Mac, Android, iOS and Linux library formats?
    • By JoAndRoPo
      Hi!
      I have a doubt regarding the Daily Bonus.
      Let's say 7 days. Player receives Daily Bonus in Day#1, Day#2, Misses Day#3, Plays on Day#4, and so on. What happens when the player misses a day? Does the Daily Bonus reset back to day#1? or does the player miss the reward of the missed date and continue to receive the reward on the next day? Can you name me some games that have used a unique daily bonus logic?
  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!