Java Thread Synchronization performance: round 2

You didn't think I was done, did you?

The previous post attempted to look at the most basic component of Thread synchronization and estimate its cost. The conclusion was that the cost is too low to be considered an issue.

Now I want to add another element to testing. Does the number of threads that might hold the lock significantly impact synchronization performance? I'm still not considering actual contention for the lock (I'll get to that). But how well is the synchronization code optimized to handle many threads, even when there is no contention.

My conclusion here? That the number of threads does impact synchronization performance, however, that impact is minimal to the point of unimportance. It's possible that continuing to increase the number of threads will eventually find a break point where performance degrades very quickly, but the change was fairly constant up to 1000 threads. The increase in time is small enough that it's not worth fussing over. If you're building a massive application that has many thousands of threads, you should probably run your own tests to be sure of the impact, but otherwise I wouldn't worry about it.

The code and results are included at the end of this post, so you're free to draw your own conclusions.

I ran the tests on FreeBSD 10 with OpenJDK 1.7.0_60-b19 (some of that version number may be FreeBSD-specific version information). Feel free to grab the code and try it out on your favorite JVM. Of course, hardware will have a non-trivial effect on overall run time, but the ratio of run times between the various numbers of threads should be fairly consistent within a specific implementation. Whether other JVMs have different performance characteristics is a question for someone else to answer.

Test Code:

public class Test2 {

  public static boolean run;
  
  public static void main(String[] args) {
    Test2 app = new Test2();
    app.go();
  }
  
  private void go() {
    
    int loops = 30000000;
    int[] sizes = new int[] {1, 1, 5, 10, 50, 100, 500, 1000};
    int runsEach = 30;
    
    for (int size : sizes) {
      System.out.println("");
      System.out.println(">> Testing with " + size + " threads");
      long total = 0;
      for (int i = 0; i < runsEach; i++) {
        startThreads(size);
        total += doTest(loops);
        stopThreads();
        java.lang.System.gc();
        try {
          Thread.sleep(900);
        }
        catch (InterruptedException e) {
          System.out.println("!! Main Thread interrupted");
        }
      }
      System.out.println(">> Average time = " + total / runsEach);
      System.out.println(">> Average time per call = " + total / (runsEach * loops));
    }
    
  }
  
  private TestThread[] threads;
    
  private void startThreads(final int num) {
    threads = new TestThread[num];
    run = true;
    for (int i = 0; i < num; i++) {
      threads[i] = new TestThread();
      threads[i].start();
    }
  }

  private long doTest(final int loops) {
    long start, end;
    TestThread test = new TestThread();
    start = System.nanoTime();
    for (int i = 0; i < loops; i++) {
      test.work();
    }
    end = System.nanoTime();
    System.out.println("Run time " + (end - start));
    return end - start;
  }

  private void stopThreads() {
    run = false;
    for (int i = 0; i < threads.length; i++) {
      try {
        threads[i].join();
      }
      catch (InterruptedException e) {
        System.out.println("!! Thread interrupted before successful join");
      }
    }
  }
  
  private class TestThread extends Thread {

    public void run() {
      while (run) {
        try {
          Thread.sleep(10);
        }
        catch (InterruptedException e) {
          // Just continue with the loop
        }
      }
    }
    
    public synchronized void work() {
      float f = 1;
      for (int i = 0; i < 10; i++) {
        f += f;
      }
    }
    
  }
  
}

Results:

>> Testing with 1 threads
Run time 795962042
Run time 786286857
Run time 199196969
Run time 16297397
Run time 17163671
Run time 16824990
Run time 16407745
Run time 17554201
Run time 15890607
Run time 17541246
Run time 16434331
Run time 16932517
Run time 16085874
Run time 15215291
Run time 15619357
Run time 15115641
Run time 15780876
Run time 15205568
Run time 15643645
Run time 15472839
Run time 15974359
Run time 15157174
Run time 15617533
Run time 15438992
Run time 15468485
Run time 15507157
Run time 15244974
Run time 15875522
Run time 15191091
Run time 15783097
>> Average time = 73729668
>> Average time per call = 2

>> Testing with 1 threads
Run time 15386418
Run time 15348036
Run time 15663421
Run time 15212932
Run time 15658743
Run time 15153505
Run time 15835270
Run time 15256209
Run time 15382945
Run time 15965559
Run time 15231225
Run time 15880726
Run time 15271493
Run time 175648894
Run time 178731461
Run time 190533321
Run time 199313983
Run time 199060600
Run time 199415887
Run time 198765814
Run time 199796152
Run time 198772032
Run time 199028302
Run time 199572685
Run time 199027456
Run time 199549007
Run time 198859863
Run time 198762869
Run time 198742303
Run time 198504792
>> Average time = 117777730
>> Average time per call = 3

>> Testing with 5 threads
Run time 199484393
Run time 198697191
Run time 200076825
Run time 199277548
Run time 199980755
Run time 199297630
Run time 199438981
Run time 199254148
Run time 198903016
Run time 199377172
Run time 199109173
Run time 200369934
Run time 199544113
Run time 200267803
Run time 199367557
Run time 200217676
Run time 199541885
Run time 199430942
Run time 199129716
Run time 198968970
Run time 198969677
Run time 199830897
Run time 198897138
Run time 199976410
Run time 199251960
Run time 199445897
Run time 199301249
Run time 198974016
Run time 198842029
Run time 199144413
>> Average time = 199412303
>> Average time per call = 6

>> Testing with 10 threads
Run time 199150382
Run time 199320156
Run time 199138419
Run time 199160883
Run time 199245564
Run time 199021987
Run time 198903988
Run time 199016954
Run time 199358554
Run time 199310135
Run time 200188974
Run time 199290615
Run time 199183679
Run time 199238515
Run time 199217762
Run time 199035672
Run time 199041539
Run time 199471882
Run time 199150993
Run time 199165169
Run time 199301659
Run time 198992886
Run time 199086269
Run time 199257415
Run time 198941664
Run time 199705914
Run time 199222760
Run time 199960150
Run time 199671478
Run time 200217657
>> Average time = 199298989
>> Average time per call = 6

>> Testing with 50 threads
Run time 200530217
Run time 199892436
Run time 197262962
Run time 201208398
Run time 199715748
Run time 199992779
Run time 200659787
Run time 200165258
Run time 199800937
Run time 199635001
Run time 200087977
Run time 200112382
Run time 200363229
Run time 200298460
Run time 199473022
Run time 199927887
Run time 199505967
Run time 200106173
Run time 200292659
Run time 200843640
Run time 199689815
Run time 200025039
Run time 200644594
Run time 199538623
Run time 199061118
Run time 199193134
Run time 200095598
Run time 199744275
Run time 199588208
Run time 198247397
>> Average time = 199856757
>> Average time per call = 6

>> Testing with 100 threads
Run time 200634862
Run time 200379624
Run time 200683595
Run time 200798071
Run time 199676874
Run time 200784278
Run time 200763565
Run time 200921517
Run time 200344951
Run time 200623614
Run time 200946937
Run time 200934182
Run time 200399438
Run time 200897918
Run time 200741948
Run time 200843386
Run time 201104921
Run time 200010681
Run time 200800678
Run time 200658461
Run time 200565042
Run time 200107552
Run time 200443788
Run time 200282941
Run time 200987905
Run time 201173373
Run time 200345061
Run time 200222440
Run time 200900207
Run time 199372010
>> Average time = 200578327
>> Average time per call = 6

>> Testing with 500 threads
Run time 203454398
Run time 205942401
Run time 210786881
Run time 206963343
Run time 202776739
Run time 205442114
Run time 208851151
Run time 207165043
Run time 215251977
Run time 209431195
Run time 205501259
Run time 215273283
Run time 212493174
Run time 212313821
Run time 206062559
Run time 208761225
Run time 209276176
Run time 210185340
Run time 206295473
Run time 208948272
Run time 208813577
Run time 209519561
Run time 211457223
Run time 208937196
Run time 205003769
Run time 211591797
Run time 208652449
Run time 207622638
Run time 210153556
Run time 211430555
>> Average time = 208811938
>> Average time per call = 6

>> Testing with 1000 threads
Run time 221468163
Run time 220505584
Run time 221465052
Run time 221587124
Run time 219965864
Run time 222025735
Run time 229103364
Run time 223751433
Run time 232994489
Run time 232980384
Run time 228709413
Run time 231892879
Run time 234950720
Run time 235469612
Run time 233690739
Run time 234489554
Run time 225850296
Run time 232385003
Run time 232641676
Run time 236887098
Run time 227695483
Run time 228017456
Run time 229519798
Run time 231757513
Run time 231118086
Run time 230468418
Run time 232784509
Run time 232030684
Run time 232966890
Run time 227513589
>> Average time = 229222886
>> Average time per call = 7

Java thread synchronization performance

I was surprised that I couldn't find anything useful on this topic from a Google search. There are a lot of questions and discussions about Thread synchronization, which is apt, since the topic is important and not terribly simple.

But there are some questions that get asked over and over but never answered, despite the answer being quite simple.

Here's the one that I couldn't find the answer to: how much overhead is there to entering a synchronization block? Just, flat out, with no other nonsense involved, how much does entering a synchronized block slow down your code?

To discuss it with a lot of people, you'd think that entering a synchronized block starts a chain of events that culminates in a petition sent to congress that could delay processing by weeks. I'll give you my results in a moment, but I suspect that misconception is the result of people watching a poorly designed multi-threaded program essentially become single-threaded because of the overuse of synchronization. That, however, is an entirely different topic.

EDIT: I'm continuing my research into synchronization, see the next installment here.

Let's construct a scenario to illustrate the question: you have a process that needs to run very fast based on the application requirements. Under normal conditions, there is only a single thread running this process, but occasionally (in unusual circumstances) there may be more than one. It's absolutely vital that these threads do not tramp all over each other, so some sort of synchronization is required. However, in the typical case, you don't want thread performance to be slowed by synchronization that isn't necessary. Can you just use synchronized blocks or will they create a performance bottleneck in the single-threaded case, requiring you to contrive some sort of synchronization that turns off and on?

So I wrote this simple test:

public class PerfTest {
  public static void main(String[] argc) {
    PerfTest pt = new PerfTest();
    pt.run();
  }
  
  private void run() {
    final int runs = 10000;
    
    for (int loop = 0; loop < 10; loop++) {
      long start, end;

      start = System.nanoTime();
      for (int i = 0; i < runs; i++) {
        withLock();
      }
      end = System.nanoTime();
      System.out.println("Synchornized run time   " + (end - start));

      start = System.nanoTime();
      for (int i = 0; i < runs; i++) {
        withoutLock();
      }
      end = System.nanoTime();
      System.out.println("Unsynchornized run time " + (end - start));
    }
  }
  
  private synchronized void withLock() {
    common();
  }
  
  private void withoutLock() {
    common();
  }
  
  private void common() {
    float f = 1;
    for (int i = 0; i < 10; i++) {
      f += f;
    }
  }
}

Results:

Synchornized run time   1533107
Unsynchornized run time 801967
Synchornized run time   346320
Unsynchornized run time 304972
Synchornized run time   340985
Unsynchornized run time 305335
Synchornized run time   342456
Unsynchornized run time 307547
Synchornized run time   343720
Unsynchornized run time 307947
Synchornized run time   343797
Unsynchornized run time 305243
Synchornized run time   344508
Unsynchornized run time 306182
Synchornized run time   340217
Unsynchornized run time 307223
Synchornized run time   340816
Unsynchornized run time 304765
Synchornized run time   343846
Unsynchornized run time 305347

Do the math and you come up with the answer that synchronized costs 3 nanoseconds (for those who aren't privy to that unit, that's .000000003 seconds)

Obviously, this is on a specific piece of hardware with a specific JVM installed. Other virtual machines on other hardware will likely produce variations in timing.

But the act alone of entering into a synchronized block probably isn't enough of a performance hit to shy away from it. Lesson being, if you think your code might ever be multi-threaded and operation could be hindered by unsynchronized access, add synchronized blocks. If your performance concerns are great enough that 3 nanoseconds is too long, then you probably shouldn't be writing Java in the first place.

There's obviously a lot more to thread synchronization. Hopefully I'll take some time to write some more in the near future.

Idamu Caverns: Lessons Learned

I'm winding Idamu Caverns down for a bit.  Overall, I just can't justify the amount of time I've been spending on it, and if I don't get some other projects rolling, I'm going to end up with a money problem soon.  I'm not saying I'm abandoning development of the game, but there will certainly be a pause for the remainder of 2014.  Given the low level of interest, I doubt if anyone will notice, but touch base with me if you're interested in seeing development continue.

The more interesting part of the project (to me anyway) is lessons learned.  I think the easiest way to describe these various lessons is to examine the goals of the project, and discuss whether or not each goal was achieved.

Goal 1: Familiarize myself with the Android platform

I think IC was most successful in fulfilling this goal.  While I'm not a "Google Recognized Expert Developer", I find that I'm able to write Android code quickly and effectively now, without getting bogged down in problems like how to write an app that doesn't lock up, etc.  There were a lot of points during the early development of IC where I tried to use a desktop programming paradigm that just didn't work right, and I feel like I'll be able to avoid those mistakes with my next projects.

Goal 2: Familiarize myself with the Android market

I feel like this was also successfully achieved.  I know my way around the play store, I have a good feel for what is necessary to launch an app, and I feel like I can put the required pieces in place without a lot of flailing for future app launches.

With both goals 1 and 2, I feel like releasing IC as a free app was extremely helpful.  It allowed me to make mistakes (which I did, for sure) without having upset paying customers, requests for refunds, or anything else nasty come through the Play Store.  It set the expectation with the consumers and I feel like it also established goodwill -- I don't know of anyone who feels cheated by Idamu Caverns, to put it plainly.

Goal 3: Build a community around a work in progress

Utter failure, without a doubt.  My attempts at social media, as well as paid advertising, just haven't resulted in the kind of response that's needed to actually build a community.  It's tough to know why things never took off, but I have two guesses: Possibly the Rougelike genre just isn't popular enough to bring in a large community, or possibly there just aren't many people out there who want to be part of a work in progress.

A number of people commented on this when I first started, and I admit that this was one of the big conceits of the project: the idea that people would jump in and contribute.  Many people told me that it wouldn't work, in may different ways, everything from "people don't know what they want" to "you can't give people a blank slate and expect them to be interested."  I didn't feel like IC was ever a blank slate, but apparently, in some way, it was too blank for people to be inspired by.

In general, I didn't get anywhere near the level of interest I expected at all.  Even ignoring the game input, the number of people who downloaded the game was frighteningly small.  I did (what I felt was) a fair amount of paid marketing, as well as doing my rounds on the social networks.  I have to believe that it's the lack of allure of the game and not the marketing, otherwise it's difficult to believe that anyone would ever succeed at marketing any game at all.

Goal 4: Turn Idamu Caverns into a profitable venture

This goal was, without a doubt, failed.  It's failure is the primary reason I'm putting the project on the back burner.  The plan had always been "pay what you want" for the app (using Patreon).  It seems to me that this failing is a chain reaction of the failure to build a community, since I've only got about 100 persistent players (and only 200 people who've tried the game, total) I can't expect to make much money from that small of an audience.  In general, I'd planned at this point for the game to be making at least a few $100 per month.  My most profitable month to date earned me $4.

Android's NotificationManager ignoring errors

I found another one. This has been a rather frustrating week for me, working around quirks in Android, many of which are clearly bugs (like this one, or yesterday's post) and others where the jury is still out.

Today, it's a problem with NotificationManager. Specifically, NotificationManager.notify() silently swallows invalid notifications. In particular, if you create a notification without calling setSmallIcon(), the NotificationManager will simply not bother to add it to the notification panel. Like yesterday's problem, this is particularly difficult to debug because there are no errors or warnings anywhere.

What makes the whole thing more interesting, is that if your notification includes a sound or vibration, those actions will still happen, which leads you to believe that the weirdest thing ever is going on since nothing shows up after the noise. Of course, that's slightly less weird than having it do nothing at all, which leaves a developer with absolutely no idea how to debug or proceed.

I hope the Android team manages to find time to fix some of these issues.

Android SQLite and rawQuery()

It seems as if rawQuery() is unable to process data modification statements such as UPDATE or DELETE.

I don't know if this is by design of SQLite, or by design of the Android API into SQLite, or an accident of one or the other, but it would be nice if this were documented somewhere. It's possible that some part of some manual somewhere has a note on it, but when I brought myself up to speed on the tools I saw it nowhere; and over the course of two days worth of debugging to figure out why my code wasn't working, my searches didn't turn up any mention of it.

It appears that the only way to modify rows is to use the update() method. There's nothing wrong with that.

What is wrong is the fact that when given an UPDATE query, the rawQuery() method simply does nothing, without throwing an exception, logging anything, or in any way indicating that something has gone wrong.

This is the second piece of developer-hostile behavior I've come across since I started doing Android programming earlier this year. Here's hoping that Google will fix it, and anywhere else in the system where errors mysteriously disappear. If a method is passed illegal instructions, it should throw an exception. I can think of no justification for silently swallowing an invalid instruction.

Ahh ... the Internet culture

Less than a day after moving my new app, This is Why I'm Right, to production, and before starting any of the launch activities (such as marketing or an actual announcement) I've got a single 1 star review.

Aviv Gelman eloquently describes the app as "BS app, remove!!!"

This guy is very serious about his review. You can tell by the number of exclamation points. Also, by the fact that he feels that Google should remove the app. Oddly, using This is Why I'm Right, I find that BS apps have more fun per download than serious apps.

So, since I'm obviously right, I'm more interested in Aviv's experience.

First off, the term "BS app" is pretty ambiguous. What does that even mean? The app does exactly what it claims it does, so it's not BS in the deceptive sense. It doesn't steal your data or crash your phone or do sneaky things, so it's not BS in the criminal sense. Since he was complaining about the free version, he can't even argue that it wasn't worth the price he paid.

The only conclusion I can come to is that the app hurt Aviv's feelings. It was inevitable, really, that some people's feelings would be hurt. When you don't get a joke, often your feelings are hurt. And sometimes when a person has hurt feelings she/he lashes out violently, with things like 1 star ratings.

I'm sorry that I hurt your feelings, Aviv. Whatever you do, please don't download any animal simulators ...

Part 5: Dynamic Plots

This is part 5 of a series of posts on procedural generation of content in Idamu Caverns.  You may want to go back and read the earlier posts as well.

The idea of procedurally generated plots seems like the holy grail of computer programming.  Not only could a chunk of code doing this revolutionize the game industry, but it could put a bunch of script writers for TV and movies out of business as well (especially for a lot of mediocre sitcoms on television).

Luckily for those writers, accomplishing this seems to be very difficult.  If you know of anyone doing it, please drop me a line and tell me about it.

While that doesn't mean it's impossible, I expect that it's too difficult for a lonely developer to build on his own.  Of course, that makes me all the more determined to do it!

I'm writing this blog post prior to 99% of the code being written, so most of what I'm about to say is speculative planning.

The key to most programming problems is to break the problem down into pieces and solve each piece independently of the whole problem, while keeping the solution flexible enough to be usable even when unexpected things are discovered about the overall problem.  Abstraction is key (think about the Map interface in java, and how you can easily swap out different implementations based on the specifics of the problem).

That being said, the part that is currently written is to avoid the complexity of each creature in the game having to track their attitude toward you independently.  Instead, each creature belongs to a faction, and reputation and other things are tracked by the faction.  Each creature, then, stores only information about what faction they belong to, and some indication of how closely they follow that faction.  This quickly allows the few factions to remember extensive and detailed information about the player while each creature (of which there are many) only has to remember two small pieces of data.

Organizing things into factions is only the tip of the iceberg.  The complex and interesting part is the code that I haven't even started yet: how do the intelligent creatures react to the player based on faction standing (a large part of this is that I haven't created code for intelligent creatures yet ...)

Like mentioned in earlier parts of this series, completely random information is usually not the best way to do things, and this approach should avoid that.  If the player meets the Spider Queen and she randomly decides whether to be friendly or hostile, that's not very engaging or realistic.  However, if the Spider Queen is hostile because he's been killing and looting every spider he's met since the beginning of the game, that becomes interesting.  Not to mention the fact that it encourages the player to come back and play additional times, perhaps not killing so many spiders the next time through to see what benefits there are to befriending them!

Interactions become more interesting based on this mechanic alone.  If the Cat people and the Dog people are at war, and the player has an excellent reputation with the Cat people, she's not going to like the first encounter she has with the ruler of the Dogs, even if she has avoided fighting them.

But are the Cats and Dogs at war?  This is a place where random generation is interesting.  If each run through the player doesn't know whether there is an uneasy peace or all out war between these two factions, then the replay value of the game goes up quite a bit!

This alone could be considered a procedurally generated plot.  If each faction has a randomly generated attitude toward every other faction, and there are rules and code in place to control how factions behave toward each other depending on whether they're allies, or at war; then we have a state of affairs that the player has to contend with that changes with each play through.

Many other behaviors can be the result of faction reputation: Do faction members attack on sight?  What kind of prices do merchants offer?  What quests are available?

Writing this got me to thinking.  Each of the monsters in the game has a hardcoded reaction to the player at this time.  Spiders always hate you.  Rats ignore you.  But what if this were based on faction, and the faction attitude was random?  One time you pay the rats hate you, the next time they ignore you.  Depending on the other attributes of the factions, this could change up the game quite a bit.

The key to making this work programmatically, is good programming interfaces between the code that handles behaviors and the code that manages creature-specific attributes.  Doing that well is a completely different discussion.

This is the last post in this series for now, but I may come back to the topic another time.  If you've enjoyed these posts, please share, and consider downloading Idamu Caverns and becoming a Patron.

Part 4: Quests

I'm writing this blog post as I create the initial code.  This is Part 4 of a series of posts on procedural generation in games.

I've been thinking about quests in Idamu Caverns for quite some time.  Now that it's time to start implementing the code for the next feature release, I've been thinking about them a lot more.  Quests form an integral part of many game genres, and previously I'd thought it would be poor form to have them generated programatically.

However, the last few days, as I plan out my actual strategy for the code, I'm realizing that quests aren't that different from a lot of other game aspects that can be generated.  For one thing, most quests fall into one of a few categories with aspects that are easily randomized.  At it's core, a quest contains the following elements:

1. Someone/something to communicate with about the quest
2. A thing to do for the quest
3. A reward for the quest

Number 3 is the easiest to generate: pick a valuable item that the player doesn't have and offer it as a reward, possibly in addition to points added to the score, or an achievement if the game supports that mechanic.

Number 2 is only slightly more complex.  Wikipedia has a list that breaks quests down into categories, which basically handles everything I need to say about this.

Number one is where things get interesting.  On the surface it seems simple, spawn an NPC and put it somewhere the player will find, then use that NPC to manage the issuing and rewarding of the quest.  If it were that easy, though, you could just have a book of quests that the player can read from any time she wants.  One of the important reasons for creating an NPC to begin with is to create some sense of realism to the game.  Sure, I could simply place a Creature that says "Bring me $number $items and I will reward you with $treasure." and having a simple generator like that would be better than no quest at all, but it lacks the emotional power that many gamers crave.  Many gamers want the game to give them an emotional reward in combination with an in-game reward.  Something like, "thanks to you, my wife's spirit can finally rest in peace."  I don't know if I can generate that sort of thing with code.

From a programming perspective, all quest code has a fixed way in which it needs to interact with the rest of the game code:

1. There needs to be a way to communicate the desired difficulty to the quest generator
2. The quest generator needs to ensure that all the game objects required for the quest are populated
3. The NPC has to communicate the quest to the player
4. The NPC has to recognize when the quest is complete and reward the player
5. If it's possible to fail the quest, the NPC has to recognize and react to that as well

There are other things that could be added.  For example, the player's reputation with the NPC might determine how good the reward is, or whether the quest is available at all.  There are also non-critical nuances, such as what happens when the player has received the quest but has not yet completed it, then talks to the NPC again.  In the end, however, the above five are pretty much the minimum for getting a quest engine running.

For the first round of quests in Idamu Caverns, I've decided to create a quest manager that can select from multiple types of quest generators when the time comes to make a quest.  That will allow me to gradually implement different quest types and have the quest manager be a central place to enable them when they're ready.

The early quests will be fairly generic in nature, and thus not have much emotional value to the player.  However, once the code is in place, it will allow me to easily write specific quests and interleave them with the generated ones, the overall goal being to quickly provide a wide array of shallow quests to make the game feel broad, then add quests with depth over time, to strengthen the game.

If you join the Idamu Caverns community on Google+, you'll see updates as they happen and will know when this new code is released.  If you're enjoying reading about the development of Idamu Caverns, or enjoying the game itself, please consider becoming a Patron to ensure I can continue developing it.

The next post in this series discusses dynamic plots.

Part 3: The Director

This is the third post in a series about procedural generation in Idamu Caverns.

Anything generated on the fly presents a challenge in maintaining game balance.  If levels are designed by humans, those designers will ensure that the levels are appropriately challenging, and pre-release testing will ensure that the level designers have done their job in creating levels that are challenging but not impossible.  When generating levels dynamically at run time, this testing isn't available.  Furthermore, since there's no linear flow to Idamu Caverns, a player could easily take any one of multiple routes, thus arriving at a point with different equipment and buffs accumulated.

It seemed logical to me that there needed to be an explicit section of code for maintaining this balance -- a game Director, similar to what was designed for Left 4 Dead.  The purpose of the Director code is twofold:

1. Keep the game as challenging as the player requested.
2. Keep the game fun and interesting.

When you start the game, you are asked to select a difficulty level.  This selection is stored as part of the game state, and the Director attempts to maintain that difficulty level throughout the game, adjusting for how well (or poorly) you play.

The code is called primarily at level generation time.  Once the map generation code has finished, the map contains rooms, hallways, stairs, and spawn points.

For each spawn point, the director is consulted at multiple times during the population process.

First, the Director is consulted to see if the spawn point should spawn a treasure.  Here the director is fufilling the role of keeping the game at the requested challenge level.  To determine this the Director keeps track of how many treasures have already been populated on the current map, and compares that number to a number derived from the requested difficulty, factoring in a small random element to keep things from being too predictable.  A higher difficulty setting results in treasure spawning less often, while a lower difficulty setting means more often.

When it's time to populate a treasure, the director is consulted again to determine what type of treasure to populate.  Here the primary goal is to keep the game fun.  The code has already determined to present you with something helpful at this point, so the goal is to ensure that it's populating something useful.  The Director essentially rifles through your inventory to see what you're currently carrying, and tries to present you with something that you need.  This is why you won't see backpacks spawning once you already have a backpack (because there's no value to having multiple backpacks).  The code here is still imperfect, so you will occasionally find items that you have no need of, but it does fair job for the most part.

Next the Director determines whether to spawn a monster.  The chance of a monster spawning is always 100% if no treasure was spawned, but a factor of the difficulty level otherwise.  While it seems odd to have unguarded treasure lying around, it's a matter of keeping the game interesting, as there aren't enough items yet in the game to have every monster drop something.  This is code that will have to be adjusted as the catalog of game items increases.

Selecting which monster to spawn brings up another factor in the Director's operation.  Each creature in the game (of which the player is one) has a challenge rating that can be computed at any time.  It takes into account every factor that makes the creature dangerous, such as damage resistance, maximum health, and potential damage dealt; and returns it as a single number.

The player's challenge rating is calculated, and the requested difficulty is added.  This results in the desired challenge rating of the monster to be populated.  To mix things up a bit, a random element (based on the requested difficulty) may increase the target challenge rating, resulting in a monster that's a bit more challenging than would be expected on that level.  The list of possible monsters is searched to find the one closest to the target challenge rating, and that monster is placed at the spawn point.

The Director does a good job of keeping the game on track as far as being fun and challenging, but it's too random.  Monsters and items are spread completely at random across each level, which removes any sense of coherency from levels.  I have plans to improve on this in the future.  Another challenge is that every new element added to the game upsets the balance of the Director's equations and requires some tuning.  This is a problem only because Idamu Caverns is being developed incrementally, and ensuring that each version is playable requires careful testing to ensure the Director is still doing it's job properly.

You should download Idamu Caverns and try playing at different difficulty levels to see how all this translates into a game.  Please also consider becoming a Patron to help ensure I can keep making games and giving them away for free.

The next post in this series discusses generated quests.

Part 2: Procedural Map Generation

This is part of a series on procedural generation in games.

Generating maps pragmatically is trickier than it seems.  First off, the ability to write a good map generation algorithm is highly dependent on the desired output.  As an example, I'm not aware of any first person shooter that uses generated maps, and I would be amazed to see one.  The nuances required for a good map in that genre are quite complex.  On the other hand, generated maps are not uncommon in the dungeon crawling genre, as it seems it's easier to make a useable map with code there.  Since Idamu Caverns is a dungeon crawler with generated maps, that will be the focus of this post.

I did a lot of research before starting on Idamu Caverns.  Probably the single most influential thing I read is this nine part series on developing Roguelike games.  It's quite a lot to read, but if you're planning on developing anything vaguely Roguelike, I recommend that you set aside time for it.

It's difficult to write this without the article becoming overly long, as there's a lot to be said on the topic, but one of the most important things to clarify before you start writing map generating code is to understand why you're doing so.  Not so much, why am I having code create maps instead of just creating the maps myself; but why do I need maps in the first place?

Unless you're writing a text adventure (remember those?) you'll need a way to represent game play graphically, but even with text adventures there were maps.  To get to the real answer, we have to dig deeper, to the core concept that exploring maps is fun.  Take away the monsters and loot and everything else, and there's a joy alone in exploring a map.  And map exploration is something video games do better than any other medium I can think of.

So, if you're going to have a map at all, you need to make sure that exploring that map is an adventure in itself.  This leads to another concept that I'll touch on over and over again: random generation is usually bad and should be used sparingly.

Taken to an extreme, a purely random map isn't even playable.  It would have a completely random tile on each square, and probably wouldn't even be traversal.  While such an extreme case may seem pointless to bring up, the rule of thumb that less random is better probably holds true in most cases.

The map generator currently used by Idamu Caverns is actually many layers of map generation, as well as many iterations of the code.

From the start, I recognized that many techniques of map generation existed, that I probably wouldn't get it right on the first try, and that the the different methods could produce maps with different feels and it may be useful to have more than one method.  As a result, the first thing Idamu Caverns' map generator does is to select a specific map generator.  This approach allows me to work on new map generators over periods of time, and leave them disable in the production code until they're finally ready, which works well with the frequent release model of the game.

The first map generator code was non-random procedural generation.  A long hallway was generated with the up and down stairs at opposite ends, and equally sized rooms placed equal distance along the hall.  The only random element to the map would be what monsters and items spawned in each room.  The advantage is that the code was simple, reliable, and fast; but the disadvantage was that the resultant maps were boring.  They had no entertainment value in themselves.  As a result, this original code didn't even survive to the first release version.

What replaced it was a random generator that worked by drawing random sized rooms, then connecting them with hallways.  This was considerably more interesting, but also more challenging to make work.  The complexity of connecting the rooms without having hallways that overlapped and created an ugly mess was challenging.  Early versions would frequently create maps with sections inaccessible from the stair.

Furthermore, even this was too boring.  Hallways were never interesting, it was difficult to allow them to intersect while preventing them from intersecting too much and in ugly ways.  With each room simple a rectangle, there was never anything interesting about the rooms.

In essence, there was too much random, and not enough human controlled interest.  I didn't need to be a genius to solve the problem, though, I just took some hints from the article mentioned above and programmed a method for extracting data on human-generated rooms and placing them instead of random sized rectangles.  This allowed me to draw any sort of room (or possibly a configuration of multiple rooms) and have the code randomly place it on the map then connect everything with halls.  The unintended benefit is that it allows the hall code to become simpler.  No longer were hall intersections allowed, instead, a small number of "rooms" are drawn that are essentially hall intersections.  The random placement algorithm puts these on the map occasionally and connects them to everything else as if they were a room.

The algorithm continues to evolve, and as it does it keeps appearing that less randomness is better than more.  One such optimization was that instead of placing rooms completely at random, the algorithm now breaks the room sizes into large and small, and places a few large rooms first, then attempts to fill in the rest of the map with small rooms.  This ensures that maps will always have a large room, and not simply be crammed full of tiny rooms.  It also avoids the uncommon, but annoying map with only a few large rooms.

A lot of the design emerged as I experimented.  Originally, I intended for every level to have a single stair down to the next level.  However, I couldn't quite get the code to guarantee that there would always be a path between the two stairs.  To shorten a long story, instead of ensuring that you could always get to the down stair, I embraced the concept of the occasional dead end level by creating workarounds that prevent it from stopping further gameplay.

There's a lot more I can say on this topic, so it's likely I'll do additional posts.

The next post in this series concerns keeping the game fun and challenging.

Part 1: Procedural Generation in Games

I was about to reply to a question on reddit when I realized the topic was large enough and of enough interest that it warranted a blog entry.

For those not familiar with the term, procedural generation of a game map would be a map that is generated by code in the game, as opposed to a map that is created by a human and simply shipped along with the game.  This is of particular interest to me, since Idamu Caverns uses a lot of procedural generation.

In case you don't want to visit reddit to see the original question, it basically boils down to asking what people think about procedurally generated data in games, such as maps.  The original question posited that procedural generation results in games with a lot of breadth, but not much depth.

An example given was Minecraft.  At first look, Minecraft seems to have both depth and breadth.  However, playing it for any length of time makes you realize that the depth is simply an apparency created by the tremendous breadth of Minecraft's procedural generation.  Minecraft has no quests, no real characters.  You can count the different types on enemies on one hand.  The terrain in the game starts to look repetitive very quickly.

I think the first lesson to learn from this is that significant breadth can give the illusion of depth.  So if you're going to make a procedural game, giving it a lot of breadth can make up for some lack of depth.

Let's take a much more classic game: Angband.  Everything in Angband is generated procedurally, but the depth of monsters and items that the procedures have to pull from is incredible.  Perhaps that's why Angband is still developed and played almost 25 years after it was first released, and has more clones and spinoffs than I can count.

So, another lesson is that depth + breath = immortal classic.

Looking at Idamu Caverns, I wanted it to eventually have the same "immortal classic" magic that Angband did.  I did a lot of research, and what I finally decided on was a hybrid approach, closer to procedural than fixed, but a combination of both.

The idea is that I would grab whichever method seemed like it would be best for a particular aspect of the game.  For example, I decided on procedurally generated maps, but I've decided on prepackaged quests.

This post could easily get very long, so I'm going to break it into sections and post updates every few days.  Some of the topics I plan to cover:

• Map Generation
• Keeping the game fun and challenging
• Quests
• Dynamic Plots

This list will probably expand over time.  Once I actually start writing new posts, I will probably come up with additional topics, realize that some topics need to be broken up, and who knows what else.

Android and OpenGL

If you're doing any drawing in Android, you're using OpenGL.  It might not be immediately obvious, but as far as I can tell, even when you're not using the OpenGL-specific API, the work of drawing goes through the OpenGL code.

It makes sense, really.  If you're going to include OpenGL as a core API of your system, might as well make all the drawing functions funnel through it.  It probably makes the underlying code simpler than having multiple channels to the hardware, and if implemented carefully should be reasonably fast.

The problem I'm about to describe isn't something that's a direct result of using OpenGL.  It's more of a mistake that could happen any time one leverages libraries to create other libraries.

I found this while optimizing some drawing code for Idamu Caverns.  I'd decided not to use any game development frameworks for the game, so the drawing code talks to the Android APIs directly.

To summarize the situation:  The code uses a dedicated rendering thread to render the map to a Bitmap, then displays the Bitmap on the screen in the main UI thread.  This ensures that the UI stays snappy, possibly at the loss of a few frames here and there if the rendering thread gets overly busy.  It also makes some operations simpler.  For example, the render thread always draws the entire map, even if the zoom factor will result in only a small portion of it being displayed, so the render code isn't cluttered with checks on the screen extents.  Additionally, the UI thread can zoom and reposition the map without waiting for the render thread to finish updating it.

Unfortunately, these advantages were also causing problems.  At high zoom levels, the rendered bitmap was huge, despite the fact that most of it would never be seen.  But the memory use wasn't the biggest problem; I worked around that by catching OutOfMemoryError during Bitmap allocation and reducing the zoom factor until allocation succeeded.

No.  The problem was that on some devices, at some zoom levels, the screen just disappeared.  No exceptions, no explanation, no crashes, just no display.

Logcat finally revealed the source of the problem.  It seems that Android's drawBitmap() method works by creating a OpenGL texture from the Bitmap, then issuing OpenGL commands to render the Bitmap to the screen (note that I haven't looked at the code, but you'll see why I'm making this claim shortly).

The Logcat message that I was seeing:

W/OpenGLRenderer﹕ Bitmap too large to be uploaded into a texture (4096x4096, max=2048x2048)

A little research explains that OpenGL keeps texture memory separate from other memory, and that there is a hard limit.  This is no surprise.  What is surprising (and frustrating) is that exceeding said limit simply results in a warning message and failure of the code to do anything.  In my mind, this really should generate an OutOfMemoryError so the situation is detectable by the code.  Furthermore, how much texture memory is available is different for every device and it's somewhat tricky to determine how much is available (it involves talking directly to the OpenGL API, which seems cumbersome, especially in code that doesn't use OpenGL directly.)

In the end, I solved the problem by breaking the map into smaller sections and rendering each one independently (think of how Google maps works when you zoom).  This results in improvements all around: sections that aren't on the screen are deallocated and not rendered, and the UI thread doesn't have to wait until the entire map is rendered to start displaying, to name a few.

But best of all, since each map section is small, even at high zoom levels, the size never exceeds the OpenGL texture limit (at least not on any hardware I can find).  So my mysterious blank screens are gone.

If you want to experiment with this a bit for yourself, the following code should give you a place to start playing:

package com.gamesbybill.drawexperiment;
// includes omitted for clarity
public class Display extends View implements Runnable {

  public Display(Context context, AttributeSet aSet) {
    super(context, aSet);
    Thread t = new Thread(this);
    t.start();
  }

  private static int size = 1;

  @Override
  protected void onDraw(Canvas c) {
    size *= 2;
    Bitmap b = Bitmap.createBitmap(
      size,
      size,
      Bitmap.Config.RGB_565
    );
    Canvas bmCanvas = new Canvas(b);
    bmCanvas.drawColor(Color.BLUE);
    c.drawColor(Color.LTGRAY);
    c.drawBitmap(b, 0, 0, null);
  }

  @Override
  public void run() {
    while (true) {
      postInvalidate();
      SystemClock.sleep(50);
    }
  }

}

Add the following to the XML file for your main activity to make it go:

<com.gamesbybill.drawexperiment.Display
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        />

At some point the code will crash with an out of memory error, but look prior to that in logcat to see the OpenGL message that doesn't crash the app, but simply causes drawing to fail. The limits are different for every device, and once you know the limits for the device you're testing on, you can tweak the code to make the effect easier to see.

Formatting charts on Android with AChartEngine

AChartEngine is a great tool to allow you to quickly add charts of various types to your Android app.
As good as it is, it's unfortunately not perfect.  I'm currently running into some formatting problems when using larger font sizes.  I'll be opening a bug ticket shortly, but this blog entry will allow me to go into detail more easily than I could in the bug reporting system.

At the end of this post is source code.  Using that code, you get the following result when run on a phone:

You can see that the legend is crowding the bottom of the graph to the point of overlapping the X axis title.  This problem becomes more pronounced as font size increases, and is much worse on a tablet, where the code increases the font size even further.

I searched around in the AChartEngine source a bit, in the hopes of generating a patch that just fixed the problem.  I feel that the problematic code is line 104 of AbstractChart.java:

float currentY = y + height - legendSize + size;

Searching around the code, I couldn't come to an understanding of what that simple equation is supposed to be doing.  Instead, I took a brute-force approach and replaced it with:

float currentY = height - size;

Which unclutters the result:

While this works for me, I'm fairly sure that it's not correct overall.  In particular, I don't expect it to work when there are many series that cause the legend to span multiple lines.

Hopefully there's enough in this post to make it easy for someone else to generate a correct fix.

Source code:

// imports omitted for clarity
public class MyActivity extends ActionBarActivity {

  private final static Random rand = new Random();

  @Override
  protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.activity_my);
  }

  @Override
  protected void onResume() {
    super.onResume();
    Point p = new Point();
    p.x = getWindowManager().getDefaultDisplay().getWidth();
    p.y = getWindowManager().getDefaultDisplay().getHeight();
    int maxDim = p.x > p.y ? p.x : p.y;
    int fontSize = maxDim / 60;
    LinearLayout layout = (LinearLayout) findViewById(R.id.graph_surface);
    XYSeries series1 = new XYSeries("Series 1");
    setXYSeriesData(series1);
    XYSeries series2 = new XYSeries("Series 2");
    setXYSeriesData(series2);
    XYMultipleSeriesRenderer renderer = new XYMultipleSeriesRenderer();
    renderer.setLabelsTextSize(fontSize);
    renderer.setLegendTextSize(fontSize * 2);
    renderer.setShowLabels(true);
    renderer.setAxisTitleTextSize(fontSize);
    XYSeriesRenderer r = new XYSeriesRenderer();
    r.setColor(Color.RED);
    renderer.addSeriesRenderer(r);
    r = new XYSeriesRenderer();
    r.setColor(Color.RED);
    renderer.addSeriesRenderer(r);
    renderer.setXTitle("X Title");
    renderer.setYTitle("Y Title");
    XYMultipleSeriesDataset dataSet = new XYMultipleSeriesDataset();
    dataSet.addSeries(series1);
    dataSet.addSeries(series2);
    renderer.setYLabelsAngle(270);
    layout.addView(ChartFactory.getLineChartView(this, dataSet, renderer));
  }

  private void setXYSeriesData(XYSeries r) {
    int start = 1;
    int end = 10;
    int value = 0;
    for (int i = start; i < end; i++) {
      r.add(i, value);
      int change = rand.nextInt(15) - 7;
      value += change;
    }
  }
}

Statistics paralysis ...

Technical people know all about statistics.  We focus on frames per second, or INSERTs per second or any number of other stats to tell us whether we did a good job with our programming or not.  It's rather amazing (to me) how much of our statistical tracking is about performance.  I suppose that's a side-effect of the perception by most of the world that the primary purpose of computers is to do things faster.  It might also be related to the fact that it's something that's easy to measure and communicate.  You don't often see technical people relaying stats about improved accuracy or improved quality as a result of software.  It happens, but not nearly as often as somethings per second are reported.

From a business side, people tend to worry about ROI-focused statistics.  Things like cost-per-click or number of page views for marketing, or profit/loss for the accountants.

Most of this isn't new.  If you see an old movie with a room full of workers at adding machines, they're probably compiling the statistics for their company.  What is relatively new to the business world is the speed and simplicity with which statistics can be collected and converted into a consumable form (such as graphs and charts).  Computers can collect data and turn it into statistics so fast that a lot of people don't even realize that there's a difference between data and statistics, or a process to converting.

I ran afoul of this last week, experimentally running some advertisements while at the same time doing some performance improvements to Idamu Caverns.  I found myself micro-profiling parts of the code until I ran out of ideas on how to make it faster, then spending a lot of time refreshing the statistics of the advertising system I was using to watch the page views and clicks change over time.

There were two big problems with this:

1. The game was already fast enough.  Sure, it can always be faster, but the performance was no longer the most important thing I needed to work on, yet I'd become so focused on making the numbers smaller that I'd failed to notice that fact.
2. Watching advertising statistics in time intervals less than 24 hours is almost a complete waste of time.

But I could do both of those things, so I did.  It wasn't until the next day when I was reviewing my work from the previous day and planning what to do next that I realized that I'd become paralyzed by the statistics, a slave to them perhaps.  Constantly tweaking ridiculous things and watching to see if the numbers improved.

It's not to say that super-tweaking is never good.  If you have a server that's hosting a large number of users and you can improve performance by 0.1% -- that could result in significant gains over time.  But that's a business justification.  Improving performance simply because you can is not productive, and that's what can happen when you look at the numbers without carefully considering what they mean.

I've seen this in large companies where there are people who's job it is, specifically, to look at the stats.  Since that's all they do, it's very easy for them to bog down others in their constant analysis of stats.  I think the solution to this is strong leadership within the company that specifically lays out time periods over which statistics are to be analyzed.  You see some of this.  For example, boards of directors will commonly want to see statistics on a quarterly basis, and don't want to be bothered with it more often than that.

On a personal level, it's an act of self-discipline (for me, at least).  I find myself doing it when the important tasks I have to do are unpleasant ones, but also spending too much time on it due to a failure to notice that things are already "good enough."  For me, I find that scheduling daily times when I go over my TODO list and prioritize it keeps me from getting too far off track.  But also, I sometimes allow myself to do the tasks that I enjoy, even if they aren't the most important.  It takes some of the sting out of doing the unpleasant ones.

Being both the worker and the boss is frequently a challenge for me.  I often joke that I don't get along with my boss at all.

Idamu Caverns Roadmap

Idamu Caverns is successful as a game, and I'm excited about where it's going.

Unfortunately, it's not getting there as fast as necessary to pay my bills.  It's likely that it will be a year or more before the game is generating sufficient income to support the time spent continuing development.

To avoid total failure, I'll be shifting my schedule a bit to focus on other projects that should provide more short-term income.  This means that I'll be cutting back releases of Idamu Caverns to every other week.  The current development road map is as follows:

• September 15th: new item type: ring and a few magic rings to show off the new feature
• September 29th: basic quest code and a single quest to show off the new feature

That's as far out as I'm planning at this time.  Based on the progress of other projects, as well as the reception of the September 15th and 29th releases, I'll plan October out later this month.  Unless something changes the releases will be on the 13th and 27th of October.

If you'd like to see Idamu Caverns development move faster, there are some things you can do:

1. The most important thing is to spread the word.  The game doesn't have enough exposure yet, and advertising is expensive.  Like/Favorite my posts about the game and share them with anyone you know who might be interested.  Talk about the game on your blog or convince others to do so.  Post a positive review on the play store, or join the Google community and tell me what you don't like so I can improve it.
2. If you can afford a few dollars a month, pitch in by becoming a Patron of the game.

Thank you to everyone who has supported the game so far.  I hope that you're enjoying playing it, and I'm looking forward to making it more enjoyable with each release.

Android Rect

While working on a performance-related redesign of Idamu Caverns, I came across some disappointing issues with the design of android.graphics.Rect (issues which are shared with RectF in the same package).

If you're not familiar with the android.graphics package, it contains a number of classes related to 2D drawing.  With Idamu Caverns being a 2D game, it makes heavy use of the classes in that package.

To condense the story into its essential parts: the Rect class is used extensively to communicate drawing information to other classes and methods for the purposes of 2D rendering.  For that reason, Rect objects are peppered throughout the drawing code of Idamu Caverns.

The first issue I came across was a subtle bug in my code that took me far longer than it should have to isolate and resolve.  In the end, it turned out that I was accidentally inverting the top and bottom of a Rect object used to draw the parts that weren't working right.

The Rect object is fussy about it's parameters.  This is only slightly hinted at by the documentation, which states that it doesn't check them for validity (i.e. that top is a smaller value than bottom).  What is hidden behind that comment is the fact that Rect will allow you to set invalid parameters without any errors or warnings.  But furthermore, when you try to use that invalid Rect anywhere, instead of generating an error or warning, you'll just get the wrong result.

The first issue is less of a bug and more of a missed opportunity.  While it's understandable that Rect is designed to work with the coordinate system native to the screen, it would not have been that difficult to make it work with other coordinate systems, such as the Cartesian coordinate system that's rather popular.

The second issue, however, I'd classify as a bug.  If you have a set of parameters that have an important relationship between them (such as the top/bottom situation) it's expected that the internal workings of the class will enforce those relationships, or at least give you a clear warning when you've violated them and things aren't going to work right.

I was pretty upset when I finally identified the problem.  Upset because I trusted the Rect class to be reliable, and had spent a lot of time looking everywhere else in the code on the assumption that if the parameters were invalid I would have gotten an exception.

But my disappointment in the design didn't stop there.  I decided to do the right thing and subclass Rect into a ScreenRect class that would validate it's parameters and provide the type of sanity checking that would make my development more efficient.  Since ScreenRect would subclass Rect, I could use it in any of the android methods that required a Rect.  Object oriented programming at it's finest, right?

Except that the Rect class is final and therefore can't be subclassed.  I spent far too much time trying to understand why anyone would make the Rect class final, as I can think of a number of theoretical reasons to subclass it.

As a result, I had to make the ScreenRect class do all of the work I wanted, while providing a getRect() method to extract a Rect from it when the underlying API requires it.  Feels like really hacky programming to me.

All said, it feels like Rect wasn't really designed so much as thrown together without any real thought.  If anyone knows a valid reason why Rect has all these shortcomings, I'd be interested to hear it.

== equals()

I saw this in a code example somewhere earlier this morning and after thinking about it for a while decided to write a short post on it.

if (stringVar1 == stringVar2 || stringVar1.equals(stringVar2)) {

I've seen this other places, by other developers.  Discussing this is interesting, because depending on your level of expertise, you might have many reactions to this code snippet:

The inexperienced Java coder will wonder why you'd use the .equals() at all ...

Someone with at least a little experience knows that two String variables can be different and yet represent the same sequence of characters, which is the purpose of .equals().  That programmer might be thoroughly confused as to why you'd ever use == when it's not guaranteed to work.

A slightly more experienced programmer will probably assume that the == is there as a performance tweak, to avoid the overhead of the call to .equals() if the two variables happen to point to the same String object.

But the really experienced programmer will note that the whole thing is just stupid.  Why?  Because the first thing that String.equals() does is test to see if the two variables point to the same object, so the alleged performance tweak is insignificant.  Additionally, since the actual chance that both of those variables point to the same object is very slim in most use cases, this construct is probably making the code slower most of the time.

Programmers should know this.  Beyond simply the String implementation, the Java documentation specifically recommends that the first thing that an equals() implementation should do is test for the same object reference.  It's widely accepted best practice ... and most IDEs will generate that code for you if you right-click and then hit whatever button automatically generates equals() and hashcode().  So why do people still do this?  I can't really be sure.

This isn't a terribly common construct, but it's common enough that it makes me worry about how much young coders "code by example" and how dangerous it is that there are so many bad examples out there to copy from (despite the number of good examples also extant).

The reason it stuck in my head is that shortly after seeing it, I saw another bad code example in the Android API docs.  The docs for the Android TestCase class recommend that you use assertTrue(result == 5.0) instead of using assertEquals(5.0, result).  Of course, anyone who's done much with unit testing knows that the former will provide a cryptic, unhelpful message in the event of a failure; whereas the latter will at least tell you what was expected and what was actually achieved, which starts you down the road to solving the problem.  What's an even greater irony in this case is that the example is supposed to be of assertTrue(String, boolean), thus hammering home the point that unit test failures should be verbose enough to be helpful.

Challenges with Idamu Caverns and iterative development

I knew, going in, that not everyone was going to understand quick iterative development.  In fact, when I started Idamu Caverns, I listed the ability to communicate what I was doing as one of the biggest challenges.

Things seldom turn out the way I expect.  For starters, the number of people who understand the "work in progress" side of things seems to be just about everyone, and the number of people tolerant of it, and even enthusiastic is much higher than I anticipated.

It seems, however, that explaining is still the biggest challenge, just not in the way that I expected.  I guess what's actually happening is logical, and I should have expected it.

People are looking at the graphics and their response is generally, "I understand that the graphics aren't very good because the game is a work in progress."  But when faced with missing pieces of functionality, people seem to get confused, or assume that there is a bug.

My earlier post about swords in backpacks is a good example.  Part of the problem is that the inventory system, like everything else in the game, is incomplete.  I expect that at some point I'll have inventory slots for a belt and scabbard so that you have a logical place to put long blades, but the work to create those bits just hasn't been done yet.

There are other challenges in this same vein.  People have complained that there aren't enough monsters, aren't enough weapons and treasure, etc, etc.  All of these complaints are completely valid, but are not really problems with the game so much as additional indications that it's still a work in progress.

Overall, I guess the answer is to simply keep communicating that fact to people.

Of course, because I'm me, I have to look deeper into things.  I have to see if I can extract some meaningful life lesson from things like this.

I spent last week at Gen Con.  I'm not the most serious RPGer in existence, but I enjoy occasionally putting my fate in the hands of a terrible accent and a good die roll.  I managed to get myself into a couple of Timewatch sessions, and watching the other players got me thinking about how gamers have changed over the years.

It seems that not too long ago, sitting down with gamers resulted in them constantly trying to find a way to do whatever they wanted.  "What do you mean kicking dirt in the Orc's face only gives him a -1?  He should be completely blind!"

Timewatch allows (and actually encourages) you to pull Bill and Ted-style shenanigans, such as "Oh?  My character is about to die?  Except that a future version of myself comes back to save her at the last minute!"  And it has game rules to determine whether such a stunt will succeed (hint, it usually does, that's the point of the game!)

I was disappointed in how seldom players took advantage of that ability, and I include myself in that generalization.  Looking back, it felt like doing that sort of thing would be against the rules.  Is that what the other players were thinking as well?  Or was it just a case of new players taking a bit of time to warm up to the system?

Either answer is interesting, but when I look at the lack of feedback and involvement by Idamu Caverns players, I don't know if it matters.  Whether they're unsure of the rules, or simply not warmed up to the idea, it's my responsibility to encourage feedback from them.  I think that's going to take a greater role in game development over the next few weeks.

A bug or not a bug?

It's happening in a manner that could be described as "periodic."  Someone contacts me about Idamu Caverns for Android to tell me they've found a bug: they can't put their dagger in their backpack!

"Bug" is in interesting word, as it has different meanings to different people, and the exact definition is (in my experience) cause for much strife programmers and users.

• In the programming sense, a bug is when software is behaving differently than designed.
• To most users, a bug is when software is not behaving in a way that they expect or understand.

It's a subtle but important difference.  In the case of "daggers don't fit in backpacks," there is no bug in the programming sense.  Think about it.  Take a real-life backpack, then stuff a naked blade the length of your forearm into it.  What's going to happen?  If you're lucky, it will only tear a single hole and you'll notice before you lose anything, or before the blade dangling out of your pack slices you in some way.  So, yes, the behavior was completely intentional.

However, it is absolutely a bug in the second sense.  Why?  Because every other game out there allows ridiculous stuff to go into backpacks.  Open a typical virtual backpack and you find full-length swords, battle axes, even entire suits of armor!  None of this is liable to fit inside a real backpack at all, let alone leave room for anything else or be light enough to carry.

But the industry has set an expectation, and deviating from that expectation is considered a bug.

There are logical reasons for this: Games are not real life, and trying to make them too much like real life causes them to be tedious and unpleasant in all the ways real life is tedious and unpleasant.  Having an unreasonably large backpack allows for additional game dynamics (what I call inventory grinding).  And, in general, not having a practical way of carrying something frustrates gamers and makes the game less fun.

The thing that is amazing to me is that the game behavior is the expectation, so much so that assuming that the game might, in any way, mimic reality isn't really considered.  Instead, the gamer assumes that the programmer made an error.  It's an interesting psychological observation.

I did make an error.  Whether allowing daggers to go in backpacks is an error is a topic for debate, but that's not the error I'm talking about.  The error was in providing a generic message to the gamer, "You have nowhere to put this."  From a software perspective, that's good design, any time the inventory code can't accommodate you, it provides this message (special cases in software create complex and error-prone code and should be avoided).  From a usability standpoint, it's terrible design, as generic error messages make users believe that something happened that wasn't intended to.

Really, there are three possible solutions to this problem:

1. Just allow the player to store naked blades in the backpack.
2. Provide a more specific failure message: "You can't do this because putting a naked blade in a backpack will tear and destroy it."
3. Let the user put the blade in the backpack, then when they take a step, have the backpack slice open and all their stuff spill out.

#3 sounds hilarious, but in reality it would just frustrate players.

It got me thinking, though ... if I took the code for Idamu Caverns and frameworkized it (is that a word?) I could then make another game in which silly behavior is rewarded with silly results.  In addition to #3, if you put crazy stuff (like a full suite of plate mail) into your pack, it would work fine; except that a few steps later your back would give out and you'd have to pay 5000 gold to a chiropractor to get rid of your -1 penalty on all future actions ...