Well, it took almost all afternoon, more like the past 2 - 3 hours, but the VFS Manager is also complete now. It is a very barebone version, which is why it is technically only 60% complete. It can be found here.
Some of the missing features can be fixed quite easily, while others may take a little bit of work. I think that's it for working on this for this week. I'll continue on it after I get my proposal completed.
Some of the missing features:
Well, the first portion of the work is done. This is probably like 33% of it though, since generating the VFS is the simple part. The application can be found here.
E-Day went by without a hitch and I got some interesting responses for my demos, which were very interesting on their own. I had one mother come up and ask me about prosthetics because her son had one foot amputated from knee down. That was kind of surprising because I had no clue about prosthetics, but it was good that I could kind of answer her question. Then another person asked me the time line by which an actual product using my algorithm could hit the market. That was kind of surprising too and gave me some food for thought. I told him maybe 5 to 10 years. So, overall, I got some interesting results, responses and ideas. Being such that its kind of a turning point in life for me, I'm really starting to think whether I should put aside my passion for game development and move into robotics.
Then on Saturday, I was suddenly hit with an idea on how to implement a virtual file system. It was one of those problems that I'd been working on for a while, but then the solution suddenly hit me. It seems that since my application is fairly limited in the sense that I only need a virtual file system to be able to store file and be able to pull them out, the design became quite simple. It seems that I can split the FS into multiple pieces. Then each piece contains fixed sized cells that end with pointers to the next piece and cell the next part of the file is. The calculated overhead for this is fairly low, even when including a header that contains information about which cells in a piece has information. The overhead is probably less than 1% the storage space if the cells are set at 1024 bytes each.
Checking for free space is a very simple task along with deleting files. The test system I'll build will probably be fairly small though. The VFS may be no more than a few MB in total size. Come to think of it, I had forgotten to implement the delete feature. I'll be using many Wind32 based I/O to speed things up, especially the use of file maps. The nice thing about file maps is that it is great when you are working on and modifying files of fixed size, which is what we are doing here. I wonder if I can later write a streaming wrapper for the VFS such that it supports the streaming of data......hmmm.......
The general coding of the test system is done, so I'll be building the wrappers tomorrow. This is going to be one of those very bad weeks though, since I have to finish the final draft of my proposal. My advisor's last revision kind of left it all in red.
Its finally done. My E-Day demo is finally finished. The stand alone executable version can be found here.
The interface is pretty self explanatory. I will add a readme document with more instructions later, but you can drag the 3D portion to rotate the camera and use the arrow keys to manually move the center of gravity in interactive mode.
The algorithm ended up being very crude. Not the prettiest, but it kind of works. The end result seems to be that the program will settle on a feet configuration that is most stable for most situations. So, it will mostly be one foot forward and one foot back. Kind of an interesting result. I will be putting together at least a tech report of it soon, if not a complete conference paper. The way the system is designed, it is actually scalable to multiple feet. :D
Now I need to dig around and put together a second demo. Or simply polish up one of my semi-finished stuff.
Most of the drudgery is now over with my E-Day demo. The main code is complete. Now all I need to do is to wrap it in a OpenGL based User Interface. All this being wrapped together by SDL in the frontend. The number of files have grown to being 25 files from the original handfull and its still not quite done. It should be noted that most of the code is untested and the optimization algorithm only works on a theoretical basis.
My goal right now is just to go to sleep tonight, wake up in the morning and start finishing up the user interface and 3D representation so I can start doing some serious debugging on the algorithm level. The good thing is that I somehow survived the compile portion and the code is running right now, but does nothing. I did run into some trouble with the math template I wrote. There seems to be some specific way you need to use to specifically declare template methods for specific types, specialization. The linker kept throwing me a redundant declaration error, so I just went ahead and took out some of the stuff and made everything single type. I may have to end up going back to consulting the 3DGEA book for the details on it.
From a preliminary point of view, it seems that the List and Array containers are working as they should, at least right now. I'm pretty sure I'll come across some abnormalities when I really get down to debugging the algorithm. Its one of those facts of life that no matter how perfect your coding is, there will always be minor errors. Planning ahead and being careful can reduce a ton of those, but almost never down to 0.
Over the years, I've accumulated a large volume of code from various projects. I am not very organized though and I always have the bad habit of starting from scratch every time. It wasn't until recent years that I have started doing code reuse and forcing myself to create modularity. Even with that though, I still have trouble with book keeping, since many times I have different versions of the same code present in different projects.
In the E-Day crunch time like now, I am suddenly glad that of all the code I've written, the most useful has been a Vector class that supports three componets, assignments, basic operations including normalization, cross products, etc. I was going to try and build a e-day demo without them, but alas, its just way too much work, considering all the stuff I will have to code and the time constraint I'm under. So, I pulled out my old vector class, and modified it. Yes, I added a method to overload the [] operator. Maybe not such a good idea in the long run, but sure solves many problems now.
*sigh*
The neverending conflict between good software practices and time constraints.
Man, that was kind of grueling if you ask me. The math of things is still pretty natural for me, but somehow I still grudge it. So, now, I finally have the math part complete, but not tested. I will soon be testing it for real on my E-Day project mentioned earlier. Before that, however, I still need to finish implementing the data structures for vectors and matrices, seeing that I will be operating on those ALOT. It should be fun to see the results.
With all things that have a deadline, there is always an ideal goal and a practical fall back. The E-Day demo's fall back will most likely be a 2D version which only involves the feet only, since the key is to position the feet based on the CoG. so, either way, that will be the fall back.
As project designs go, you always start out with something big and then cut and trim it down to be specific and doable. So the full 3D demo will probably be trimmed down in functionality. The base line functionality currently seems to just be having the legs be able to adjust stance while the CoG is moved around within a certain area. So, this way, we're guaranteed that the model will not shift into some unmanageable form at current phases. Later on, of course, the goal is to coax it into sort of walking, but before that, we'll just have to settle on a proof of concept.
Every year, Auburn University's College of Engineering has an open house called E-Day where we get high school students from around the area and try to make them come study at Auburn in the Engineering Department. For the past 3 years or so, I've always had a graphics demo to kind of impress some of the high school students. Of course, most of my demos were pretty crappy and did only a few neat things.
Last year, I presented a project me and my advisor was working on called IDEA (Interactive Distributed Evolutionary Algorithms). It sounds complex, but all it is is simply a network application where users (clients) can use the front end to evolve smiley faces. What the user is given is basically the task of choosing a face out of the 9 candidates they are presented with that satisfies the criterion we give. Like say, "a face that shows pain." Then the one they choose is fed to the server, thrown into a gene pool, and mutated. The user is then presented with 9 new faces based on their last choice. It really is more like distributed interactive design. The smiley faces were simple, but it could be extended to stuff like designing more complex things....like a comfortable chair. The project was eventually dumped off to others after the prototyping phase, which was like.....I think a month?
Then the year before, I presented a visualization of the 2D game of life in OpenGL. The plane that was used also had the ability to morph into a torus. It was kind of cool, but not especially thought stimulating.
Then the year before that, I showed off some of the 3D stuff I did, but those were not too interesting either, beyond the normal stuff, since back then I wasn't really into texture mapping yet.
Then, going back further, 2001, I showed a product of my particle swarm research. It was kind of funny because back then I didn't realize the importance of that piece of code. I basically built a robotic arm in OpenGL which had 1 finger. The user then moved a target around in 3D space and the finger will follow it. The cool thing was that the arm movement did not involve any form of inverse kinematics (IK) because back then I didn't know what it was either. All I did was drop in a particle swarm optimizer that tried to find rotational combinations of the joints that brought the finger as close to the target as possible. It was pretty darn fast too. With a few tweaks with wrap around search spaces and large scale local searches, it worked pretty well. It wasn't until recently that I got into skeletal animation that I realized how neat my little invention was.
So, this year for E-Day, I'm going to take the arm and replace it with legs and see if I can make legs that can shift to accomodate for a shifting center of gravity. This is the complete reverse of what most people do with the problem. From a robotics point of view, you'd be more concerned with the position of the feet and legs and how joints bend. For me, what's important is the location of the center of gravity (CoG). So, instead of a bottom up approach, I'm going with a top down approach. Well, its not really top down either. The problem will actually be tackled from both ends. The keys are the feet and the CoG. It doesn't really matter how your knees or hips are positioned, as long as the CoG is satisfying a specific criterion. So, I can then optimize the rotation of the knee and hip joints with a particle swarm with a chance of infeasible solutions. Then we bring in the research I've done with distributed constraint satisfaction and treat each leg as seperate agents that are working together for a common fitness. So, there really are 2 sets of particles being used, one for each leg. Then based on their fitness, they then decide which leg moves. Its a very interesting combination of ideas. I've completely given up "learning" and am just treating the problem as a real time optimization problem. Its processor intensive, but not memory intensive. If things go well, this may have quite a few commercial applications. Imagine a Segway with feet instead of wheels.
Its kind of funny or ironic, but though I was an applied math major as an undergrad, math is still a headache subject for me. Sort of like the fact that I used to be a swimmer, but is currently avoiding the pool like the plague. Don't ask me why because I'm not sure either.
After completing the containers for queues and stacks, and lists, I boldly went ahead to build my math module. However, all of a sudden, the sines, cosines, tangents and radians lost me. I just kind of sat there staring blank at the code. It wasn't because I didn't know how to code it up, its just a sudden reluctance hit me. I did manage to code up some basic wrappers for the built in math functions available from the C++ math library, but just sort of stopped there. I guess it was just a sudden realization of how tedious coding the whole thing would be and I just got lazy. Hopefully tomorrow I can finish what's left of the math module. As for the table look up thingy I proposed yesterday, after sleeping on it, I realized that it may not be as useful as I first thought. I will eventually test it, but since I'm sort of under a little time constraint here, I have to get some code out.
The current set of code can be found here.
I think I finally got working versions of my two containers done, array and list. Been playing with them for a while and finally got them to compile and made simple runs with them. I'll have to continue to work on the stack, queue, and maybe set containers. May build a hash table container as well, based on some of the things from the 3DGEA book.
The next step up is to start building the math modules. There is definitely a need fast math processing especially in 3D intensive applications. Probably the core has to be calculating trig values like sin and cos and stuff like that. The book presents some examples of lower precision expansions of these trig functions based on Taylor Series, but I think we can abuse the system a little more, especially when the precision we seek is below 0.001.
Based on the sample given in the book, we can easily achieve errors of less than 10^-6 with reduced versions of the sin and cos expansion, but I believe that we can reduce the process to about 3 multiplication and 4 addition operations, if not less, by generating a look up table. The nice thing about templates is that they are generated during compile time into actual classes. So, it is possible to generate a look up table of sin or cos values during compile time with the use of templates. So, we can generate a lookup table with values of more than 10^-9 in accuracy. The look up table will be based on degrees, not radians, but the class will have a radian to degree conversion, which is where 1 multiplication step is. sin and cos values are nice because they are continuous. So, we can start by generating a lookup table with 360 entries. So, what if an angle is not an integer? We can simply do an linear interpolation based on the 2 integer values its in between. This will take 1 multiplication, 2 subtraction, 1 addition, and 2 array entry accesses. All these can be done fairly easily and quicker than solving the taylor series. For sin and cos, the error is around 10^-4 to 10^-5, which is fairly reasonable. For most cases, that kind of precision is enough.
You can further reduce the look up table size in memory by exploiting symmetry in the values of cos and sin, which can at least half the memory requirement, which should be around 720B if using floating points and 1,440B if using doubles. So, the two look up tables will take up a max of 2,880B and should cover values for tan as well.
Of course, tests have to be performed to see if the speed up is worth the memory trade-off. I think i some cases its worth it. Implementation-wise, I think I'll use all three methods of calling the C/C++ math module, the lower precision fast math methods given in the book, which at least gives 4x speed up, and my look up table method. Depending on how things go though, the lookup table method may have to go. We'll see. :p
Well, been playing with my Array container and running into some issues with ambiguity on the compiler side. Let's say if I had an array of integers. If I needed to append a new element onto the array, I'd have to pass it a reference or a variable containing the value I want to append. So, that means I can't just pass it a literal, which can't be converted to a reference. However, I can't really overload a method either with only having the parameter differ by whether its a reference or not. Kind of a tricky bind. I may have to go with the non-reference solution, since it solves quite a few problems.
Also started playing with the List container. First thing I learned is that you can't encapsulate a structure within a template class unless its also a template structure. No wonder the book 3DGEA had list nodes be a seperate template class. Makes alot of seense now. The things you learn by trying the things that are wrong.
Well, I finally finished my first template container for arrays after going through like two or three references about it. I guess I really am quite new to templates. The container is currently very very barebone and does a minimum of things and have relatively little usefulness in my opinion. However, the good thing is that I think I'm starting to understand the whole concept of using references instead of pointers and "const"-ness.
Now, just need to move on to the rest of the containers.....now what were they again?
I'm not sure if its just me or anyone else, but it seems that when it comes to game development, the lower level you can write your code in, the better. In reading up on templates and the do's and don't I was fairly surprised at how little I knew about all the low level stuff of C++.....
Was kind of scary thinking that I accidentally opened like pandora's box and realized the horrors of programming....
Conclusion: Fast code and readable code don't go together quite well, at least for me.
Kind of finished an Array container, but still need to test it. Not sure how it will behave when storing an array of pointers, especially when it comes to destroying things after use. May get pretty nasty....
Seems that the first task on my hand right now is reinventing the wheel in the form of container template classes in C++. Guess I'll start working on those, since they've been long overdue anyways. And from experience, I know STL is slow. Just how much slower? Well, under Visual Studios with the MS compilers, about 5 to 6 times slower. 2 programs I wrote to crunch numbers, actually two versions. One with STL and the other was written with normal dynamic memory allocation. The result....one takes 36 hours to churn out results while the other takes only 6 to do the same things. That's quite a difference if you ask me.
We all seem to take walking for granted, and we never do realize how complex a process it is. There's all sorts of muscle coordination, balance adjustments, and not to mention that there are terrain constraints as well. However, we seem to be able to walk pretty well in general on all sorts of surfaces (at least ones with some degree of friction) and all sorts of terrain. Simulating such an activity has been quite mind boggling and in most cases, all we can do is make a system copy what we do or mimic what we do.
I believe, however, that the motion of walking can be boiled down to a few things. So, to start tackling walking, you must first tackle the problem of standing. You might think standing is easy, but its not, especially trying to keep your balance. I think that it simply has to do with the location of our center of gravity in relations to our feet. Sound simple enough? It actually is. To stay balanced, we have to try and keep our center of gravity between our feet. To be more specific, we keep it within a bounding box that can be drawn out by our toes and heels. The more centered our CoG is in this bounding box, the more balanced we our. Now, to keep balance while the CoG shifts, we need to be able to readjust our feet locations to stretch or reshape this bounding box. But no matter how your CoG shifts, as long as you can keep it within the bounding box created by our feet, you're fine. This is another reason why standing on tip-toe is tough. Since in essence, standing on tip-toe narrows the effective bounding box and makes it less tolerant to any shifting of CoG.
So, given these constraints, I believe that I can use this assumption to create a optimization function to optimize leg joint rotations such that we satisfy all the constraints and requirements of staying balanced in real-time while the CoG is being pushed around. Sounds like it would be fun simulating it :p
Everything starts somewhere and goes somewhere. The question to me however, is where I am going. To tell the truth, I have no clue where I'm going. There's always this crossroad in life where you decide to go one way or another. I'm at that place and have decided to defer that decision. Instead, I'll be working on my first 3D game engine, which has no name yet. Though my advisor constantly tells me that "you must have a cool name, or you have no project." I really don't have a name right now. Maybe somewhere down the road I'll find a name.
I'll pretty much be building this from ground up following the book "3D Game Engine Architechture" that was just published last November. I'll also be working on a few ideas on my own in the form of pathfinding and AI integration. Some call pathfinding AI, but from what I've read, well, its arguable. Since I do research in swarm and emergent behavior, I thought I'd put some of my academic knowledge to use and see what I can come up with.
I'll also be using this place to post some thoughts and ideas of future projects. One of the two ideas that are under development are a turn based strategy game where the pieces evolve their own behavior through competition and teachng a skeleton how to walk by simply moving its center of gravity around.
I will also be posting small pieces of code here as well, so, I'm open for any comments that may come my way by accident.
This can almost be seen as a development log and random OpenGL ideas dump.
