Intel sponsors gamedev.net search:   
The Bag of HoldingBy ApochPiQ      
Apoch's Avatar

Apoch
XP: 64,738
Inventory
Special Items: Shpongle | XBox Live
My brain is built of paths and slides and ladders and lasers and I have invited all of you to enter its pavilion. My brain, as you enter, will smell of tangerines and brand-new running shoes.

Monday, April 28, 2008
I was coding away earlier, innocent as can be, when I suddenly was struck by an errant thought. After scolding it for interrupting my blissfully thought-free coding session, I took a closer look at it.

Turns out it was a fairly deep and important truth. In fact, I nearly came over here to write a journal entry about it - it was that good.

Now, sadly, I'm afraid the tale takes a tragic turn. I didn't feel that I could actually write an entry about it. Beginners would probably appreciate it, intermediate-level coders would recognize it, and wise old sages would find fifty ways in which I'm utterly wrong and then commence beating me about the head with rubber balloons.

So I didn't write an entry, and took a brief nap instead.


Later it occurred to me that maybe a short entry is actually OK. I mean, I know that I normally write small books every time I wander over into journal-land, but maybe it's time for some variety.

I plan to start crapping out these little tidbits whenever they pop into my brain, for two reasons. First, it will help reinforce and clarify the concept in my own mind. Secondly, someone out on the vast intertron is bound to find them useful.

So without further ado and verbosity on my part, here it is.


Observation: To actually write good code, you must keep the entire project in your mind at once. Without this, you will invariably miss some tiny detail or nuance, and this introduces inconsistency. Inconsistency is a serious source of bugs.

The Cold Harsh Reality: Doing this is very hard. It takes years of practice to increase the amount of code and logic that your mind can keep track of. However, no amount of practice makes your capacity limitless; everyone hits an upper bound somewhere along the line.

Advice: There are three main strategies for coping with this need to understand large amounts of information:
  1. Get a bigger brain (more memory)

  2. Divide the problem into smaller chunks

  3. Work at higher levels of abstraction

Method 1 is severely limited as we already saw. Methods 2 and 3, as it turns out, are deeply related to each other.

"Divide and conquer" strategies work by creating isolated "black boxes" - the stuff we commonly refer to as "modules." Each module can work by itself given some specific input and output parameters; building the final program can be thought of as stitching together lots of these modules. In today's OO-dominated culture, this usually means a class or set of classes.

Once you have a set of black box classes, you can stitch those together to create a higher level of abstraction. For example, consider these two functionally similar programs:

// Program 1
int main()
{
   float average = (4.0f + 6.0f + 10.0f + 3.0f + 15.0f + 12.0f + 1.0f) / 7.0f;
   std::cout << average << std::endl;
}



// Program 2
template <typename ValueType, class Iterator>
ValueType average(Iterator begin, Iterator end)
{
   ValueType total = 0;
   size_t count = 0;
   for(Iterator iter = begin; iter != end; ++iter)
   {
      total += *iter;
      ++count;
   }
   return total / static_cast<ValueType>(count);
}

int main()
{
   for(unsigned i = 0; i < 50; ++i)
   {
      // Assume we have a function GetNumberSet that fits in here
      std::vector<float> numbers = GetNumberSet(i);
      std::cout << average(numbers.begin(), numbers.end()) << std::endl;
   }
}



At first glance, the first program seems obviously superior: it's shorter, we can tell what it's doing immediately, and so on.

Now what happens if we need to crunch, say, 50,000 averages?

The second program is the clear winner in this case. We don't want the program to be hard-coded with 50,000 different sets of data - it would be impossible to maintain. Instead, we'd probably want program #2 with GetNumberSet coded up in such a way that it handled feeding the numbers into the average function for us.

The second program is longer and more complex than the first, but it is also more powerful. This is because the second program works at a higher level of abstraction than the first. We've created a black box - average - and now we can use it freely.

Program #2 is superior when dealing with lots of numbers because the abstraction layer lets us think about fewer elements. If we used approach #1 to handle the data, we'd have 50,000 computations to keep track of - not to mention displaying the results to the user. With the second approach, we only really need to track three things: the source of the numbers themselves, the average function, and the output.


Summary: Use whatever strategies you can to minimize the amount of detail you have to think about at one time. This will help make for more cleanly separated code, and as a bonus it will reduce defects due to oversight.

Bonus Question: Can you think of at least three ways in which program 2 is superior to program 1, besides the one already discussed?

Comments: 2 - Leave a Comment

Link



Monday, April 21, 2008
Today I quadrupled my chances of getting terminal cancer.

This may sound like a difficult feat, but in all honesty it was pretty simple: I just held a soldering iron to a lump of plastic for a while. The toxic fumes still tinge the ambience of my flat, and I now have a dull headache.

Still, I consider that my undoubtedly shortened lifespan is more than worth it. I actually melted two bits of plastic today: the first was to drill a hole in the top of my robot R2-D2; inside this hole I've mounted a simple push switch that will, eventually, chargeh mah lazer.

Now there's just a bit of wiring and reassembly left on the laser-R2-D2 mod project. I just wish I could manage to reprogram the voice recognition so I could command R2 to fire the laser off. Oh well.


The other bit of plastic I destroyed in an unorthodox manner pertains to my long-running project of building my own miniature game console. I want a totally self-contained unit. I already have the LCD and the microcontroller that will form the core of the system; what I'm missing is the actual logic to drive the LCD with some kind of active signal.

The main holdup here has been the ribbon cable that provides input to the LCD. To put it simply, the pins are damn near invisibly tiny. I can't come even remotely close to soldering my own wires onto the leads, which means I really can't send much in the way of signal to the LCD.

However, I may have a solution. Since I have a big pile of spare ribbon cables for the thing, I decided to try taking one and melting the insulation off in a few choice locations, so I could spot-solder my leads more conveniently.

Turns out that this works pretty damn well. I have five pins soldered up successfully now: the +8V rails for the backlight's inverter, and the ground leads for both the backlight and the signal circuit. This means that the screen lights up and displays a nice empty black. Opening the ground pin for the signal circuit turns the display a 1-pixel checkerboard white-black pattern.

So now my next project is to locate the input pins for the composite video support, and wire them up. These will then be connected to my VCR to see if I can get a picture on the LCD. If that actually works... I'll probably crap my pants.

Comments: 6 - Leave a Comment

Link



Sunday, April 20, 2008
I finally got motivated to start working on the R2D2 droid project again. I had a couple of ideas, and ended up picking a fairly simple one to start out with: I'm going to give R2D2 a laser eye, Terminator style.

Being a total electronic toy geek, I naturally have a few laser pointers laying around. One of them disassembles nicely into a compact piece about an inch and a quarter long, with easy leads for the power supply and a nice push-button switch all wrapped up in the bundle. I took this bit and soldered it to a battery holder from a toy FM radio, yielding this beauty:

Behold, lasers and batteries


The battery pack is hidden away inside one of the side compartments. This allows the laser to be powered independently of the rest of the droid, which decreases the chances that I'll screw something up in the inner circuitry. It also makes changing the laser batteries nice and convenient, while still outwardly invisible.

Surgery was the next point on the agenda. Specifically, I needed to actually find a place to put the laser eye, so I drilled out one of the decorative, non-functional bits on the head dome. Well, "drilled" is a dishonest term - a more accurate description would be "hacked away with a pocket knife".

This yields a nice little cubbyhole for the laser to stick out of:

The eye! It penetrates my very soul!


There's still some superglue work to be done (i.e. making the battery pack actually stay inside the compartment), and the laser needs an external switch. My plan at the moment is to put a push-toggle switch on the top of the dome; one of the blue panels is removable so you can put R2's little spy antenna up there. I'm thinking of hiding the switch under that panel.

Once that's done, it's just a bit of reassembly work, and I have my customized Terminator-D2 ready for action.


Comments: 0 - Leave a Comment

Link



Friday, April 18, 2008
I knew it had to happen eventually... but now that it has, I'm kicking myself for the choices I made.

Some of the old-timers around here may recall the old Freon raytracer project that I worked on several years ago. The goal was to develop a software reference implementation of a hardware raytracing accelerator chip. Ironically enough, the idea looked quite similar to the Larrabee project that Intel is working on.

Freon had a couple aces up its sleeve, though, including modified photon mapping algorithms that were up to an order of magnitude faster than a reference implementation of the original algorithm by Jensen. One of them has just been independently rediscovered by Jarosz.

The other worked on a similar principle, and effectively used beam tracing for the photon tracing portion of the render, and then ran a smoothing pass through a specialized adaptive kernel to ensure an aesthetically appealing gradient of the illumination values across a surface. In essence, the gradient was controlled so that it would change at a rate that was a multiple of the rate of change of the surface normal at the point of photon collision. This system also factored in the BRDF of the surface to try to minimize bias.

So there you have it - full disclosure of everything that made Freon special.

Like I said, I'm kicking myself for not acting on the research a long time ago. As cool as it is to see very close variants of my work published, it would have been even cooler to actually have blazed the trail first. Oh well, though, that's life.

The worst part is, I worked on Freon back before I had seen the light of version control - so the only copy of the code I have is in a terrible state, doesn't compile, and doesn't even include the good implementation of the lighting algorithms I had designed. So I can't even release the source code for other people to hack on.


Maybe this will light a fire under my ass and get me working on Epoch like I should be

Comments: 0 - Leave a Comment

Link



Thursday, April 17, 2008
I finally sorted out the combination of connections needed to get the on-chip debugger working for the microcontroller. I have no idea what I'm doing differently now than before, but I can run the IDE and step through code in the ROM at will.

This means that I finally have some serious potential for developing on the chip... which in turn means I really have to get off my ass and find a good project to use it for.


In the meantime, here's what I promised last time - a shot of the IDE for the NEC V850 microcontroller:

Let there be light! From the little debug test LEDs!


The test board for the MCU contains two status indicator LEDs, which are controlled by registers on the chip itself. The sample program that came with the test kit simply blinked them on and off; I modified it to have them count to 3 in binary.


I'm still interested in trying to drive the old Sharp LCD I have with the MCU; the only problem is actually physically connecting the two. The pinout from the LCD is extremely tiny, and I don't have the equipment or the steady hands required to solder it up to anything. I've been considering having a custom electronics place fab me up a little adapter board that converts the miniscule 28-pin ribbon into a larger pin grid so I can actually work with it.

In any case, the real next challenge is going to be figuring out how to output meaningful signals from the MCU. Nifty little blinky lights are one thing, but actual data is just a tad bit more complex.

If and when I come up with a good next step, I'll be sure to post details.

Comments: 0 - Leave a Comment

Link



Monday, April 14, 2008
It's been a long time ago now, but I've finally gotten around to digging up some of my electronics stuff and working on my concept of a tiny game console.

The motivation for this was a certain birthday present I recently received. Needless to say, I played with the droid as it shipped for about an hour, and then promptly struck out on the googlescape to find out what kinds of hacks people had done with these things.

A popular one seems to be to put a spy camera inside the head, but I have no real use for this. I briefly pondered adding a miniature arc welder (complete with Van De Graaff generator for lifelike sparking action!) but eventually decided against it.

I'm still not sure what to do with my R2 droid (aside from reassemble it eventually and use it as intended). However, I've definitely gotten my electronics toolkit dusted off again.


Here we can see a peek into the lair:
My workbench. Scariness indeed, Bob.


Accomplishments thus far
It took the better part of yesterday afternoon and a decent chunk of this past night, but I finally got my NEC V850 microcontroller working. I was hoping to take advantage of the on-chip debugging tools I got with it, but apparently the universe has a vendetta against me at the moment.

Instead, I simply have to compile and build the ROM on my desktop, upload it to the V850, and then run the thing by itself off a standalone power supply. This works fine when your test code is basically blinking a couple of LEDs on and off; but as soon as I want to do anything more sophisticated, I'm going to probably have to take another crack at the debugger.


Tune in next time for a glimpse of my first homebrew microcontroller code. You know you want it.

Comments: 1 - Leave a Comment

Link



Thursday, April 10, 2008
First, some background
For the past several weeks I've been working on a sort of embedded domain-specific language project. It's designed to help create simple event-trigger based missions and general game content. The details of the language itself are more or less irrelevant; they were already very well hammered out by another guy on the team before things got handed over to me.

What I've been doing lately is working on the back-end that actually executes the DSL code. Originally, the DSL was implemented on top of another DSL, which ran on an interpreter implemented in C. It's a testament to the skills of our senior programmers that the entire system performed as well as it did, both in terms of CPU time and stability.

However, for a number of reasons, the mid-level DSL is going away in the future, in favor of a purely C++ implementation of game logic. This means that the top-level DSL - the one that we use to create game content - has to be reimplemented in C++. A large part of this was already done by a couple of other guys, one of whom was the original author of the system.


The port
For the most part, the port was a success; it lacked some features, but that was primarily because the corresponding game logic hasn't been implemented yet, so the DSL had nothing to hook into. The overall principal mechanics of the system were in place, though, and working great.

Unfortunately, the port was more or less a straight copy of the code as it had been built in the mid-level DSL. That language had a number of critical differences: no floating point numerics, full garbage collection support, easy string manipulation, and weak object/class support. Compared to C++, it's a radically different beast.

The upshot of this is that the system basically relied entirely on string parsing. Behind the scenes, the type system was basically "everything is a string." This worked fine in the original implementation (largely because there wasn't really a better option), but in C++, it meant we were doing a huge amount of string munging for minimal benefit.


And now things get ugly
We decided to support floats in the DSL, as well as a few other types that could help reduce/eliminate errors for the content authors. This meant that any time we wanted to evaluate a string to see what it meant in the DSL, we had to know what type it was: integer, float, ID of a game object, and so on.

There were two basic options here. The easy out was to force the content authors to always specify what type of data they were working with. If the string "45.6" was supposed to be a seconds value, then they had to say so. If it was meant to be a number of kilometres, they had to indicate that instead.

This meant that suddenly a very friendly and accessible DSL was polluted by a lot of explicit type declarations. This cruft was really annoying, and after taking a hard look at the implications, we decided to try and eliminate it.


Making the ugly into something beautiful
We already had a good variant class implemented in the DSL's back end, so the obvious solution was to make the DSL essentially typeless from the author's point of view, and just do some intelligent type coercion behind the scenes. Any time an invalid result occurred, we could also flag it as an error and report it to the user.

This required the construction of an entirely new parser for the DSL, because the old one only understood strings. The new parser produces a syntax tree which can then be evaluated very cheaply, versus the old strings which cost a fair amount of CPU time to evaluate. Considering the fact that we may be dealing with hundreds if not thousands of evaluations per frame, this is a considerable bonus.

The downside is that a lot of logic was built to execute the DSL using... you guessed it... the old strings-based method. So scattered all through the DSL engine are countless string munging calls. A lot of the system was built rather ad hoc, so it's not always easy to locate these calls.

As a matter of fact, I'm in the middle of converting from the old to new parser in the DSL interpreter; it's tedious and mind-numbing work, which is why I'm procrastinating and writing about it instead of doing it.


Takeaway lessons
So here's what we've learned for the future:

  • Stay consistent to your DSL's purpose. If you want to make life easy and simple for the DSL authors, carefully consider any decision that increases the language's complexity. In my case, I didn't carefully consider the implications of explicit typing, and thus did a lot of duplicate work that is now wasted.

  • Plan twice, implement once. Any DSL implementation - and especially an ad hoc one - is going to take a lot of effort to rewrite when you're working with a substrate like C++. In this scenario, try not to change horses in mid-stream. Plan out exactly what the implementation should look like, and save yourself a lot of time rewriting and tweaking things.

  • Ideally, don't code a DSL on a substrate like C++. Use something like Scheme or OCaml instead, because building languages on top of C++ is like having to build your own log cabin with nothing but a dull piece of flint.



So that's what I've been doing. And now, we return you to your regularly scheduled boredom - because life after The Bag of Holding just isn't worth living.

Comments: 0 - Leave a Comment

Link


All times are ET (US)

In locus hic, omnes res dementes sunt.
 
S
M
T
W
T
F
S
1
2
3
4
5
6
7
8
9
11
12
13
15
16
19
22
23
24
25
26
27
29

OPTIONS
Track this Journal

 RSS 

ARCHIVES
July, 2009
June, 2009
May, 2009
April, 2009
March, 2009
February, 2009
January, 2009
October, 2008
September, 2008
August, 2008
July, 2008
June, 2008
May, 2008
April, 2008
March, 2008
February, 2008
January, 2008
December, 2007
November, 2007
October, 2007
September, 2007
August, 2007
July, 2007
June, 2007
May, 2007
April, 2007
March, 2007
February, 2007
January, 2007
December, 2006
November, 2006
October, 2006
September, 2006
August, 2006
July, 2006
June, 2006
May, 2006
April, 2006
March, 2006
February, 2006
January, 2006
December, 2005
November, 2005
October, 2005