FuzzyBunnySlippers

GDNet+ Basic
  • Content count

    10
  • Joined

  • Last visited

Community Reputation

1776 Excellent

About FuzzyBunnySlippers

  • Rank
    Member

Personal Information

  • Interests
    Art
    Design
    Programming
  1. Improved the AI a bit in Cannon Clash. https://t.co/8WWdTPoXnT
  2. Leading the Target

    An article needs to tell its story with pictures, words, formulas, and working code.  This article is a good start on a good topic.     I feel it needs a picture for each situation and a complete set of working code.  The general case, especially, should be expanded.  Or the article should only discuss one of the cases explicitly and not hint at a solution for other cases.   For several years, I worked on a 2-D space shooter where agents actively shot at and pursued enemies.  So this topic is something I am glad to see discussed.  It applies not just to the 2-D case, but the 3-D case as well.  I ended up leveraging a lot of that information in a different game called Cannon Clash.    For the case of a non-rotating shooter, hitting a position in the future has a closed form solution.     For the more general case of a rotating shooter, I know of at least one iterative solution (I could not find a closed form solution) described here (this article is posted on gamedev.net as well).  
  3. Visual Tools For Debugging Games

      This sounds like a solid approach.  
  4. Overview How much of your time do you spend writing code? How much of your time you spend fixing code? Which would you rather be doing? This is a no-brainer, right? As you set out to develop a game, having a strategy for how you are going to illuminate the "huh?" moments well before you are on the 15th level is going to pay dividends early and often in the product life cycle. This article discusses strategies and lessons learned from debugging the test level for the 2D top down shooter, Star Crossing. Intrinsic Tools Before discussing the tools you do not have by default, it seems prudent to list out the ones you will generally have available in most modern development tool chains. Console output via printf(...). With more advanced loggers built into your code base, you can generate oceans worth of output or a gentle trickle of nuanced information as needed. Or you can just have it print "here 1", "here 2", etc. To get output, you have to actually put in code just for the purpose of outputting it. This usually starts with some basic outputs for things you know are going to be helpful, then degenerates into 10x the number of logging messages for specific issues you are working on. Your actual "debugger", which allows you to set breakpoints, inspect variables, and gnash your teeth at when you try to have it display the contents of a std::map. This is your first line of defense and probably the one you learned to use in your crib. A "profiler" which allows you to pinpoint where your code is sucking down the frame rate. You usually only break this out (1) when things go really wrong with your frame rate, (2) when you are looking for that memory leak that is crashing your platform, or (3) when your boss tells you to run before shipping even though the frame rate is good and the memory appears stable, because you don't really know if the memory is stable until you check. All these tools are part of the total package you start out with (usually). They will carry you well through a large part of the development, but will start to lose their luster when you are debugging AI, physics, etc. That is to say, when you are looking at stuff that is going on in real time, it is often very hard to put the break point at the right place in the code or pull useful information from the deluge of console output. Random Thoughts If your game has randomness built into it (e.g. random damage, timeouts, etc.), you may run into serious trouble duplicating failure modes. Someone may even debate whether the randomness is adding value to your game because of the headaches associated with debugging it. As part of the overall design, a decision was made early on to enable not-so-random-randomness as follows: A "cycle clock" was constructed. This is lowest "tick" of execution of the AI/Physics of the game. The cycle clock was set to 0 at the start of every level, and proceeded up from there. There is, of course, the possibility that the game may be left running forever and overflow the clock. Levels are time limited, so this is not a concern here (consider yourself caveated). A simple static class provided the API for random number generation and setting the seed of the generator. This allowed us to put anything we want inside of the generation so the "clients" did not know or care what the actual "rand" function was. At the start of every tick, the tick value was used to initialize the seed for the random number system. This allowed completely predictable random number generation for the purposes of debugging. This also has an added benefit, if it stays in the game, of the game evolving in a predictable way, at least at the start of a level. Once the user generates their own "random input", all bets are off. Pause, Validate, Continue The screenshot below shows a scene from the game with only the minimal debugging information displayed, the frame rate. The first really big problem with debugging a real-time game is that, well, it is going on in real-time. In the time it takes you to take your hand off the controls and hit the pause button (if you have a pause button), the thing you are looking at could have moved on. To counter this, Star Crossing has a special (configurable) play mode where taking your finger off the "Steer" control pauses the game immediately. When the game is paused, you can drag the screen around in any direction, zoom in/out with relative impunity, and focus in on the specific region of interest without the game moving on past you. You could even set a breakpoint (after the game is paused) in the debugger to dig deeper or look at the console output. Which is preferable to watching it stream by. A further enhancement of this would be to add a "do 1 tick" button while the game was paused. While this may not generate much motion on screen, it would allow seeing the console output generated from that one cycle. The frame rate (1) is ALWAYS displayed in debug builds even when not explicitly debugging. It might be easy to miss a small slowdown if you don't have the number on the screen. But even a small drop means that you have exhausted the available time in several frames (multiple CPU "spikes" in a row) so it needs attention. The visual debugging information can be turned on/off by a simple toggle (2). So you can leave it on, turn it on for a quick look and turn it off, etc. When it is on, it dropped the frame rate so it usually stayed off unless something specific was being looked at. On the positive side, this had the effect of slowing down the game a bit during on-screen debugging, which allowed seeing more details. Of course, this effect could be achieved by slowing down the main loop update. Debug Level 1 The screen shot below shows the visual debugging turned on. Physics At the heart of the game is a physics engine (Box2D). Every element in the game has a physical interaction with the other elements. Once you start using the physics, you must have the ability to see the bodies it generates. Your graphics are going to be on the screen but there are physics elements (anchor points, hidden bodies, joints, etc.) that you need to also see. The Box2D engine itself has a capacity to display the physics information (joints, bodies, AABB, etc.). It had to be slightly modified to work in with Star Crossing's zooming system and also to make the bodies mostly transparent (1). The physics layer was placed low in the layer stack (and it could be turned on/off by header include options). With the graphics layer(s) above the physics, the alignment of the sprites with the bodies they represented was easy to check. It was also easy to see where joints were connected, how they were pulling, etc. Location Star Crossing is laid out on a floating point "grid". The position in the physics world of all the bodies is used extensively in console debug output (and can be displayed in the labels under entities...more on this later). When levels are built, a rough "plan" of where items are placed is drawn up using this grid. When the debug information is turned on, major grid locations (2) are displayed. This has the following benefits: If something looks like it is cramped or too spaced out, you can "eye ball" guess the distance from the major grid points and quickly change the positions in the level information. The information you see on screen lines up with the position information displayed in the console. Understanding the action of distance based effects is easier because you have a visual sense of the distance as seen from the entity. Entity Labels Every "thing" in the game has a unique identifier, simply called "ID". This value is displayed, along with the "type" of the entity, below it. Since there are multiple instances of many entities, having the ID helps when comparing data to the console. The labels are also present during the regular game, but only show up when the game is paused. This allows the player to get a bit more information about the "thing" on the screen without an extensive "what is this" page. The labels can be easily augmented to display other information (state, position, health, etc.). The labels scale in size based on zooming level. This helps eye-strain a lot when you zoom out or in. Debug Level 2 While the player is able to move to any position (that the physics will allow), AI driven entities in the game use a combination of steering behaviors and navigation graphs to traverse the Star Crossing world. Navigation Grid The "navigation grid" (1) is a combination of Box2D bodies laid out on a grid as well as a graph with each body as a node and edges connecting adjacent bodies. The grid bodies are used for collision detection, dynamically updating the graph to mark nodes as "blocked' or "not blocked". The navigation grid is not always displayed (it can be disabled...it eats up cycles). When it is displayed, it shows exactly which cells an entity is occupying. This is very helpful for the following: Watching the navigation path generation and ensuring it is going AROUND blocked nodes. The path following behavior does a "look ahead" to see if the NEXT path edge (node) is blocked before entering (and recomputes a path if it is). This took a lot of tweaking to get right and having the blocked/unblocked status displayed, along with some "whiskers" from the entity really helped. Navigation Grid Numbers Each navigation grid node has a label that it can display (2). These numbers were put to use as follows: Verifying the path the AI is going on matches up with the grid by displaying the navigation graph index of the grid node. For example, an AI that must perform a "ranged attack" does this by locating an empty node a certain distance from the target (outside its physical body), navigating to that node, pointing towards the target, and shooting. At one point, the grid was a little "off" and the attack position was inside the body of the target, but only in certain cases. The "what heck is that" moment occurred when it was observed that the last path node was inside the body of the target on the screen. Star Crossing uses an influence mapping based approach to steer between objects. When a node becomes blocked or unblocked, the influence of all blockers in and around that node are updated. The path search uses this information to steer "between" blocking objects (these are the numbers in the image displayed). It is REALLY HARD to know if this working properly without seeing the paths and the influence numbers at the same time. Navigation Paths It is very difficult to debug a navigation system without looking at the paths that are coming from it (3). In the case of the paths from Star Crossing, only the last entity doing a search is displayed (to save CPU cycles). The "empty" red circle at the start of the path is the current target the entity is moving toward. As it removes nodes from its path, the current circle "disappears" and the next circle is left "open". One of the reasons for going to influence based navigation was because of entities getting "stuck" going around corners. Quite often, a path around an object with a rectangular shape was "hugging" its perimeter, then going diagonally to hug the next perimeter segment. The diagonal move had the entity pushing into the rectangular corner of the object it was going around. While the influence based approach solved this, it took a while to "see" why the entity was giving up and re-pathing after trying to burrow into the building. Parting Thoughts While there were a lot of very specific problems worked, the methods used to debug them, beyond the "intrinsic tools" are not terribly complex: You need a way to measure your FPS. This is included directly in many frameworks or is one of the first examples they give when teaching you how to use the framework. You need a way to enable/disable the debug data displayed on your screen. You need a way to hold the processing "still" while you can look around your virtual world (possibly poking and prodding it). You need a system to display your physics bodies, if you have a physics engine (or something that acts similar to one). You need a system to draw labels for "interesting" things and have those labels "stick" to those things as they move about the world. You need a way to draw simple lines for various purposes. This may be a little bit of a challenge because of how the screen gets redrawn, but getting it working is well worth the investment. These items are not a substitute for your existing logging/debugger system, they are a complement to it. These items are somewhat "generic". You can get a lot of mileage out of simple tools, though, if you know how to use them. Article Update Log 30 Jan 2015: Initial release
  5. Visual Tools For Debugging Games

      Thanks.  The best part is that once you figure out the basics of what you want to show, if you build them right, you can use them across multiple projects.
  6. Estimating Effort for Small Projects

      I get that.  This is where you get to (carefully but positively) set the tone for this aspect of the relationship between you and your boss.     If the thing being estimated is small or known, the answer is usually pretty quick.  If not, it takes some time.  So I usually tell my boss something like "I can give you an off-the-cuff answer now or a more realistic number in an hour.  Which would you prefer?"  or "Can I take an hour and try to give you something believable?"   Do you think your boss honestly wants to tell his boss something that he is probably going to have to recant (or worse, explain as a gross error) because he could not wait an hour?  
  7. Estimating Effort for Small Projects

      I'm pretty sure Kirk figured out Scotty's factor was off by an order of magnitude ;).  Would you pay for (or believe) an estimate you think might be off by 10x?  
  8. Estimating Effort for Small Projects

    Overview Everybody has to report status or estimate a work task to their boss. Even "the boss" usually has to report status, if only to shareholders or the owners. This article discusses an approach using some simple formulas and Excel (or your favorite Excel substitute) to give your status a more scientific basis than "off the cuff". It also allows you to answer "what if" questions fairly quickly without a lot of "hand waving". Giving good estimates will have positive effects for you, your team, and your management (who expect you to make them look good while rewarding you with [FILL IN YOUR DREAMS AND WISHES HERE]). I may be stretching this last part a bit, or living in positive-moral-ethical-symbiotic-seeming-dreamscape that does not really exist. Trust me, though, try it out. Giving good numbers will make you feel better than pulling penguins out of your...um...imagination. Problem Statement At some point early in your career as a developer, you are going to be asked two questions that every sane developer has come to dread: What is your progress on [FILL IN YOUR TASK HERE]? When will it be finished? Initially, you will probably be asked for these "estimates" (you are not counting photons, after all) after you have already started the work. These will be used for: Figuring out if you are "getting stuff done". Enabling others to know you need help before you may realize it yourself. Keeping your nose in the code creates its own kind of myopia. Coordinating the work of others (your teammates, the test team, marketing, sales...you know...those "other folks" who go into the office as well but do not seem enthralled by what you do...yet for some reason are interested in the outcome...) so you can "join" up at the proper time. Sooner or later, you will be asked these before the work even starts and these estimates that you create will: Form the basis of how your team leader plans the tasks for the others on your team. Be used to estimate the overall project cost (and perhaps decide if it happens). Probably come back to haunt you. That is to say, plan the project, determine if it is going into the weeds, plan intersection points for the project, allocate budgets, and in general make everybody feel that the chaos is "managed". While it is true you can try to wave off or swag these questions with an off-the-cuff answer, it will usually work out better for everybody involved if you develop a strategy for answering these questions with some credibility. I Have a Great Tool If this sounds a lot like something that belongs in the Scrum or DSDM tool you have been using (Jira, Scrumwise, pick your favorite), you are correct. However, before you dash off to read a good book on Game Programming Patterns, you might consider the following: LOTS of companies do not have high-end project management tools. You may work for one already. You may work for one in the future. Better to practice it now and be ready for that interview question about how you manage your manager's expectations. Your company may work for many different clients and tools are at the project level, so you only get the good ones if you are on those projects. If the inputs to the tools have a lot of "bottom up" granularity, you might already have all you need. If they do not, you have the option of spending time putting the items into the tool or coming up with the numbers and putting a "next level up" number in. This is a decision about how much granularity you have in your tool. It is really hard to run "what if" scenarios with these tools. They are more geared to predicting based on current state. Dinking with them to flip around assignments, order of execution, weight on tasks, etc., can have unintended and complex outcomes. Sometimes the "UNDO" is REALLY hard to find. The reality is that this is a skill that is not specific to estimating a software project. It's a skill for estimating ANY project. Basic Approach As a computer scientist, the idea of giving an "estimate" may rankle you a little bit. Fortunately, many scientists have gone before us and they seem to have had some success with it, so we can skip right past the "feels icky" concern and get right to "how can we make numbers make sense". It's better than penguins. Sequential Operations The first thing you have to realize, and this will probably NOT come as a shock, is that everything you do has a "Start" and an "End". When you start, you are 0% complete. When you end, you are 100% complete. You start, go through the steps sequentially, and reach the end. It is the steps in the middle you have to count. I'm going to use the example of a rather pedestrian task, fixing bugs. Without getting too deep into the process of your company, the rough list of what you need to do to resolve a bug in a production system is as follows: Investigate the bug. Write or change some code to fix it. Perform some kind of desk check or unit test to verify it works. You may have to write the unit test. Check it in so that others can see it. Integrate your change and verify you have not destroyed the universe. Wait for QA to bless and it and close/complete it. You could just as easily have a more exciting example where you have to design a game engine; you still have individual pieces to build and the same basic SDLC steps for each one (design, code, unit test, integrate, lather, rinse, repeat, ...). The Recipe We are going to use a spreadsheet (I am using Excel, you can use any one you wish, they all support something like these operations) to keep track of the "state" of completion for each task you have to work. Practically speaking, you can really only do one thing at a time. You may be spread across other projects, but we can handle that a different way. Assume, for now, that you are going to "start", execute a series of steps to carry you along, and then finally "end" when it will be done. You assign a percentage complete (0.0-1.0, you will see why later) to each state. You assign a state to each task you must complete. Map each state to a percentage complete for the step. Add up all the "percent completes" and divide by how many there are to get the average completion (how much you are done). As this is not a course in Excel, I have put all this into a .zip file with Excel Spreadsheets in both .xls and .xlsx format. You do not have to follow this format explicitly. I am going to enumerate and describe all the elements in this particular incarnation: This is just a list of the item numbers. This way I can add charts or whatever at the top by moving the tables down and not have to worry about referring to specific "Excel" row; I always refer to #XXX. This table is for bugs. It could also be "component" or "API Method", etc. It always helps to have a reminder what the numbers refer to. No secret sauce here. These are the states you modify. Each is set up as a "Data Validation" with a "List" type (the list items are column G). I STRONGLY ENCOURAGE you to do this. Validation Lists like this stop people from randomly typing junk into things that should have a fixed set of items and breaking your house of cards. You don't let people other developers use cast to set their own values to your enum instances, right? This is a bit of the secret sauce. The value in D is looked up in G and the returned index from H is placed here. Just like a std::map/tt] lookup. This is the list of states. If you want to add a new one, just add a new element in the middle (to both column G and H) and the D/E columns will honor it. Nifty when you want to add/remove states. NOTE: I am using "past tense verbs" for states. As in "this has already been done". Be consistent in your language choice. This is the percentage looked up. A bit more secret sauce here. The space between the steps are NOT LINEAR, unless you want them to be. It takes longer to code and test than investigate, so the % complete reflects that by going from 0 - 0.2 - 0.5. A bright yellow box gives you a perfect eye-draw-point for the review where you will have to show this. It looks a little sad at 0.0% right now, though... First Pass - Basic Estimates of Completion Now that we have the basic template down, let's plug in some "actual work done" and update the numbers. So we completed two items and one of them has been unit tested. And that moves us to about 34% done. That seems pretty straight forward. The drop down on each of these boxes means you cannot fat-finger in the wrong state. One important point to "point out" is that you need to check that the states all work as expected. Move all of them to "coded" and you should get 50%. Move all of them to "integrated", 90%. And so on. Depending on how the "lookup" method works, it may require a sorted or non-sorted list for G (this one does NOT require a sorted list). Be aware of that if you start to see numbers not lining up. Always do a "unit test" to make sure you are not reporting junk. Second Pass - Better Estimates of Completion You could stop with the first pass and that might be fine. Your boss comes up to you and says, "how long will it take". You take each item, multiply it by an "average" number of hours for each and now you have the "Total Work Estimate". (1 - % Complete) X Total Work Estimate = Hours Remaining. So, you report this, get back to work, and coding bliss ensues. BUT, if you add one more "knob" to the calculation, you are going to add a dimension that lies at the heart of every savvy developer's very personal contribution to the project: YOUR KNOWLEDGE OF THE DOMAIN SPACE. If you look at the list in C, a few alarms should be going off. It is reasonable to assume that "Change Background Color" will take a considerably shorter time than "System time randomly sets to future." However, the linear-state-estimator we have gives all these tasks the same "weight" in terms of how much effort they require for that type of "state operation." What you want to do is "weight" them based on "how hard they are because you know how hard that part is going to be to fix". You can do this a lot of ways. I tend to follow the 1, 2, 4, 9 model. Also known as "trivial", "some work", "some real work", and "send out for pizza". Truth be told, this started as a square approximation for difficulty, but "2" kept showing up because there was no middle ground between "1" and "4". You can choose your own scale. The key point here is that because you have knowledge of the system, this is where you get to put it to good use. You can defend your estimates because you know "where the bones are buried". If this is not that kind of task or project, maybe you rely on your hard-earned-experience to come up with some estimates. It is still better than penguins. This is what it looks like: There are some interesting things here to notice: Our percentage completion for the same "states" we had before jumped from 34% to 63%. So completing a couple of "big chunks" up front really improves the number quickly. On the other side, if you are going through the project and you are not "weighting" but you do all the small stuff up front, you could be in for a nasty surprise, time-wise, when you start working on the bigger items. This is the advantage of using your domain knowledge to make these estimates. The "Complete" calculation consists of SUM(G)/SUM(F). The points chart is manually entered and fairly straight forward. The calculation here is just "%" X Points. A calculation for "Counts" is done by counting how many times the state (I) shows up in the states (D). This is handy for a quick look at where you are overall when the number of rows gets large. Third Pass - Time Now that we have a better estimator for how much work is in front of us and how much work has been done, we can add another dimension: Time. After all, your boss is going to still ask "how long will it take?" This is relatively easy to add. Decide how many "points" of work you can reasonably do in an hour, then do some basic unit cancellation and you get the following: I'm a big fan of "Meaningful Units". Do they still teach unit cancellation? The number of Points Per Hour is up to you, but should be reflective of the values you choose in F and your knowledge of the domain. Total Days = SUM(F) / (Points Per Hour X Hours Per Day). Days Remaining is just (1- % Complete) X Total Days. Weeks Remaining is this value divided by Days Per Week. Really, It Is Better Than Penguins Suppose you are really terrible at estimating. If you screw up a number here or there, the odds are good that you are going to go too high on some and too low on others. A funny thing happens with numbers called "The Law of Large Numbers." What this boils down to is that making and adding up a number of small estimates will average out and yield an estimate that is usually not so bad. Yes, you will royally screw up one here and there, but on average, it should work. Of course, there is ONE slight qualifier to this. You may be an "over" or "under" estimator. That is to say, you think too much (or too little) of your skills and have an internal "multiplier" on your estimates. Personally, I underestimate EVERY TIME how long it will take me to do something (so clearly my ego is healthy). But I (and I feel this is in line with most people) am consistent with my underestimation. I'm always off by about 1/2. So at the end, I always have a "multiply everything by this one factor", and my factor is 2X. DO NOT factor this in while doing your estimates...multiply it as a constant factor at the end on your Points Per Hour value. Or you can adjust your PPH value accordingly. Remember, your goal is to get a reasonable estimate quickly, not generate more work. If you don't want to figure out your factor, don't worry about it. Your boss will. If he is a good boss, he may mention it once or twice, but will probably just factor it in without telling you after that. It will be better if you come to terms with it though and just stick it in there. Playing "What If" Games Once you gotten this put together, you can play the "what if" game and answer questions quickly and easily. Your boss asks how much time can you save if they decide to abandon a fix for this cycle - Set it to "complete" or add a new state of "abandoned" and give it a % value of 1.0. Your boss says he will add a second person to do the work - Modify your Points Per Hour so you work faster (though not 2X, because nine women still cannot make a baby in one month). Your boss says "work more hours in the day" - Ok. The reason it says "6" in the sheets is because that is about how much effective actual work time developers have. You can get "more" from "crunch time", but how much more and for how long before diminishing returns make it worthless is a complicated question. That being said, you can increase the Hours Per Day, but my money says your Points Per Hour should probably go down a bit...sleepy eyes make mistakes. Your boss decides to time share you with another project. Reduce your Points Per Hour by a factor to account for this. If you are spread between two projects, you should drop your PPH by at least half (though probably more depending on your personal context switching). If your boss wants you on more projects...well...you may consider this article to be interesting. Share it with your boss at your discretion...when you run out of good options, you are left with bad ones. Conclusion If you are in the software world and think about Scrum and "burn down charts", it should be obvious that the technique presented here is definitely in the same ballpark. This technique uses a tool that is ubiquitous and the approach can be easily extended to other domains easily. Article Update Log 28 Jan 2015: Minor cleanups and added article reference. 24 Jan 2015: Initial release
  9. Estimating Effort for Small Projects

      I usually avoid tying in dates in these types of quick-tracking-and-estimating solutions.  If you need to handle dates, it is easier to start using something like MS Project (or equivalent) that understands holidays, weekends, custom schedules, etc.     I'm not saying you can't do it...but there are better tools when dates start getting involved and I am not sure you will really get what you want out of it.  I find it is easier to just say "the work will be done in X business days."  This is usually what the person who is getting the number really cares about anyway.
  10. Estimating Effort for Small Projects