I am honored to announce that I’ve done a guest spot regarding assembly language on the blog of well-known Mac developer Michael Ash. You can find my post at his blog. I highly recommend every one of his posts for OS X and iOS developers of all kinds. Thanks for the opportunity, Mike!
The one-year anniversary of the project to port Missions to modern Mac OS was one week and 5 days ago. I’m sorry I missed it, but as always, life puts a heck of a damper on the fun we want to be having. Still, I’ve got a few extra minutes to spend on it, and in the last few months I’ve learned a lot of new things. One of them is that having a plan is almost always a good idea! So as gift and apology, here’s the plan for the present and future of Missions of the Reliant!
I hope it’s obvious that I’ve put some thought into all of this. I still won’t have a lot of time to work on the game, but any is more than the none I’ve had lately, so expect to see updates coming again.
As always, my deepest thanks go out to you all for your patience as I’ve struggled my way through this project, and I’ll continue to do my best not to disappoint.
P.S.: I have considered making the game require Snow Leopard to play. It’s been long enough since its release that this might not be a bottleneck to most people, and it would considerably simplify some of the code; Apple added quite a few nice things to Cocoa only that recently. Please leave some feedback on this thought in the comments or on the mailing list!
While writing some code to implement a block-based callback on top of some classes which are still stuck in the target-action paradigm, I stumbled across this rather nice little trick for doing so in a category without having to do any memory management tricks at all in retain-release mode. This example comes from adding a block callback to iOS’s UIBarButtonItem (DR is for Dark Rainfall, of course):
// This category is required, but doesn't have to be in the same place. // The concept is simple, and used by several other code libraries: Because blocks are // also objects when the Objective-C runtime is loaded, a category on NSObject adds // the selector to them. Obviously it would be foolish to call this category on an object // that was not a block. @interface NSObject (DRBlockCallback) - (void)DRcallbackBlock; - (void)DRcallbackBlockWithSender:(id)sender; @end @implementation NSObject (DRBlockCallback) - (void)DRcallbackBlock { ((void (^)())self)(); } - (void)DRcallbackBlockWithSender:(id)sender { ((void (^)(id))self)(sender); } @end
// Now for adding a block callback... @interface UIBarButtonItem (DRButtonBlockCallback) - (id)initWithBarButtonSystemItem:(UIBarButtonSystemItem)item block:(void (^)(id))b; @end @implementation UIBarButtonItem (DRButtonBlockCallback) - (id)initWithBarButtonSystemItem:(UIBarButtonSystemItem)item block:(void (^)(id))b { // Call correct initializer. Provide the block callback as action, but no target yet if ((self = [self initWithBarButtonSystemItem:item target:nil action:@selector(DRcallbackBlockWithSender:)])) { // It's necessary to copy the block and hang on to it somewhere. Categories can not add // ivars to a class. Associated references were designed to solve exactly this kind of // problem. This call associates the block with this object, conveniently doing the needed // copy as well. objc_setAssociatedObject(self, "DRactionBlock", b, OBJC_ASSOCIATION_COPY_NONATOMIC); // Now when the block is retrieved back from the association, the copy is returned, which is // the target for the block callback action. self.target = objc_getAssociatedObject(self, "DRactionBlock"); } return self; } // There is no need to override dealloc. The association will automatically be dissolved when the // object is released, at which point the copied block will also be released. @end
Poof. Proper management of a block’s memory in a retain-release environment without any effort! This little trick could be further simplified by another method on NSObject, something like - (id)associateBlock:(void (^)(id))b withKey:(const char *)key;, but that’s overkill in my opinion. For completeness’ sake, I also wrapped the whole thing in #if NS_BLOCKS_AVAILABLE, though on iOS that’s probably unnecessary, as I have no intention of ever developing for <4.0 again, and even on OS X I would use PLBlocks if I had to target Leopard.
For those waiting for Missions of the Reliant news, I beg your patience. I have not forgotten!
And now one of the rare not-Missions-related posts.
I found myself with the need to run Lua code under iOS. Yes, this is legal according to the current Apple Developer Agreement. Who knew the journey I’d undertake in the process.
Originally, I got it running by just building the Lua source files into a static library and linking it in, then using the C API as usual. Worked like a ruddy charm. But then I decided to get clever. “Wouldn’t it be great,” I thought, “if I could run the bytecode compiler on the source and make them into unreadable bytecode objects?” So originally, I tried piping the source files through luac and running them otherwise as usual. The story of how I got Xcode to automate this process without a damned Run Script build phase is another one entirely.
Bad header in precompiled chunk.
Docs say, “The binary files created by luac are portable only among architectures with the same word size and byte order.” Fine. x86_64 and armv[67] are both little-endian, but sizeof(long) on x86_64 is twice what it is on armv7. Duh! Running Stuff on Apple Systems 101. Universal binary, here I come! I built lua 32-bit and lipo’d myself a nice universal binary of luac, ran it via /usr/bin/arch -arch i386.
Bad header in precompiled chunk.
What? Byte order and word size are correct. So I delved into the Lua source code. lundump.c, lines 214-226. Precompiled chunks are checked for version, format, endianness, size of int, size of size_t, size of Lua opcodes, size of the lua_Number type, and integralness of lua_Number. All of which should have been correct- until I remembered that I’d changed the luaconf.h of the iOS binary’s Lua to make lua_Number a float. It’s a double by default.
Rebuild my universal binary of luac using the same luaconf.h the iOS project uses. Run it through yet again. Lo and behold, it worked that time. It doesn’t really feel right to me running i386-compiled bytecode on armv7, but since Lua doesn’t even remotely have support for cross-compilation and I don’t feel like jumping through the hoops of making a luac utility on the device without jailbreaking, it’s the best I can do.
I would be remiss if I didn’t remark also upon the journey of learning how to make Xcode automate this process for me. There was more than just running luac to be done. I wanted my Lua scripts run through the C preprocessor, to get the benefits of #include and #define. Easier said than done. The C preprocessor doesn’t recognize Lua comments, and while because comment stripping is part of preprocessing I could have used C comments instead, it would have meant changing a goodly bit of code, and messed with the syntax coloring. And more importantly, my sense of code aesthetics. It’s always bothered me that the C preprocessor can be both Turing-complete and damn near impossible to work with (an aptly-named Turing tarpit). So I wrote a pre-preprocessor (also in Lua, naturally) to strip the Lua comments out first. But then I had to parse and handle #include manually. Oh well. The real benefit of C preprocessing is the macros anyway. It was quite an interesting bit of work making Lua talk to clang; the built-in library for doing things is a little bit lacking. Anyway, the upshot was there were three steps to processing Lua files in the iOS project: preprocess, luac, copy to Resources.
I finally caved in to my sense of danger and went looking for the extremely scanty reverse-engineered documentation on Xcode plugins. It was pretty awful. The API looks to be quite a mess of inconsistently named attributes with strange side-effects. It took me two hours to hunt down the cause of a “empty string” exception as being the use of $(OutputPath) inside a cosmetic attribute (Rule name). It was hardly perfect even when I declared it done, and then I realized I had the architecture problem again. I had to run a different luac for x86_64 than for everything else. If i386 was the only other architecture, I could’ve just let it be done by a universal binary, but no, it had to cover armv[67] too. Ultimately it turned out a second plugin was necessary, lest Xcode be sent into a downward spiral of infinite recursion at launch. Ugh. Don’t talk to me about all the horrifying effects the tiniest typo could have on Xcode. I love the one in particular where the application was fully functional, except for builds and the Quit command. Uncaught Objective-C exceptions equals inconsistent program state, people. And it’s not just that the API is entirely undocumented. You get those sorts of weird behaviors even if you never install a single plugin or specification file; the Apple developers don’t always get it right either. The application is a horrid mess, and I find myself desperately hoping that Xcode 4 is a full rewrite. I can’t discuss anything about Xcode 4 due to NDA, of course.
As a side note to all this, compiling extension modules for Lua also turned out to be an unmitigated nusiance. It turns out, you see, that the extension authors out there tend not to run their code on Darwin-based systems, and so all the ludicrous quirks of dyld tend to hit a user of their code smack in the face. Finding out that I needed to pass -bundle -undefined dynamic_lookup to the linker instead of -shared was easy enough from the Lua mailing list posts on the subject. Figuring out why that didn’t work either meant realizing I’d built Lua itself with -fvisibility=hidden for no good reason at all, causing the dlopen() calls to crash and burn. Figuring out why my self-written pcre interface module randomly crashed with a bad free() during Lua garbage collection meant debugging and valgrinding like nuts until I found out you’re not supposed to link liblua.a to the extension module. Static library + linked to both loader and module = two copies of the code. Anyone’s guess which you get at any given time. One could only wish dyld was able to make itself aware of this ugly situation.
If anyone’s interested, give a holler in the comments and I’ll post the pcre extension as an opensource project. It’s not fully featured (in particular it’s missing partial and DFA matching, as well as access to a few of the more esoteric options of the API), but it does work quite nicely otherwise. It’s built versus PCRE 8.10 and Lua 5.1, and is upwardly compatible with the still-in-progress Lua 5.2 as it currently stands.
I promise I’ll get some work on Missions done this week!
A QTKit-based video recorder is now integrated into the code. I tried about twenty ways to get it to record audio too, but between CoreAudio’s failings and QTKit’s limitations, nothing both sounded correct and remained correctly synchronized.
-itsoffset flag is not implemented by the FFmpeg commandline driver, nor correctly supported by the supporting libraries.In every case, QTKit either had no API to accomplish the task, or its provided APIs didn’t work correctly, as with FFmpeg. I wasn’t able to drop back to the old QuickTime API because it isn’t supported in 64-bit code and I intended this game to be forward-compatible.
There was one interesting side note to all this. In the process of recording video frames, I naturally ran into the issue that OpenGL and QuickTime have flipped coordinate systems relative to each other. Rather than play around with matrices, I wrote a quick in-place pixel flipping routine:
- (void)addFrameFromOpenGLAreaOrig:(NSRect)rect { NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; NSUInteger w = rect.size.width, h = rect.size.height, rowBytes = w * sizeof(uint32_t), i = 0, j = 0, rowQs = rowBytes >> 3; void *bytes = [[NSMutableData dataWithLength:h * rowBytes] mutableBytes]; uint64_t *p = (uint64 *)bytes, *r = NULL, *s = NULL; NSImage *image = [[[NSImage alloc] init] autorelease]; glReadPixels(rect.origin.x, rect.origin.y, w, h, GL_RGBA, GL_UNSIGNED_BYTE, bytes); for (i = 0; i < h >> 1; ++i) for (j = 0, r = p + (i * rowQs), s = p + ((h - i) * rowQs); j < rowQs; ++j, ++r, ++s) *r ^= *s, *s ^= *r, *r ^= *s; [image addRepresentation:[[[NSBitmapImageRep alloc] initWithBitmapDataPlanes:(unsigned char **)&bytes pixelsWide:w pixelsHigh:h bitsPerSample:8 samplesPerPixel:4 hasAlpha:YES isPlanar:NO colorSpaceName:NSDeviceRGBColorSpace bitmapFormat:0 bytesPerRow:rowBytes bitsPerPixel:32] autorelease]]; [self addFrame:image]; [pool drain]; }
No doubt the more skilled among you can see the ridiculous inefficiency of that approach. Through staring at the code a great deal, I was able to reduce it to:
- (void)addFrameFromOpenGLArea:(NSRect)rect { // All of this code assumes at least 16-byte aligned width and height // Start r at top row. Start s at bottom row. // For each row, swap rowBytes bytes (in 8-byte chunks) of r and s, incrementing r and s. // Width = the number of 8-byte chunks in two rows (rb = w * 4, rq = rb / 8, times two rows = ((w*4)/8)*2 = (w/2)*2 = w NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; NSUInteger w = rect.size.width, h = rect.size.height, i; uint64_t *p = malloc(h * w << 2), *r = p, *s = p + (h * (w >> 1)); NSImage *image = [[[NSImage alloc] init] autorelease]; glReadPixels(rect.origin.x, rect.origin.y, w, h, GL_RGBA, GL_UNSIGNED_BYTE, p); for (; s > r; s -= w) for (i = 0; i < w; i += 2) *r ^= *s, *s ^= *r, *r++ ^= *s++; [image addRepresentation:[[[NSBitmapImageRep alloc] initWithBitmapDataPlanes:(unsigned char **)&p pixelsWide:w pixelsHigh:h bitsPerSample:8 samplesPerPixel:4 hasAlpha:YES isPlanar:NO colorSpaceName:NSDeviceRGBColorSpace bitmapFormat:0 bytesPerRow:w << 2 bitsPerPixel:32] autorelease]]; [self addFrame:image]; free(p); [pool drain]; }
Much better, but still pretty inefficient when the size of every single frame is the same. Why keep redoing all those width/height calculations and buffer allocation and defeat loop unrolling? So I wrote a specialized version for 640×480 frames, with all the numbers precalculated.
- (void)addFrameFromOpenGL640480 { NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; if (frameBuffer == NULL) frameBuffer = malloc(1228800); glReadPixels(0, 0, 640, 480, GL_RGBA, GL_UNSIGNED_BYTE, frameBuffer); register uint64_t i, *r = frameBuffer, *s = r + 153280; for (; s > r; s -= 640) for (i = 0; i < 40; ++i) { *r ^= *s, *s ^= *r, *r++ ^= *s++; *r ^= *s, *s ^= *r, *r++ ^= *s++; *r ^= *s, *s ^= *r, *r++ ^= *s++; *r ^= *s, *s ^= *r, *r++ ^= *s++; *r ^= *s, *s ^= *r, *r++ ^= *s++; *r ^= *s, *s ^= *r, *r++ ^= *s++; *r ^= *s, *s ^= *r, *r++ ^= *s++; *r ^= *s, *s ^= *r, *r++ ^= *s++; } NSImage *image = [[[NSImage alloc] init] autorelease]; [image addRepresentation:[[[NSBitmapImageRep alloc] initWithBitmapDataPlanes:(unsigned char **)&frameBuffer pixelsWide:640 pixelsHigh:480 bitsPerSample:8 samplesPerPixel:4 hasAlpha:YES isPlanar:NO colorSpaceName:NSDeviceRGBColorSpace bitmapFormat:0 bytesPerRow:2560 bitsPerPixel:32] autorelease]]; [self addFrame:image]; [pool drain]; }
I took a look at the code the compiler produces at -O2, and I’m fairly sure that its assembly will run parallelized, though not actually vectorized.
Yes, I’m fully aware that glReadPixels() is slower than creating a texture. I was testing my optimization skill on the low-level C stuff, not the entire routine. I only regret I didn’t have the patience to try doing it in raw SSE3 assembly, because I recognize an algorithm like this as being ideally suited to vector operations.
“Lock phasers on target.” – Khan
“Locking phasers on target.” – Joachim
“They’re locking phasers.” – Spock
“Raise shields!” – Kirk
“FIRE!” – Khan
The Reliant now has targetting and scanning systems implemented. There’s still several bugs to work out, but the basic system is in place. When that one little fighter I put in as a test shows up, the ship can lock onto it. Of course there’s no indication on the radar (since there isn’t a radar yet) and no way to destroy it (since there isn’t a laser cannon – though there are laser couplings – or torpedo holds or torpedo launchers yet), but at least we can scan it! Or we could if fighters weren’t always unscannable. Oh well.
Still, that little flashing box on top of the fighter is darn aggressive.
The reason I don’t have more to show than a buggy targeting system is I spent the majority of the time implementing it also working out a huge mess of memory management bugs I’d been ignoring since day one. Leaks, retain cycles, overreleases, you name it. What kills me is that the Leaks tool missed all but a very few of them. I ended up with manual debugging of retain counts by calls to backtrace_symbols_fd(). As uuuuuuuuuuuuuuuuuugly as lions (Whoopi Goldberg, eat your heart out). In the end a few tweaks to the way things were done were in order. Too much work being done in -dealloc when I had a perfectly good -teardown method handy that functions much like the -invalidate suggested by the GC manual.
Why aren’t I using GC and saving myself this kinda trouble? Frankly, given my current understanding of things, I think GC would be even more trouble than this! This, at least, I understand quite thoroughly, and I have considerable experience dealing with the issues that arise. I know how to manage weak references properly to avoid retain cycles and how to do a proper finalize-vs-release model. I haven’t even gotten tripped up by hidden retains in blocks more than once! Yes, I screwed it up badly here, but that’s because I was paying very little attention. I do know how to do it right if I try, and now I’m trying.
Garbage collection, on the other hand, is a largely unknown beast to me, and from what I’ve read on Apple’s mailing lists, the docs Apple provides are very little help to developers new to the tech. The hidden gotchas are nasty devils, much worse than hidden retains in blocks. Interior pointers and missed root objects come to mind, especially since I’m targeting 10.5 where GC support was still new and several bugs in it were known to exist (and may still). Apple chose to provide an automatic stack-and-heap scanning collector, whereas I would only have been comfortable with a manual heap-scanning collector, which is really little more than autorelease anyway. In such a light, the model I’m familiar with and clearly understand seemed a much better choice than trying to learn an entirely new paradigm for this project. Ironically, I still chafe at manual memory management in C++ projects, especially the lack of autorelease, and as with GC, I don’t understand such things as auto_ptr and shared_ptr well enough to get any use of them. Templates make me cringe.
With the targeting scanner implemented, all I need to do is debug it. The next step will be to write the radar, so as to double-check that the fighter AI is working as it should and that the target scanner is de-targeting properly when something falls out of range. After that I need to test the scanner versus multiple targets, especially the new smart-targeting mode I’ve added as an easter egg. What can I say, it always drove me nuts that it targeted “the next enemy in the internal array of enemies” rather than “the nearest enemy to my ship”. But finding how to enable it is left as an exercise to you nostalgic people like me who’ll actually play this port :-).
Come on, iTunes. Jesse Hold On – B*Witched? *punches the shuffle button* 太陽と月 – 合田彩. Much better! Sorry, interlude *sweat*.
Anyway, once the scanner can handle multiple targets, it’s time to implement the third and final component of the laser: the cannon. Time to blow things up with multicolored hypotenuses of triangles! I might even study up on a little QTKit so I can take movies from the OpenGL context to show off. Bandwidth, though; this blog isn’t exactly hosted off DreamHost. (Linode actually, and they’re really awesome). Oh well, we’ll see. Maybe I’ll even leave the feature in as another easter egg…
To summarize, the current plan is:
I’m not making it up as I go, I swear!
As if all the mucking about with coordinates before wasn’t bad enough, next I had to deal with unit vectors, polar/Cartesian coordinate conversion, sign adjustment vs. trigonometric functions… you get the idea.
In this case, my problem wasn’t caused by needing to update the algorithms Mike used at all, but rather by my need to replace the old MacToolbox FixRatio() and AngleFromSlope() functions with modern trigonometrics. Now, I’d already done all this, or else the impulse and warp drives would never have worked for this long, but in poking about in the implementation for mobile enemies, I realized I’d have to generalize the code, or else end up repeating it in about a dozen places, a well-known recipe for disaster.
In literal code, warp speed goes like this:
double diffx = warpCoordX - playerCoordX, diffy = warpCoordY - playerCoordY, theta_raw = atan2(-diffy, diffx), theta = round(fma(theta_raw, RAD_TO_DEG_FACTOR, 360 * signbit(theta_raw))), // make use of theta in degrees here to calculate a turn factor maxSpeed = warpSpeed, newDeltaX = cos(theta * DEG_TO_RAD_FACTOR), newDeltaY = -sin(theta * DEG_TO_RAD_FACTOR), finalDeltaX = playerDeltaX + newDeltaX, finalDeltaY = playerDeltaY + newDeltaY; if (fabs(addedDeltaX) >= fabs(maxSpeed) * newDeltaX) finalDeltaX = maxSpeed + newDeltaX; if (fabs(addedDeltaY) >= fabs(maxSpeed) * newDeltaY) finalDeltaY = maxSpeed + newDeltaY;
Conceptually, this reads:
Why, one wonders, do I do a Cartesian->polar conversion, only to immediately convert back to Cartesian again? Answers: 1) I need the angle to calculate which way to turn the ship towards its destination. 2) The distance between current position and destination is a vector of (usually) rather high magnitude; I need to normalize that vector to get a delta. And the formula for normalizing a Cartesian vector is x/sqrt(x*x+y*y), y/sqrt(x*x+y*y). Two multiplies, an add, a square root, and two divides, all floating point. Without benchmarking I still intuitively think that’s slower (and I’m SURE it’s conceptually more confusing) than cos(atan2(-y, x)), -sin(atan2(-y, x)), two negations, an arctangent, a sine, and a cosine. Maybe I’m crazy.
Of course, typing all this out made me realize that I can, in fact, eliminate the degree/radian conversion entirely, as well as the range adjustment, by changing the conditional in the turn calculation. Once again I fell for the trap of not thinking my way through the code I was porting. At least you weren’t as bad at geometry as me, Mike :-).
Then I had to go and get really curious and benchmark it:
#include <stdio.h> #include <math.h> #include <sys/time.h> int main(int argc, char **argv) { struct timeval cS, cE, pS, pE; // Volatile prevents compiler from reading the loops as invariant and only running them once. volatile double x1 = 1.0, x2 = 2.5, y1 = 0.4, y2 = 3.2, dx = 0.0, dy = 0.0, inter = 0.0; gettimeofday(&cS, NULL); for (int i = 0; i < 100000000; ++i) { dx = x2 - x1; dy = y2 - y1; inter = sqrt(dx*dx+dy*dy); dx /= inter; dy /= inter; } gettimeofday(&cE, NULL); gettimeofday(&pS, NULL); for (int i = 0; i < 100000000; ++i) { inter = atan2(y2 - y1, x2 - x1); dx = cos(inter); dy = sin(inter); } gettimeofday(&pE, NULL); struct timeval cD, pD; timersub(&cE, &cS, &cD); timersub(&pE, &pS, &pD); printf("Cartesian diff = %lu.%06u\n", cD.tv_sec, cD.tv_usec); printf(" Polar diff = %lu.%06u\n", pD.tv_sec, pD.tv_usec); return 0; }
Foot in mouth. cos|sin(atan2()) is consistently 3x slower than x|y/sqrt(x^2+y^2) at all optimization levels. Somehow I just can’t see this as being an artifact of the brutal abuse of volatile for the benchmark.
Mike got around the whole issue, in the end. Knowing that he only ever had to calculate cos()/sin() for the angles in the period [0,35]*10, he just precalculated them in a lookup table. And cutting the cosine and sine calls out of the benchmark reduces the difference between the methods to about 1.6x, making his way a win over a four-way compare/branch for the turn calculation.
Live and learn.
Oh, and changes to Missions: Again, nothing you can see in play yet. But at least now I have the right building blocks to make the enemies from.
At last, an update!
As with the lament of all programmers faced with the demands of the technologically disinclined, I’ve accomplished a great deal, but since it can’t be seen, it might as well be nothing at all. Wasted time, the hypothetical slave driver- I mean, boss- would say. But it isn’t, I swear to all two of you who read this blog!
And now, another math rant.
Once again, as with so many things, the way Mike did things in the original code was correct and logical for the time he did it, but doesn’t fit into the object-oriented model I’m cramming his code into, despite its pitiful cries for mercy from such rigid structure. There are days I wish we were living in times when code could be so freeform as his was and still be comprehensible, but you can’t do that in Cocoa. Oh sure, I could port all the Pascal functions 1-to-1, but the Toolbox calls would be sticky at best. Anyway, in this particular case, I was trying to wrestle with the radar range calculation.
The original code reads something vaguely like: screenPos = Planetabs - (Playerabs - Playerscreen) inRadarRange = n <= screenPos / 16 <= m. Translating, this means that whether or not a given entity (a planet in this case) is within radar range of the planet is dependant upon the Player’s position in screen coordinates, as well as in the game’s absolute coordinate system.
In the old days, this design made a certain amount of sense. He already had the screen coordinates immediately handy, so why take the hit of indirecting through A5 to touch a global for the absolute position? However, my design makes the screen coordinates a bit dodgy to use. So I had to recalibrate n and m to represent distances in game coordinates.
Algebra to the rescue. The code above, reduced and replacing the inequalities, becomes the algebraic equation (x - (y - z)) / 16 = a, where a is the radar range coordinate. The only screen coordinate term in this equation is z, so solve to eliminate z:
(x - (y - z)) / 16 = a x - (y - z) = 16a - multiply both sides by 16 x - y + z = 16a - distribute the subtraction over the parenthetical expression x - y = 16a - z - subtract z from both sides
But, because both a (the radar range) and z (the player’s position on screen) are actually constants, all I had to do was take Mike’s original numbers (let’s use 64 for a and 268 for z) and calculate 16*64 - 268 = 756. Then, retranslating, the equation becomes the inequality inRadarRange = (myPosition - playerPosition) <= 756;. Repeat for the lower and upper bounds of x and y coordinates, and boom, no screen coordinates at all and I can calculate whether or not an object's in radar range based on nothing but its offset from the player.
To be clear, what I did up there was to eliminate a term from the inequalities so that they could be evaluated based on the position of the given entity in game space, rather than on the position of the entity's sprite on the screen.
I can't believe it took me a week to doodle out that bit of math.
Let me describe the setup for this issue.
Take a gobal (set property on a singleton object) list of objects which holds only weak references (in this case, if it held strong references, the objects would never lose their last retain and could never be deallocated, yes I know GC avoids it):
@implementation Singleton - (void)init { if ((self = [super init])) { CFSetCallBacks cb = { 0, NULL, NULL, CFCopyDescription, CFEqual, CFHash }; NSMutableSet *container = (NSMutableSet *)CFSetCreateMutable(kCFAllocatorDefault, 0, &cb); } return self; } - (NSMutableSet *)container { return container; } - (void)setContainer:(NSSet *)value { if (value != container) { [container setSet:value]; } } // The other KVC-complaint methods for an unordered to-many relationship // Singleton pattern stuff here @end
Now consider a class which, as part of its initialization and deallocation, adds itself to and removes itself from this singleton’s container:
@implementation ListedObject - (id)init { if ((self = [super init])) { [[Singleton singleton] addContainerObject:self]; } return this; } - (void)dealloc { [[Singleton singleton] removeContainerObject:self]; [super dealloc]; } @end
This pattern is useful when you need to track every instance of a given class – in this case, my actual code maintains the set property as a property on the class object itself rather than a separate singleton, but the result is the same and I thought I’d use something more familiar for this example.
The first time you release an instance of ListedObject to the point of deallocation, you’ll crash during your next event loop.
Next event loop? Experienced Cocoa readers will immediately guess “autorelease pool”. And they’d be right. To debug this, I added backtrace_symbols_fd() calls to -retain and -release of the ListedObject class. This may seem strange versus using a GUI tool like Instruments’ “Object Allocation” template, but I’m old-fashioned and this was simple. The object was indeed being overreleased, with the extra release coming from the main event loop’s autorelease pool.
The cause is rather intricate. At the time of the deallocation, I had a registered key-value observation on the container property. So, when the object removed itself from the list, KVO called [NSSet setWithObject:removedObject] in order to pass it as part of the change dictionary to the observer callback. This naturally went on the autorelease pool. But oops, we were already in -dealloc of the removed object, so the retain the autoreleased set tried to add was a no-op. Finally, next time through the event loop, that set was freed by the autorelease pool, and tried to call -release on the removed object, but that object had already been fully deallocated. Crash!
Now, a purist will say “stop trying to do things in -dealloc!” Others would point out that GC would bypass this entire problem. Either way, I wanted a simple solution. The problem was an autorelease pool, so just add another one!
- (void)dealloc { NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; [[Singleton singleton] removeContainerObject:self]; [pool release]; [super dealloc]; }
KVO’s set is no longer deferred-release, and all is well.
As it happens, this uncovered an underlying issue in my code, a design flaw which essentially makes the entire debacle unnecessary because the list management needed to be in other methods rather than -init and -dealloc, but I thought it was an interesting note nonetheless.
I’m back, and I didn’t give up on Missions! I’m sure there must be exactly one person out there who cares :-).
But seriously. I don’t have any new features to show at the moment, unfortunately. When I went to implement the laser cannon for the player, I realized I’d never be able to test it without something to fire at. I also realized the cannon itself would be useless without the target scanner since it has to lock onto a target. The scanner is also useless without something to scan. So, it was time to implement the base code for mobile enemies. Probably should’ve done that long ago, and here’s why…
As we all know, I’m using Objective-C to write this code. That means, among other things, that my code is object-oriented in nature. Up until this point, things like planets, starbases, and the player had all been entirely separate implementations. This is what Mike did with the original code. As always, what he did then was only sensible for the time and environment, but I can avoid a hell of a lot of code duplication by giving everything that exists in space a common superclass: a “Presence”. (Presences are themselves subclasses of the even more general “Responder”, which is used for everything that needs to process game happenings in any way, but that’s only a side note). As one can imagine, since I didn’t have the foresight to design the code this way to begin with, implementing it now required some significant refactoring.
Another issue cropped up halfway through the refactoring: The severe limitations of Apple’s built-in Key-Value Observing, which I use extensively throughout the code to avoid having to call “update this” and “update that” manually for every single affected object whenever something changes. For example, KVO doesn’t let you use blocks for callbacks, and if a superclass and a subclass both register for the same notification, there’s no way to manage the two independantly. Fortunately, Michael Ash noticed these problems some time back, and created a replacement, his MAKVONotificationCenter. Unfortunately, even the updated version published by Jerry Krinock didn’t do everything I needed, at least not in a way that I found usable with blocks added to the equation. Managing observations by tracking the resulting observation objects means having lots of instance variables to hold the observations, and since I’m building for Leopard, I can’t use the new associated objects for the purpose.
“Wait a minute,” you’re saying! “Leopard? Then why are you talking about using blocks?” Answer: I’m using PLBlocks.
So, armed with PLBlocks on one side, and Michael Ash’s typically brilliant code on the other, I dove in and pretty much rewrote the entire MAKVONotificationCenter to do three things it didn’t before:
With that done (and unit tested, and Doxygen-documented), I’m now integrating them into my revised class heirarchy for Missions itself. With any luck, I’ll have at least a screenshot of a fighter flying around before the week is out. Stay tuned, those of you who are crazy enough to stick around for all this :-).
Footnote: I was finally able to find a way to access the original model files for the game’s graphics; with some luck and a bit of help from Mike (I’m clueless when it comes to this stuff), there may be higher-quality graphics to be seen in the screenshots soon.
In the course of experimentation, I just discovered a neat trick. You can use key-value observing on a class object! Consider this simple example:
#import <Cocoa/Cocoa.h> static int Test_x = 0; @interface Test : NSObject { } + (int)x; + (void)setX:(int)x_; @end @implementation Test + (int)x { return Test_x; } + (void)setX:(int)x_ { [self willChangeValueForKey:@"x"]; Test_x = x_; [self didChangeValueForKey:@"x"]; } @end @interface Observer : NSObject { } - (void)observeValueForKeyPath:(NSString *)keyPath ofObject:(id)object change:(NSDictionary *)change context:(void *)context; @end @implementation Observer - (void)observeValueForKeyPath:(NSString *)keyPath ofObject:(id)object change:(NSDictionary *)change context:(void *)context; { printf("observed for %s, value = %d\n", [keyPath UTF8String], [Test x]); } @end int main(int argc, char **argv) { NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; Observer *o = [[[Observer alloc] init] autorelease]; [[Test class] addObserver:o forKeyPath:@"x" options:NSKeyValueObservingOptionInitial context:NULL]; [Test setX:99]; [[Test class] removeObserver:o forKeyPath:@"x"]; [pool drain]; return 0; }
And it works!
$ gcc kvotest.m -o ./kvotest $ ./kvotest observed for x, value = 0 observed for x, value = 99 $
It has some caveats, of course:
-willChangeValueForKey: and -didChangeValueForKey:[NSNotificationCenter defaultCenter] and use that.static variable to hold the value.
The only use for it I can think of offhand is when you have a class which keeps a list of its objects and provides a method for accessing that list as an array, and you want some other object to be notified when that list changes (for example, one could in theory want to observe changes in NSValueTransformer’s +valueTransformerNames). The documentation explicitly states, “Instead of observing an array, observe the ordered to-many relationship for which the array is the collection of related objects.”,
so to see changes in the list by KVO, one has to observe the property of the class itself. Classes can’t have properites (or static instance variables, come on Apple), so something like this is one way of doing the trick.
Use at your own risk!
I ran across this bit in Mike’s code, and couldn’t help but smile:
IF totalEnergy < 0 THEN totalEnergy := 0; {this line saved my sanity! Believe me, shieldLevel _can_ be negative}
I’ve met few programmers who don’t put funny comments in their code now and again. For example, here’s one of mine from the warp drive subsystem:
if (enteringWarp && velocity > minWarpVelocity) // We hit 88 miles per hour! Activate the flux capacitor!
I pity anyone whose code review guidelines forbid them from doing things like this. When trying to figure out someone else’s code, a little humor is desperately needed.
I’ve accomplished surprisingly little in the last couple of days, in functional terms. I can sum up why pretty easily: I’ve had to stop and puzzle out exactly how Michael did some of the things in his code. Player velocity, especially, is giving me grief.
This isn’t Michael’s fault. He didn’t write obscure code (well, a little…) or implement anything stupidly. The problem was his confinement to old Mac Toolbox APIs in Pascal. One does not simply toss around floating-point math in System 7. (Nor does one simply walk into Mordor, but that’s another story.) Pascal had a floating-point type (REAL), but in those days it was slower than my brain on a Monday morning. I’m not sure why, since almost every Mac since the Mac II had a MC68881 or better FPU, but we were always told to use the FixMath package for efficiency just the same. So we used fixed point types and did fun little things like this:
integerPart := trunc(Fix2X(fixedValue)); fractionPart := fixedValue - Long2Fix(integerPart);
With math like that, and manual compensation for overflow going on, I think I can be forgiven for having to stare blindly at the uncommented code for about two hours before it finally made sense to me. It’s been quite a few years since I’ve worked without native floating-point, and a lot of that time was spent dredging up the memories. 21 lines of Michael’s Pascal code, all of them necessary in the environment it was written for, boil down to a single line in modern C, and in fact a single assembly language instruction too if you care to look at things at that level. In these days of multimedia CPU extensions, if I thought it were necessary for performance I could write it such that all the calculations for all the game objects that needed to move around were done in one vector instruction (SIMD add). I don’t think it’s necessary, but the fact that I could is a sign of just how much CPUs have changed. It’s also a tribute to all those people who did it the hard way 15 years ago.
Other progress includes implementation of the sector object map (meaning planets and starbases, and their locations), reconversion of the rather broken SapirSans font (just opening it in Font Book made ATSUI whine quite loudly, and the italic variant was progmatically indistinguishable from the plain one) into a correctly-formed font suitcase by the very helpful if cryptic FontForge font editor program, and cargo, personnel, and crew management code. As usual, all of this stuff is backend and not visible in a build yet, so I have no screenshots to show. I will soon, though; now that I’ve figured out how the player moves around I can at least make the viewscreen work. Stay tuned.
P.S.: If there’s anyone who follows and enjoys the little roleplay blurbs, speak up in a comment and I’ll continue them. It only takes one voice!
Alliance Headquarters
Stardate 2310.13816640048673
In the last few days I’ve been dealing with several annoying issues, such as no one documenting that you have to turn on Core Animation support in a containing window’s content view to make the OpenGL view composite correctly with Cocoa controls. Four hours wasted on one checkbox. Sigh.
Still, there’s some progress to be had.
PICT resources into individual files and doing a batch convert to PNG. The sprites… those were a problem. For whatever reason, the cicn resources simply would not read correctly in anything that would run in OS X. Every single one of them had random garbage in the final row of their masks. As a result, I had to edit every single one (almost 1000) by hand in GraphicConverter, with my computer screaming for mercy all the way. Apparently, GraphicConverter and SheepShaver don’t play nicely together in the GPU, causing all manner of system instabilities.asm ("bsrl %2, %%ecx\n\tincl %%ecx\n\tshll %%cl, %0\n\tdecl %0" : "=r" (npo2), "=r" (r) : "1" (r) : "cc", "ecx"); for i386 and x86_64. I fall back on a pure-C approach for PPC compilation. I haven’t benchmarked this in any way, and I know for a fact that doing so would be meaningless (as the arc4random() call is inevitably far slower than either approach). It was mostly an exercise in knowing assembly language.As always, more updates will be posted as they become available.
Alliance Headquarters
Stardate 2310.12630998555023
Progress today was unfortunately small, interrupted by a sudden power outage and further stalled by an Internet service that refused to be restored, but here’s the usual list of what was accomplished.
Yep, that’s all *shame*. I suspect I’ll have better luck tomorrow.
Alliance Headquarters
Stardate 2310.11526541942353
P.S.: Neither the gibberish in the report nor the numbers in the signature are random. A copy of the latest build will be sent to the first person to correctly guess what either of them actually mean in a comment on this blog.
“For all we know, at this very moment, somewhere far beyond all those distant stars, Benny Russell is dreaming of us.” – Avery Brooks as Benjamin Sisko, Star Trek: Deep Space 9, “Far Beyond the Stars”.
Working on Missions at the level I am so far, I feel about that far away from the game’s universe. Still, there’s been a bit of progress today.
DrawString(). An time-honored and venerable way of doing things in the Mac Toolbox, but not at all suited to efficiency in an OpenGL application. Wiping out the buttons was the first step in separating them out entirely for compositing as OpenGL textures. Probably overkill anyway in the end, but keep in mind this is a learning experience for me and I figured I’d use the general code instead of special-casing this screen more than necessary.glTexImage2D() and voila, the main screen now displayed in the window! Of course, that screen was bereft of all the nice details that make Missions what it is, so I set about adding the little touches back in. The most obvious of these was the version number in the lower-right corner of the screen. It took me a while to figure out how to get the arcane combination of string drawing in NSImage and writing into an OpenGL texture object correct, but I got there in the end thanks to a little timely help. Incompatible coordinate systems and swapped RGBA/BGRA component ordering were the order of that couple of hours. Whew. A few calls to -[NSBundle objectForInfoDictionaryKey:] and several searches online for versions of the embedded fonts that worked properly later, I had the version number composited neatly on top of the background. Progress!And here’s the reward of all that hard work:
First draft of the Missions of the Reliant main screen
I know it doesn’t look like much, but as with all programming, it’s the infrastructure behind it that counts. It’s something most users never see and don’t realize the sheer difficulty of maintaining, but it’s there and it’s important. With all that structure in place, once I’ve gotten some sleep I can make much faster progress tomorrow.
Stay tuned for further updates.
Alliance Headquarters
Stardate 2310.11299452429843
Well, having the project file for Missions in place, I went to organize some of the resources – sprites, backgrounds, strings, all that fun jazz, and there’s plenty of it. In particular, I found myself re-engineering a couple of icons to support the much larger icon sizes we’ve gotten in Mac OS since the ancient days – 8-bit 32×32 icons are well and good, but how’s a 32-bit 512×512 snapshot with alpha channel sound? Pretty good? I thought so. A couple hours tweaking around in GraphicConverter and Photoshop Elements later, I had a nice large icon for the application and saved games. Of course I kept the original icon for 32×32 and 16×16 sizes.
One might ask, what the heck was I doing playing around with graphics when there’s so much code to write? There are two answers. One, that’s just the way I work: Once I get it into my head to finish a task, I get a bit exclusive about it. Two, it was fun, and a part of adding the tiny little bits of personal touch to the port. I wouldn’t want to detract from Michael’s work, of course, but at the same time I am putting in quite a bit of effort to bring that work to the modern audience, so I see no reason that effort can’t be remotely noticable.
Of course, most of the original graphics were vector models done in an old program called Infini-D. Unfortunately, I can’t find this program or anything which can read its format…
Having finished poking around in Photoshop Elements, I went to look up the fundamentals of OpenGL 2D on Mac OS X. Four hours of playing around with CGImage, NSOpenGLView, and glTexImage2D later, I figured out why the alpha channel in the PNG I was using to test was being completely ignored: I never called glEnable(GL_BLEND);. Egg on face much? Oh well. At least I finally made it work. I now have a basic setup in place with which to draw sprites and backgrounds in the game window. Not bad for a few hours and not having done OpenGL in five years, if you ask me.
At least I was vindicated in thinking NSOpenGLView had to be at least a little bit useful despite loud claims by OpenGL coders that I might as well resign myself to subclassing NSView and doing the setup by hand!
That’s about it for today. I’d like, however, to share this amusingly useful little macro with my fellow Objective-C users who aren’t in GC-land yet. I wanted a nice compact way to add a Core Foundation object to an NSAutoreleasePool without doing lots of ugly typecasts. The result was this:
#define CFAutorelease(cftyp) ((typeof((cftyp)))[((id)(cftyp)) autorelease])
Nothing like cheating a bit with typeof(); despite appearances, the expression is not evaluated twice! That let me write bits like CGColorSpaceRef colorSpace = CFAutorelease(CGColorSpaceCreateDeviceRGB()); instead of CGColorSpaceRef colorSpace = (CGColorSpaceRef)[(id)CGColorSpaceCreateDeviceRGB() autorelease];. Much more readable, IMHO. The fact that sending autorelease to nil/NULL does nothing and returns NULL is just a lovely little bonus. This doesn’t work quite right in GC code, of course, so don’t try it there.
The other thing that made me happy was thumbing my nose at all the “ARB_texture_rectangle is so useless” noise. Sure, if you’re doing fancy 3D drawing, a texture with non-parameterized coordinates and no non-clamp wrapping and no mipmaps or borders is a problem. Not so much in simple 2D. Why complicate backwards compatibility by using ARB_texture_non_power_of_two?
Those who have been using Macs for at least 14 years may or may not remember a space game for old Macs that went by the name “Missions of the Reliant”.
It was a really fun little game with a few missions in it, changable crew members in your ship, powerups for your ship, a nice big galaxy to hang around in, systems that took damage and could be repaired… if you’re thinking Rescue!, don’t, Missions was much better.
Anyway, like all the old Mac games, it’s long since nonfunctional on modern machines. But I wasn’t willing to settle for that, so I pulled up my e-mail and wrote a letter to Michael Rubin, the original author of Missions, asking if I might get the source code and take a crack at porting it to OS X.
His enthusiasm was beyond anything I could have hoped for. I’m very grateful to him for the opportunity he’s given me to bring a classic back to the Mac. I’ll be posting updates here regularly about my progress on the port.
Progress Report 1
Well, I’ve got the code, and I’ve looked it over. Ah, the old glory days of Pascal, inline A-traps, GWorlds, manual event handling… The Mac Toolbox did almost nothing for you; it was a true low-level interface to the OS, something I feel we’ve gotten away from in these days of Cocoa. Sure, OS X has the POSIX interfaces, but they’re a whole different world. Anyway, the code is a real trip back to olden times, and I love every minute of it.
First step was to create the Xcode project. That took about three hours.
Wait, what? Three hours? Well, once you figure setting up the project settings, the target settings, tweaking the things Xcode’s templates don’t get quite right, editing the pregenerated files to not have broken line breaks and incorrect heading comments, and writing the entire Info.plist for the application, that’s a lot of work! I had to look up Info.plist keys, UTI listings, sweep the original source code for the proper value of NSHumanReadableCopyright, and ask a question or two about semantics in the #macdev IRC channel.
Next step, I figure, is to sweep up all the original visual resources – strings, pictures, icons – and reorganize them out of old-style rsrc files into a modern application’s Resources folder. Yes, I’m aware you can still use resource files in OS X, but I feel if you’re going to do something, you might as well do it right!
After that, I have to take a little time out to brush up on my OpenGL 2D, it’s been awhile since I used it and I never did use it for anything this complex. Binding several dozens of textures to represent all the various sprites should be a fascinating undertaking.
I’m enjoying the hell out of myself *grin*. Thanks again, Michael!
String parsing in C is painful and annoying.
I want to parse the components of an absolute POSIX path. Here’s the code to do it in several languages.
Continue reading