Game AI for Developers

BROADCAST: Understanding the Second Generation of Behavior Trees – #AltDevConf (February 12th)

This upcoming broadcast on Sunday, February 12th at 19:00 UTC will take place online within your browser using streaming audio/video:

“This presentation will provide the most comprehensive overview of the implementation of behavior trees to date. Since their incremental evolution into the games industry ~8 years ago, a lot has changed and there are clear trends in their uses and applications in commercial games. You'll learn the key principles behind first- and second-generation behavior trees as they are currently used in games — and what challenges and opportunities this presents for your game's AI and scripting system.”

To subscribe for email reminders and check the exact time in your current timezone, visit this broadcast's page on AiGameDev.com.

#AltDevBlogADay

Global Game Jam 2012 Wrap-Up

The 2012 Global Game Jam is over and it was another year of awesome games in the Raleigh-Durham – North Carolina area.  This week I wanted to put the spotlight on all the games lovingly crafted by our crack squad of jammers – especially mine, Low Power! :D

The Theme

The Ouroboros – but no explanation was given.  We just showed the jammers the image and it was up to them to interprete it.

LOTR Body Snatching

Rock, Paper, Scissors with body snatching!
Avoid or possess enemies to stay alive and win.

Low Power

In order to survive Low Power you must consume yourself (like the Ouroboros) to survive.  You control a robot whose battery is constantly draining but there are valuable energy cores scattered throughout the level that will sustain your life.  There are all kinds of dangerous environmental hazards that unless you enable your sensors/abilities (lights, shield, ground sensor, microphone) you’ll never survive.  However enabling the different systems will drain your battery even faster!

Parasite

You are a Parasite that leeches off battle ships. Enemies will constantly come in formations to destroy the ship you are occupying. Using the possessed ship, you must defeat your enemies! However, as you leech your ship it slowly dies, you will constantly need to take control of and leech of another ship. With out a ship for protection you are helpless!

Planes on a Snake

A rift in spacetime has resulted in a large number of World War II era planes getting stuck on the world snake.  Join the frequent fliers club of Ouroboros Airlines, racking up points while taking advantage of the torus nature of your new environment.

Roller Snake: The Quest for Chili Dogs

Control “Hardy the Hoop Snake, Jr., III, IV, and V” in his quest to eat as many chili dogs as possible while winding through ‘Catastrophe Canyon’

Snake Run

You are the snake’s guardian, you must ensure that balance is maintained.  Let enough creatures be eaten by the snake to ensure he doesn’t starve, but not enough that he frenzies and destroys everything.  All the while outrunning him!

Global Game Jam 2012 Wrap-Up @ nickdarnell.com

Gathering and Analyzing Data with Django: Part 3

After an even longer delay here is part 3 of Gathering and Analyzing Data with Django. Apologies to those who were waiting for the rest of the series, as the entirety has been completed for awhile. The article itself was picked up for publication in a gems style book so I ceased further distribution. The book’s status is now in flux so I’m going ahead with the posting the rest.

The goal of the series is to showcase Django as a way to build web-enabled tools. The example presented is an analytics site for gameplay data. In the first post we setup the site and created the database schema. In the second post we collected the logs and populated the database. In this post we’ll begin generating the statistics, and provide a Web API to access them.

Generating the Statistics

With our gameplay logs now successfully loading, we can turn our attention to mining the data. Some metrics we’d like to examine are the number of players, that status of the quest among players and – where applicable – the completion time. In its present state all this data is already contained in the database, however as our player base grows so does the time required to generate the statistics. We need a more scalable solution.

Mining data can put a significant strain on the database. To mitigate this we can run the queries and then cache the results inside the database. Django has a straight forward way of accomplishing this through management tasks.

Management tasks are commands that can be run on the project. In fact we’ve already been using them substantially as they are invoked through manage.py. Creating one involves subclassing the base command and supplying our implementation. By convention the commands go in the manage directory within the application’s folder structure. To keep with the component nature of Django we’ll be creating an additional application, called analytics, that will hold the statistics as well as the tasks used to generate them.

Management tasks live within the application’s directory in a subfolder of management named commands. Here we create queststatistics.py which holds the implementation.

class Command(BaseCommand):
 
    def handle(self, *args, **options):
        player_count = Player.objects.count()
        quests = Quest.objects.all()
 
        for quest in quests:
            print 'Quest\n'
            stats = QuestStatistics(quest=quest)
 
            # Get statistics for the various states
            completion_query = QuestState.objects.filter(quest=quest, status=QuestState.COMPLETED_STATUS)
            stats.completed = completion_query.count()
            stats.accepted = QuestState.objects.filter(quest=quest, status=QuestState.ACCEPTED_STATUS).count()
            stats.rejected = QuestState.objects.filter(quest=quest, status=QuestState.DECLINED_STATUS).count()
            stats.not_encountered = player_count - stats.accepted - stats.rejected - stats.completed
 
            # Get statistics for the completion times
            if stats.completed > 0:
                result = completion_query.aggregate(Avg('completion_time'))
                stats.average_completion_time = result['completion_time__avg']
 
                result = completion_query.aggregate(Min('completion_time'))
                stats.shortest_completion_time = result['completion_time__min']
 
                result = completion_query.aggregate(Max('completion_time'))
                stats.longest_completion_time = result['completion_time__max']
 
            stats.save()

The task simply filters the status information based on the state. From there it populates the counts for each individual state. Additionally it uses aggregates, which function as wrappers around SQL functionality such as the min and max. We can then run the command by invoking the following

python manage.py queststatistics

In our case we can schedule the command, and any others we create, through a cron job. The task is run nightly so all the data is ready to use the next day.

Designing the Web API

Now that we have a means to generate statistics on our data, we need a mechanism to query this information. The most flexible way to go about this is to create a Web API, which is a defined set of HTTP requests that generate structured responses in XML or JSON. The benefit gained is the ability for other applications to process the data. Perhaps later on someone will want to link in the data to a spreadsheet, or create a fancy visualization of the data. The possibilities are endless.

To build the API we need to define a set of views which respond with a JSON. In this view we will be taking in the identifier for the quest and then pass back the associated statistics.

def quest_statistics(request, quest_id):
    try:
        quest = Quest.objects.get(pk=quest_id)
        stats = QuestStatistics.objects.filter(quest=quest).latest('date')
 
        response_dict = {}
        response_dict['accepted'] = stats.accepted
        response_dict['rejected'] = stats.rejected
        response_dict['completed'] = stats.completed
        response_dict['not_encountered'] = stats.not_encountered
        response_dict['average_completion']  = to_timespan(stats.average_completion_time)
        response_dict['shortest_completion'] = to_timespan(stats.shortest_completion_time)
        response_dict['longest_completion']  = to_timespan(stats.longest_completion_time)
 
        response_dict['status'] = [
            {
                'label': 'Accepted',
                'data' : stats.accepted,
            },
            {
                'label': 'Rejected',
                'data' : stats.rejected
            },
            {
                'label': 'Completed',
                'data' : stats.completed
            },
            {
                'label': 'Not Encountered',
                'data' : stats.not_encountered
            }
        ]
 
        return HttpResponse(simplejson.dumps(response_dict), mimetype='application/javascript')
 
    except Quest.DoesNotExist:
        return HttpResponseBadRequest()
    except QuestStatistics.DoesNotExist:
        return HttpResponseBadRequest()

We then link a URL to the view. The URL contains the parameters for the view. Django matches these using regular expressions that are then passed on.

If we point our browser to http://127.0.0.1/quest_statistics/0 we’ll see the JSON that is returned.

The statistics in JSON

Up Next

In the next, and final installment, we’ll visualize the statistics we’ve generated. We’ll be discussing Django templates and use some Javascript to create our graphs after querying our Web API.

Also posted to my personal blog

c0de517e Rendering et alter

Normalmaps everywhere/2

First followup to this: http://c0de517e.blogspot.com/2012/02/normalmaps-everywhere.html

Nothing smart really, it's just a small Mathematica playground I made to visualize and experiment with normalmaps, mipmaps and phong, I'm posting it in case you want to play too!

http://www.scribd.com/doc/80425295/Normalmaps-mipmaps-Mathematica-playground

Just to be clear, this is something to have fun and experiment, of course if all I wanted to do was to fit Phong (or any other rotation-invariant BRDF or part of them) I could have done it better in many other ways (first of all, by considering a single parameter that is the dot between the normal and the reflection vector/halfvector instead of working on the hemisphere). Hopefully I'll have something more "serious" coming out on the topic soo.. eventually :)

AMD at Play

Jagged Alliance: Back in Action

A ruthless dictator has seized power on the island state of Arulco. The ousted former President has asked you to hire the best mercenaries in the world to fight to restore him as the rightful leader of his country. Assemble powerful teams of mercenaries and recapture the island sector by sector. Join forces with the local rebels and train and arm them. Exploit resources in the occupied areas to acquire the financial means to purchase supplies of weapons and equipment and to hire new mercs. Coordinate the various teams on the strategic map before plunging headlong into battle to win back the country.

www.youtube.com/watch?v=m1LXuEH53DI

Features:

• The Jagged Alliance series achieved numerous awards and is considered to date as milestone in the genre of real time strategy
• Unrivaled mix of combat (tactics), roleplay, business and strategy
• Innovative “Plan & Go” combat system combines RTS gameplay with turn-based elements
• Liberate a fictitious island from a dictator
• Realistic war setting with authentic-looking firearms
• Laptop/computer menu as a central anchor point for the player
• Assemble your own unit of mercenaries from over 60 unique mercenaries
• Simultaneous control of multiple squads using a strategic map
• Every mercenary has a detailed set of likes, dislikes, strengths and weaknesses
• Convincing characters who interact with and comment on the game events
• All the dialog has audio
• Train your mercenaries to improve their effectiveness
• Acquire resources by capturing mines and encampments

Screenshots:

Official Website

Developed by: Coreplay GmbH
Published by: bitComposer Games and Kalypso

Game From Scratch

Daz3D Hexagon 2.5 Mini-Review

As I recently mentioned Daz3D have made Hexagon, Bryce and Daz Studio all available for free for a limited time.  As a Blender user, until they finally ship BMesh, I am always in the market for a good modeler with effective COLLADA support.  So at a price of 0$ I figured I would try out Hexagon 2.5.  This is not a complete review, not even close, think of this more as a “These are the things I ran into that made me decide to not waste any more time on Hexagon” review.  Obviously, it doesn’t have a happy ending, which is a shame.

First off, it is a remarkably capable modeler, almost every feature you could want is in there… somewhere.  Feature-wise, it actually spanks Blender handily, with support for n-gons, good boolean supports, surfacing, etc.

First a look at the interface:

At first glance it’s pretty clean.  Properties and scene graph on the right, a tool shelf ALA Maya across the top and a mish mash of visibility buttons across the bottom across the bottom.  Then this is where things start to show the sloppiness as well.  Consider this expanded icon:

As you can see from the tool tip, this control “Activates actual lighting” and when you click it, that toolbar folds out.

Any guesses what any of these icons means?  Cause, I’ll tell you, I don’t have a bloody clue either!  None of them have mouse over tool tips, so you are stuck trying to figure it out from the icons…  good luck with that.

Don’t worry, there is always the help files to sort things out…   or wait, is there?

Here comes big and I mean BIG strike number two.  The help, yeah, there is none!

Of course, there is a Help menu, and as you can see, the options look pretty encouraging over all but they do nothing!

You click Help->Documentation or Help->Tutorial and you are brought to Daz3D’s website.  At first it appears that it is going to bring you to a documentation page, but then you are redirected back to the Front page.  Yay.

Alright, so the help hyperlink is broken, no big deal right, just surf to the help manually in your browser?

Ah good idea, let’s try that!

So you go to Support->Wiki from the front page manual.  Then select Hexagon on the left hand side and click the Hexagon documentation link.

Ooooh, this looks encouraging!  Hexagon 2.1 Manual in English, it’s an earlier version but better than nothing, lets click that!

Oh my!  Amateur hour continues.  So, no help, I guess you are on your own figuring things out and, well…  good luck with that.  The interface is downright confusing.

Take view navigation for example.  Other than Blender, the 3D world has become pretty standardized on how to navigate in 3D, so lets see how it works in Hexagon.  To pan your view, hold down your middle mouse button.  Ok so far.  To zoom in your view, use the scroll wheel.  Ok, pretty standard.  To Dolly/Rotate your view you….

Um….

You…  well apparently you use the arrow keys.  Yep, by default there is no mouse mode to actually orbit the camera!   Of course, there might be, put to hell if I can find it with a complete lack of documentation!   Of course, a little googling later and I discovered the answer… It’s a preference and it’s by default OFF! Huh?  Why?  Seriously, why?

For those following along at home, its pretty easy to resolve. Go to the Edit Menu->Preference Editor.  Under the User Interface tab, click Misc then select Dolly around selection center, like so:

Can you seriously tell me a reason why this wouldn’t be enabled by default?  It’s a small thing, but it is infuriating until fixed.  It’s a problem that exists for no reason, and those are always the worst kinds of problems.

There are a few thousand examples like this, all around, it’s like death from a thousand paper cuts.  Like features are added or removed with no thought to being a cohesive tool.  Lets take a look at the tools panel for an example:

Second Life???  HUH?  Why exactly is Second Life getting such important placement, or even placement at all?  Now *this* is the type of thing you make optional in the Preference Editor!  Now take another look back at the shelf and answer me this… where you do think you would go to say… split an edge?  If you said anything except Vertex modeling, you are wrong.  Now lets take a look at that process…  How do you split an edge?  Using a tool named Tessellate, that expands down with various options, lets take a look at that next!

Lovely eh?

So, not only do you not have documentation, you also do not have tooltips so its basically anyone’s guess which icon you actually want to press.

But wait, there is a description of each icon below the shelf!  Oh wait… the expanded toolbar obscures the description text!

Again, a small niggling thing, but 5 minutes in QA should have caught this.  Again, it’s like people keep adding features with no thought to how they fit or should work.  Even worse, you have items that simply don’t exist in the panel, but only via menu.  For example, there is a utilities panel, and a tools->Utilities menu, but WELD can only be accessed via the menu! Or how about the “Lines” menu that has 5! items called arc!  I’m not kidding… look:

Then there is the lack of polish that if you switch to a different part of the tools panel with a menu expanded, it doesn’t close.  You have to switch back to Vertex modeling, click Free Tessellate again to get rid of the menu, otherwise it’s stuck there forever. There are tons of little things like that with the UI, that make the UI toolkit they used just feel… sloppy and frankly, slow.

Speaking of slow, I am running Hexagon on a 12GB i7 machine purchased 3 weeks ago and it can be downright sluggish.  This is especially true when it comes to sub-division surfaces.  The finally

It’s all such a shame, as reality is, there is a great program underneath the surface here.  I didn’t give this program a lot of time; I didn’t have to.  The glaring problems are exactly that, glaring.  I encountered a good dozen “WTFs?” in less than half an hour and within three or four hours with this program I realized it had nothing to offer me that Blender/Wings didn’t already do better.

If there was documentation available ( a big huge mistake, especially when they new they were going to have a giant influx of new users with the promotion ), it might be worth fighting through the stupidity, but there isn’t and it’s not really worth it in the end.

Product Link: Hexagon 2.5

It’s free for the remainder of February, so there is no need to take my word for it, check it out yourself.  Be aware though, once you sign up, Daz is a little spam happy.  Since signing up this weekend, I believe I have received 5 emails, in addition to the receipt and serial number emails you get initially.  A word of advice to Daz, first off, it’s really cool you have made your applications available freely and I hope you see an uptick in your market sales as a result; but dial it back on the volume of emails or you are going to be blocked as SPAM and ignored by the users you are trying to attract!

OpenGL

Triton Ocean SDK 1.3 Improves Ship Wakes

A new revision of the Triton Ocean SDK adds propeller backwash effects to its 3D ship wakes and FFT-based waves, together with improved support for geocentric / ECEF coordinate systems and improved accuracy for height queries on the ocean surface. Triton takes advantage of OpenCL in addition to OpenGL 2.x - 4.x, and is available for Windows and Linux developers. Demos, screenshots, and a free evaluation SDK are available at Sundog Software’s website.

Gamasutra Feature Articles

Building the World of Reckoning

Gamasutra speaks to the game's lead world designer, Colin Campbell -- who explains exactly why the team decided to build a cross-discipline art and design-based world building team for the massive open-world RPG.

SPONSORED FEATURE: TwitchTV - How to Build Community Around Your Game in 2012

TwitchTV co-founder Justin Kan explains how his company uses video streaming to reach a large audience, and how you can capitalize on the fact that "your players are creating and distributing video about your game for you.”

LightSleeper

pkisensee

GDC is coming up fast: March 5-9 in San Francisco. I’ll be speaking on the latest C++ performance technology — move constructors, perfect forwarding and rvalue references. My session title is Faster C++, 11:30a on Friday, March 9. Microsoft is hosting our annual game developer day, this year entitled “Entertainment Reimagined,” on Tuesday, March 6th. I’ll kick off that event as the master of ceremonies. We’ve packed a ton of great content covering new technologies for Windows 8 and Xbox LIVE across multiple platforms. Be sure to also stop by the Microsoft lobby bar in the North Hall: a great place to meet up with friends, check out the latest games, sign up for Dream.Build.Play 2012, and enjoy some refreshment after a long day of talks and walking the expo floor. See you at GDC 2012!

Geeks3D Forums

Separable Subsurface Scattering tech demo

The day has come
...
The main idea behind the new separable SSS approach is that you can get very similar results to the full 12-pass approach ... by just using a regular two-pass setup. It...

Game AI for Developers

Evolving Scripts in City Conquest

(Copyright © AiGameDev.com, 2012.)

As the games industry struggles with designing increasingly complex systems and mechanics, AI is proving to be a great tool for handling this complexity. In particular, there's an increasing number of researchers and companies looking into using AI as a tool for assisting game design and consequently reduce time taken fine tuning the particular properties of game elements.

In this interview with Paul Tozour we will take a look at his current kickstarter project City Conquest, a tower defense game that breaks off the usual pattern by including an offensive part as well. Yet what we will be covering over this interview won't be the novel mechanics or features but instead we will take a look at the evolutionary process Paul used to tune up the difficult parameters that keep the game balanced.

The Big Picture

Q: Did you find it necessary to try to express 'player fun' or 'player experience' into your fitness function? Is that even possible to achieve in practice?

For the first 16 years that I worked in the industry, I thought machine learning in games was pointless. I used to love to say "There’s no fitness function for fun." Whenever a conversation turned to machine learning techniques like neural nets or genetic algorithms, I’d just say "There’s no fitness function for fun" and argue that that makes machine learning useless for games, and that would be the end of it.

A Shield Generator.

And if you take it at face value, it's absolutely correct! I mean, imagine that you had a computer program that could actually tell you how much “fun” any given part of a game was. How could a program like that even work? How could it know that a certain part of your game is too repetitive? How could it know that fighting the Swamp Boss is more fun than the Lava Boss, that level 5 isn’t engaging because it has too much traversal, that the Plasma Gun isn’t fun to use while the Lightning Blaster is a thrill?

Writing a program like that would be like solving the Turing Test, only harder. You’d have to be able to fully model the player’s perception of the game and their interaction with it and accurately model all of the thousands of little reward centers buried in the human brain to know what actually makes a human player happy, and why we get such a bizarre thrill from making plumbers jump and clicking on cows.

So of course, that's impossible.

And saying “there’s no fitness function for fun” is actually more than correct – it’s also useful! Particularly in game AI development, people who are new to the industry sometimes come in with wildly unrealistic expectations for what machine learning can do and where it’s appropriate to use it. If they come from an academic background, sometimes they seem to think it’s “wrong” to solve game AI problems by hand, and they look for a magic wand they can wave to create the whole AI at once.

You have to push back against that mindset and shatter those illusions, and remind such developers that sometimes you can use machine learning to make a good AI system better, but it’s a terrible tool for trying to make a good AI in the first place.

And for a long time, I was satisfied with that answer.

But I eventually came around to the realization that while it’s correct, it's also irrelevant!

And I had a huge change in perspective. I came to the realization that machine learning isn’t a tool for game AI – it’s a tool for game design.

You may not be able to write a fitness function to put an exact number on entertainment value, but if you can state your design goals clearly, then you can very often write a fitness function that measures whether some part of your game satisfies them.

And then it's about selecting the right design goals in the first place to create the kind of entertainment experience you’re looking for, and determining which of those design goals are appropriate targets for any kind of AI-assisted tuning.

For example, with City Conquest, I had a specific tactical role in mind for every offensive and defensive building, and a lot of ideas as to what I expected would constitute effective offensive and defensive strategies. But I also had specific design goals for how the buildings should work together:

• Uniqueness: Each of the nine defensive buildings (towers) and offensive buildings (dropship pads for units) should be distinct from all the others
• Minimum bound on utility: No building type should be "underpowered" – every building should be important, and it should have some clear tactical role, and there should always be some scenario in which that building is the most important to winning.
• Maximum bound on utility: No building type should be "overpowered" – in other words, no single building type, or combination of a limited number of building types, should allow the player to win the game against a non-reactive opponent.
• Cost equivalence: Every building in the game should have a resource cost equivalent to its actual utility in the game.
• Combined arms: Combinations of several different building types should be far more effective than building only a small number of building types (both offensively and defensively).
• Reactivity: The optimal strategy for each player should depend significantly on the other player's strategy.

» Click here to view this embedded content.

Q: Do you feel that machine learning algorithms have been unfairly prejudiced against in the game industry?

The Disruptor tower.

Not necessarily. There’s a bias, but it’s not completely unjustified.

Some forms of ML (neural networks) are genuinely useless; many of them (genetic algorithms) are much too slow to be used at runtime; the results aren’t predictable; and as I mentioned, newcomers to the industry are sometimes very unrealistic about its potential and give it a bad reputation. There’s nothing worse than an AI developer who wants to wave the magic wand of “machine learning” instead of writing code.

But I’m not doing this because I’m any kind of ivory-tower academic or a starry-eyed idealist. I’m an industry veteran; I worked on two Metroid Prime games and was employee #3 at Gas Powered Games. I’m doing it because it works, and because I’m a capitalist and I believe in raising quality and lowering costs.

Q: What led you to use computational intelligence for game balancing?

I got tired of designing AI, and I realized it was time to “AI” design.

Here’s a thought experiment:

How are people going to design games 100 years from now?

Never mind that we have no idea what games themselves will look like that far into the future. A “game” probably won’t look anything like it does today. Maybe they’ll be holodecks or something. But it doesn’t matter.

In the year 2112, how will game designers get their jobs done?

What kind of tools are they going to use?

I don’t know the answer, but there’s no question it’s not going to look like what we have today. Game design is still in its infancy – or maybe its messy and chaotic pre-teen years.

A century from now, what it means to be a “game designer” will have evolved beyond recognition. We won’t have designers giving hand-wavy answers to basic design questions, making sweeping design changes without understanding the side-effects, or spending inordinate amounts of their team’s time (and their company’s resources) exploring the design space in the name of “iteration”.

At a minimum, we’ll have a shared design language across the industry, a shared understanding of what constitutes “good design”, and vastly more powerful design tools.

Imagine that you wanted to build a bridge. You’d need to hire a licensed structural engineer, wouldn’t you? That engineer would have to have earned a civil engineering degree with 3-5 years of study under their belt, and then satisfy a host of requirements to become certified to build bridges.

And that happens because everybody understands that bridges can fail, and earthquakes and wind and traffic accidents can topple them if they’re not designed correctly, and things like that can kill people and destroy the bridges. So you have to spend a lot of time studying to understand how to build a bridge the right way.

Everybody appreciates all of that, so everybody accepts that certifying civil engineers is the right thing to do to make sure they build good bridges.

But there’s nothing like that for games.

We consistently hire people who are enthusiastic rather than people who are genuinely qualified – we prefer charismatic designers who can talk the talk over cautious practitioners who can walk the walk. We take million-dollar projects and put them in the hands of people with no adequate design training, and then we fail to train them further or build a shared design vision between them. We let them endlessly throw ideas against the wall to see what sticks, and then we wonder why we end up with burned-out teams, failed projects, and studio failures out the other end.

The Ground Slammer.

And mostly that happens because we don’t talk about what happens when designers fail. We hide the devastating consequences of design failure. When a bridge collapses somewhere, it’s too big to hide and the whole world knows about it … but in the game industry, a design collapse is painful and embarrassing and we have the luxury of hiding it in our own studios.

And that has to stop. It’s just too expensive and too risky to keep doing design that way. Design has become the bottleneck.

So we need two things to happen.

First, game design needs to grow into a real discipline. I’m not saying we need actual certification like you have in civil engineering (though that might not be a bad idea), but the discipline of game design needs get out of its infancy (or chaotic pre-teen years) in a hurry.

And secondly, we need vastly better tools.

If you were to go back in time 30 years and asked designers what tools they’d like to see in the future, they would have described some amazing tools for building levels and doing scripting in three entire dimensions. And now those tools exist! We have engines like Unity and Unreal and Gamebryo that are everything a designer in 1981 would have asked for and more.

But these aren’t the only tools we need. Unity and Unreal can’t give you any insights on your game design. They can help you build your game, but they can’t tell you anything at all about the design decisions you make.

There’s so much more that can exist, and that will have to exist someday. It’s just that we don’t see that, because those tools haven’t been built yet – so we don’t realize they should exist, and we don’t realize they’re missing!

We have game “engines,” but we don’t realize that the rest of the car is missing.

Again, I used to think machine learning techniques were useless. But I got to a point where I stopped thinking of machine learning as a game AI tool and started thinking of it as a design tool, and that changed everything.

Take Wall Street as an example. There used to be a time when the New York Stock Exchange was full of traders yelling and making complicated hand gestures to each other to buy and sell shares. It only took a decade for all those pits to be abandoned and replaced with computers. Since then it’s been an ongoing arms race of ever faster servers and ever tighter connections and lower latency for high-frequency trading within microseconds. And it will never go back to the old days.

Or I could compare it to baseball recruiting. Baseball recruiting used to be a very subjective process. It was ten managers sitting in a room arguing about who to recruit to fix a broken baseball team, without really understanding what they should be looking for and no clear idea how to properly evaluate the factors that make a baseball team work. “We can’t hire that guy – he has an ugly girlfriend; that means no self-confidence!”

And in the book and movie Moneyball, you see how Billy Beane (played by Brad Pitt) hired an economics PhD from Yale and put together a statistical modeling approach that ultimately drove the Oakland Athletics to a staggering string of victories and changed baseball recruiting into a quantitative discipline. And it will never go back to the old days.

Game design right now is like the NYSE before computers, or baseball recruiting before Billy Beane.

And it will change, so we might as well embrace it. Moore’s Law is still in effect, and we have a massive amount of computing power at our disposal in cloud computing clusters.

Every day, computing power becomes a little bit cheaper and game designers become a little bit more expensive.

We’ve finally arrived at the point where we can actually run the millions of gameplay simulations we need to run to do GAs effectively and get those insights back into the hands of designers in a few hours or days, and it’s inevitable that that will transform the design process.

Q: So can we get to a point where we replace designers once and for all? :-)

The Lightning Tower.

My hope is that the future will bring much more powerful tools to bear on game design problems. We’ll have all the powerful game engines we have today, but we’ll also have the equivalent of a GPS and navigation system for game designers to guide them toward the decisions that satisfy their design goals.

And that will also raise the bar for what a game designer is expected to do to work effectively. So the best designers will have more powerful tools that help them design better games, faster … and the pretenders will find themselves out of their league and will probably have to find new jobs.

Both of those are good things.

Q: Currently you're using AI as a tool to assist the design process. Do you think it's possible to use genetic algorithms to optimize the game's parameters rather than just finding the dominant strategy?

Definitely. My approach is just one particular way of using GAs for one particular kind of balancing problem. It’s only a starting point; it’s not the only approach and it’s not necessarily the best one.

Phillipa Avery and Julian Togelius wrote a really neat paper (with Alistar and van Leeuwen) on using GAs to tune parameters for a more traditional tower defense game, where they evolved the parameters for their creeps and towers directly.

Alex Jaffe of UW also has a really terrific paper coming out on this topic (along with several co-authors). I’ve gotten a sneak preview but I’m sworn to secrecy.

There’s one company I know of with a broadly similar overall concept – the +7 Balance Engine. But their approach is very different. Their webpage says that they want to ensure that there are no dominant strategies.

I don’t think that’s a valid approach. You have to empower designers, and let them decide whether there should be any dominant strategies. Maybe they do want one dominant strategy! You can’t take someone else’s game and say “Here, let me balance that for you” because you can’t know what they mean by “balance.” You can’t anticipate all of their design goals in advance.

It’s about giving valuable feedback to the designers so they can ensure that their gameplay meets their design goals.

The big-picture goal is to build systems that dramatically expand designers’ visibility over the dynamics of the gameplay they create. We’d like to build systems that shine a floodlight on the fitness landscape and which player strategies emerge from every design decision.

And we want to be able to give them visibility on how any design change they could make will affect those dynamics, so designers can ask questions like, “what happens if I tune this parameter here – how does that change the set of viable player strategies?” Or alternatively, “What would I need to change in my parameters to make strategy X more (or less) desirable?”

Behind The Scenes

Q: How would you rate the importance of the underlying evolutionary algorithm compared to the overall infrastructure/process? How long did it take to implement this part of the code?

It’s been ~10% of my total engineering time. There were 3-4 days of dedicated coding to create Evolver in September – we had to split Evolver into a separate build, disable the renderer, increase the time step in the update loop, optimize the gameplay code, and then make it parallel using Microsoft’s PPL library. That got us to a point where we can run several million entire games overnight.

Since October, it’s only been 30-90 minutes a day of tuning. We have a dedicated Dell desktop PC running Evolver 24/7. Every day or two, we terminate the Evolverand extract the two best players by fitness score (one each from the red and blue player populations). Then we plug them into the game, play them back, and watch how they play each other and decide how to tune it based on that gameplay session. Then we make the code changes and run it again, and only occasionally dig deeper and make tweaks to Evolver itself.

The Grenade Launcher.

So that’s very handy. It’s like having a virtual playtesting team that works for free. It cost me a few days of development, but when I compare that to the salary I’d have to pay somebody to do that full-time, it’s a no-brainer.

Of course, it’s not a magic bullet. You still have to do manual playtesting, and it’s still a good idea to plug your parameters into Excel every now and then and fit them to a curve with Solver. But those are now small, secondary tasks, not the core of the balancing process itself.

So once I get Evolver’s output, I can plug it back into my game and watch the red and blue players duke it out. If I see a pattern where both players are over-using certain buildings or upgrades or combinations of buildings, then I probably need to “nerf” those features somehow – either I need to make them weaker, or I need to increase the resource cost to buy them in the first place.

Similarly, if there are certain buildings or upgrades that they never buy at all, I need to stop and ask myself why. Are they too expensive? Are they not useful enough? Or is there something else going on? Why is the Evolver not finding it useful enough to survive evolution? So I’ll increase its utility or decrease its cost to compensate.

And finally, I look at the context in which everything is being used and see if it matches my design goals for each unit. Sometimes I find the Evolver adapts the strategies I expected it to; other times, it surprises me, and I have to figure out whether I should tune the game to stop it from happening, or embrace it as an unexpected new strategy.

Some of the AI researchers I've been speaking with have raised the issue that my approach can really only identify one dominant strategy at a time. For example, you might have two strategies, A and B, that are both dominant, and with the way I’m doing it, the computer can only identify one of those dominant strategies.

And that's true, but you have to keep in mind that tuning is an ongoing process – it's not something you do in a single pass! I'm running the Evolver continuously and re-tuning every day or two based on its output. So if it only happens to find that A is the dominant strategy today, that’s fine, because it means I’m going to respond to that, and A will get nerfed so that B has a much greater chance to stick out like a sore thumb the next time I run it.

Q: Can you give us some examples of interesting results Evolver has given you?

This is more of a bug than a balancing issue, but I had a really interesting phenomenon on October 30 where the best red player script was always winning the game by a huge margin. And looking through the evolved script, it didn’t seem to be doing anything really unusual; the only unusual thing I could see was that it was building a Laser tower at a particular spot fairly early in the game.

Now, the Laser tower is a very unusual building in City Conquest. It’s the only defensive tower that doesn’t have a range limit – it can fire all the way across the map. It was designed to do a very small amount of damage to a very large number of units. The trick is to set it up the right way to ensure that it hits as much of the enemy army as possible.

So when I started playing back the scripts in the game, I was floored – the red player’s Laser was positioned in just the right spot where it could target the blue player’s Collectors from all the way across the map! It took 8-9 shots to take them out, but once it did, the blue player’s Collectors were destroyed with no way to rebuild them, so it would be starved of resources and it would lose every time.

Again, it’s more of a bug than a feature – Collectors were supposed to be invulnerable, and Lasers shouldn’t even be able to target them anyway, but invulnerability and targeting tweaks hadn’t been implemented yet and were scheduled for a later date. But it goes to show you how computational intelligence can find a path through the design space that a human designer might never even imagine.

A Laser attacking the blue player’s Collectors. The red player’s Laser is firing from offscreen to the upper-left.

Here’s a different example that shows some really good behaviors that I think closely mirror what a smart City Conquest player would do. These are two screenshots from a recent run that I discussed in Update 4 of my Kickstarter campaign. Again, keep in mind that everything you see in these screenshots (excluding the pyramid-shaped Mining Facilities on the crystals) was evolved entirely by the computer.

Here’s the blue player’s base:

There are five really interesting things going on with this base:

• Single point of entry in the back of the base: The blue player forces all the enemy units to funnel around to a single attack point at the rear of its Capitol. This is the best possible positioning for the attack point, because it forces enemy units to go all the way around before they can attack, and it gives the blue player many more opportunities to defeat them.
• Dividers to separate enemy forces: The blue player divides and conquers the red player's forces, splitting them between a northern and a southern route around his city. Since one route is longer than the other, enemy units will arrive at different times, and this makes them much easier to deal with as they will reach the Capitol at different times.
• A well-placed Disruptor (the floating sphere with yellow stripes) near the top entrance allows him to interrupt the red army's cloaking, shielding, and healing effects at exactly the right time, just as they're beginning to get truly pounded by the blue player's defenses.
• A fully-upgraded Shield Generator unit toward the upper left (the dropship pad with three aqua-colored lights) allows the blue player to protect nearby units from damage.
• A set of 3 Lightning Towers cleverly dispersed at the front, side, and rear of the blue player's base, ensuring that these expensive buildings rarely waste time targeting the same units simultaneously.

Here’s a screenshot of the red player’s base. Notice how it employs many of the same intelligent strategies as the blue player, which are exactly the behaviors I intended to be good strategies in City Conquest.

• Single point of entry: Like the blue player, the red player forces the opposing army to attack at the rear of his Capitol. The design of the base forces blue’s units around to the north, above the Mining Facilities, and then back through the rear entrance on the left side of the image.
• Dividers to separate enemy forces: Like the blue player, the red player splits the opposing army into two different paths (east and west paths at the front of his base) to upset their arrival timing.
• A perfectly-placed Disruptor (the floating sphere with yellow stripes above the Capitol) allows the red player to interrupt cloaking, shielding, and healing effects all along the front and side of its base (all along the north edge five Mining Facilities you see), as well as when enemy units circle around to the rear and finally close in on the Capitol.
• A Lightning Tower at just the right spot (black spiral just above and to the right of the Capitol) gives excellent coverage, allowing the red player to zap enemy units at the front, side, and rear of its base. This placement ensures that this relatively expensive tower will see as much utilization as possible.
• A pair of Ground Slammers, one at the front of the red player's base and another at the rear (shaped like tall pillars wearing metallic thumpers), allow the red player to create earthquakes and give area-effect damage to all ground-based units that pass by.
• A pair of Grenade Tossers (deep holes in the ground on the left and right sides) is also nicely distributed in a very similar way, with an upgraded Grenade Tosser in the front and another non-upgraded Grenade Tosser in the rear. These allow the red player to hit all ground units in a wide area with a moderate amount of area-effect damage -- enough to weaken them considerably and allow the other towers to take them out.

Q: What type of evolutionary approach and individual representation did you use? Simply put, what did you evolve?

In this particular case, we’re just trying to evolve highly competent players to see what strategies good players use. We essentially evolve scripts of build orders.

City Defense is a tower defense variant, so it only has three player verbs: “build,” “upgrade,” and “sell” (I’m excluding the verbs for “game effects,” which are more like spells that players can cast). Also, selling buildings is usually a bad idea since you can’t get a full refund, so there’s no reason for Evolver to do it.

So an Evolver player script just boils down to a sequence of build and upgrade commands – build a building of type T at (X,Y), or upgrade the building at position (X,Y). There are no timing values associated with the commands; Evolver will ensure that each player executes a command as soon as it can afford to do so.

Also, since every building in City Conquest has a resource cost in terms of gold or crystals, but not both, it effectively processes the build order as two separate lists in parallel, one for each resource.

We start by generating 500 random build scripts for each of the red and blue players. Then we run four tournaments, each one pitting all 500 red player scripts against all 500 blue player scripts, using a random offset so that we’re pitting each blue player script against a different red player script in every tournament.

It’s probably easiest just to show you the C++ pseudo-code:

static int const skNumTournaments = 4;
static int const skPopulationSize = 500;

// Run 4 tournaments which pit all 500 blue scripts and all 500 red scripts 
// against each other
for ( int tournament_iterator = 0; tournament_iterator  skNumTournaments; 
++tournament_iterator )
{
    int random_offset = rand() % skPopulationSize;

    for ( int i = 0; i  skPopulationSize; ++i )
    {
        // This ensures that ALL members of BOTH populations will play a game
        Script & blue = blue_player_scripts» Click here to view this embedded content.;
        Script & red = 
            red_player_scripts» Click here to view this embedded content.;

        // Now play a full game, and adjust the scores for “blue” and “red” 
        // as appropriate
        RunSimulation( blue, red );
    }
}

We do 4 tournaments of 500 games each (pitting each red player script against a random blue player script) to make sure we get good coverage and reasonably accurate fitness values at the end of each tournament. Once the tournament is completed, we sort the scripts for each player by their fitness score, and apply standard genetic operators – random replacement of the lowest-scoring scripts (falling off linearly to a fixed minimum value over the first few hundred tournaments); random mutation of each script; and performing “crossover” to combine two scripts (biased toward crossover with higher-scoring scripts rather than lower-scoring ones).

A “mutation” has a random chance to change a building’s type, change a command’s location, swap the ordering of two commands in the script, or copy a command on top of an existing command.

We also added additional safeguards to ensure that scripts would stay flexible. For example, if Evolver tries to execute a build command and there’s already a building there, in most cases it will sell the existing building to allow it to build the new one and continue executing the script.

Of course, this is a relatively simple application, and it’s made easier by the fact that City Conquest lends itself to this as a TD game. Not every game can get away with a non-reactive build script like this. Most games are more complicated, and you need an entire AI system to get a reasonable simulation of a player.

For our next project, we’re planning to evolve entire behavior trees to allow us to generate more complex reactive behaviors rather than just a fixed build order. We’re also planning to move the Evolver into a cloud computing cluster and separate the populations out using an “evolution islands” approach with metadata.

Q: How do you determine the fitness of an individual? Evolutionary algorithms are often very sensitive to the definition of the fitness function.

Yes, they are. It depends on the particular game and what you’re trying to evolve.

In City Conquest, it’s back-and-forth tower defense gameplay, and the Capitol is the only attackable building. The game ends when one player’s Capitol gets to zero health. So the ratio of the health of the two Capitols is actually a VERY good indicator of who's winning. And when the game ends, the health of the winning player’s Capitol tells you a lot about how close a game it was. In an evenly-matched game, both players will do a lot of damage to each other’s Capitols; in an uneven game, the winner will destroy the opposing player’s Capitol without allowing much damage to his own.

Each script has a fitness score associated with it. After each game, Evolver takes the health of the winning player’s Capitol and adds that to the score of the winning player script and subtracts it from the score of the losing player script. This ensures that the greater the victory, the greater the effect on both scripts’ fitness scores.

When I started development on Evolver, I discussed my plans with a number of the top researchers in AI-based design and automated game balancing – Phillipa Avery of the University of Nevada – Reno, Gillian Smith and Adam Smith of UCSC, Alex Jaffe of UW, and a few others.

A few of them suggested that I set up “archetype” scripts using standardized “known” player strategies to ensure that I’d evolve against a broad set of possible human strategies. I recorded my own gameplay as I executed half a dozen standard strategies, and then for a few weeks I tried using Evolver to test against all six of those archetype scripts.

But I found that as I rebalanced my game every day based on the feedback from Evolver, it would invalidate all of those “archetype” scripts. I couldn’t commit to re-recording all those scripts every week or two as my balancing changed, so I had to abandon that approach.

Later in the development cycle, I also tried adding additional fitness qualifiers to encourage the evolved scripts to do more of what I felt a human player should do. Some of these didn’t work out, but one that did was adding a fudge factor to the fitness function for building and upgrading Skyscrapers. This is critical to success in City Conquest, since Skyscrapers expand your buildable territory, and upgrading them not only consolidates your hold over your territory but also gives you additional resources over time. But it’s the type of thing that isn’t necessarily immediately rewarded in a fitness function, because an evolved script won’t immediately capitalize on the additional territory and additional resources right when the Skyscraper is first added.

The Skyscraper fitness adjustment helps compensate for the natural delay between building and upgrading a Skyscraper and then evolving everything else you need to actually reap the benefits from it. This is purely a way of telling Evolver, “trust me, you want to be doing this, and we don’t want to wait for evolution to prove it every time.”

Final Thoughts

Q: What advice would you give to other developers thinking about using machine learning algorithms in their games?

I was the founder of my startup, so I already had the buy-in I needed from the upper management to run the experiment. And I undeniably realized major benefits from it.

But I can’t imagine trying to push something like this at any of the studios I’ve ever worked at.

Machine learning will take time to prove itself. It’s not going to happen overnight. The (often justified) skepticism toward machine learning in the industry makes it a tough sell to launch this kind of initiative internally. It’s probably going to have to enter from the outside, disruptively, rather than from inside studios that would offer enormous cultural resistance.

I’m reminded of when I worked on Thief: Deadly Shadows and Deus Ex: Invisible War at Ion Storm Austin. I had to fight tooth and nail to gain acceptance for the use of navigation meshes for pathfinding. I think almost every single programmer and designer in the studio argued against it at one point or another. Some of them treated me like I was crazy; others treated me like I had to be some kind of pointy-haired academic who ought to be off in a research lab somewhere if he cared so damned much about obscure academic issues like good pathfinding.

And now, they’re very common. I can make a list as long as my arm of successful AAA products that used navigation meshes.

But at the time, it was open warfare, and it was very difficult to make the case for something that seemed to me blindingly obvious.

It will be the same for machine learning and AI-based game design for some time to come.

So my advice is to make sure you have buy-in. Don’t put yourself through the pain if you can’t get full support and commitment at every level. Otherwise, you’re just painting a target on your back.

And if you can’t get it, and you see the possibilities, consider quitting your job. Launch a startup, or join mine!

If you liked this interview don't forget to take a look and back this interesting project at City Conquest Kickstarter Project!

The Brainy Gamer

About the podcast...

Before discussing my own show, a quick heads-up on a couple of other ‘casts I enjoy. I recently had the pleasure of visiting the erudite gents over at A Jumps B Shoots. They host one of my favorite games-focused podcasts, so I was delighted to join them for TWO shows. We discuss authorship, auteurism, aspirational play, and aesthetics broadly defined. In other words, we dig pretty deep, but Matt, Steve, and Rich keep it accessible and entertaining from beginning to end. You can listen to the first show here and the second show here.

I also made a guest appearance on the GameCritics After Dark show along with my friend Jeffrey Matulef discussing Skyward Sword and the Zelda franchise generally. It’s a lively conversation, and I thank Richard and Mike (both decidedly not fans of the latest Zelda game) for giving Jeffrey and me a chance to have our say. You can download the episode here.

So, on to my own show, the Brainy Gamer Podcast. If you’re a listener you’ve probably noticed that I haven’t released an episode lately, so I thought I’d offer an explanation and share a few things I’ve been thinking about.

A funny thing happened on my way to recording an end-of-year favorites of 2011 show. I took a look around the games podcast space and noticed that everybody and his brother, sister, mother-in-law, and second-cousin had released a best-of-2011 show. Recently I’ve harbored a concern about my show, and it’s this: I don’t think I’m adding enough value to the general conversation about games to make my show worth doing, at least as it’s currently configured. Given that I could listen to, literally, a dozen good podcasts with smart people (and, frankly, three times as many mediocre shows) all rounding up the best games of ‘11, why throw another me-too show onto the pile?

This connects to my larger concern that games podcasts mostly all sound the same: a few knowledgeable folks engaging in friendly banter about games. A “whatcha been playin’” segment is typically followed by a more focused segment on a particular game or two. A gaming-related issue may be explored. A special guest may appear. But basically - and I include my own show - it often seems like we’re all producing variations of the same format.

When I launched my podcast back in ‘07, I saw a need for a show devoted to “thoughtful conversation” about games. When I look around me now, I see many podcasts doing just that, and doing it well. The two I mentioned above, of course, but also Big Red Potion, Experience Points, Gamers With Jobs, Three Moves Ahead, and others I follow regularly.

I want to continue producing my show, but I think it’s time to reformat it. I’m drawn to the idea of a podcast that focuses each episode on a single person (or occasionally a creative duo) and explores his or her work, ideas, influences, etc. I can imagine a fascinating gallery of designers, composers, animators, writers, actors, critics, producers, etc. - each person a collection of experiences worth exploring in depth. I’m imagining a one-on-one Charlie Rose-style interview format that gives me time to discuss a wide range of topics with guests, but remain focused on the work, the unique personalities, and the individual stories of each.

I’d love some constructive feedback on this idea. If you like it, dislike it, or have suggestions for refinement, please leave a comment and let me know. I’ve always enjoyed recording my podcasts, even when my schedule makes it difficult to produce them. I’m eager to continue, but I need a stronger sense that they’re worthwhile and add value to the broader conversation about games. I think it’s time for a reboot. What do you think?

Procedural World

Tree editor in Voxel Studio

Timothy Lottes

Another Hawken Tube

iPhone Development Tutorials and Programming Tips

Best Resources In iOS Development – February 6th, 2012

Welcome back to another edition of the best resources in iOS development listing the latest resources from this site in order of popularity.

This edition features a great tool for viewing the iOS SDk decomentatiion on your iOS device, easy ways to simulate slow and poor connections within your iOS apps, and a guide to easy downloading and caching of images.

Here are the resources:

Tool: Open Source App For Easy (And Beautiful) Viewing Of The iOS SDK Documentation On iPhone And iPad - A fantastic project you can install on your iOS device and easily view/download/search/bookmark iOS documentation with style.

Tip: Simulating Different Network Conditions To Make Sure Your iOS App Doesn’t Screw Up On 3G - Tools for setting up your internet connection to simulate different networking speeds and quality.

Tutorial: How To Download And Cache Images With The MKNetworkKit iOS Networking Library - A tutorial on how to easily download an cache images using the MKNetworkKit library.

Apple Posts New iOS Development Videos Covering In-App Purchases, Open GL ES, And More - Apple has posted new videos for iOS developers covering many of the topics featured at the iOS tech talks.

Open Source: Excellent Easy To Use iPhone Sliding View Control - A lightweight control for creating sliding views with a very nice clean syntax.

Open Source: Great Block Based UIAlertSheet And UIActionSheet Replacement Library - A great solution for quickly programming UIAlertSheet’s and UIActionSheet’s which can be very tedious to code.

Open Source: Excellent Easy To Use Flip (Flipboard Style) Transition Component - A component for applying “half flip” style animations to flip solid colors and dynamic text or images.

Macros Allowing You To Easily Create Code That Works In Both ARC and Non-ARC Projects - Some macros you can apply to your code allowing it to compile when used within both non-arc projects and arc projects (without turning off arc for the files).

Example: How To Update Apps By Downloading Modified Files From A Server - A great example on updating apps by downloading modified files.

Open Source: Sliding View Control For Showing Information Like Folders On The iOS Springboard - A control allowing you to easily apply the slide similar to the iOS springboard, even the mid-view slide used by Newsstand and Folders.

Open Source: Slick Control For iOS That Makes An Interesting Progress Indicator - A control for making a very interesting sprring progress indicator.

Tutorial: Quickly Create A Jetpack Joyride Like Game With Cocos2D, Box2D, LevelHelper, And SpriteHelper - An extensive tutorial on creating a game with using Cocos2d and the LevelHelper, and SpriteHelper tools.

Thanks for reading, please bookmark and share this post!

©2012 iPhone, iOS 5, iPad SDK Development Tutorial and Programming Tips. All Rights Reserved.

GPGPU.org

New CLOGS library with sort and scan primitives for OpenCL

CLOGS is a library for higher-level operations on top of the OpenCL C++ API. It is designed to integrate with other OpenCL code, including synchronization using OpenCL events. Currently only two operations are supported: radix sorting and exclusive scan. Radix sort supports all the unsigned integral types as keys, and all the built-in scalar and vector types suitable for storage in buffers as values. Scan supports all the integral types. It also supports vector types, which allows for limited multi-scan capabilities.

Version 1.0 of the library has just been released. The home page is http://clogs.sourceforge.net/

#AltDevBlogADay

Component Granularity

In one of my previous post (The Game Entity – Part III, Components) I touched on the subject of component granularity as being something to keep an eye on. Since the post I have had a few discussions where there has been some confusion about what is meant by component granularity.

Over the years a number of very intelligent people have tried to create a quantitative system for granularity with varying degrees of success. As one chap put it :

“Granularity is a bit like pornography, it’s hard to define but you know it when you see it.”

I have had a fair bit of experience with components and thought it would be interesting to try and explain my perspective and thoughts on the subject. Hopefully clarifying what is meant by component granularity and how it can be useful in improving the code.

Functionality

“Granularity is an indicator of how much functionality is being encapsulated inside a single component”

How I gauge a component’s granularity is based upon it’s functionality, this is NOT based upon the number of functions or the amount of data contained within the component. I generally describe a components granularity size with words such as; Tiny, Small, Medium, Large or Huge.

Let’s consider two components; The first is called “Health”, it can handle different types of damage, keep track of poisons, damage resistances and generate messages when certain conditions are met. In short it is the bees knee’s and contains a fair number of functions and data in order to allow it to work.

“Basic Health” on the other hand knows nothing of the different types of damage that exist, doesn’t generate any messages and is as the name says basic.

Both of these components I would personally consider to have a similar granularity of between small to medium.

The Granularity Alarm

Let’s be clear there is nothing wrong with a component rated with a large or tiny granularity. There are games that have shipped with both examples and they work just fine. The granularity however can be an indicator that there might be something with the design of your component that could be improved.

Every entity component system has a certain overhead in terms of memory and CPU cycles to handle and process each component. If your component falls into the tiny range then very likely you are spending more on the maintenance of the component than you are on the actual component itself.

An example of this might be a component that contains a single floating point value, during the update stage it simply adds the current time delta to the float. In this scenario I would suggest that this functionality would be better integrated into other components since it doesn’t do enough to justify the overhead cost.

The larger the granularity size the less likely the component is to be re-usable and / or interchangeable. One of the first things that people new to components do is usually take the code from an entire entity and simply dump it into a component. If you have an entity with a single component attached that’s a good indicator that something on the design side might not be right.

Component Design

The subject of component design could fill a few posts, however it actually can be boiled down to a simple sentence:

“The high level aspirations for all component design should be to contain a chunk of functionality that is self contained, re-usable and interchangeable.”

To clarify that a little:

A chunk of functionality – Well that’s the granularity that is so interesting to pin down.

Self contained – Although it might use other components to make decisions / achieve results it doesn’t actually need any other component to do its job. For example, Health and Navigation components.

Re-usable – The whole point of a component system is to allow as much functionality to be re-used as possible with minimal effort. The higher up the component chain you go the less re-usable parts become, for example the Dragons Brain is specific to the dragon and won’t be very re-usable except on other dragons. The components Render, Physics and Audio however are incredibly re-usable.

Interchangeable – This is probably the most difficult aspiration to attain, a component that can be swapped in and out with little modification. An example is the Physics component, I have worked on projects where the physics system has been switched two or three times during development. On one of those projects we were not using a component system and hence the game code needed some extensive rewiring with each switch rather than a single component’s internals.

Component Granularity is a very fuzzy subject, hopefully his has helped to clarify some of the confusion.

Syntopia

Distance Estimated Polychora

My last post mentioned some scripts that Knighty (a Fractal Forums member) made for distance estimated rendering of many types of polyhedra, including the Platonic solids. Shortly after, Knighty really raised the bar by finding a distance estimator for four dimensional polytopes. In this post, I’ll show some images of a subset of these, the convex regular polychora.

There are several ways to depict four dimensional structures. The 4D Quaternion Julia, one of the first distance estimated fractals, simply showed 3D slices of 4D space. Another way would be to project the shadow of a 4D object onto a 3D space. Ideally, a proper perspective projective would be preferable, but this seems to be complicatated with distance estimation techniques.

The technique Knighty used to create a 3D projection, was to place the polychoron boundary on a 3-sphere, and then stereographically project the 3-sphere surface onto a 3-dimensional space. For a very thorough and graphical introduction to stereographic projection of higher-dimensional polytopes, see this great movie: Dimensions. It should be noted that the Jenn3D program also uses this projection to depict a variety of polytopes (using polygonal rendering, not distance estimated ray marching).

Back to the structures:

The convex regular 4-polytopes are the four-dimensional analogs of the Platonic solids. They are bounded by three-dimensional cells, which are all Platonic solids of the same kind (similar to the way the Platonic solids are bounded by identical regular 2D polygons). The convex regular polytopes are consistently named by the number of identical cells (Platonic solids) that bounds them. In four dimensions, there are six of these, one more than the number of Platonic solids.

5-cell

The 5-cell (or 4-simplex, or hypertetrahedron) is the simplest of the convex regular polytopes. It is composed of 5 three-dimensional tetrahedrons, resulting in a total of 5 vertices and 10 edges. It is the 4D generalisation of a tetrahedron.

The curved lines are a consequence of the stereographic projection. In 4D the lines would be straight.

8-cell

The 8-cell (or hypercube, or Tesseract) is also simple. Composed of 8 3D-cubes, it has 16 vertices, and 32 edges. It is the 4D generalisation of a cube.

16-cell

Things start to get more complicated with the 16-cell (or hyperoctahedron). It is composed of 16 tetrahedrons, and has 8 vertices and 24 edges. It is the 4D generalisation of an octahedron.

Notice, that if we rotate the 3-sphere, we can get interesting depictions, with edges getting infinitely long in 3-space:

24-cell

The 24-cell is exceptional, since it has no 3D analogue. It is built from 24 octahedrons, has 24 vertices and 96 edges.

120-cell

The 120-cell is a beast, built from 120 three-dimensional dodecahedra. With 600 vertices and 1200 edges, it is the most complex of the convex, regular polychora. It is the 4D generalisation of a dodecahedron.

Zooming in, it is easier to see the pentagons making up the dodecahedra.

600-cell

Finaly, the 600-cell is built from an even larger number of polyhedra: 600 three-dimensional tetrahedrons. However, the simpler polyhedra means there is only a total of 120 vertices and 720 edges. It is the 4D generalisation of an icosahedron.

Knighty’s great Fragmentarium scripts can be found in this thread at Fractal Forums.

Knighty’s script is not limited to regular convex polychora. Many types of polytopes can be made. Here are the parameters used for the images in this post:

polychora06.frag parameters:

Type,U,V,W,T
3,0,1,0,0 - 5-cell
4,0,1,0,0 - 8-cell
4,0,0,1,0 - 24-cell
4,0,0,0,1 - 16-cell
5,0,1,0,0 - 120-cell
5,0,0,0,1 - 600-cell


And for completeness, here are the parameters for the 3D polyhedron script:

Type,U,V,W
3,0,1,0 Tetrahedron
4,0,0,1 Cube
3,1,0,0 Octahedron
5,0,0,1 Dodecahedron
5,0,1,0 Icosahedron


#AltDevBlogADay

Don’t Store That in a Float

I promised in my last post to show an example of the importance of knowing how much precision a float has at a particular value. Here goes.

As a general rule this type of data that should never be stored in a float:

Elapsed game time should never be stored in a float. Use a double instead. I’ll explain why below.

As an extra bonus, because switching to double is not always the best solution, this post demonstrates the dangers of unstable algorithms, and how to use the guarantees of floating-point math to improve them.

How long has this been going on?

A lot of games have some sort of GetTime() function that returns how long the game has been running. Often these return a floating-point number because it allows for convenient use of seconds as the units, while allowing sub-second precision.

GetTime() is typically implemented with some sort of high frequency timer such as QueryPerformanceCounter. This allows time resolution of a microsecond or better. However it’s worth looking at what happens to this resolution if the time is returned as a float, or stored in a float. We can do that using one of the TestFloatPrecision functions from the last post – just call them from the watch window of the debugger. In the screen shot below I tested the precision available at one minute, one hour, one day, and one week:

It’s important to understand what this data means. The number ‘60’, like all integers up to 16777216, can be exactly represented in a float. The watch window shows that the next value after 60 that can be represented by a float is about 60.0000038. Therefore, if we use a float to store “60 seconds” then the next time that we can represent is 3.8 microseconds past 60 seconds. If we try to store a value in-between then it will be rounded up or down.

How long did it take?

One of the most common things to do with time values is to subtract them. For instance, we might have code like this:

double GetTime();
 
float TimeSomethingBadly()
{
    float fStart = GetTime();
    DoSomething();
    float elapsed = GetTime() - fStart;
    return elapsed;
}

The implication of the precision calculations above is that if ‘fStart’ is around 60, then ‘elapsed’ will be a multiple of 3.8 microseconds (two to the negative eighteenth seconds). That is the most precision you can get. If less than 3.8 microseconds has elapsed then ‘elapsed’ will either be rounded down to zero, or rounded up to 3.8 microseconds.

Therefore, if our game timer starts at zero and we store time in a float then after a minute the best precision we can get from our timer is 3.8 microseconds. After our game has been running for an hour our best precision drops to 0.24 milliseconds. After our game has been running for a day our precision drops to 7.8 milliseconds, and after a week our precision drops to 62.5 milliseconds.

This is why storing time in a float is dangerous. If you use float-time to try calculating your frame rate after running for a day then the only answers above 30 fps that are possible are infinity, 128, 64, 42.6, or 32 (since the possible frame lengths are 0, 7.8, 15.6, 23.4, or 31.2 milliseconds). And it only gets worse if you run longer.

As another example consider this code:

double GetTime();
 
void ThinkBadly()
{
    float startTime = (float)GetTime();
    // Do AI stuff here
    float elapsedTime = GetTime() - startTime;
    assert(elapsedTime < 0.005); // 
}

The purpose of this code is to warn the developers whenever the AI code takes inordinately long. However when the game has been running for a day (actually the problem reaches this level after 65,536 seconds) GetTime() will always be returning a multiple of 0.0078 s, and ‘elapsedTime’ will always be a multiple of that duration. In most cases ‘elapsedTime’ will be equal to zero, but every now and then, no matter how fast the AI code executes, the time will tick over to the next representation during the AI calculations and ‘elapsedTime’ will be 0.0078 s instead of zero. The assert will then trigger even though the AI code is actually still under budget.

It’s a catastrophe for base-ten also

The general term for what is happening with these time calculations is catastrophic cancellation. In all of these examples above there are two time values that are accurate to about seven digits. However they are so close to each other that when they are subtracted the result has, in the worst case, zero significant digits.

We can see the same thing happening with decimal numbers. A float has roughly seven decimal digits of precision so the decimal equivalent would be getting a time value of 60.00000 and having the next possible time value be 60.00001. Given a seven-digit decimal float we can’t get more than a tenth of a microsecond precision when dealing with time around 60 seconds. When we subtract 60.00000 from 60.00001 then six of the seven digits cancel out and we end up with just one accurate digit. For times less than a tenth of a microsecond we have a complete catastrophe – all seven digits cancel out and we get zero digits of precision, just like with a binary float.

Double down

The solution to all of this is simple. GetTime() must return a double, and its result must always be stored in a double. The cancellation still occurs, but it is no longer catastrophic. A double has enough bits in the mantissa that even if your game runs for several millennia your double-precision timers will still have sub-microsecond precision. You can verify this by using the double-precision variation of TestFloatPrecisionAwayFromZero():

union Double_t
{
    int64_t i;
    double f;
    struct
    {
        uint64_t mantissa : 52;
        uint64_t exponent : 11;
        uint64_t sign : 1;
    } parts;
};
 
double TestDoublePrecisionAwayFromZero(double input)
{
    union Double_t num;
    num.f = input;
    // Incrementing infinity or a NaN would be bad!
    assert(num.parts.exponent < 2047);
    // Increment the integer representation of our value
    num.i += 1;
    // Subtract the initial value find our precision
    double delta = num.f - input;
    return delta;
}

You can see in the screenshot below that if you store time in doubles then after your game has been running for a week you will have sub-nanosecond precision, and after three millennia you will still have sub-millisecond precision.

Clearly a double is overkill for storing time, but since a float is underkill a double is the right choice.

Aside: my initial calculation of the precision remaining after three millennia was wrong because the calculation of the number of seconds was done with integer math, and it overflowed and gave a completely worthless answer. Which proves that integer math can be just as tricky as floating-point math.

Changing your units doesn’t help

All along I am assuming that you are storing your time in seconds. However your choice of units doesn’t significantly affect the results. If you decide that your time units are milliseconds, or days, then the precision available after your game has been running for a day will be about the same. It is the ratio between the elapsed time and the time being measured that matters.

Or use integers

Tom Forsyth points out that the same issues happen with world coordinates and that switching to integer types can give you greater worst-case precision, as well as consistent precision. The Windows GetTickCount() and GetTickCount64() functions use this technique, using milliseconds as the units. This alternative to using a double for time is quite reasonable, especially if you encapsulate it well. A uint32_t with milliseconds as units will overflow every 50 days or so but you can avoid that by using a uint64_t. However despite Tom’s threats to invoke his OffendOMatic rule for all who use doubles, I still prefer doubles for game time because of the combination of convenient units (seconds) and more than sufficient precision.

While Tom and I appear to disagree over whether you should use double in situations like this, we agree that ‘float’ won’t work.

Note that while GetTickCount() and GetTickCount64() are millisecond precision they are often actually less accurate than you would expect. Unless you have changed the Windows timer frequency with timeBeginPeriod() the GetTickCount functions will only return a new value every 10-20 milliseconds (insert pithy comment about precision versus accuracy here).

Time deltas fit in a float

It is important to understand that the limited precision of a float is only a problem if you do an unstable calculation, such as catastrophic cancellation cancelling out most of the digits. The code below, on the other hand, is fine:

double GetTime();
 
float TimeSomethingWell()
{
    double dStart = GetTime(); // Store time in a double
    DoSomething();
    float elapsed = GetTime() - dStart; // Store *result* in a float
    return elapsed;
}

In TimeSomethingWell() we store the result of the subtraction in a float – after the catastrophic cancellation. Therefore our elapsed time value will have tons of precision.

Similarly, if you are using floats in your animation system to represent short times, such as the location of key-frames in a 60 second animation, then floats are fine. However when you add these to the current time you need to store the result of the addition in a double.

Tables!

Forrest Smith made a pretty table showing how the precision of a float changes as the magnitude increases, and I mangled it to suit my needs. Here it is for time:

And here is the table showing how the precision of a float diminishes when you use it to measure large distances, with meters being the units in this case:

Stable algorithms also matter

Some time ago I investigated some asserts in a particle animation system. Values were going out of range after less than an hour of gameplay and I traced this back to an out-of-range ‘t’ value being passed to the Lerp function, which expected it to always be from 0.0 to 1.0. Clamping was one obvious solution but I first investigated why ’t’ was going out of range.

One problem with the code was that the three parameters were all floats, so over long periods of time it would inevitably have insufficient precision. However we were getting instability much earlier than expected and it felt like switching to double immediately might just mask an underlying problem.

The parameters to the function, all time values in seconds, corresponded to the end of an animation segment, the length of that segment, and the current time, which was always between the start of the segment (segmentEnd-segmentLength) and ‘segmentEnd’. Because the start time of the segment was not passed in this code calculated it, and then did a straightforward calculation to get ‘t’:

float CalcTBad(float segmentEnd, float segmentLength, float time)
{
    float segmentStart = segmentEnd - segmentLength;
    float t = (time - segmentStart) / segmentLength;
    return t;
}

Straightforward, but unstable. Because ‘segmentLength’ is presumed to be quite small compared to ‘segmentEnd’, there is some rounding during the first subtraction and the difference between ‘segmentStart’ and ‘segmentEnd’ will be a bit larger or smaller than ‘segmentLength’. The resulting difference will always be a multiple of the current precision, so it will degrade over time, but even very early in the game the result will not be perfect. Because the value for ‘segmentStart’ is slightly wrong the value of “time – segmentStart” will be slightly wrong, and occasionally ‘t’ will be outside of the 0.0 to 1.0 range.

This will happen even if you use doubles. The errors will be smaller, but ‘t’ can still go slightly outside the 0.0 to 1.0 range. As the game goes on ‘t’ will range farther outside of the correct range, but from just a few minutes into the game the results will show signs of instability.

The natural tendency is to say “floating-point math is flaky, clamp the results and move on”, but we can do better, as shown here:

float CalcTGood(float segmentEnd, float segmentLength, float time)
{
    float howLongAgo = segmentEnd - time;
    float t = (segmentLength - howLongAgo) / segmentLength;
    return t;
}

Mathematically this calculation is identical to CalcTBad, but from a stability point of view it is greatly improved.

If we assume that ‘time’ and ‘segmentEnd’ are large compared to ‘segmentLength’, then we can reasonably assume that ‘segmentEnd’ is less than twice as large as time. And, it turns out that if two floats are that close then their difference will fit exactly into a float. Always. So the calculation of ‘howLongAgo’ is exact. Ponder that for a moment – given a few reasonable assumptions we have exact results for one of our floating-point math operations.

With ‘howLongAgo’ being exact, if ‘time’ is within its prescribed range then ‘howLongAgo’ will be between zero and ‘segmentLength’, and so will ‘segmentLength’ minus ‘howLongAgo’. IEEE floating-point math guarantees correct rounding so when we divide by ‘segmentLength’ we are guaranteed that ‘t’ will be from 0.0 to 1.0. No clamping needed, even with floats.

This real example demonstrates a few things:

• Any time you add or subtract floats of widely varying magnitudes you need to watch for loss of precision
• Sometimes using ‘double’ instead of ‘float’ is the correct solution, but often a more stable algorithm is more important
• CalcT should probably use double (to give sufficient precision after many hours of gameplay)

Your compiler is trying to tell you something…

With Visual C++ on the default warning level you will get warning C4244 when you assign a double to a float:

warning C4244: ‘initializing’ : conversion from ‘double’ to ‘float’, possible loss of data

Possible loss of data is not necessarily a problem, but it can be. Suppressing warnings, with #pragma warning or with a cast, is something that should be done thoughtfully, after understanding the issue. Otherwise the compiler might say “I told you so” when your game fails after a twenty-four hour soak test.

Does it matter?

For some game types this problem may be irrelevant. Many games finish in less than an hour and a float that holds 3,600 (seconds) still has sub-millisecond accuracy, which is enough for most purposes. This means that for those game types you should be fine storing time in a float, as long as you reset the zero-point of GetTime() at the beginning of each game, and as long as the clock stops running when the game is paused.

For other game types – probably the majority of games – you need to do your time calculations using a double or uint64_t. I’ve seen problems on multiple games who failed to follow this rule. The problems are particularly tedious to track down and fix because they may take many hours to show up.

Store your time values in a double, and then you don’t need to worry, at least not as much, as long as you avoid unstable algorithms.

Next time…

On the next post I think it might finally be time to start jumping into the delicate subject of how to compare floating-point numbers, with the many subtleties involved. Previous articles in this series, and other posts, can be found here.

Bitsquid

Sensible Error Handling - Part 2

In my last post I wrote that there are three kinds of errors that we game programmers need to deal with:

• Unexpected errors
• Expected errors
• Warnings

Expected errors

Minimize the points and types of failures

class SaveSystem
{
 struct Data {const char *p; unsigned len;};
 enum LoadResult {IN_PROGRESS, COMPLETED, FAILED};

 unsigned num_saved_games();
 LoadId start_loading_game(unsigned i);
 LoadResult load_result(LoadId id);
 Data loaded_data(LoadId id);
 void free_data(LoadId id);
};

To except or not to except

class SaveSystem
{
 struct Data {const char *p; unsigned len;};
 class LoadException : public Exception {};

 unsigned num_saved_games();
 LoadId start_loading_game(unsigned i);
 bool load_completed(LoadId id);
 Data loaded_data(LoadId id);
 void free_data(LoadId id);
};

class SaveSystem
{
 struct Data {const char *p; unsigned len;};
 class LoadException : public Exception {};

 unsigned num_saved_games() throw();
 LoadId start_loading_game(unsigned i) throw();
 bool load_completed(LoadId id) throw(LoadException);
 Data loaded_data(LoadId id) throw();
 void free_data(LoadId id) throw();
};

if (ss->load_completed(id)) {
 Data data = ss->loaded_data(id);
 ...
}

1. The code gets littered with error checks, making it hard to read.
2. Undescriptive error codes lead to confusion about what errors a function can return and what they mean.
3. Since C functions cannot return multiple values, we cannot both return an error code and a result. If we use error codes, the result must be returned in a parameter, which is inelegant.

enum LoadResult {IN_PROGRESS, COMPLETED, FILE_NOT_FOUND, FILE_COULD_NOT_BE_READ, FILE_CORRUPTED};
LoadResult load_result(LoadId id);

struct Data {const char *p; unsigned len;};
Data loaded_data();

const char *loaded_data(unsigned &len);

struct SaveResult {
 enum {NO_ERROR, DISK_FULL, WRITE_ERROR} error;
 unsigned saved_bytes;
};
SaveResult save_result(SaveId id);

#AltDevBlogADay

Sensible Error Handling – Part 2

In my last post I wrote that there are three kinds of errors that we game programmers need to deal with:

• Unexpected errors
• Expected errors
• Warnings

An unexpected error is an error that is unlikely happen and that the caller of our API has no sensible way of handling, such as a corrupted internal state, a failed memory allocation, a bad parameter supplied to a function or a file missing from a game disc. I also argued that the best way of dealing with such errors was to crash fast and hard with an assert, to expose the error and avoid “exporting” it in the API.

In this post I’m going to look at the expected errors.

Expected errors

An expected error is an error that we expect to happen and that the caller must have a plan for dealing with. A typical example is an error when fetching a web page or saving data to a memory card (which can be yanked at any moment).

If you are familiar with Java, the distinction between “expected” and “unexpected” errors matches quite closely Java’s concept of “checked” and “unchecked” errors. Checked errors are errors that the caller must deal with (or explicitly rethrow). Unchecked errors are errors that the caller is not expected to deal with. They will typically cause a crash or a long jump out to the main loop, for the applications where that makes sense.

My main rule for dealing with expected errors is:

Minimize the points and types of failures

In other words, just as our APIs abstract functionality — replacing low-level calls with high-level concepts — they should also abstract dysfunctionality and replace a large number of low-level failure states with a few high-level ones.

Minimizing the points of failure means that instead of having every function (enumerate(), open(), read(), close, etc) return an error code, we design the API so that errors occur in as few places as possible. This reduces the checks that the caller needs to do and the number of different possible paths through her code.

Minimizing the types of failure means that when we fail we only do it in one of a very small number of well-defined ways. We don’t return an int error code that can take on 4 billion different values with vaguely defined, ambiguous and overlapping meanings (quick: what is the difference between EWOULDBLOCK and EAGAIN?).

In most cases true/false is enough (together with a log entry with more details). If the caller needs more information, we can use an enum for that specific function, with a very specific small range of values.

Again, the idea behind all this is to reduce the burden on the caller. If there is only a small number of errors that can happen, it is easy for her to verify that she has all the bases covered.

As an example, a (partial) save game interface may look like:

class SaveSystem
{
	struct Data {const char *p; unsigned len;};
	enum LoadResult {IN_PROGRESS, COMPLETED, FAILED};
 
	unsigned num_saved_games();
	LoadId start_loading_game(unsigned i);
	LoadResult load_result(LoadId id);
	Data loaded_data(LoadId id);
	void free_data(LoadId id);
};

Note that there is only a single place where the caller needs to check for errors (in the reply to load_result()). And there is only one possible fail state, either the load completes successfully or it fails.

To except or not to except

Exceptions are often touted as the latest and greatest in error handling, but as you know from my previous post I am not too found of them.

Exceptions can work for unexpected errors. I still prefer to use asserts, but if you are writing a program that cannot crash, an exception can be a reasonable way to get back to the main loop if you reach an unexpected failure state. (It’s not the only option though. Lua’s pcall() mechanism is an elegant and minimalistic alternative.)

But for the expected errors, the errors that are a part of the API, exceptions have a number of serious problems.

The first is that exceptions do not have to be declared in the API, so if you encounter an API that looks like this:

class SaveSystem
{
	struct Data {const char *p; unsigned len;};
	class LoadException : public Exception {};
 
	unsigned num_saved_games();
	LoadId start_loading_game(unsigned i);
	bool load_completed(LoadId id);
	Data loaded_data(LoadId id);
	void free_data(LoadId id);
};

you are immediately faced with a number of questions. Which functions in the API can throw a LoadException? All of them or just some? Do I need to check for it everywhere? Are there any other exceptions that can be thrown, like FileNotFoundException or IJustMadeUpThisException. Should I just catch everything everywhere to be safe?

In my view, this is unacceptable. The errors are an important part of the API. If you don’t know what errors can occur and where, you have an incomplete picture of the API. Fine, we can address that with throw-declarations:

class SaveSystem
{
	struct Data {const char *p; unsigned len;};
	class LoadException : public Exception {};
 
	unsigned num_saved_games() throw();
	LoadId start_loading_game(unsigned i) throw();
	bool load_completed(LoadId id) throw(LoadException);
	Data loaded_data(LoadId id) throw();
	void free_data(LoadId id) throw();
};

Now the interface is at least well-defined, if a bit cluttered. Note that if you go down this route every single function in your code base should have a throw declaration. Otherwise you are back in no man’s land, without any clue about which functions throw exceptions and which don’t.

But declaring exceptions can have its drawbacks too. If you require all functions to declare exceptions, a function that just wants to “pass along” some exceptions up the call stack must declare them. This gives the exceptions an infectious tendency. Unless you are careful with your design the high level functions will gather longer and longer lists of exceptions that become harder and harder to maintain. Templates cause additional problems, because you can’t know what exceptions a templated object might throw.

These issues have sparked a heated debate in the Java-community about whether checked (declared) exceptions are a good idea or not. C# has chosen not to support exception declarations.

At the heart of the debate is (I think) a confusion about what exceptions are for. Are they for diagnosing and recovering from unforeseen errors, or are they a convenient control structure for dealing with expected errors? By explicitly distinguishing “unexpected errors” from “expected errors” we make these two roles clearer and can thus avoid a lot of the confusion.

Anyways, the declarations are not my only gripe with exceptions. My second issue is that they introduce additional “hidden” code paths, which makes the code harder to read, understand and reason about.

Consider the following piece of code:

if (ss->load_completed(id)) {
	Data data = ss->loaded_data(id);
	...
}

By just glancing at this code, it is pretty hard to tell that an error in load_completed() will cause it to leave the current function and jump to some other location higher up in the call stack.

When exceptions are used you can’t just read the code straight up. You have to consider that at every single line you are looking at, an exception might be raised and the code flow changed.

This leads me to the concept of exception safety. Is your code “exception safe”? I’ll go out on a limb and say: probably not. Writing “exception safe” code requires having a mindset where you view every single function in your code base as a “transaction” that can be fully or partially rolled back in the case of an exception. That is a lot of extra effort, especially if you need to do it in every single line in your code base.

It might still be worth it, of course, if exceptions had many other advantages. But as a method for dealing with expected errors, I just don’t see those advantages, so I’d rather use my brain cycles for something else.

So what do I propose instead? Error codes!

Yes, yes I know, we all hate error codes, but why do we hate them? As I see it, there are three main problems with using error codes for error reporting:

1. The code gets littered with error checks, making it hard to read.
2. Undescriptive error codes lead to confusion about what errors a function can return and what they mean.
3. Since C functions cannot return multiple values, we cannot both return an error code and a result. If we use error codes, the result must be returned in a parameter, which is inelegant.

I have already addressed the first two points. By designing our API so that errors only happen in a few places, we minimize the checks that are needed. And instead of returning an undescriptive generic error code, we should return a function-specific enum that exactly describes the errors that the function can generate:

enum LoadResult {IN_PROGRESS, COMPLETED, FILE_NOT_FOUND, FILE_COULD_NOT_BE_READ, FILE_CORRUPTED};
LoadResult load_result(LoadId id);

As for the third problem, I don’t know why C programmers are so adverse to just putting two values in a struct and returning that. In my opinion, this:

struct Data {const char *p; unsigned len;};
Data loaded_data();

Is a lot nicer than this:

const char *loaded_data(unsigned &len);

Maybe in them olden days, returning 8 bytes on the stack was such a horrible inefficient operation that it caused your vacuum tubes to explode. But clearly, it is time to move on. If you want to return multiple value — just do it! The “return in parameter” idiom should only be used for types where returning on the stack would cause memory allocation, such as strings or vectors.

This is how you return an error code in 2012:

struct SaveResult {
	enum {NO_ERROR, DISK_FULL, WRITE_ERROR} error;
	unsigned saved_bytes;
};
SaveResult save_result(SaveId id);

In the next and final part of this series I’ll look at warnings.

(This has also been posted to the BitSquid blog.)

Performance Anxiety 3 – Road Blocks

Damn you, Roadblock!

The learning curve so far while developing our first mobile title, Itzy3D (try the game, plug plug plug), has been steep to say the least.  We knew the task in front of us wouldn’t be an easy one but to actually live through the stress and sleepless nights of it all isn’t anything I imagined it would be.  Casual games as a small business plan makes sense to us, but creating our first product offering has proven to have unique challenges none of us had considered.  It was in the interest of sharing that experience that I sat down and outlined my first two Performance Anxiety pieces.  Those dealt with the specific hurdles we encountered making Itzy3D.  Now that Itzy has been unleashed upon the world a whole new set of performance issues have cropped up.  Road blocks – from trying to get our game to market to making people aware our game is available.  It all rather makes me long for solving the performance issues related to the game’s development that I at least I felt I had some control over.  I’ve recently shared some of the marketing techniques we’re employing to get our little game noticed but now I thought I’d comment on two of the road blocks keeping me up at night.

Apple – When will this frustration end?

Yeah, I feel like throwing a sledgehammer too

Our inexperience on Apple’s procedures launching to the app store have been maddening, as has been Apple’s support.  When we finished the game in early January, it took one button press and we were live on the Android Marketplace within minutes.  With Apple, that button press turned into a yellow “Waiting for review” button.  So we waited.  And waited.  Over a week went by and during this period we made a few upgrades based on feedback we had received.  Since the app hadn’t yet been reviewed, we updated the binary file to the latest version.  That action resulted in resetting us in Apple’s queue.  The waiting started anew.  Eight days later, we received the exciting message that our app was finally being reviewed!  A few hours later, rejected.

The reason Apple gave us was we did not include our in-app purchases for review.  When we contacted Apple to clarify as we had setup all our in-app purchases and submitted them as far as we could tell, a day later they informed us that if we went to the very bottom of the details section of our app (not the actual, in-app setup section), expanded a closed menu, all the in-app purchases were listed there and we simply had to tick off the boxes and resubmit.  We followed the instructions and in another day, we were approved and Itzy3D was live on the App store after roughly two weeks since we initially submitted.  It was then we realized that a seemingly innocent change we had made to the tutorial took away a significant gameplay function in other levels.  We discovered and fixed this error within the day.  Embarrassing, but these things happen.  Surely it wouldn’t take long to have the fix submitted and approved now that the initial review of our app was complete?

It’s now over a month since we submitted our first binary and we still do not have our fixed version of the title on the Apple App store.  The wait for review again seemed about 6 business days, and again our binary was rejected as Apple claims we did not include our in-app purchases for consideration.  The difference is, this time we were submitting an update and the option did not present itself to check off the in-app purchases which have already been approved and are available for sale.  Apple has not yet responded to a single one of our requests for help.  It’s been over a week since we asked for help.

Reviews – I can’t get arrested in this town

Come on! It'll just take a second to have a look

As much as I fear what reviewers will have to say about our first title I’m also excited to finally see our work in the hands of others and hear what they have to say.  It turns out everyone has an opinion until you need them to have one.  I’ve crafted a mailing list which is still a work in progress, I’ve researched review sites and press release agencies and put together a nice little review package and a month after Itzy3D’s launch, not a single reviewer has offered their opinion.  I have had two reviewers contact me and let me know they plan on reviewing Itzy, one contact me and ask to see the iOS version when it’s ready, but of the over hundred reviewers I’ve contacted so far, we have yet to see a single review.

There is an option with many sites to pay for reviews, but given our limited budget I can’t simply throw money at sites to review our game when I don’t even know how many visitor their site see in a day or if we’ll see any impact.  Already, based on the results we experienced with our first advertising campaign I know my money would most likely be better spent on ads than reviews, but it would still be nice to hear something…anything from the review community.

I find what’s eating me up at this point is the feeling that I have so little control.  One of the reasons we went into business for ourselves was so that we could have some measure of control over our ultimate fate for good or bad, but I can’t force Apple to make our updated binary available on the app store.  I also can’t force review sites to skip over their review backlogs and rush to give our game a look.  As much as it was a challenge to overcome some of the performance issues we experienced developing Itzy3D, at least those were challenges we could meet head on.

Confetti Special FX

KGC 2011

KGC 2011 was a blast. We showed off our new Dynamic Global Illumination System demo “RawK II” with dozens of lights with shadows attached and all with one bounce diffuse and specular global illumination. We also showed of the latest code drop of the Dynamic Skydome system … Stay tuned we will be posting screenshots [...]

New Global Illumination System

We are going to show off our new Global Illumination System next week on KGC. This system is fully dynamic, works with static and dynamic objects like animated characters, does not require any pre-process data (game objects are destructible, 24 hour cycle possible, streaming not an issue) and works on a large number of lights. [...]

GDC 2012

GDC is right around the corner. We will have a booth on the expo floor. Please come by and check out our demos. We will also have a talk in the INTEL theater on “Dynamic Global Illumination”. Stay tuned for the date and time.

Agile Game Development

Answering the right questions

Icare3D Blog

Ph.D thesis: GigaVoxels

I defended my Ph.D thesis on GigaVoxels last July, and the document is now online.

You can download it there:
GigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large And Detailed Scenes

You can also check my other publications on my Ph.D webpage.

iDevGames

King of Dragon Pass — Postmortem

King of Dragon Pass is a game for iPhone, set in Glorantha (world of the games HeroQuest and RuneQuest).

Morgan3D / Twitter

morgan3d: SRAA in a single pass http://t.co/tpLJsJZ0

morgan3d: SRAA in a single pass http://t.co/tpLJsJZ0

iPhone Development Tutorials and Programming Tips

Open Source: Excellent Easy To Use Flip (Flipboard Style) Transition Component

Some time ago I mentioned the FlipView component which has since been removed from Github.

I’ve received several inquires about a similar component, and today came across a component allowing you to create similarl styled transitions both horizontally and vertically.  This component allows you to flip with solid colors (you could use a screenshot to create an effect similar to the FlipView component) and dynamic text.

The component also supports several different types of interaction such as tap to flip and page style flipping.

You can see a video demonstration below:

The component is by Dillion Tan and can be found with an example on Github here.

While it’s not quite the same as the previously mentioned component you can see how the flipping is done.

©2012 iPhone, iOS 5, iPad SDK Development Tutorial and Programming Tips. All Rights Reserved.

Morgan3D / Twitter

morgan3d: Some hints of how urban planners now approach pedestrian notions of "distance" and shared space--references dual graphs http://t.co/krFi0gWQ

morgan3d: Some hints of how urban planners now approach pedestrian notions of "distance" and shared space--references dual graphs http://t.co/krFi0gWQ

OpenGL

C/C++ interpreter 7.0 and Embedded Ch 7.0 with OpenGL support released

Ch is an embeddable C/C++ scripting interpreter for 2D/3D plotting, shell programming, numerical computing and embedded scripting. It supports the OpenGL API under Win32, Unix, Linux, and Mac OSX for cross platform scripting without compilation. Ch can be easily embeded or plugin into other C/C++ application programs as a scripting engine for games etc. Ch version 7.0 is a major release with many new features to make Ch especially appealing for secondary school and college students to learn computing and math.

#AltDevBlogADay

My game design hat

One of the main traits that an indie developer must cultivate is that of wearing many hats. All indie game develepers will tell you about it, and it is the first thing you will realise when going indie. Wearing many hats is usually the result of small budgets. Small budgets mean less heads, but equal amount of hats. What I learned through the course of developing my indie game is that your success depends on how well your head fits those hats. Your game will simply be as good as the worst fit.

One of the hats I had to wear for the development of “Pop Corny” was that of the game designer. The closer I had ever come to game design before this, was playing games with a little more inquiring spirit than most players do. This can definitely be interpreted as a bad hat fit. It was clear that in order to have a successful game, I had to find clever ways to improve the fit. This of course could be done by adjusting the head (becoming a better game designer) or by adjusting the hat (adjusting the problem itself to something that I would handle). It was obvious that I had to do the first as much as possible, but without the later I was not going to go far.

Adjusting the head

So I went out and absorbed every single drop of knowledge I could on game design. Read blog articles, watched video presentations, hanged posters of Johnathan Blow over my desk, etc :) All these helped, but I knew that I had to bring the battle to my battlefield in order to win. This meant that I had to base my game on a simple (yet effective) gameplay idea, and build on that using analytic methodology where I can be good at. My guidelines were:

• single touch, simple and effective game mechanic that would make great gameplay for touch devices
• The player should be able to start a game whenever he had some time to “kill”, whether that is 1 minute or 10 minutes or half an hour, and enjoy the game equally.
• The gameplay should not require too much “brainpower” from the player and depend more on trained reflexes and getting used to, while giving you the joy of acquiring true skills.

The process of meeting the above requirements can’t be fully transcribed, as it was mostly intuition based. It was clear that the game had to be an endless runner, which basically means that the player can never finish the game, and getting better would mean better score and more play. This would allow for my “short fun” direction.

I struggled a lot more on what an effective game mechanic should be to produce a great gameplay for touch devices. The simplest of all mechanics on a touch screen is the “tap”. I wasn’t feeling right about it, as it is overused and you probably end up with an experience not so original. Then I looked at swipes. Swipes are simple, but at the same time elaborate enough to resemble real life “game” actions. For example a swipe can be a throwing action in real life. So I centered my thinking around throwing stuff with your fingers. I did some prototypes of throwing circles and hitting rectangles and it was fun. Through an experimentation process I ended up with the “sling” throwing mechanic. You basically swipe in the opposite direction of the intented. This was a revelation. The inverted swipe posed a slight challenge to the players brain, that as one started to get it, it gave a very cool feeling of accomplisment. I went out and gave it to friends so I could test reactions. As people where getting it you could see fingers pointing all over the screen… fights over the who plays next, etc… I was convinced.

Mr. Pop Corny is a popcorn loving monster

The idea of the pop corn, the pop corn loving monster, etc came from my sister during a brainstorming session. So we had a theme. Next we started thinking of ways to enrich the experience and keep the players’ interest for longer time. One of the elements that worked was the “box progression”. I got the idea originally from Tiny Wings, and the way you upgrade nests, but found out that it is a common thing in the iPhone games field. So the user has to complete certain objectives to upgrade his popcorn box and get bigger score multipliers. We also used this progression to teach the player how to get bigger scores, and survive longer. After that we added an extra task of collect drachma coins for the player (an inside joke for my country possibly defaulting to its national currency drachma). He could then use the drachma coins to upgrade bonuses and buy new pop corn boxes that gave extra powers. So the game became more complex and hard to balance, but this was mainly a problem I could cope with as an engineer. I was in my field.

Do it like an engineer

Questions like “how much should a bomb cost?” (a bomb is used once and pops all corn on the screen at once) are hard to answer without the right tools. What data is necessary to give a good answer? For the above question you need to know the answer to at least “How many coins does the player get in one game session?” and “How many bombs in a single session does not put the game out of balance?”. An experienced game designer might be able to answer the original question by instinct and get it right. However, I had to do what I can do good. Break down, measure, answer, build and repeat until the required feeling is achieved.

What I did was log all the key elements of game sessions by beta testers, and interpret them with the so handy SciPy and related NumPy modules for python. These modules allow you to easily read csv files, process the data with almost every statistical analysis method in the world, produce beautiful graphs, etc. For example lets look below at the number of sessions per coin collected range. These are the samples that were collected for the same player level in the game.

These follow the normal distribution around the value of 80. This means that most of the times a user will collect 80 coins per game. However there might be caveats if we are not careful enough. For example lets look at the distribution below:

If we try to fit a Gaussian function in the above data we will have huge errors in our estimations. Before we go and hit least squares and optimization algorithms, we would always try to think through of what is generating the data. Here the false assumption about our data comes from the fact that we consider them all to be coming from the same “generator”. That “generator“ is the player interacting with the game in order to collect as many coins as one can. However because the game is a beta, and users are beta-testing it, the generators are two. The first is the one I described before, but there is also the sessions that the user tries to test some other aspects of the game and does not collect coins! So what we really have here is two different data sets mixed to one. One from the players trying to collect coins that produces a distribution of values around 80 (the red graph) and one from the players that don’t collect because are testing something and produce a distribution of values around 0 (the green graph). Adding the red with the green gives the original observed blue. The graph bellow illustrates it:

So we need to fit the sum of two Gaussians in our data with unknowns the two mean values and the two variances. This way we get the correct value of 80 for the mean coins collected per game session, which would otherwise be detected as 60 or something. So if you want the player to be able to afford 3 bombs every 4 games you set the bomb to cost 100 coins and you are set.

Conclusion

This was my approach to designing my game, and it seems to have worked out quite well, with the game receiving great acceptance. The game got to #1 Top Paid Game in the Greek AppStore within hours of its release and #2 Top Paid across all app categories, all 5 star reviews. On most reviews the addictive gameplay was mentioned, which is so comforting when I know that was not my best field. It turns out you can replace part of intuition and experience with analytic tools.

You’re So Vain

Games and gamers are a pretty self-involved bunch. We make games that are impossible to play without a couple years practice, games with communities that are hostile to “outsiders”, and games that talk, sometimes literally, about themselves. Are we still so insecure that we’re afraid to explore other fields or audiences?

I touched on this problem in my last AltDevBlog post, Talkback Games. ‘Gamers’ as an audience are easy, we know the input  language that game systems expect, and games feed back the language that players expect. Gamers know that an ammo stockpile means you’re about to meet a boss, or that you need to quicksave often, etc…  So yes, making games that reach outside this system is harder. Not only do you have to make simple or easily taught interfaces, but feedback has to be intuitive to non-gamers. However, I don’t think that blaming the lack of accessible mainstream games on lazy devs is either accurate or fair.

Can we blame the audience? The game community is known for its outspokenness, and studios have to work under the watchful eye of a legion of fans. Try to make a more accessible PC game and be accused of pandering to consoles. Make a sequel that departs too much from the original(s) and no one buys your game. The fickleness of audiences, and studios too willing to pander to them produces an industry afraid of change. This is hardly a new statement, but people seem to accept it. The mainstream game industry is in serious danger of following the same route as comic books. Readers became so averse to new series that publishers stopped making them, instead making countless crossovers that sold well, but were of no interest to non-fans. Today, comics are most definitely a cult industry, with the top-sellers only popular due to film/tv adaptations. We can only avoid the same fate if gamers become willing to spend their money on different games. Smaller, different games can still sell well (obligatory Minecraft reference) so is the audience really so afraid to try new things?

Something else is holding developers back. The ‘art’ or ‘Art’ debate is tiring now, but many of the popular ‘Art’ games cited are those that dissect other games. Bioshock as comment on gamers’ lack of narrative control, The Stanley Parable as rant against traditional narratives in games.  The audience might find it interesting, but in the end, players don’t care about theories of game design, they just want a good game. There is a danger of creating a culture that just wants to talk about itself, like some unintentional parody of post-modernism. Repeating a statement about game mechanics isn’t noteworthy, you have to use it to help another statement. Shadow of the Colossus uses gamers’ urge to continue to make a tragedy, the player realises the horror of what they are doing, but is unable to stop. I just watched The Artist, and although at first I thought it was exploiting the style of silent films as a gimmick, it plays with the format to enhance the story. It uses this knowledge of film techniques to make something new, interesting beyond a pastiche.

So where does all this come from, and why can’t we stop? Perhaps we can blame the stereotype of the ‘gamer nerd’. Games have been looked down on for most of their existence, maybe we’ve just given up trying to reach out to new players. We turned to the art world in an attempt to justify all this to ourselves. A museum is a terrible place to put games, yet we parade them there to get the approval of ‘real’ artists. But we don’t need them, we have the attention of the wider world and it wants to play games, as Zynga has shown. We need to stop looking at the magic mirror and make games for everyone else.

Note: This is reposted on my blog, if you’re into that sort of thing

OpenGL

Qt SDK 1.2 Released with threaded OpenGL

Qt SDK 1.2 update sets a new baseline for the developers for a longer perspective. Qt SDK 1.2 now integrates the very latest tools, most recent mobile build targets for Symbian and Nokia N9, and the still fresh Qt 4.8 for desktops. Threaded OpenGL support enables those who are not OpenGL-ninjas to render OpenGL from more than one thread concurrently. More info on threaded OpenGL in 4.8 is available in this post.

XNA Creators Club - News List

Five New Markets for Windows Phone Developers

Windows Phone Marketplace is now officially open for business in 5 new markets around the world—Argentina, Indonesia, Malaysia, Peru, and the Philippines

OpenGL

Khronos Group launches 2012 Pan Pacific Tour starting in February

Throughout 2012, The Khronos Group is hosting a series of media events, educational sessions and F2F meetings for consortium members and prospective clients. The Khronos Pan Pacific Road Show 2012 is devoted to our members and colleagues in the Pan Pacific region with a focus on education and training, OpenGL and OpenGL ES, OpenCL, WebGL and WebCL. Complete details on all the upcoming events can be found on the Khronos Group event page. The first events will be held in Taiwan starting February 13 2012.

Gamasutra Feature Articles

Happy Action, Happy Developer: Tim Schafer on Reimagining Double Fine

This week, Double Fine launched Double Fine Happy Action Theater, a Kinect-based game and the first in its second set of small projects -- a shift into little games the studio made after 2009's Brütal Legend. In this interview he reflects on those, and talks Kinect tech, too.

Real-Time Rendering

CFP: IEEE CG&A, “Scattering: Acquisition, Modeling, and Rendering”

Like the title says, IEEE Computer Graphics & Applications has a call for papers on the topic of scattering: acquisition, modeling, and rendering. Deadline is August 25th, for inclusion in their May/June 2013 issue. See the complete CFP here.

Geeks3D Forums

OpenCL - The Future of Accelerated Application Performance Is Now

OpenCL™: The Future of Accelerated Application Performance Is Now

OpenCL™, or Open Computing Language, is the first open programming standard OpenCLfor writing software for...

MSI Afterburner 2.2.0 Beta 12 (2012-02-02)

Hi guys, today we have another update of MSI Afterburner 2.2.0 beta 12, do you guys find the Beta 11 already support HD 7950? If not, you can also use the Beta 12 to support HD 7950! There is another new GPU (5500+2270? lol) is supported by Afte...

Shared Level-1 instruction-cache performance on AMD family 15h

AMD family 15h-class CPUs use a new micro-architecture that, under specific circumstances,
leads to different performance characteristics compared to previous processor generations.
This white paper describes the nature of instruction-cache cr...

Morgan3D / Twitter

morgan3d: Wow, NS2 is looking really good: http://t.co/E1EZ9e28 It appears to be time to eat some space marines.

morgan3d: Wow, NS2 is looking really good: http://t.co/E1EZ9e28 It appears to be time to eat some space marines.