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 Ey-Lord
      Hello everyone

       
      I am here to gather your opinion, remarks, ideas or any constructive criticism you may have about what I am going to present. Don’t be shy!


       
      A bit of background:

      I am working alone on an indy web-based game, a simulation of RPG (idle game) where the player controls a group of 4 characters that he can sent into battle and that will fight automatically based on some AI preference that are similar to the FF 12 system (but more complex / powerful). He then earns some experience and resources that he can use to improve his unit’s gear, talents and skills. He has a lot of control on what skills his characters will use and how/when.


       
      What brings me here today:

      The AI of Monsters. I have the AI settings for players covered (basically a bunch of if/then/and/or/else settings that he can combine and order so that his units will act as he intends in battle). I’ve been working on the AI of monsters for quite some time, made a long break and came back recently to it.


       
      Short description of the battle system:

      No movement involved. Battle is fully automated. Players setup its units AI settings before battle and monsters are controlled by a separate AI. This is a 4v4 battle, like FF7 with some kind of ATB and any time a unit fill its ATB, it can play and the then the next unit who will fill it will play, etc. The player is completely free of his playstyle and may create very offensive group or very defensive ones. 4 healers or 4 tanks is completely possible.

      The battle system is very complex and allows for very varied and sometimes unusual strategies, like killing your own allies to proc an “on death buff” that will be devastating for the opponent.


       
      What I want for my AI?

      It needs to be fun to fight against and challenging. Ideally, I would like an AI as smart as possible (not omniscient but thinking as a human would). I know that a super-smart AI is not always the best way to make a game fun or challenging but in the context of my game, this is the result I want to achieve. It may seem unfair to have the AI try to kill your squishy while your tank is standing right there but my class design gives the tools to players to counter that so it’s not an issue (tanks are not purely aggro based for example). I want players to always be challenged by AI moves and that they must carefully think about their strategy because if they leave a big hole in it, I want the AI to exploit it.

      In practice, it means a few requirements:

      No dumb decision / do not fall into obvious player’s traps Exploit obvious flaws of the opponent Act in coordination when appropriate with other units Able to find who should be their focus in the player’s team (some notion of threat) Find the best move to use and if there is some kind of combo possible, use it

      These requirements are harder to meet than it looks. The issue is the sheer number of different mechanisms and strategies available to players and to monsters as well. For example, there are many cases where killing or attacking a player unit might be detrimental (units that return damages or that gain power when you hit then for example).


       
      What I have tried before?

      I have tried or at least reviewed many different AI concepts so far.

      -          A simple copy of my player’s AI system (hierarchical if/then/else). It was easy to script as I already have the UI in place for players so I can quickly define a basic AI for any new monster’s group. The main drawbacks are that it needs to be written for every monster group, it does not allow smart targeting and cannot find the best target or the best skill to use. It will also make dumbs decision as the targeting options cannot assess threats at all.

                I’ve rules out planners since for purely selecting the best pair of (skill, target), they do not seem to match my needs.           (H)FSM or BT does not seems to match my needs as monsters do not have states / transition condition that can lead to something useful for me.        I’ve ruled out aNNs as they might, with proper training, be able to find the best action at a given time but it’s very tedious to implement and will not solve my need of finding combo or coordinating with other units very well. (plus, let’s be honest, I’d be a bit out of my depth to program them)           I have spent an extensive period of time trying with tree searches. Mainly: monte-carlo with random sampling and came to the conclusion that due to the complexity of my battle system, it is excessively costly to compute any kind of reliable data this way.
      -        My current AI system is a version of my first one (the same as the players) but with access to some “smarter” targeting function that in theory allow to choose the best target. These functions work by gathering data for thousands of simulated fights during the AI time to play (1 second). It’s a first step to find the best target but not very accurate (lots of big flaws that can be exploited by players) and it is very time consuming and that is something I’m trying to get away from. I do not want to use 100% of the players CPU as I do now.


       
      What is my latest idea?

      I started to study more in-depth the Utility theory as described by Dave Marks (I read his book and watched his GDC AI lectures as well). I liked the idea. I like that I can start on something relatively simple and add more considerations as things progress to handle more and more situations. While my work began as something very close to utility theory, it evolved a bit afterward. Here is what I plan on doing to compute a unit’s best course of action:


       
      A – Score every of its move (each move is a pair [skill, target]).

      B – Chose the move according to a selection strategy (highest score, weighted random, random amongst the top scores… lots of different selection algorithm can be used there).


       
      So far, easy, right? Let’s dig deeper into our first phase of scoring (A), which is the hard part. For all the damage or healing skills:


      Step 1: The final scoring of the move [skill,target] will be function of the a “Survival” scoring for the player team and for the enemy team. An example of this relationship could be: Adding all the survival scores of each unit in Team A and divide the result by the addition of all the survival scores for each unit in team B.

      Step 2: The survival score of each unit will be its Health after the move we are evaluating, divided by the total damage per turn that we estimate other units can deal to her (minus the total heal it ca receive). [This a step where we can process damage and heal over time as well]

      Step 3: This damage per turn estimation will be, initially, the sum for every unit in battle of the damage or heal per second it can deal to that unit. For example: If I’m alone vs 2 bad guy that can deal 1 dmg/turn and if I can deal 1 heal/turn, the damage per turn estimation against me will be 2-1 = 1. [This is not optimal since we are counting the damage of each unit once per enemy unit but it’s a start]

      Step 4: To compute the DPS or HPS of each unit, we review the unit’s skills and compute their output against the unit we want to evaluate it against. From that, we construct a skill sequence to maximize the damage output and once we got the optimal skill sequence, we can compute its DPS or HPS output and pass it along for Step 3.


       
      It might seem like a lot of work, since, in a world with only damage or healing skills, the DPS or HPS sequence of each unit will be the same in every situation and as such only the damage done or healing done by the skill evaluated would be enough. But…


       
      The tricky part comes from buffs and debuffs. If we use the above algorithm, (de)buffs that changes the damage or healing someone does or receive will be evaluated correctly as it will change the damage or heal per second output of units and it would affect the survival score and the final scoring. That is why I chose to include DPS and HPS computations for each unit for each move.


       
      This is all fine until we consider (de)buffs that changes the power of other (de)buffs. Like: I cast a buff that double the length of all my future buffs. My algorithm can’t evaluate it correctly. It’s a situation that will be common enough in my game and I want my AI to deal with it. Note: there are more complex situations where a unit could buff a buff that buffs a buff that buff a buff [….] that will end-up buffing a damage or healing skills, but those cases will not be addressed as they will hopefully be rare and too cumbersome to compute anyway.


       
      So, my goal is to score properly buffs that: 

            Buffs the damage or healing output of someone           Buffs that buffs a skill that does the above

       
      L    Long story short of how I am doing that. I’m using my initial algorithm but while also estimating damage or healing per second change for each dps or hps sequence.To do that I’m evaluating every move of the unit (or every unit in case of AoE but lets keep it simple with single target) that is targeted by the buff. So, we are switching PoV here compared to the initial unit we are evaluating (unless the move evaluated is buffing itself)

      -          I’m doing the above in 2 situations:

      o   A : After a cast of the buff skill I’m evaluating

      o   B : Without the cast of the buff, just like if it was that unit’s turn to play

      -          Using a sort of min/max approach: if the unit targeted by the buff is an ally, we will take the best branch of our tree in A and compare it with the same branch (pair [skill,target]) in B. If the unit targeted by the buff is an enemy, we want to lower their maximum score and will select the tree branch that does that in A to also compare it with the same branch in B.

      -          The information we extract here are DPS or HPS delta for each sequence of DPS/HPS for each unit vs each other unit.

      -          Then, we go back to our steps 1 to 5 and compute our scoring for the move (buff) while using our new dps/hps deltas to get better and more accurate dps/hps sequence for units affected by the buff.


       
      This is basically it. I’ve ran a manual version of the algorithm in 2 different battle settings to test it and see if it gave good results. It worked. Not flawlessly but it worked. Lots of cases will still require tweak and additions to the basic idea but I think its promising. (taunts and CCs are not easy to deal with but it’s manageable)


       
      What I like is that I can add more considerations later (as in the utility theory) like: resource cost, general unit strategy (cleave or focus), behavior (careful, lunatic, reckless). While this will still be a bit time consuming it should be a good order of magnitude faster than my current AI. It also does not prevent me from adding hardcoded AI move if I want to “script” more some monsters. Debugging and tweaking might be a bit painful though, especially when fights will involve lots of skills & stats but that’s an issue that most AI for my game would likely have anyway.


       
      To come back with my initial goals:

              No dumb decision / do not fall into obvious player’s traps
      o   Not perfect but it should choose the best target whenever possible

                 Exploit obvious flaws of the opponent
      o   Same as above

              Act in coordination when appropriate with other units
      o   This can be done simply by adding weight to some targets or computing moves for all units of a group before deciding which one to take (for example to take the best move vs a specific unit, on average)

             Able to find who should be their focus in the player’s team (some notion of threat)
      o   It will naturally focus the unit who is the easiest to kill and debuff or CC the ones that deal the more heal/damage. But, to better solve this, we will need to add other considerations to the AI scoring process, It should not be *too* hard    

            Find the best move to use and if there is some kind of combo possible, use it
      o   Combo are very often in the form of buff/debuff setup before an actual damaging or healing skills and my AI can compute up to a 3 moves combo (buff > buff > skill that dmg or heal) which should cover most cases.


       
      I’m quite happy with my initial tests. I’m not going to be coding it now. My goal was to reflect on the subject on paper and try to see if designing my AI would be a roadblock or not for my project. There are a few other area I want to design and take time to really think about before getting back to my project full time. I’d love to hear your toughs and feedbacks about my AI ideas. Do you see huge roadblocks I’m missing? Does it sound ok to you?

      If you read that far…. thank you and I can"t wait to hear from you guys😊

    • By EchoCell
      Hello folks! I’m looking for advice on which engine I should go with for a 2D game I want to make. The goal is to make a side-scrolling beat’em up/2D fighting game hybrid where the main levels are in beat’em up mode, but the boss battles are in 2D fighter mode. The combat controls (combos, special moves, etc) would be the same in both modes, and the game would include a tournament mode that is entirely in 2D fighter mode.
      I have minimal game developing experience, and am essentially a noob. I am mostly familiar with RPGMaker, but have also experimented lightly with Unity. I have zero programming knowledge, and thus am partial to engines more accessible to complete beginners.
      What engine(s) would be best suited to this kind of game? I am interested in both M.U.G.E.N and OpenBOR, but I don’t think either would allow the kind of genre-crossing I want to accomplish without significant programming skills that I don’t have.
      Also - and I realize I’m thinking too far ahead - I would like to be able to release this game via HTML5 and just host it online somewhere if possible. Otherwise I am okay with it being PC only.
      Thank you for your time and input!
      -Autumn
    • By Sword7
      I googled for terrain collisions but found only some sources about flat worlds.   I want collision detection for spherical terrain worlds.   I have "3D Engine Design for Virtual Globe" book but it did not mention any algorithms about collision detection for landing, rolling, walking, crashing, etc...   Does anyone have any good sources for spherical terrain collision detection?
    • By Velvet
      Hello everyone! I finally mustered the balls to come here and ask for your advice.
      To simply put it, my friend and I would like to emulate, or make a small private server of, this pretty old MMO.
      We've managed to obtain the database of said MMO, even though it's not the most recent version.
      The issue is.. both of us are what you'd call non-programmers, so we have no idea where we should start.
      Having the database we've used SQL Server to take a look at it, but that's as far as we go.
      He says we need somone who's familiar with c# & sql programming languages to help us set this up, skills that none of us have.
      All we want is to put a small server up and running so that the two of us and a couple other friends can play together, kind of like minecraft.
      We'd like to find people to help us set this up, or to at least guide us on what we have to do so we can hire some programmers.
      So I'd like to ask:
      Since we have the database and (I think) don't need reverse engineering, what are the next steps to make it work and have the server go live? What are the programms that we need to use for said steps? What kind of skills should we look for in the people we'd hire to set the server up? I'm sorry if this sounds halfassed but I really appreciate any advice you'd have to offer.
      Thank you in advance!
    • By JeremyAlessi
      In the 5th PixelCast, Jeremy shares some fond memories of Castlevania IV now that it's October and Halloween gaming is on. Jeremy also dives into the news and covers an issue that's been on his heart and mind lately; the increasing number of game developers who seem to be passing away in their 40's and 50's.
       
       

      View full story
×

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!