 |
|
|
| Home Products Screenshots Company
How did we make Abound?
The inspiration for Abound began in 1995 at Georgetown High School where our chief architect, Devin Rose, took his first computer science class with Mr. Haynes. In addition to becoming excited about computer science, Devin was fascinated by one of Mr. Haynes' screensavers where balls bounced around the screen and eventually filled it up. You see, Mr. Haynes, being a computer science teacher, had the best computer in the school (and probably the whole district), a Pentium 100 MHz! This was when most computers were 33 MHz, even after hitting the "Turbo" button on the computer, if you remember that. Mr. Haynes also had a TV hooked up to the computer's display output, so that the class could see the code he wrote as he instructed them. Well, sometimes Mr. Haynes would leave the computer and go to the chalkboard to teach, and then his computer would be idle. Usually after 5 minutes or so, the screensaver would kick in. This is what Devin waited for. What screensaver was it? The famous After Dark screensaver collection, in particular the "Marbles" or "Balls" screensaver. One by one, balls would fly in from the top of the screen, bounce off of stationary pins and other balls, and come to rest. There was something entrancing about watching this. Though Devin dreamed of making such a cool program, the fact was he was a first year computer science student in high school, learning Turbo Pascal, and creating games or graphics programs was low on the priority list for his high school computer science curriculum. Also, Turbo Pascal is not known to be the best language for graphics out there, or for anything besides teaching, though it does a serviceable job of that. Laying the foundation Many years passed, and Devin went to college majoring in electrical engineering. Even though he liked programming better than engineering, he knew engineering was a broader discipline, and he could always do programming if he wanted to. In college, he got an internship at NASA, Johnson Space Center, where he worked in the Electronic Systems Test Lab (ESTL). Here he learned how to program in C++ and worked on a program that would allow ESTL to test the engine telemetry recorder that flies on the space shuttles. He learned a lot by annoying his mentor with lots of questions, so much so that his mentor hid from him while at work. When he returned to college, he wanted to work on his own project using C++, and since he always loved the game Tetris, he began work on a Tetris clone. Through the world wide programmer's web, he found Haakon Martinsen from Norway, who also was a young man wanting to program, who loved Tetris. Together they colloborated on a Tetris program where Devin wrote the "engine" code and Haakon wrote the graphics in DirectX. Amazingly, even though both were inexperienced programmers, they made the game work, and it even looked pretty cool! Devin and Haakon eventually lost contact with each other, but both had learned a lot about programming. Soon after this Devin graduated from college, and got a job at medium sized tech company in Austin. He continued working on his own projects, however, writing a Tetris artificial intelligence (AI) program to play the Tetris game that he and Haakon had written. The AI program used a genetic algorithm to improve its play, and eventually could get well over 100,000 lines on average. Incidentally, for an even better Tetris AI program, including a setup with image acquisition for a computer to play Tetris, check out this man's very cool project. Additionally, Devin was learning a lot about modern software design at his work. His mentor was a man who had a great love for programming and had command of a tremendous number of advanced programming skills. Devin benefited from his mentor by adopting many of his practices, including interface-based componentized programming. The dream of creating a screensaver like the After Dark Marbles screensaver kept coming back. Finally Devin decided to begin work on it. Inspiration into action Beginning in late 2003, the project was started. The project was christened with the name Abound early on, inspired by the Caedmon's Call song, Close of Autumn. Abound was a great name because the screensaver was going to be balls bouncing around the screen, "bounding" off one another. Devin made some big decisions early on about the project.
The answer: Interface-based design! Well, what does that mean? It means creating interfaces for the major components in the project. What are the components? Well, there is the engine code, which coordinates the main execution loop, so it needs an interface. Then there is the graphics code, which should implement a generic interface. Then there is the collision detection code, which should be an interface. So now we have three interfaces, and we called them:
Interface-based design helped us accomplish this in the following way. We first implemented the IGraphics interface with basic Windows GDI graphics. GDI graphics is the simple Windows API for graphics. So the idea is we first implement this interface with GDI, and then once we have the other part of the project working, we reimplement the interface using OpenGL! Here are the functions we chose for the IGraphics interface initially: interface IGraphics : IUnknown { HRESULT Initialize([in] GfxInitData* initData); HRESULT GetScreenSize([out] long* height, [out] long* width); HRESULT BeginScreen([in] BOOL eraseBackground); HRESULT EndScreen(); HRESULT DrawLine([in] POINT* pt1, [in] POINT* pt2, [in] GfxImageData* imageData); HRESULT DrawCircle([in] POINT* center, [in] long radius, [in] GfxImageData* imageData); HRESULT DrawRectangle([in] POINT lowerLeft, [in] long width, [in] long height, [in] GfxImageData* imageData); HRESULT Finalize(); }; These seem like reasonable functions for graphics. Although we want our graphics to be 3D eventually, GDI doesn't do 3D objects very well, so we went with simple 2D objects like circles, lines, and rectangles. Next we implemented the IGameManager interface, which looked like this: interface IGameMgr : IUnknown { HRESULT Initialize([in] GfxInitData* gfxData, [in] LPWSTR cmdLine); HRESULT GameMain(); HRESULT Finalize(); }; It is very simple: we can initialize it, call its main function in our execution loop, and then finalize it. It's GameMain will handle all of the work for the program. Before we implement the collision expert, we needed to know what types of objects it will be detecting collision on. So we created an interface called ICollidableObject, and if a class implements that interface, we can handle collision detection for it. We knew we wanted to have balls and walls around the borders of the screen, and we needed to detect collisions for balls hitting other balls and balls hitting walls. So we created 2 classes, one for the balls and the other for the walls that implemented the ICollidableObject interface: interface ICollidableObject : IUnknown { HRESULT GetPosition([out] double* xPos, [out] double* yPos); HRESULT GetPrevPosition([out] double* xPos, [out] double* yPos); HRESULT GetCollidableObjectType([out] CollidableObjectTypes* type); }; These functions allow the collision expert to discover where these collidable objects are on the screen and peform collision detection on them based on what type of object they are. Next we wanted to get the ball to bounce off the bottom wall object we made. So we implemented the collision expert's function that tried to detect a ball to wall collision. The ball managed to bounce off the wall, but eventually seemed to tunnel through the wall, as we had not implemented the collision function quite right. After getting ball to wall collisions working decently (by far not perfectly yet), we wanted to get balls to collide with each other. Our idea at first would be to just have one moving ball at a time, and so we would only have to worry about a moving ball colliding with an unmoving one. Devin spent days trying to figure out the collision angles and resultant velocity and angle, with little results. Fortunately, one of his coworkers who was much better at physics than he was gave him a simple solution with vectors. Now the ball was colliding with stationary balls (called pins) and walls. Things were starting to take shape. In this early going, there were all sorts of bugs: the balls would sometimes sneak through the walls and out into the nether world off the screen. They would also fly through pins instead of colliding with them, collide and fly off in the wrong direction, and generally follow physics laws very different from the ones that our world runs by.  Soon we ran into two of the most difficult problems in the development of Abound.
We hacked around this at first and put in some scrabbled together cases to try to make it work, including detecting if it kept hitting the bottom wall a lot, since eventually it should come to rest at the bottom if it kept bouncing with very small speed on the wall. Also, if it was between two pins and bouncing with very low speed, it could come to rest. This hack worked for quite some time with enough accuracy for us to live with. The second problem was also difficult. What happened was, the ball would bounce at almost the dead center on top of a pin, and then sit there on top of the pin. We had no notion of the ball being able to "roll" around anything, it was only collision detection and bouncing, so at first when we detected this case, if the ball had very low speed, we gave it a "kick" to try to bounce it out of its predicament so it could bounce off the pin. This looked very unrealistic, as the ball would almost be still and then suddenly jump like a Mexican jumping bean off the pin. Another one of Devin's coworkers came up with an idea for this problem: Make the balls go into a special rolling mode when this case is detected, where the tangential velocity is determined of the moving ball to the pin and the ball is moved along this path. This idea worked very well, and if you watch the screensaver in action you can even discern when a ball enters rolling mode around another ball. You can see it sometimes because the transition from normal motion to rolling motion is not always perfect, and there may appear to be a jump in velocity at this time.  OpenGL has been around a long time, and so we assumed that it could draw graphics very quickly and attractively. This is not completely true, at least when we first started using it. We started learning OpenGL from Jeff Molofee's NeHe site, which has excellent tutorials. To our dismay, we thought we were going to have to create spheres ourselves using simple polygons (ugh), but fortunately we found a function called gluSphere that did this for us. Unfortunately, we had a problem, OpenGL could not draw more than about 100 spheres to the screen at one time without slowing down tremendously. This was bad because our screensaver could create thousands of spheres as the screen filled up. We were using OpenGL's double buffered rendering, so we would draw to the back buffer then flip surfaces so that drawing would show up on the screen. We were redrawing all the spheres every time, and OpenGL could not keep up. So we tried to figure out what we could do to speed it up. Idea 1: Display lists OpenGL has something called display lists, where you give it a list of objects to draw ahead of time and save it as a list. So we gave it thirty stationary pins to draw and saved it as a display list. This sped things up by a factor of two, but it had one big problem. As the moving balls came to rest, they became stationary pins, but we could not add them to the display list because you can't add objects to a display list once it is created. This seemed like a flaw in OpenGL to us, but someone pointed out the difficulty in implementing such a feature. That didn't help us any, but it kept us from blaming OpenGL too much. Incidentally we considered creating multiple display lists of balls, once enough moving balls came to rest, compiling them into a list, but since the display lists were still not fast enough once you got too many objects in them, we rejected this idea. Idea 2: Scissor windows Our next idea was given to us by another of Devin's friends, who had much experience with OpenGL. Since we really only needed to update one object on the screen, the moving ball, we could use scissor windows to tell OpenGL to only update that little region. The glScissor function creates a "clipping" rectangle where only that rectangle will be updated by drawing. This sounded great, but there was a big problem with it: We could no longer use double buffering with these scissor windows, and so we would be responsible for not only drawing the balls but also erasing them ourselves before each graphics update. Previously, the double buffering solved this issue, because every new screen we redrew everything at its updated position and then flipped the old surface with the new surface. Now we had just one surface, which was displayed all the time, and we had to erase the old position of the moving ball and draw the new position. Well, no problem, we thought, we will just draw a black sphere over the old sphere, that way it will be wiped out and we can draw the new sphere at the updated position. Wrong! This didn't work because the lighting effects actually showed the black sphere on the screen, with a specular or phong highlight on it. Okay, so we could draw a black rectangle over the old ball. This too, had problems. First of all, the rectangle drew over other objects on the screen, like the pins, and so square corners were being cut out of them. Also, it caused the moving ball to flicker badly between its normal color and black. This was unacceptably ugly. We were about ready to give up at this point, as there seemed to be no way to get the scissor windows to work right. But we were given one more idea by our graphics friend. First set the scissor window to encompass the old position of the ball, then clear the depth buffer, then draw the ball at its new position, and then draw a black rectangle behind the ball. This sounds complex because it is to some degree, but it worked! The ball looked great and updated fast. Here is why it worked: The depth buffer gets cleared to the background color, which doesn't clear anything of itself, because the color buffer still has the old ball drawn in it. Then we draw the new ball, which usually overlaps the old ball by a good portion, since we are updating the screen many times per second and the ball doesn't have a chance to move too far in a few milliseconds. Finally, we draw this black rectangle just behind the ball at its old position. This causes the old object to be erased, because the depth buffer has basically pulled the rug out from underneath the old ball and just left its shadow there. Now the black rectangle fills in the depth buffer at this location with itself, blotting out the old ball. Yeah, it's confusing, but it works! The graphics could now draw very fast, since only a small window of the screen was updated each time, where the moving ball was. Multiple moving balls Abound was starting to really take shape at this point, but it was a little dull, because with just one moving ball it took a long time to fill up the screen, and there was only so much interest in watching the ball bounce around by itself on the screen. So what about having multiple moving balls, that can collide off one another in addition to the pins and walls? Great idea! How do we do it? Firstly, we need the collision detection between two moving objects, which must take the balls' masses into account, and how bouncy they are. Also, our game manager code had become hard coded with assumptions in many parts that there was just one moving ball at a given time. This had to be fixed, including the special scissor window graphics code, which now needed to keep track of multiple active windows and draw each of them correctly. For the collision detection between two moving balls, we had an excellent game programming book by Andre LaMothe. Modifying our code to now take into account multiple moving balls was more difficult, as many bugs now surfaced where multiple balls could collide at almost the same instant. Additionally, when we set more than about 10 balls on the screen, the screensaver slowed to a crawl, because we were comparing for collisions against every single object on the screen for every single moving ball, and we needed to do this 30 times per second at least to keep up the smooth frame rate. This led us to devise our own quad tree class. A quad tree is a data structure that divides the screen into 4 quadrants, then divides those quadrants into 4 more quadrants, and so on until the screen is represented in small pieces. The quad tree sped up our calculations tremendously by putting each ball and pin into a small quadrant and then only testing for collisions between objects in the same quadrant with each other..  We still had a big problem: Our program was not accurately simulating the physics for multiple moving balls. It was cheating in a big way to avoid major computation. Here is why: To truly model the physics of multiple moving objects, you need to move the objects with the smallest timestep possible before one of them hits another one. When you find this timestep, you need to move all the objects just that timestep forward, calculate the resultant velocities and trajectories, then move the smallest timestep for the next collision to occur. The problem is, what if you have 50 objects moving on the screen? Picture three of them very close to one another, hitting each other many times in a very small time frame. Well, to accurately model these collisions and not miss one of them, all the objects on the screen should only move each iteration by the amount of time of the next collision between any two of them. So even though the other 47 balls are in a totally different part of the screen and not interacting at all with these 3 who are colliding constantly, they must only update to the small timesteps of the collisions of the 3 objects. Now imagine that at any given time with 50 balls on the screen moving around, there are probably about 6 pockets of two or more balls in close proximity hitting one another. All of them must try to move, find their next collisions, but then see if they can move their whole time amount to their next collision, or whether they must move less time, since another ball somewhere else is hitting a ball sooner. This leads to very intense calculating of collisions, and makes it very hard to update the screen in smooth motion 30 times per second, which is required for good looking animation. To solve this we devised a compromise scheme between simulating perfect physics versus having glaring errors in the screensaver. We move all the balls how far they need to move after detecting their next collisions, if any occur in the normal timestep. Then we go through all the moving objects one time, and we correct the timesteps of any objects that, if we moved them how far they thought they should move, would lead to errors in the physics, like overlapping balls. This works for 99% of the cases, but not always, as you can see sometimes when balls will overlap with each other. Black Hole time One of Devin's coworkers challenged him saying: "It would be really cool if there were black holes on your screensaver, acting as gravity wells and pulling in balls." He also told Devin he would gladly pay $3 for such a screensaver with black holes. This was enough incentive for Devin to declare that Abound would have black holes! Fortunately, we had already programmed the notion of a generic force being added to an object, which is exactly what a black hole is: a force. Specifically it is a force that acts at a specific point on the screen, which accelerates objects from their center of mass to its center of mass, and whose force strength dissipates over distance by the inverse square law (1 / d^2). Conceptually the black hole was added quite quickly, although the graphic for it was just one pixel on the screen. Watching the balls twist and swerve for the first time around the black hole due to its influence was very cool! Then came the graphics for it. How do you make a good looking black hole effect? It was obvious that something needed to be swirling around the black hole's center, since that is the way they are always depicted, even though in real life of course you cannot even see one since light cannot escape them. We had an idea: Why not just create very small moving balls and apply the black hole force to them, but not the gravitational force, so that they would only be influenced by the black hole, thus swirling around it. This worked pretty well, but the balls would get flung way out of the black hole across the screen and never return. So then we added the idea of a bounding circle to a ball's motion, and if it went outside that circle, it would be automatically corrected to stay within it. You can see this motion of the balls (or motes, as Devin's mother calls them), which move around the black hole. Finally we added the idea of the number of motes circling the black hole increasing with how many balls they have engulfed. Can you guess how many balls they have to engulf before a new mote is created? Now we were sure to make one sale, at least, to Devin's coworker! Before release We were code complete at this point, at least for the main code. The screensaver code itself needed a bit more work, as all the shareware registration logic had to go into it, annoying to write at best, but necessary for shareware. Also we needed an installer to install the program on a system. We chose InnoSetup, which is easy to use and worked great. Additionally, we had been developing using an Academic edition of Visual C++. To build a professional product, we needed the professional version of Visual C++. For this we turned to Microsoft's Empower program. After creating a release version of Abound with Visual Studio 7.1 enterprise architect edition, we were amazed at the speed it ran at, easily 4 times faster than with the 6.0 academic edition version. Finally, we had been testing on Windows XP and 2000, but what about the dreaded Windows 98, which many people still use? The Empower program gave us access to Windows 98, so we installed it and tested our screensaver. Amazingly, it worked just like it did on XP and 2000! Any developer will tell you that is no small feat, as 98 has about 9800 weird things that cause programs fits when running on it. Abound 1.0 goes live We created our website and used lunarpages.com to host us. They offered a great package with good speed and bandwidth at a reasonable price. We chose BMT Micro to handle the payments from customers. They are very trusted and respected in the shareware community, and offer easy to use interfaces and good prices. On September 28th, 2004, Abound 1.0 went live for download! Devin's dream of creating a screensaver like the one he loved back in high school was finally realized. Mr. Haynes would be proud. Immediately we started receiving feedback on it and new feature requests. We are gathering these together and planning the next version for March of 2005. Submit your feedback today! |
| Site contents Copyright © 2004 Heroic Virtue Creations. All rights reserved. Contact us, Privacy Policy |
