tag:blogger.com,1999:blog-26117094068399818352012-11-02T12:19:55.297-07:00DartGameDevsBleeding edge tutorials and news for game developers working with DartJohn McCutchanhttp://www.blogger.com/profile/11853082520850627688noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-2611709406839981835.post-77851579264556402722012-11-02T10:35:00.001-07:002012-11-02T10:36:17.199-07:00Free Lists For Predictable Game Performance<br />Games need predictable frame performance. Frequent memory allocations interacting with the garbage collector can make this difficult to achieve. A free list is a data structure that helps relieve pressure on the memory allocator and garbage collector, giving you predictable frame times. Read on to find out more about free lists.<br /><br />A common pattern in games is to create an object, use it for a frame or two, and then delete the object. Shortly after deleting the object, an object of the same type is created. This repeats every frame and it has a performance cost. (I’ve seen some professional engines which do this 10,000 times in a single frame! They never managed to get a 16ms frame time.)<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-RqvreL3LwhE/UJQEB98ItzI/AAAAAAAAAA8/LL8rK_k6c00/s1600/Waste_collection_vehicle-Thai.JPG" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="240" width="320" src="http://2.bp.blogspot.com/-RqvreL3LwhE/UJQEB98ItzI/AAAAAAAAAA8/LL8rK_k6c00/s320/Waste_collection_vehicle-Thai.JPG" /></a></div> <br />In languages that require manual memory management, like C++, the cost of frequent construction / deletion of objects can be high but the programmer can control when it happens in the frame. Good programmers go a step further and use pool or fixed block allocators, further reducing the cost of frequent object creation. In languages which automatically manage memory through garbage collection, like Dart, there is no explicit “delete this object now” mechanism— it happens whenever the virtual machine decides is a good time. If it happens at the wrong time the game may miss a frame and appear janky. In order to create high performance games in languages like Dart, you must avoid creating garbage.<br /><br /><b>The Free List</b><br /><br /><script src="https://gist.github.com/4002832.js"> </script><b><br /></b><b id="internal-source-marker_0.12510621454566717" style="font-weight: normal;"><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Key points:</span></b><br /><ol style="margin-bottom: 0pt; margin-top: 0pt;"><li style="font-family: Arial; font-size: 15px; list-style-type: decimal; vertical-align: baseline;"><b id="internal-source-marker_0.12510621454566717" style="font-weight: normal;"><span style="vertical-align: baseline; white-space: pre-wrap;">It can be constructed empty or given a list of objects that are already allocated and unused.</span></b></li><li style="font-family: Arial; font-size: 15px; list-style-type: decimal; vertical-align: baseline;"><b id="internal-source-marker_0.12510621454566717" style="font-weight: normal;"><span style="vertical-align: baseline; white-space: pre-wrap;">When an object is no longer being used, you return it to the free list by calling the add method.</span></b></li><li style="font-family: Arial; font-size: 15px; list-style-type: decimal; vertical-align: baseline;"><b id="internal-source-marker_0.12510621454566717" style="font-weight: normal;"><span style="vertical-align: baseline; white-space: pre-wrap;">When you need an object of type E instead of calling new E you call getNextFree.</span></b></li></ol><b id="internal-source-marker_0.12510621454566717" style="font-weight: normal;"><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;">What to do when the free list is empty?</span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">It is possible that when your program first starts or suddenly needs many objects that the free list becomes empty. At this point getNextFree returns null and you have to construct a new instance of type E. Later on, when this new instance is no longer needed, this new instance can be added to the free list. Transparent support for this could be added to the FreeList class which now looks like:</span></b><br /><br /><script src="https://gist.github.com/4002874.js"> </script><b style="font-weight: normal;"><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"><br /></span></b><b id="internal-source-marker_0.12510621454566717" style="font-weight: normal;"><span style="font-family: Arial; font-size: 15px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;">Constructors</span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Because the objects returned from the free list are already constructed you must be careful to decouple your constructor logic from your actual constructors. You can do this easily in Dart by having all constructors call separate object initialization functions, like this:</span><br /><br /><script src="https://gist.github.com/4002897.js"> </script> <span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Now objects returned from the free list can be initialized using the same logic that is used when “new” is called.</span></b><br /><b style="font-weight: normal;"><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"><br /></span></b><b id="internal-source-marker_0.12510621454566717" style="font-weight: normal;"><span style="font-family: Arial; font-size: 15px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;">Care Required</span><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Free lists make it easy to shoot yourself in the foot. If some code holds a reference to an object that was added to the free list you’ll have an object that is being manipulated from two places that should only be manipulated from one. Closures make this even trickier because your callback function may not be called until much later, possibly after the object was added to the free list. Be careful.</span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">One solution here is to hide the object references themselves behind a proxy object or integer handle.</span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;">Statistics!</span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Free lists come with a side benefit of being able to track the current allocation count, high water mark and other statistics. If the current allocation count keeps climbing, you may have a leak.</span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">These statistics can be used to tune how many free objects should be kept around and how many objects should be pre-allocated and used to initialize the free list.</span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;">Conclusion</span><br /><span style="font-family: Arial; font-size: 15px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;"></span><br /><span style="font-family: Arial; font-size: 15px; vertical-align: baseline; white-space: pre-wrap;">Free lists are an important tool to use in your quest for predictable performance. They avoid unnecessary allocation load, provide a central location to track object life cycle statistics, and force you to decouple your object initialization logic from the constructors themselves. </span></b> <div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-yetGrOOIrOM/UJQEMQAwfOI/AAAAAAAAABI/2nmvQKdCwt0/s1600/Recycling_symbol.svg.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="310" width="320" src="http://4.bp.blogspot.com/-yetGrOOIrOM/UJQEMQAwfOI/AAAAAAAAABI/2nmvQKdCwt0/s320/Recycling_symbol.svg.png" /></a></div> <div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/2611709406839981835-7785157926455640272?l=www.dartgamedevs.org' alt='' /></div>John McCutchanhttp://www.blogger.com/profile/11853082520850627688noreply@blogger.com3tag:blogger.com,1999:blog-2611709406839981835.post-32653767380553677712012-10-26T14:08:00.001-07:002012-10-26T14:16:12.576-07:00Spectre Graphics Library #2 Debug DrawingTo the uninitiated it might be surprising that game and graphics programming is mostly math. From physically simulating a box falling, to an enemy determining what angle and velocity to throw a grenade so that it lands near the player—It's all math. Having a way to visualize these calculations while the game is being developed is an incredibly powerful debugging tool. It's much easier to debug an aiming problem by being able to see the arc of the grenade versus studying a bunch of numbers. In this post I'm going to show you how you can add a DebugDrawManager to your Spectre game and easily draw things like lines, arrows, coordinate systems, and spheres in your world to help you debug that tricky math problem.<br /><br /> <div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-EImDPRpYrt0/UIr9MTiyFhI/AAAAAAAAAAo/Ux5FqHdgsxM/s1600/Untitled.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="270" width="480" src="http://4.bp.blogspot.com/-EImDPRpYrt0/UIr9MTiyFhI/AAAAAAAAAAo/Ux5FqHdgsxM/s320/Untitled.png" /></a></div> <br />Adding a DebugDrawManager is easy:<br /><br /> <script src="https://gist.github.com/3961371.js"> </script> Now that you have a debugDrawManager you can add debug primitives to be drawn: <br /><br /> <script src="https://gist.github.com/3961398.js"> </script> All Spectre Debug Draw primitives can be drawn for a fixed amount of time. This is important because it allows you to fire off a debug draw request right where you compute it and the DebugDrawManager will remember the values until they should no longer be drawn. <br /><br />The only thing left is to update the DebugDrawManager in your game loop and draw it. <br /><br /><script src="https://gist.github.com/3961441.js"> </script> <br />It only takes 6 lines of code to add a Spectre DebugDrawManager to your game. Once added you can draw the following primitives for any length of time in any color: <ul><li>Line</li><li>Sphere</li><li>Circle</li><li>Axis Aligned Bounding Box</li><li>Coordinate System Frame</li><li>Cross</li></ul> Next in the Spectre Graphics Library series I will discuss the resource manager, which magically refreshes your assets while your game is running!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/2611709406839981835-3265376738055367771?l=www.dartgamedevs.org' alt='' /></div>John McCutchanhttp://www.blogger.com/profile/11853082520850627688noreply@blogger.com0tag:blogger.com,1999:blog-2611709406839981835.post-73742833093025407192012-10-24T13:33:00.002-07:002012-10-24T13:33:40.252-07:00Building Interactive Content with HTML5 Canvas and Dart<a href="https://plus.google.com/110066012384188006594/posts">Kevin Moore</a> ran an excellent Hangout on building interactive content (games!) with HTML5 Canvas and Dart. He wrote a minesweeper clone—Pop, Pop, Win! <div></br></div>Be sure to checkout the <a href="https://github.com/dart-lang/pop-pop-win">source code</a>. <div></br></div><iframe width="560" height="315" src="http://www.youtube.com/embed/mjNOxR6-soQ" frameborder="0" allowfullscreen></iframe><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/2611709406839981835-7374283309302540719?l=www.dartgamedevs.org' alt='' /></div>John McCutchannoreply@blogger.com0tag:blogger.com,1999:blog-2611709406839981835.post-49842482629836693582012-10-24T13:26:00.001-07:002012-10-24T13:26:26.155-07:00Spectre Graphics Library #1 Hooking Up A CameraEvery 3D game needs a camera. If you're implementing a first person perspective game, <a href="https://github.com/johnmccutchan/spectre">Spectre</a> has a camera and camera controllers built in.&nbsp;Adding a FPS style camera with Spectre is really easy. In this post I will walk you through the four steps:<br /><ol><li>Creating a camera</li><li>Creating a camera controller</li><li>Updating the camera controller based on user input</li><li>Update the camera every frame</li></ol><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-MIsVFKpw8Nk/UIhJCdppT8I/AAAAAAAABvA/91w9_DpEhFY/s1600/G2Panaflexclosed.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="237" src="http://3.bp.blogspot.com/-MIsVFKpw8Nk/UIhJCdppT8I/AAAAAAAABvA/91w9_DpEhFY/s400/G2Panaflexclosed.jpg" width="400" /></a></div><div><br /></div><div>Step 1: Create the camera</div><div><br /></div><script src="https://gist.github.com/3948486.js"> </script> The code is self explanatory. The camera is sitting 2.5 units down the Z axis and focused on the origin. The aspect ratio of the camera is 16:9. <div><br /></div>The camera has the following knobs: <ul><li>Camera position</li><li>Camera focus position</li><li>Aspect Ratio</li><li>Field of view</li><li>Near cut off plane</li><li>Far cut off plane</li></ul> <div><br/></div><div>Step 2: Create the camera controller</div><div><br/></div><script src="https://gist.github.com/3948546.js"> </script> <div><br/></div><div>Step 3: Updating the camera controller based on user input</div><div><br/></div> <script src="https://gist.github.com/3948569.js"> </script> Lots of code there. From the top: <ol><li>When a W,A,S, or D key is pressed down update the camera controller to move in that direction</li><li>When the mouse is moved and we are in pointer lock mode, accumulate the mouse movement</li><li>When the the canvas is clicked, request pointer lock mode</li><li>Hook up DOM event handlers to call our functions when the mouse or keyboard is active</li></ol><div>Step 4: Update the camera every frame</div><div><br/></div><script src="https://gist.github.com/3948613.js"> </script> <div><br/></div>The above four steps will give you a working FPS style camera for your 3D game. Once you have this working you will be able to fly around the world using W, A, S, and D keys and your mouse. By using pointer lock the mouse pointer will never move out of the window and stop functioning. <div><br/></div>Next time: retained mode debug drawing.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/2611709406839981835-4984248262983669358?l=www.dartgamedevs.org' alt='' /></div>John McCutchannoreply@blogger.com0tag:blogger.com,1999:blog-2611709406839981835.post-16304286283462905432012-10-20T09:32:00.003-07:002012-10-20T09:32:21.617-07:00IntroductionsWelcome to <a href="http://www.dartgamedevs.org/">www.dartgamedevs.org</a>. Your one stop for all the latest news and tutorials on <a href="http://www.dartlang.org/">dart</a> game development.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/2611709406839981835-1630428628346290543?l=www.dartgamedevs.org' alt='' /></div>John McCutchanhttp://www.blogger.com/profile/11853082520850627688noreply@blogger.com0