In Objective C you can easily retrieve a class by name and instantiate it:

Class clss=NSClassFromString(@”Foo”);
id foo=[[clss alloc]init];

The above is perfectly equivalent to:

Foo* f=[[Foo alloc]init];

If your package doesn’t provide a Foo class, clss will be nil.

Sometimes it’s a good idea to make sure that the class you retrieved is a subclass of a base class or complies to a protocol; for example you can use this.

BOOL okay=[clss isSubclassOfClass:FooBase.class]

There are a few uses for this. Notably this kind of technique is useful to serialize runtime graphs.

Sometimes also, you want to break type dependencies at compile time,

For example let’s say you have a ‘game shell’ module. You want to reuse the model to run various games. Each game you have may then have it’s own game class. Your game shell might retrieve the name of the game class from a plist and dynamically instantiate it. There are other tricks you might use to achieve the same goal (e.g link the same header against concurrent .m files) but I think this way of doing it is clean and simple.

Similar tricks can be found on pilky.me, and for somewhat frightening(?) hacks of the ObjC runtime, you can read an article on Phrack Magazine.

18th of January (hissing wind, desert sand, husky narrator voice).

“I was looking for a title for my next series of articles when I look up Wikipedia, who apparently decided to bully their users into… …what? Challenging the US congress?”

This obviously has nothing to do with me – writing from my favorite coffee shop in Beijing, I am staring doubtfully at a banner offering three equally enticing options:

• Facebook (blocked)
• Google+ (crippled)
• Twitter (blocked)

Imagine a world without Facebook, Google and Twitter. Imagine my world.

Facebook/ the champion of phatic communication (opted out in 2006).

Google+/ from the guys who pitifully stabbed Firefox using Chrome just when we thought the browser wars were over.

Twitter/ a puzzling social platform priming concision over clarity. With a 140 characters limit, may appeal to regex coders.

No regrets. Be assured we got our own trash and the restrictions don’t do much other than promoting local platforms and boosting the economy.

One thing we do have is Wikipedia. Asking why? Hey maybe Wiki is way too very useful to get all their pages banned anywhere in the world (1)

Jimmy Wales, check your encyclopedia. If Washington makes you feel uncomfortable, there are slightly under 196 countries who will be very willing to host your servers.

Maybe less offensive, the decision not to translate their call to arms despite opting for a worldwide ban. I empathize with scores of users anxiously wondering why Wikipedia is banned in their country today.

And what with the dumbass banners begging for money? Since you guys integrated ads in your mix, how about you played the real ones to finance your s**t? You’d even get pocket money to fight the creepy adpedia virus clogging your system.

Notes

(1) Yea, there are a few countries that block wiki or just certain pages – or just in certain places like US schools. I tried to get the list but it’s in Wikipedia, which got banned banned by Jimmy Wales today. Sorry guys.

I started getting my next app ready to release. I’m looking into small things – icons, launch images and the like. This article is mainly about compliance. It is meant as a quick reference if anything and may be little help if you have never released an app before. You can check references at the bottom of this article if you’re looking for comprehensive information.

Finally, keep in mind that this kind of information easily gets out of date. Even if you find this article useful please check every information using reliable sources.

Launch images

XCode 4.2 (for iOS5) will rename images using the following convention:

Default.png, Default@2x, Default-Portrait~iPad, Default-Landscape~iPad

Default-Landscape~iPad won’t work on my iPad running iOS 4.3.

Using these names instead: Default-Portrait, Default-Landscape (without the ~iPad extension) works and the images still appear in XCode.
However using this method, so far I only got Default-Landscape to be recognized (may need to refresh build completely)

Another way to fix the issue is to add keys in the info.plist:

UILaunchImageFile, UILaunchImageFile~ipad

There is a Q&A about that.

App icons summary

iPhone: 57×57 (Icon.png)
iPhone (retina): 114×114 (Icon@2x.png)
iPad: 72×72 (Icon-ipad.png)
iPad (spot): 50×50 (Icon-spot-ipad.png)

Icon-settings.png 29×29

iTunesArtwork.png: 512×512

Note 1: I am not sure whether names are needed depending on the plist configuration; however keeping names is also good to maintain backwards compatibility.

Note 2: In XCode 4.2, if you add icons to the summary view, XCode will duplicate and rename the icon file, even if the icon file is already added to the project and already uses the correct name. If the icon is correctly named and you don’t to keep the duplicates (for example because your project folder is organized in a different way), I think it’s okay to delete the duplicates (icons still appear in the summary view). Additionally XCode adds entries to the info.plist automatically. Apparently older entries may not be overridden so doing a little house keeping may be necessary.

Caveat: in iOS5, it seems that there is a new info.plist entry for icons and this may require adjusting the ‘gloss effect’; check
CFBundleIcons > CFBundlePrimaryIcon>UIPrerenderedIcon, which apparently overrides it’s namesake in the plist root.

Universal apps

In XCode 4.2 some work will be done automatically when you switch to universal app, e.g. copying MainWindow.xib. The UI will look so-so and require corrections. In some situations the same xib file can be used for both (if the UI is simple) – obviously designing a dedicated UI is the best.

Other than MainWindow-iPad.xib (wired from the info.plist), it is the developer’s responsibility to point at the correct xib files.

References

For launch images and icons, check this comprehensive article on the OOPS tech blog

Also check: iPhone Dev 101 – size of UI elements

Today I purchased a Sony Ericsson Experia X8. It appears to be running Android 2.1.1 and is therefore officially out of date. I’ve been curious about Android for a long time. As a user I care little (got my iPad2). As a developer I feel that it may be a bit early to jump onboard. Overall I find the user experience off-putting, sugar substitute and less of the real thing.

Despite endless choices and attractive price tags, app gourmets will be disappointed. Incidentally none of what follows refers to hardware specs, so getting the latest model isn’t a fix.

I’d love to see more innovation from the iPhonoid team. Is iOS doing a lot more than scrapping overlapping windows (possibly one of the worst design ideas borrowed from Xerox), keeping icons lined up and beautifully taking advantage of haptics and UI design metaphors? Surely there is more to mobile UIs than merely copying the core user experience and the form factor? Sadly enough lawyers may be cheaper and safer than innovation, at least in our galaxy.

My new phone came installed with a load of krapps but…

…let’s not get ahead of ourselves. I talked with my girlfriend (who started with an iPod touch, lost a 3GS and sold an iPad2) and suggested that she might use my iPhone4 until 5 comes out, and I would get myself something ‘middle range’.  I could buy an Experia Play with a 30% discount over list price, or a low range HTC for 40% less – but I’d rather save my money to buy the next PSP and anything under 200 bucks felt somewhat flimsy.

So I got an X8 and it runs average 3D content around 20-30 FPS – pretty much what a 2nd gen. iOS device did a couple of years ago.

First contact

After installing an SD card (I somehow put into my head that this might be needed to play games, and apparently it is), I fired the thing up and hurriedly glossed over the setup wizard (nice touch tho’). I then connected to our WIFI and felt growing frustration as I could browse the web but couldn’t log into my google account (needed for gmail and the android store). Then I realized I forgot to set the date. Well yea, but it would be nice to pop up ‘certificate not valid yet’ instead of the ambiguously quizzical ‘no reliable connection to the server’.

The krapps I need, the hand that feeds

Learning how to remove things is always good. Understanding how to do it on iPhone had been somewhat of an accidental discovery. After removing a dozen of these (one reported ‘failed to uninstall correctly’) and removing the icons (somehow resurrected as ’shortcuts’ after deleting the apps), I noticed with some frustration that way too many apps remained, and these apps cannot be removed (without jailbreak or so called ‘rooting’). I don’t need Crazy Penguins (by no means a shiny demonstration of state of the art technology). I don’t need Facebook (who does?). No more than I needed the sticky Nike app on my iPhone (or YouTube, which I can’t access anyway).

If I can’t even clean my desktop, ‘Open System’ is off to a bad start. And by the way throwing in a couple of demos, like videos and a bit of realtime 3D, might have encouraged me to get something higher-spec-ed. Oh well.

After a hopeful reset to factory settings (which resurrected Krapps that weren’t there before along with the utterly definitely irretrievably sticky ones) I noticed, somewhat puzzled, that Ericsson made their own game store, ‘PlayNow’ something optional. I didn’t delete it, having a look at their offer was one of the reasons I wanted to get an Ericsson phone in the first place.

Essentials (less is more)

Even without a whole page of annoying stuff that can’t even be dumped in a group, my phonetop would look cluttered. Amusingly there are 3 separate apps for timer, alarm and clock.

There are also two mail apps including mobile gmail and foobar mail. I’d like to believe they use a completely different protocol unfortunately that’s not the case. foobar mail can receive gmail, and although it looks rudimentary at first sight, it works.

I can’t get mobile gmail to work on my Android phone. My guess – a little glitch that only affects ‘unlucky users’.

Shopping

After pushing all the krapps on page 3 (at least until I get my hands on the Sun’s famed Page 3 Widget For Android) I headed for the marketplace and the PlayNow store.

The marketplace gracefully skips all paid apps. This has given rise to a Chinese legend according to which ‘everything is free on Android’. The bleak truth is that the best stuff isn’t free stuff, and the paid stuff isn’t available worldwide until you root (a.k.a jailbreak) your Android phone (may also require a foreign credit card). Paid apps aren’t available in all countries.

PlayNow vaguely hints at a server or connection issue. It would be so much easier to just say it: PlayNow is only available in 13 countries (apparently doesn’t include the US or Australia. WTF ). A-ha! Here is why SE gracefully allows the frustrated, bewildered user to uninstall PlayNow. How ingenious, how considerate! Millions of frustrated game-jocks can now get rid of the neutered game widget after only minutes of intense frustration.

Back to the Android marketplace, it’s a boring list of… …apps. No editorial. Nothing like decent, well organized features, enticing layouts or attractive banners. Nothing like a shop. Even the (defunct?) Ovi store looks better in some ways (except for making downloading apps a major pain). While it might take the average iPhone gamer at least a year to touch the bottom of the top 200s (with all the minimally well organized sections and subsections), it took me just under 2 minutes to give up and head off to Android Games on Appo.

The problem is, assuming our average user haven’t drowned under the 5 pages of krapps bundled with their phone, the Android marketplace does little (precisely, nothing) to advertise apps as shiny little gems that everybody must dig into – the brilliant antithesis of itself, brought to you by the very same company that made one size fits all its anthem.

So I’m not really surprised given the lack of polish that user comments are badly spelled and the sparse categories are filled with irrelevant apps that belong nowhere. The window is already broken. iPhone users like the app store enough that they (seldom) deface it with ugly, idiotic comments (I love receiving abuse in my support email instead of reading it in the comments section and ‘being the last one to know’). iPhone developers know their apps might get rejected, many fear that putting their app in the wrong category may result in a rejection assorted with weeks or months of ‘quarantine’.

The best way to advertise your shiny Android app is to make an iPhone version and submit it to Apple. If you make a good app, it will appear in one of the many top 200s. But that’s not the point. The point is App Store bling bling casts an aura on every little app. After looting the main chambers dedicated app geeks go on questing, looking for the famed hidden gems, passing on the knowledge and keeping your sales alive with neatly written, educated reviews.

I know there are local stores – just uninstalled one because I don’t read Chinese – whereas there won’t ever be anything but a localized app store on the iPhone. Call it many more opportunities, what I see is a fragmented market and sub-critical business models (freemium without alternative, advertisement a must and quality content an accessory).

Conclusion

1. My Android phone needs a jailbreak. Ironically I never had much of a need to jailbreak an iOS device (so I didn’t). With an open OS, every manufacturer and operator along the chain can push whatever content they please until this gets delivered to the end user, all neat and frozen. Clearly Google took precious little steps into making sure that these guys wouldn’t spoil the fun (but hey, it’s not GNU. Ain’t you tired of all the angel company buzz anyways?). I need a jailbreak just so I can buy apps(!). I need a jailbreak to get rid of the krapps. Heck I might even install an iOS emulator.
2. Google aren’t interested in selling apps. The (Apple) App Store, the submission process, the presumption of censorship and partiality, that’s all work put into creating a store that’s inviting and engaging – for the worse, and definitely for the better.
   The Android marketplace owes it’s momentum to the App Store. Without the latter, it might take substantial advertisement budgets and a complex network of publishers and distributors to sell apps on Android. In other words apps will get more expensive, 90% of app users will use a cracked version and indies will go back to the day job (Bye bye to the buzzing and vibrant community of happy-go-lucky developers that brought you Angry birds, Doodle Jump and Tiny Wings).
3. If you want an affordable, modern handset and don’t wanna be appy, an Android phone is no worse than an iPhone, and a lot cheaper if you shrug off the latest offerings.

A note

For high quality adult content, get a subscription with an established provider and watch it on your iPad. For anything more interactive the real world may occasionally offer a more tangible (tactile, even) experience. Anyway who needs to jerk off on the go? In parks? On the underground? In the middle of a sodding meeting?

Even in the 22nd century, you’ll be shamed when your android gets all over you in the street, purring in a moist, digital voice.

I haven’t worried about device orientation in a while. Supporting a variety of orientations is *nice*.

On iPad, supporting all orientations is strongly recommended; not supporting ‘upside down’ variants of your orientation is rarely tolerated(*). Unless you have a good reason not to (e.g. accelerometer freak app).

So I thought I’d rehearse a little. I learned new things and discovered an iOS 4.0 cherry that helps avoiding orientation caveats: UIWindow’s rootViewController property.

(*) Keep safe from harm.

How to support device orientation changes?

• Edit the info.plist file for your target
• Your views should be managed by view controllers. You can do without view controllers but then you’re pretty much on your own although at least there’s a system callback to tell you the orientation changed (seriously, you can find it yourself).
• Your view controllers should override shouldAutorotateToInterfaceOrientation.
• Your nib files should be nicely configured so your widgets won’t fly around in a happy mess when rotated.
• Know more about how views are managed, and how view controllers relate to the key window (see caveats)

info.plist

Specify supported orientations in the info.plist for your target:

1. Select your project in the navigator
2. Select your target
3. Press/Depress orientation toggles in the summary tab (big icons showing rotated devices).

view controller

Override this and return YES to your supported orientations:

- (BOOL)shouldAutorotateToInterfaceOrientation:(UIInterfaceOrientation)interfaceOrientation

interfaceOrientation may take one of the following values:

UIDeviceOrientationLandscapeLeft, UIDeviceOrientationLandscapeRight, UIDeviceOrientationPortrait,

UIDeviceOrientationPortraitUpsideDown

Sadly this appears to have a life of its own. Setting the info.plist property doesn’t further restrict a view controller’s response to orientation changes. In other words your plist may say that you only support landscape left/right. If a VC returns yes to all orientations, this won’t prevent its views from rotating.

Configure your nib files

A savvy approach to managing rotation is to create documents that look good both in portrait and landscape mode. It is possible to use different nib files for different orientations (not covering this here).

• In the attributes inspector for your document’s main view, set ‘Autoresize subviews’ to true.
• In the size inspector, use the autosizing toggles to determine what should happen to each element when the view rotates. You (or your UI designer) should do this for each element in the UI, deciding whether that element should size to fit / use a fixed size, and how to anchor the element (left, right, top-left, bottom, …).
• You can toggle the current ’simulated’ orientation of a view using the orientation setting in the attributes inspector.

You can remove/resize elements programmatically (check Apple docs as referred below).

Caveats

In a worse case scenario, changing device orientation will do little other than moving the status bar (if there is one). Two possibilities:

1. Your view controller isn’t notified of the change, so it can’t rotate its view.
2. Your view isn’t managed by a view controller.

Read about custom view controllers (link to SDK docs). Under “Presenting a view controller’s view”:

” [...] use only the suggested techniques for displaying the views of your view controllers. In order to present and manage views properly, the system makes a note of each view (and its associated view controller) that you display directly or indirectly. [...] When the device orientation changes, a window uses this information to [notify] the frontmost view controller. If you incorporate a view [...] by other means (by adding it as a subview to some other view perhaps), the system assumes you want to manage the view yourself [...]“

And this, under “Understanding the rotation process”:

“[...] the window object does much of the work associated with changing the current orientation. [...] Specifically, it works with the view controller whose root view was most recently added to, or presented in, the window.”

Only one view controller will receive the event, and propagate it to it’s (unique) view (and the underlying hierarchy).

Note: if you search for UIVviewController in XCode docs, also read the lovely article: “Why won’t my UIViewController rotate with the device”.

Common Solutions

In my experience, using several view controllers and adding their views to the main window is error prone. Pity, because it feels like a natural, no-nonsense approach to displaying views (but see the nice solution, below).

• Use a unique view controller. Doesn’t sound great but if you have a simple app, at least it’s safe.
• Display the view controller’s view modally. This often makes sense since a view controller is meant to manage one screen’s worth of content. IMHO the downside is that system semantics are associated with modal transitions, and misinterpreting how these transitions should be used may hurt you. For example, you may be struck by lightning.
• Use a navigation controller, a tab bar interface or a popover.
• Hacking a controller’s view down the hierarchy of the controller that receives orientation events. Ugly. However, note that hiding and showing views is a lot faster than adding and removing views. On older devices this may affect the user experience.

A nice solution

I wasn’t desperately happy with *any* of the above. Following the ‘one controller manages one screen’s worth of content’ idea, it would make sense if…

• APIs prevented us from adding several views to the main window.
• Any view added to the main window must be managed by a view controller.
• We could actually tell the window which controller it should be working with.

In IOS4.0 and later, there is a public, documented property that works with UIWindow. You can assign a window’s rootViewController property. This does a lot of work underhand:

• Remove the existing view hierarchy displayed by the window
• Add the new root controller’s view hierarchy to the window
• Make the VC ‘frontmost’. That VC will now receive notifications when the orientation changes.

I tried this and it works like a charm. I seemed less lucky when combining [window addSubview:] with the root view controller property, but maybe it can still work.

Resizing OpenGL surfaces

EAGLView is a utility class for displaying OpenGL content. You can find it in iOS SDK samples and it is often used as a starting point for OpenGL applications.

When an instance of EAGLView is rotated, it calls its [layoutSubviews] method. If you created your EAGLView programmatically, remember to set the autoresizing mask, as follows:

view.autoresizingMask=UIViewAutoresizingFlexibleHeight|UIViewAutoresizingFlexibleWidth;

Otherwise your EAGLView won’t resize, and [layoutSubviews] is never called.

layoutSubviews calls this onto another utility class, aka ‘renderer’ (typically, ES1/ES2Renderer).

[renderer resizeFromLayer: (CAEAGLLayer*) self.layer];

The sample code provided in ES1/ES2Renderer resizes the underlying buffers correctly, so you could use it as a starting point. I get wimpy when it comes to buffers, but I still managed to get it right using the following ideas:

• The color buffer is resized from the CAEAGLLayer.
• We then retrieve the backing width/height from that same buffer.
• Other buffers (depth, MSAA etc…) can be reallocated using whatever method we already know (remember to use the updated width/height).

What if we just wanted to share a little bit of code?
What if we where extremely lazy and didn’t want to learn about XCode 4 workspaces?
What if we didn’t want to create and maintain static libraries?

What if we wanted a solution that’s not even scalable, but does the trick while we bide our time?

And finally, what if we had a bunch of similar products based on a budding ‘framework’. Then we might decide to be evil, and dump all of our products in the same XCode project. Yay.

I decided to have a try. Until I hire another programmer, every day of my life is a Sunday. I found that cloning targets is easy, and just a little fiddling will take us from cloning targets to cloning apps and mutating them into something new.

Creating new targets isn’t hard, but then we have all these files we want to add to the new target. That should be easy as pie, but it’s not.

You can try this on a Saturday too, unless you’re working overtime.

1. Duplicating targets

(right click on an existing target, select ‘duplicate’ and follow the signposts).

If two products (an existing one and a new one we’re about to make) are rather similar, duplicating targets may be the fastest way to setup the new product. It doesn’t duplicate any code or resource. Initially both targets use exactly the same stuff. To ‘fork’ a new product, we then duplicate the resources that ‘aren’t the same’.

The big advantage of this approach is that all existing resources are added to the target right away. So this approach is easy if somebody bothers defining a ‘product template’ that contain little / no product specific stuff.

But first and foremost…

We don’t want the same info.plist, right?

Correct. If we use the same info.plist, we can still have two different products on the desktop, but we won’t have different products in-store. A lot of the meta-data distinguishing a ‘product’ (something users can eventually download) from another is the metadata in the plist.

The fastest way I found to actually clone the plist file is to do it from the desktop (sigh) and adjust the Info.plist File setting in Build settings.

Why my ‘target names’ don’t update in the build selection drop-down? Why do I still see an entry there after deleting a target?

At this point I had created, deleted and renamed several targets. My ‘build selection drop-down’ ignored whatever name change or deletion I carried out.

After a few minutes of deep anxiety, I realized that the build thingy doesn’t directly relate to targets. At the bottom of the drop-down thing XCode 4 shows 3 options: Edit Scheme, Add Scheme, Manage Schemes.

• After deleting targets, delete the associated schemes (go to ‘manage schemes’).
• After renaming targets, delete all schemes (go to ‘manage schemes’) then press the top right button (’auto create schemes now’).

2. Setting up a new target

Setting up a new target and adding resources to it is the slower, meaner way to (loosely speaking) ‘clone an existing product’:

1. Go to File > New > New Target.
2. Choose Window-based application (or whatever you please)
3. Select a product name and fill in the company id.
4. Leave ‘include Unit Tests’ checked (no need to be THAT evil)
5. Press finish.

The sad point here is that no existing files are included in the new target (other than the boiler plate generated by the wizard) and XCode 4 doesn’t provide much of a nice, quick and easy way to add all these files we want to share across targets. We can select several files at once and edit their target setting in the file inspector, but we can only do this for files that belong to the same group.

3. to share or not to share…

There are several types of resources we might want to share across products:

• Code
• Frameworks
• XIB files
• Data files
• Image files
• …

If you use the ‘target clone’ method, at some point you definitely want to introduce these classes that make your app what it is (a new app! with some resources and code borrowed from the old one). Then comes the ‘forking’ question:

• Do the targets use the same MainWindow.xib?
• Do they use the same app delegate
• …

If the two targets use a different xib as entry point, it’s easy to fork (because the xib is listed in the info.plist, and surely the info.plist is forked).

Otherwise, the quick and dirty way is to use homonyms. So we may have two ‘MyAppDelegate’ classes (same name, different folder); and we associate one with each target. IMHO this is really evil, but it’s like chocolate. A tiny bit won’t hurt.

You could also check PrEV’s Demystifying app startup article. Knowing more about app startup can help us resolve certain questions pedantically.

I also found a post about renaming projects. I kinda managed it before, but maybe the post is useful.

Conclusion

Maintaining several apps in the same XCode project is possible. It doesn’t mean it’s a good idea. Learning how to do it is a moderately fun way to learn about targets in XCode.

Back in 2010, our game got popular in iTunes Japan and I got curious about local titles. Shockingly, popular anime/manga serializations lie in the $15-$30 range; at this price, local publishers aren’t short of customers.

Need an example? Chaos Head Noah ($26) ranks #30 in top grossing adventure games and there’s hardly a reason to think it’s anything more than a semi interactive bunch of pics with voiceovers and subtitles. Now you think these ‘derived products’ couldn’t be successful without ip, brand, loads of content and a generous lite version, right?

Doujin developer m-kz put it to the test. They did away with the scary price tag and started rolling moe novels at ‘app store prices’. For just a buck, Twilight Cherry lightly carries the glamor, emotion and humor characteristic of bishoujo mangas, and does it pretty well. 12 months after its initial release, Twilight Cherry carries on merrily in the JP store, proving that ‘moe for less’ is a reasonable option for an indie studio.

.

Lots of text

There was something indefinitely enticing about Twilight Cherry that motivated me to offer helping out with a polished english translation. I didn’t know what I was getting into when I started playing the game, let alone when I suggested fixing up the translation – not just it takes time, but it requires a reasonable dose of inspiration too! After a dozen sessions at my favorite coffee shop, lolled by sirupy A-pop and sore from typing, I eventually saw the end of it. A month later, m-kz rolled the update and voila! (app store link).

Technology

Long before Apple officially lifted the ban on scripted apps, japanese studios were already using markup solutions to get the job done. Twilight Cherry uses the Artemis engine, a cross platform solution running windows and iOS. I didn’t get awfully deep into it, but among interesting things it would seem that even smileys can be used to control the app. WYSIWYG? On the downside, files that combine the original text with markup and translations are fairly hard to read and I would feel sorry to lend them to translators without a technical background.

After a short break in Paris, I’m finding my game physics module where I left it: unfinished. I’m afraid this post isn’t all too informative, but I’ve renewed my commitment to keeping this blog a developer’s diary…

PhysicalModel, for all it’s worth…

I tried to have a look at how PhysicalModel could be implemented. The idea behind PhysicalModel was to have a protocol giving access to physical bodies and/or colliders. This uses a well known pattern: instead of adding the items we want to process to a list or set, we have a protocol specifying how the items are being accessed (a kind of iterator). But frankly I doubt whether the pattern is relevant here. For the sake of efficiency we’d probably allocate an old style array of pointers and iterate that instead, because it’s much faster. For the sake of simplicity, we’d just use an NSArray.

What partakes the physical model?

How do I initialize and maintain the content of PhysicalModel? Nothing explicitly specifies the content of PhysicalModel. We have candidates, but none of these actually describes the model the way I want it to be:

• I have the cast (the list of actors). To keep things simple i’d like every actor to be modeled as a cylinder.
• Then we have the terrain. I’d like every platform to be modeled as a special physical body with detailed processing (on a per face basis)
• Finally, there are a number of elements present in the scenegraph that I would model as obstacles. For these, cylinder/spherical bounds may be enough.

Provisionally, I decided to rebuild the model at the beginning of each chapter. The physical model might need additional maintenance – for example, if actors are added/removed while playing a chapter – but it seems like a decent start. I have a utility class in charge of (re)building the model, looking like this:

@class AntistarCast,WalkableScene,PhysicalModel;

@interface AntistarPhysicalSystemBuilder : NSObject {

}

+(void)buildUsingCast:(AntistarCast*)cast

terrain:(WalkableScene*)terrain

target:(PhysicalModel*)model;

@end

All we have to do to build the model is iterate the terrain/cast and generate physical bodies for matching elements.

Simplifying the model

I had Collider (something other objects can collide with) and PhysicalTarget (can be affected by collisions) protocols. I got rid of that and only kept PhysicalBody. As a result, processing is simplified – each PhysicalBody instance is tested against all other instances for overlaps.

Whether we use separate interfaces or not, we can still reduce overheads - only moving objects need to be tested for collisions. So maybe the distinction between colliders and targets isn’t very useful at this point.

In this post I am exploring a lazy, (somehow) entertaining method to do path-finding.

The idea of this can be captured simply:

Walking randomly will take us anywhere

If an actor is walking randomly on a terrain, no matter where they actually mean to go, they will eventually get there – whether the target is moving or not. A more interesting variant of the above involves stigmergy. An example of stigmergy is provided by ants dropping a ’scent’ on the ground for other ants to follow. In this case the environment is used by agents to share information, which is pretty much what stigmergy is about(*).

Pathfinding using particles

I am not suggesting actors should be roaming randomly, however. Instead, here’s the idea:

• Actors and items (targets) function as particle emitters
• Particles travel randomly onto a navmesh (this could also work with waypoint interpolation)
• Whenever a particle reaches a new site (another triangle on the nav-mesh), its age is increased.
• To reach a target, agents follow particles ‘back to the source’.

I have been thinking about this for a while and tried to simplify it in order to avoid overheads. For example, we could actually keep track of the distance from a particle to the source, or integrate signals (that is, two particles referring the same target cannot co-exist on the same site); or a particle could maintain a ‘history’ of visited locations. All this stuff would require more memory, more reallocations and more development time, so until we have a good reason to add this or that (e.g.: we actually believe this will somehow benefit in some way), there’s no reason to worry about this or that.

Interfaces

Before going further, it’s probably useful to figure a few interfaces that clients will use to interact with the path-finding system.

• SPListener is used by a client to observe particles from an agent’s neighborhood. The interface identifies the type (the kind of object detected, e.g. bread, a flower, a rat etc…) of the particle and it’s source – agents only receive signals from their immediate neighborhood on the navmesh.
• SPEmitter is implemented by clients that act as sources. A registered emitter can return it’s location on the navmesh and it’s type, so we can generate particles from that location.
• SPNetModel is implemented by the navmesh (or a wrapper) and is used as ‘propagation model’. In other words, it is used to retrieve the neighbors of a given site on the mesh. It is also used to retrieve listeners local to a site.

Finally SPSystem allows clients to perform the following actions:

• Register an emitter
• Update particles
• Configure the number of particles maintained by the system

System behavior

At each iteration, the system will perform the following operations:

1. Generate new particles. Typically new particles will override older particles, and this happens at a set rate.
2. Update all particles. Each particle will be moved to a new (randomly selected), nearby site and it’s age is increased by 1.
3. Notify listeners. Every time a particle has reached a new site, listeners interested at the same location will be notified.

What’s the point of doing all this when we already have A*?

Compared to regular path-finding, this method probably has disadvantages. For one, it hardly warrants an agent will use the shortest route to reach a target. However, it does have a interesting features:

• We directly control the balance between resource allocation and accuracy. By controlling the number of particles and the frequency of updates, we control memory allocation and CPU overheads.
• We don’t need to worry about the number of agents or targets, or how often agents need to use path-finding. The overhead of notifying agents is marginal. Adding emitters doesn’t directly increase processing overheads.
• Performance degrades gracefully. We may lose in accuracy and liveliness if we under-allocate resources, but at least there’ll be something going on with agents roaming around and homing onto their targets ‘more or less randomly’. So we can scale down overheads on lower performance devices, or temporarily reduce update rates if we want to allocate more resources to, say, rendering, or something else.

(*)This method has been used in games for quite a long time. Recording the PC’s ‘track’ on the terrain may be one of the oldest, cheapest and most reliable ways to do path-finding.