Thursday, November 13, 2014

Game Outcomes Project Methodology


This page is designed to explain the technical details of the Game Outcomes Project, as the technical appendix to a 5-part series.

The Game Outcomes Project team includes Paul Tozour, David Wegbreit, Lucien Parsons, Zhenghua “Z” Yang, NDark Teng, Eric Byron, Julianna Pillemer, Ben Weber, and Karen Buro.

In October and early November of 2014, the Game Outcomes Project team ran a survey targeting game developers asking roughly 120 questions about each respondent's most recent team-based game development effort.  Questions centered on development culture, teamwork, project management, and the project's outcome.

We received 771 responses, of which 302 were completed, and 273 referred to projects that were neither cancelled nor abandoned.

We chose to exclude responses related to cancelled and abandoned projects for reasons we explain at the end of this post.  This blog post explains our survey design methodology and our  analytical methodology for the remaining 273 questions for those who wish to delve into the statistical and mathematical details.

In other words, this is the page for all of the gory technical details we didn't want to put in the other articles.

You can download the survey questions here: (PDF).

We will also make our full data set available shortly after publication of the final article.

Survey Design Approach


Our survey was designed as follows:
  • Page 1 was a merely a qualifier page.  In order to ensure that we received responses only from our target demographic, we asked respondents to only complete the survey for projects with known outcomes within the last 3 years which had a team size of 3 or more and on which they had served in a development role.  Although we posed these questions as four check boxes, this was merely to dissuade casual survey-takers or inappropriate respondents, and the answers to these questions were ignored in our analysis.
  • Page 2 contained background questions such as team size, production methodology, financial incentives offered to the team, and project lifetime.
  • Pages 3 and 4 contained a little over 100 questions around teamwork, culture, and various other factors relating to game development using a 7-point Likert scale.
  • Page 5 asked only four questions, asking respondents to rate the outcome of the project along a 6- or 7- point Likert scale for four different dimensions: project delays or cancellation, return on investment, aggregate review scores (MetaCritic or GameRankings), and the team's internal satisfaction with whether the project had achieved its goals.
In designing the survey, we took several steps to help reduce the risk of bias.  Although some survey respondents have complained about these aspects of the survey, they were entirely intentional:

  • We occasionally asked important questions twice, once with a positive frame (“I rarely had to work overtime”) and once with a negative frame (“I had to work a lot of overtime”). We did this as we were concerned that if we asked all questions with same frame, respondents who felt positively or negatively about a project would be tempted to simply scroll through the list and click somewhere along the “agree” or “disagree” part of the spectrum.  We felt that intentionally disrupting this behavior by occasionally shifting the frame of the questions would force the respondent to pay attention and consider each question individually.
  • We sometimes asked slightly different versions of the same question in an attempt to tease out the cause of some phenomenon. For example, we had five questions related to “crunch” and overtime, and one of those questions asked about voluntary overtime while another asked about mandatory, imposed overtime. We felt we could use these subtle distinctions to tease out deeper causal factors (spoiler: we could, and we did).
  • We deliberately removed the section names and enabled randomization of the question ordering via SurveyMonkey. Although this led to a large wall of questions that was off-putting to some respondents, we felt that announcing the section names openly might tip our hat as to what we were looking for in each section, and allowing the answers in each section to remain clustered together would likely have a similar effect and allow respondents to simply use the same answer for all questions in that group. By randomizing the ordering of all the questions on a given page, we would greatly reduce the likelihood of these sorts of phenomena.
  • We added a qualification page at the beginning of the survey asking respondents to continue only if they had worked on a team project in a development role within the last 3 years that had some sort of known outcome. We deliberately wanted to avoid continuously-developed projects as the outcomes of these types of efforts are much more difficult to quantify.

Participants


We recruited participants from several different sources.  Of the 771 responses we received, our best guess as to the distribution (based on the timings of the various surges we observed in survey completion) is as follows:

  • ~100 responses: posts on TheChaosEngine.com (internal, private game industry forums)
  • ~120 responses: announcement on Gamasutra.com
  • ~400 responses: direct IGDA mailer exclusively to IGDA members
  • ~150 responses: Twitter announcements, various other forum posts, and other/unknown sources
Given the diversity of sources both here and in our final responses, we feel comfortable asserting that our results represent many different teams of many different sizes (though with a moderate bent toward AAA development over indie development, based on the "final team size" results).

However, we have no way to track completion rates, so it's impossible for us to determine which of the final 273 responses (all responses which were fully completed and referred to non-cancelled projects) derived from each source.

The Aggregate Game Outcome Score


Lacking any way to objectively define “success” or "failure," we decided that the best way to quantify the outcome was through the lenses of four different kinds of outcomes – critical reception, return on investment (ROI), delays or cancellation, and the team’s own perception of its success or failure – and later combine them into a single “outcome” score during the post-survey analysis phase.  This led to four questions, each of which allowed answers along a 6- or 7-point scale.
  • Delays: “For the game's primary target platform, was the project ever delayed from its original release date, or was it cancelled?”
  • ROI: “To the best of your knowledge, what was the game's financial return on investment (ROI)? In other words, what kind of profit or loss did the company developing the game take as a result of publication?”
  • MetaCritic: “To the best of your knowledge, was the game a critical success?”
  • Internal: “Finally, did the game meet its internal goals? In other words, was the team happy with the game they created, and was it at least as good as the game you were trying to make?”

We base the decision to combine the four outcome values into a single score on two factors.  First, since all four questions are related to different aspects of project outcomes, it seems intuitively obvious that they are related, and that all of these four different aspects of the project’s outcome must have come after the end of development, and had to have been caused by the development cycle itself (or other factors, such as consumer tastes and marketing spend) rather than by each other.

Secondly, all four outcomes are strongly positively correlated to one another, as shown in the scatterplots below.

Figure 1. Animated GIF of cross-correlations betweeen all four game project outcome factors (on a 4-second delay).

Note that this image is an animated GIF with a 4-second delay; if you don't see it changing, wait a bit longer for it to finish loading.  Also note that all data has been randomly "jittered" slightly for these charts to make coincident data points more visible.  Note also that all four of these output dimensions have been "normalized" on a 0-1 scale with a "1" being the best possible outcome (the game shipped on time, critics loved it, it made huge piles of cash, or the team was thrilled with the fruits of their own efforts), and lower values being quantized equally along the 0-1 scale depending on the number of gradations in the question.

Each of these correlations has a p-value (statistical significance) under 0.05 (the p-value gives the probability of observing such data as in our sample if the variables were be truly independent; therefore, a small p-value can be interpreted as evidence against the assumption that the data is independent).  This makes it very clear that the four aspects of game project outcomes are interrelated.

We eventually settled on a simple non-weighted sum for the aggregate outcome score.  Although we were tempted to give each outcome value a coefficient, there is no objective basis for determining the coefficients.

We assigned the best possible outcome for each factor (terrific reviews, makes lots of money, no delays, team couldn't be happier with it) a value of 1.0, and we gave a worse outcome a correspondingly lower score (closer to 0) along a linear scale depending on the number of gradations in the questions asked (some of the outcome questions were asked on a 6-point scale, others on a 7-point scale).  We then added them together.

        Score = 25 * ((Delays) + (ROI) + (MetaCritic) + (Internal))

Note that the multiplication by 25 effectively converts the score to a 0-100 range, since each of the 4 outcome values is between 0 and 1.

We also experimented with exponents for each factor which we tuned in Solver to try to maximize the cross-correlations between the outcome factod, and with multiplying them as a probability value instead of simply adding them.  However, we found that simply adding the four outcome factors, in addition to being simplest, achieved the highest correlation, and we could not justify the additional complexity of any other approach.

Missing Data Handling


Roughly 5% of the data in our survey was missing, as we allowed respondents to leave a small number of questions blank on pages 3-5 of the survey.

For the majority of the responses, we simply averaged the non-blank data for each question using the AVERAGEIF() function in Excel, and then used this to fill missing data for that question.

For the four outcome questions, given the critical nature of these values, we felt a more exhaustive approach was required.  Here, we used the mean of two values: the average value of all non-empty responses to that question, and the average of all other non-empty outcome values for that response.

Correlations and p-Values


As nearly all of our data used a Likert scale, the Spearman correlation was a more appropriate measure than the more commonly-used Pearson correlation coefficient.  This required us to use the SCORREL() function from the Real Statistics Resource Pack available from real-statistics.com rather than the built-in CORREL() function in Excel.

In practice, we found there was little difference between the two -- typically, a difference of less than 0.02 for nearly all of our correlations, though occasionally (in less than 2% of cases) the difference was as large as 0.07.  However, despite these nearly-identical results, we felt it was essential to go the extra mile and use the more-accurate Spearman correlation coefficient.

We used a p-value threshold of 0.05 for each factor in our survey; however, only 4 questions had p-values between 0.01 and 0.05, so had we used a lower p-value threshold of 0.01, this would have only invalidated 4 of our 120 questions, which would not materially change our results.

In cases where we compared a binary variable to the combined outcome score, we used the Wilcoxon Rank Sum Test to determine p-values (via the WTEST() Excel function provided by the Real Statistics Resource Pack).  This includes the various types of financial incentives discussed in article 1.

In cases where we compared a variable with several discrete, independent values to the combined outcome score (such as which production methodology or game engine was used, as discussed in the first article), we used the Kruskal-Wallis test to determine p-values (via the KTEST() function provided by the Real Statistics Resource Pack).

Cancelled and Abandoned Projects


We decided to ignore responses that turned out to be for cancelled or abandoned projects. This was a tough decision, but the fundamental problem is that we have no good way to assign an outcome value to a game project that was cancelled or abandoned before completion – the “outcome” has to include its critical reception and ROI for a real direct comparison, and since it was cancelled before completion, these will never be known.

Initially, we felt a 0 was a proper score for a cancelled project. This makes intuitive sense, as surely a cancelled project is the worst possible outcome and has no value, right?

But this isn’t necessarily the case. There’s a world of difference between a team abandoning what could have been a great game 3 months into development because they decided that working on some other, even greater game project would be a better use of their time, and a team slogging through a multi-year death march, impairing their health with extended overtime, and ending up with divorces, only to see their game cancelled at the last moment. Those two games should score very differently in terms of their “outcome,” and for cancelled or abandoned projects, that data does not exist.

There’s also the simple fact that many times, cancellations and abandonment are caused by factors outside the team’s control. Perhaps a key employee ran into health issues, or perhaps despite a team being terrific and working on a very promising game, the parent company ran out of money and had to close up shop. These kinds of stories happen all the time, and of course there would be no way for our survey to detect these things.

That’s not to say that cancellation and abandonment are entirely random. However, we found that the correlations with cancellation were generally far lower, and only a handful of variables correlated reasonably well with this outcome. We hope to discuss the cancellation issue further in a future article, but for main part of our series, we focus solely on non-cancelled game projects.


Predictive Modeling


We looked at a number of different ways of building predictive models that would use all the inputs to predict the aggregate outcome score.  We imported the data into Weka and tried the following models:
  • Linear Regression Full: 0.82
  • Linear Regression 10-fold: 0.51
  • M5 Prime Full: 0.89
  • M5 Prime 10-Fold:0.59
  • Additive Regression (20 learners) Full: 0.81
  • Additive Regression (20 learners) 10-fold: 0.62
We also built two linear regression models in Excel, limiting ourselves only to inputs which exhibited statistically significant correlations (p-value < 0.05) with the aggregate outcome score (this excluded only roughly 30 of the ~120 survey questions).  The full linear correlation achieved a correlation of 0.82, identical to the Weka linear regression above.

However, to avoid overfitting, we later constrained the linear regression so that the correlation coefficients had to have the same signs as the correlations of those underlying inputs.  This gave us a correlation of 0.73 -- still an excellent correlation.

We also ran cross-validation with separate parts of the data set (excluding 20 data points at a time, roughly 10% of the data set) against this linear regression, with identical results.

We ultimately used these linear regression coefficients to help us identify the most useful and relevant independently predictive variables in the Self-Reflection Tool and to construct the linear regression model provided in that tool.

Data Verification


We asked respondents to subjectively grade nearly everything in our survey.  Therefore, we cannot independently verify the accuracy of the responses, as we have not worked on the game development teams the respondents report on, and in most cases, we don't even know what specific projects they relate to and have no way to find out.

However, we did ask an optional question at the end regarding the name of the project in question.  Roughly 10% of our respondents answered this question.  This allowed us to do two things:

  • For those that did answer the question, we looked at MetaCritic scores of those game projects, and were able to verify that the question regarding MetaCritic scores had indeed been answered accurately.
  • We had hoped that there would be several cases where different people on the same team reported on their project.  However, there is only one case in our data where two respondents reported on the same project AND supplied the name of the project in this optional answer field.  However, we did compare these two results and found that the answers were quite similar, with the answers to most questions differing by 1-2 gradations at most.
Therefore, although we have no way to independently verify the data, those two avenues of investigation underscored that we have no reason to doubt the veracity of the data.

Additionally, although some of our friends at GamaSutra were worried about the survey potentially being overrun or trolled by those who use the "#GamerGate" hashtag on Twitter (as a previous Gamasutra developer survey had allegedly been recently corrupted by this loose affiliation of individuals apparently angry at that publication), we heard no rumblings of any ill will toward our survey on social media, and we felt it was unlikely that anyone would complete an entire 120-question poll just to try to bastardize a survey.  We also felt that anyone attempting that kind of "trolling" would likely reveal themselves with snarky comments at the end of the survey, and we saw no comments whatsoever that appeared snarky, disingenuous, sarcastic, or otherwise likely to have come from anyone other than genuine game developers.  Therefore, there is simply no evidence that might allow us to believe that any such corruption would have occurred.

"Bitterness Bias"


Some on our team pointed out that there may have been pre-existing bias on the part of respondents to answer questions in a positive or negative way depending on the outcome.  In other words, participants who worked on a troubled project were probably more likely to feel lingering bitterness toward the project or the team and answer negatively -- especially if they were laid off or experienced significant stress on the team -- while respondents who had a positive experience would be more likely to answer positively.

We cannot deny that some minimum level of bias is entirely possible, or even quite likely, and that this surely impacted the answers to some degree.

However, a large part of the point of our study was to identify which specific factors made the most difference in outcomes.  We would expect that when people felt emotional bias toward or against a past game project that skewed their answers away from what they might otherwise have answered, this bias would affect most, if not all, of their answers in that direction.  However, we should not expect that it would create the kinds of clear correlations that we actually see in the study, where some elements have far stronger correlations than others.


Why We Call it a Predictive Model


We refer to our linear regression models (both the one used in the charts in parts 1 and 2 of our article series, and the slightly different ones included with the Team Self-Reflection Tool) as "predictive models."

We justify this claim due to the fact that with every linear regression we've built, we've been able to predict the outcome scores from the input factors with a very high degree of accuracy (correlations 0.6-0.82).  We've also maintained an "out-of-sample" set in each case, and we were able to show that the prediction performed just as well on the out-of-sample group as it did on the training set.

One can certainly argue that our correlations do not imply direct causal links, and there may be additional factors involved behind the factors we listed that are the actual causes of the correlations.  This may be true; however, this does not make it any less of a predictive model.

We know that the outcomes are caused either by the factors we listed or by other factors not listed which influenced both these factors and the related outcomes; we know for certain that the causality does not go the other way (i.e, the outcomes do not cause the inputs, since they came later in time).  So regardless of which case is true, it remains a predictive model.

Optional Questions - Text Entry


We also gave respondents an opportunity to optionally provide three forms of information via text entry boxes.  Roughly 5-10% of our respondents answered each of these.

  • We asked respondents what game they were replying about.  This was primarily to identify cases where multiple respondents referenced the same game (only 1 game mentioned was shared between 2 respondents, and the respondents' answers were nearly identical).
  • We asked for suggestions for improving the survey in the future.  Some of these are listed in "Future Directions," below.
  • We asked respondents to share any interesting comments about their experiences on the team.  Some of these stories were truly amazing (or horrifying).  Where we can do so without violating privacy, we are sharing these anonymously on Twitter at a rate of 1-4 every week.  All of these are marked with the #GameOutcomes hashtag for easier searching.


Future Directions


We regard the first iteration of the Game Outcomes project as a surprisingly successful experiment, but it has also given us an excellent guide for refining our questions in the future.

In future versions of the Game Outcomes Project, we expect to be able to narrow our list of over 100 questions down to 50 or so, and add a number of additional questions that we simply did not have room to ask in this version of the survey:
  • What was the working environment like?  Was it mostly comprised of cubicles, 1-person offices, multi-person offices, or open working space?  Did the working space facilitate team communication, and did it foster enough privacy when developers needed to hunker down, focus, and get work done?  Significant research indicates that cubicles, often championed in the industry for fostering communication, actually hinder both productivity and communication (link link link link)  At the same time, there is some evidence to indicate that a moderately noisy environment can enhance creativity.
  • Was a significant amount of work on this project thrown away due to re-work?
  • How did the team hire new members?  Was there a formal, standardized testing process?  Did the team do any level of behavioral interviewing techniques?
  • How long had the team worked together?  A significant amount of research shows that teams working together for the first time are far more mistake-prone, while teams that have worked together longer are far more productive (Hackman).
  • To what extent was the team working on an innovative design as opposed to a clone or a direct sequel?
  • To what extent was the studio’s structure flat or hierarchical?
  • To what extent was customer focus a part of the development culture?
  • Did the game’s production have a discrete preproduction phase, and if so, how good a job did the team do of ironing out the risks during preproduction?
  • Did most team members exhibit professional humility, or were there many know-it-alls who always tried to prove themselves smarter than everyone else?
  • Did the studio have fixed "producer" roles, or were production tasks shared by other team members?
  • How did accountability work at the studio?  How did the company determine who to hold accountable, and for what, and in what way?  Was the management particularly obsessed with holding individuals accountable?
  • When code reviews or peer programming occurred, what form did they take?  Were they performed as team reviews, one-on-one reviews, peer programming sessions, or reviewed checkins?  How many developers were involved in each review, and how frequently were they performed?
  • Did the organization have performance reviews, and if so, how did they work?  Were they manager-driven reviews, "360-degree" reviews, or stack-ranking, a la Valve?  If stack-ranking was used, was it democratic, or manager-driven?  Some surprising recent research indicates that performance reviews may actually not only be useless, but counterproductive in their entirety  ...  and some evidence that some forms of stack ranking (particularly those that require termination of the lowest-ranked N% of staff) are highly counterproductive.
  • We will likely ask respondents if they took the 2014 survey or read our articles on the results, so we can compare those who answered 'yes' or 'no' to each question and see whether this may have influenced their responses.
  • It has been noted that our focus on outcomes really only looks at one aspect of team effectiveness.  The other two aspects are individual development and well-being (i.e. did team members end up better off than they started, able to keep working, and with an improved skill set?) and team viability (is the team still intact, still working together well, and able to develop another game at least as good as the last one)?  This will allow us to not only answer the question of what made a team successful, but what made it effective.

Initially, we had also questions about the development team’s gender and ethnic composition and geographic location in the initial survey, but we had to drop these due to space constraints and concerns about spurious correlations; we may bring them back in future versions of the survey.

A number of additional questions were directly or indirectly suggested by survey respondents themselves in our optional text entry boxes at the end of the survey:

  • Was the team's leadership mostly composed of individuals from an art, programming, design, production, or biz dev background, or a combination?
  • What percentage of the design decisions on the game was made by those in the trenches – the artists, programmers, or designers?
  • What percentage of the design decisions were made by people in leadership roles with no formal design authority, such as producers?
  • Were the team leads particularly heavy in one discipline (art, engineering, or design), or was there a mix, or was the leadership comprised mostly of producers or managers with little or no discipline-specific experience?
  • If the team disagreed with a decision made by the project’s leadership, was it able to get the decision changed?
  • What was the process for how new team members were trained or incorporated into the team? 
  • To what extent did the team use internally-developed vs. externally-developed tools?
  • How would developers judge their quality of life?
  • Did team members have a good sense of when a feature is complete?
  • Did the team spend a significant amount of time and resources creating demos for upper management or the marketing department?
  • The Joel Test contains a number of interesting questions (more directly related to software development teams) worth investigating further.
  • Was the team happy, and did the project’s leadership work to help facilitate happiness?  (There is significant research showing happiness causes higher productivity, not the other way around; Scott Crabtree of Happy Brain Science can tell you more about this)
We are also considering modifying our outcome-related questions to allow respondents to select the ranking of the outcome factors in order of their importance to the team.  Although we suspect most teams will have return-on-investment (ROI) as the most important factor, we suspect a good deal of variability in the ranking of the remaining factors.  This ordering could help us develop a more accurate aggregate outcome score that took into account the actual importance of each outcome factor for each team by weighting them appropriately.

We will also likely add a question related to overall marketing spend, not because we doubt the role of marketing in altering a project's outcome, but only so that we can subtract the effect that we expect to see here.  In other words, taking marketing budgets into account will help us more accurately estimate the effect of all the other factors.

We will likely  use a lower p-value (0.01) in order to further reduce any uncertainty about our results (although, again, using this lower p-value on our current data set affects fewer than 5% of our results).

Finally, we will ask participants if they also took the 2014 version of the Game Outcomes Project survey and/or read its results, as this will allow us to detect any potential biases or differences in answers between those who did and did not participate in the previous survey, and whose answers may have been influenced by some level of bias due to awareness of our intentions with the survey.
Posted by at No comments:

Monday, September 29, 2014

Call for Participation: The Game Outcomes Project needs your help!



Hi everybody,

The blog has been on hold for a while as I've been working on something much more important: starting up a new studio in Austin, TX, which I look forward to announcing in just a few weeks!

In the meantime, I've been participating in an exciting new project with a team of five producers from the IGDA Production SIG and an advisor from the Wharton School of Business.  We've built a unique study which is, as far as I can tell, the first and most comprehensive study of its kind in the game industry.

If you’re a game developer with at least one team project under your belt, please help us by taking a brief survey about your most recent team project in the industry.

Here's the official description:


The Game Outcomes Project
is a first-of-its-kind experiment to statistically evaluate game development efforts across hundreds of game teams and generate insights as to how teamwork, culture, leadership, and production practices contribute to the success or failure of game development projects.

Currently, there’s little or no actual data on how different factors such as crunch/overtime, production methodologies, or team size impact the success or failure of projects in the game industry.

We hope to change that!

With your help, we hope to gain insights at to what factors produce the greatest risks in game development and what best practices development teams can follow to better manage the risks they face.

You can access the survey here --- >> https://www.surveymonkey.com/s/FDGPLL5 <<


The Game Outcomes Project is not affiliated with the annual IGDA Developer Satisfaction Survey or any other survey or organization.

Please help spread the word!  Share the survey with your colleagues, and follow us on Twitter at @GameOutcomes.
Posted by at No comments:

Sunday, December 1, 2013

Decision Modeling and Optimization in Game Design, Part 9: Modular Level Design

This article is the ninth in a continuing series on the use of decision modeling and optimization techniques for game design.  The full list of articles includes:


The spreadsheet for this article can be downloaded here: link

We've had to put off this instalment of the series for the last few months, as we've been very busy starting up a brand new game studio in Austin.

 We're looking forward to announcing more about that in 2014, but in the meantime, we took advantage of Thanksgiving break to finally write up the long-awaited Part 9 of this series.  We apologize for the delay and hope to get Part 10 completed by January.

The Story of Pirate Planet

It was a warm day in Austin in April of 2007.  As they waited for feedback, the level design team for Pirate Planet on Metroid Prime 3: Corruption grew nervous.  They had been working on building Pirate Planet, one of the game's major worlds, for over five months, but for one reason or another -- due to the inevitable delays and re-prioritizations that always occur in game development -- they had never had a chance to show it to Kensuke Tanabe, their supervisor from Nintendo's Software Planning and Development group.

Now they were only a scant few months from ship, with precious little time for changes, and Tanabe-san -- a man whose frequent and major design changes were almost as legendary as Miyamoto's -- did not seem pleased.

In fact, he seemed rather disappointed.

Instead of offering his usual feedback, he simply said, "Come back tomorrow.  I'll have feedback for you then."

Tanabe-san took a build of the game into his office and shut the door.

When the next day came, the team was stunned.  Tanabe's plan was more than an overhaul -- it was a dramatic redesign.  Every single room was to be connected to a completely different room than before.  The entire world of Pirate Planet was to be completely rearranged, and even many basics such as item pickups were to be moved.

The level design team went through the usual stages that Retro developers experienced when confronted with the often overwhelming feedback from their Nintendo bosses: first, horror at the enormity of the challenge of making so many changes; second, reluctant acquiescence to the fact that they did indeed have to make all the changes listed; and finally, acceptance when they saw the effect of the changes in-game, and realized that nearly all of them were for the better.

The Metroid Prime games benefited enormously from this kind of modular approach to level design, which allowed them to build expensive "rooms" and cheaper "hallways" and separate them with identical doors (which also cleverly masked the loading times as new rooms were streamed in).  This gives designers a great deal of flexibility, then, as it allows them to quickly modify the configuration of an entire level.  Many games use broadly similar approaches, with The Elder Scrolls: Skyrim being a notable and very successful example.

The configuration of the level, then, can be seen simply as a graph.  Each node in the graph is one room, and its connections to other nodes indicate how its various entrances and exits connect to other rooms.

In theory, if we had a formula to tell us whether one graph configuration was "better" than another, we could use that to optimize an entire level, and find the "best" one.

Of course, that's theory.  Naturally, if you're an experienced level designer / world-builder, you know that there are far too many factors that go into consideration when building a level to try to build all of these considerations into any kind of neat mathematical formula or an Excel spreadsheet.  It's an ongoing, iterative process, with countless considerations based on all of the player's possible paths through the space.

But it's useful to take a look at how you would approach this problem in practice to see what can be done and how you can go about doing it, and what the capabilities and limitations of decision modeling techniques are when we apply them to this sort of problem.

And it's useful to know that there's a tool that can answer part of the problem for us, and suggest possibilities, even if we don't end up using decision modeling to figure out how the rooms are connected.

A Sample Problem

Suppose for a moment that our game is based on a reconfigurable room system, just like the Metroid Prime games.  Assume that we have various types of rooms that all fit within a square grid.  We have pre-built rooms that connect 2 neighboring rooms ("L"-shaped or straight line), rooms that connect 3 other rooms ("T"-shaped), and rooms that connect 4 neighbors ("+"-shaped).

We can visualize these as similar to the road tiles in the classic board game Carcassonne (playable on Kongregate here):


Assume we have a fixed "level entry" and "level exit," and we need to figure out the best set of rooms that will connect them.


We can place any of our rooms anywhere inside the grid, and we can rotate them arbitrarily.  Also, for the sake of simplicity, assume that rooms with 2 exits ("hallways") can be arbitrarily bent or un-bent like a garden hose, so that we can switch any such "hallway" piece between straight and L-shaped as needed.

Your problem is as follows: given the entry and exit points marked above, and assuming you have 9 "2-way" rooms, 4 "3-way" rooms, and one "4-way" room, what's a valid way to place all the rooms in the 5x7 grid above such that each room is used exactly once?


Optimizing Connectivity

We'll begin by using the cells in the 5x7 grid as our decision cells.  Each cell will hold either a '0' or a '1' -- a '0' to indicate that there's no room in the cell, and a '1' to indicate the presence of a room.

We also paste '0' and '1' values around the outside of the 5x7 grid to indicate which tiles have rooms.  The grey tiles on the left and right side indicate the level entrance and exit, respectively.


Following the formatting standard we laid out in Part 2, the decision cells are colored yellow to make clear that they are decision variables.

Just below that, we add a second table which counts the number of neighbors of each cell, but only if the cell itself has a nonzero value.  This will be our neighbor count.  More on that in a moment -- we'll show you the completed table after we solve.

Just to the right of that, we add up all of the things we want to happen when we optimize this table.



Each row of this table indicates a constraint.  The "Actual" column determines various things about the actual current characteristics of the decision table or the neighbor count table.  The "Desired" column indicates the value we actually require in each case (i.e. the desired value) as stated in the problem statement above (i.e. the values stated in the previous section, "A Sample Problem").  The "Difference" column just subtracts the "Actual" column from the "Desired" column.

Finally, the "Total Difference" cell will be our objective cell.  This simply adds up all the values in the "Difference" column.  We're trying to minimize that value -- ideally, it should reach 0 to indicate that this problem is "solved."

The first four rows count how many cells of various types exist in the neighbor count table (1-neighbor, 2-neighbor, 3-neighbor, and 4-neighbor cells, respectively), using Excel's COUNTIF() macro.  Finally, the last row counts whether there are tiles right next to the entrance and exit.

What else do we need?

Well, in theory, we also need a way to make sure there's a connection between the entrance and the exit.

The constraints above -- telling the solver that we want 0 1-neighbor tiles, 9 2-neighbor tiles, 4 3-neighbor tiles, and 1 4-neighbor tile -- should ensure that we end up with the right number of tiles and that everything is connected in a way that's valid.

If you think about it, though, it should be clear the guarantee of connectivity does not guarantee that there will be an actual path between the entry and the exit.  It's possible that individual clusters could form near the entry and exit points, or that there could be separate pieces floating off in the corner, not connected to anything else -- for example, you could get 4 "L-shaped" 2-way tiles in a small square, each connected to two others but none of them connected to the rest of the level.

However, we'll put off dealing with this problem -- proving reachability is overkill for this particular problem, when the fact is, it will probably be fine when we solve it, and if it isn't fully connected as we expect, we can just solve it again to get a new answer.

Finally, we run Excel Solver.


Note how simple this is.  We simply set it to minimize the objective cell, then specify the yellow decision cells as the variable cells and add constraints that they must be integers between 0 and 1.  We select the Evolutionary method and press Solve!

Solved!

After running the Evolutionary solver for a while, you may get something that looks like this:



Note that we've enabled the "conditional formatting" feature in Excel to color the second table -- the one that counts the number of neighbors.  As you can see, each cell properly counts how many neighbors it has (if you include the 'entry' and 'exit' cells just outside the table), and there are exactly 9 2-neighbor cells, 4 3-neighbor cells, and one 4-neighbor cells, which is exactly what we wanted.

Problem solved!  With just a tiny amount of work, we've gotten Solver to figure out a whole new level configuration for us based on our specifications.  We can even run Solver several times with different random seed values to see which level configurations it suggests, and from there, figure out which of those configurations seem to work best.

In terms of Carcassonne tiles, our level would look like this:



We can then use Solver to quickly spit out suggestions for alternate room configurations.  For example, if we want to generate a layout with 10 2-neighbor tiles, 6 3-neighbor tiles, and 2 4-neighbor tiles, we could just plug those numbers into our constraint table and re-run Solver to get something like this:




Extending the Example

Now let's say we want to extend the example to include the difficulty level.

Assume that each room has an overall difficulty level that represents how much of a challenge the player will encounter in that room, where '1' represents an easy room, '2' represents a moderately challenging room, and '3' represents a challenge, with a room that contains a boss monster or something like that.  So instead of simply using a '1' in our decision table for each cell with a room in it, we'll have a number between 1 and 3 indicating difficulty.

Our first criterion is that we want some variation in difficulty levels.  So we'll add a new table where each cell measures the change in difficulty between that cell and any nonzero neighboring cells (or 0 if the corresponding cell in the decision table is 0).


Now we add a cell to our constraint table that measures the average difficulty change -- the first row inside the red box in the modified constraint table shown below.  It does this using Excel's AVERAGEIF() function to count the difficulty change from the table above if the corresponding cell in the decision table is nonzero.


The second row in the constraint table tests whether there's one cell in the second-to-last column to the right (column H) with maximum difficulty.  This will help us ensure that the maximum difficulty is close to the exit, since the exit is at the rightmost side.

We also add a third row to check if every column in the neighbor cell is nonzero.  This will return a value of 1 only if each column of the neighbor count table is nonempty.  Since we know that a valid solution must have nonempty columns, this constraint will make it more likely that the generated level is fully connected, and there is a path between the "entry" and "exit" cells.  By itself, it's not enough to absolutely guarantee that the level it generates will be properly connected, but it gives us better odds than the previous spreadsheet did.

Finally, we make sure these three rows are added to the "Total Difference" objective cell, and solve.  Note that the Solver dialog is exactly the same as before, except that we now constrain the decision table cells to have values between 0 and 3 instead of 0 and 1.

Let it run for a few minutes, and voila!


Our decision table looks almost identical to the last one, except that each decision cell has a difficulty level associated with it, and the average difficulty change is 1.

Conclusion

Of course, this is something of a toy problem.  We built a grid-based system simply because that's what we can represent most easily with the grid-based design of Excel, but most component-based level design systems don't lend themselves to this format.

However, with a little work, we could also adapt this to a different, non-orthogonal representation, such as the graph-based representation we used in Part 8.  We could also limit ourselves to swapping compatible rooms within an arbitrary fixed configuration, and use that approach to find the best configuration of rooms within a game level without changing the overall layout.

In any event, the fact that it was so easy for us to build this example should tell us something.  There are clearly a vast number of ways to apply this approach; if we can only find a useful fitness function for the right configuration of rooms, it becomes almost trivial to apply that to many types of level recombination problems.

Stay tuned for Part 10, due sometime in the next few months, when we'll wrap up our discussion of decision modeling and discuss some very important big-picture issues.

-Paul Tozour

 This article was edited by Professor Christopher Thomas Ryan, Assistant Professor of Operations Management at the University of Chicago Booth School of Business.
Posted by at No comments:

Sunday, September 22, 2013

Decision Modeling and Optimization in Game Design, Part 8: Graph Search

This article is the eighth in a continuing series on the use of decision modeling and optimization techniques for game design.  The full list of articles includes:


The spreadsheet for this article can be downloaded here: link

    Metroid Prime World Design

    If you’ve ever played any of the games in the Metroid Prime trilogy (or for that matter, any of the Metroid games), then you’re familiar with the way a typical Metroid world is set up.  Each map is a complex, interlocking set of rooms, with many parts of the map sealed off by requiring access to different suits, weapons, and power-ups.  As the player gains access to new technologies such as "morph ball mode," "spider ball mode," and different suits and weapons, different parts of the map structure gradually unlock, forcing a large amount of re-traversal for the player to visit each new unlocked area.

    As a result of this complexity, handling all of the traversal and re-traversal opportunities available to the player at each point in time is one of the major game design challenges on a Metroid style of game.  If we move any rooms, change the connections between rooms, or change the location where the player gets a certain suit or weapon or power-up, that has the potential to completely change the player's flow and quite possibly break the game.

    The in-game map looks something like this:



    If you’re a programmer, you’d probably look at a map structure like this and immediately realize the potential for all sorts of design tools you could use to build and manage the map structure.  Most likely, you'd make a system where designers could:
    • chart out a map's structure graphically,
    • get instantaneous feedback on where the player could move at each stage of the game,
    • view the combination of rooms the player could access with any combination of power-ups, and
    • instantly determine the fastest route from any room to any other room with any possible combination of power-ups (or indicate that no such path exists).

    Under the hood, you'd probably use an A* search or Dijkstra's search along the graph, taking the player’s movement capabilities into account while crossing each graph edge.

    A tool like that would be relatively easy to create; it would probably only take a talented programmer a few days to write, and it would likely save designers several weeks over the life of the project.

    Surprisingly, though, the creators of the Metroid Prime series never had a tool like that.  When I worked at Retro Studios / Nintendo between 2003 and 2008, we did it the old-fashioned way, and our then-Assistant Producer meticulously maintained large printed maps of all the worlds of each Metroid Prime game, hanging all of them around the company meeting room.  Each time one of the worlds changed, he would edit the associated map graph and re-print all the affected world maps.  These maps looked a lot like this:



    As much as we'd like to actually create a "map design tool" like this, we promised in Part 1 that we wouldn't write any code in this series.  So that kind of a full-featured map design tool is outside the scope of this article.

    What we'll do instead is show how we can handle a problem like this directly inside Excel.  So even if we're designers who can't get any programmer support to build this kind of a tool, we can still create something similar without having to rely on outside help.  And once we're done, we'll have a good template in place that programmers can take and run with to build exactly that kind of a map design tool.

    The Metroid World Example

    To illustrate this problem, we will build an example "Metroid world" and show how to solve it in Excel.  In order to prove that you can actually handle a problem like this from right inside Excel regardless of complexity, we’re going to make this a very complex problem, with 17 rooms and non-obvious connections between them.

    Our example world will look like this:




    Each bubble shows a different room, and the arrows indicate the connections between pairs of rooms.  The number next to each connection indicates the cost of traversing that connection in either direction.  We'll assume these costs fully account for the traversal time to get between any pair of rooms, and there are no costs associated with the rooms themselves (i.e. the traversal costs are to some arbitrary point inside each room).

    We'll explain the coloring of the different rooms later.

    Once we've built the model, we'll be able to ask it questions such as "what's the shortest path for the player to get from the Library to the Sanctuary?"

    A Simpler Problem

    Let's start by working our way up to that with a simpler problem.  Assume we have 6 rooms, 'A' through 'F', with connections as shown in the following directed graph.



    We want to know: what's the fastest way from A to F?  Is it ABEF, ABCEF, ABCDF, ADF  ...?

    You can quickly figure it out yourself by adding up the weights in all four potential paths, but let's see how we'd encode it in Excel Solver.

    First, we make a column with all the possible arcs: A->B, A->D, B->C, etc.  For each arc, we list the total distance of that arc (its traversal cost) in the "Total Distance" column.  To the right of that, we have columns for each room, and for each arc, we put a '1' in the room where the arc originates and a '-1' in the room where the arc terminates (so, for example, "C->D" has a '1' in the 'C' column and a '-1' in the 'D' column).



    We also have a "Decision Variables" column in yellow -- this indicates which arcs the decision model will actually use.  Right now, we'll set all of those to 0 to indicate that they're not currently used (i.e. the problem hasn't yet been solved).

    Because we're following the formatting conventions listed in Part 2, the decision variables are yellow and the predefined values stated as part of the problem description are in blue.

    Now, we add two rows beneath the right part of the matrix to sum up the current target values: this is the "Current" row shown below.



    The "Target" row indicates what we're attempting to achieve.  We simply put in a '1' for the origin, a '-1' for the destination, and '0' for all the other values.  We will use these when we set up the constraints later in the exercise in order to make sure that any potential solution begins and ends where we want it to.

    Finally, we set up the objective function.  This is simply the decision variables multiplied by the respective values in the "Total Distance" column (implemented with the Excel SUMPRODUCT() formula).  In other words, if any arc is used, its decision variable will be 1, and we will multiply it by the respective length of that arc in the "Total Distance" column; otherwise, its decision variable will be 0, and we will get a 0.  This will ensure that the objective function accurately measures the total distance of all the arcs that are actually used in whatever solution we find.

    Now, we solve (see Part 2 if you need a refresher on how to find and use Excel Solver).



    In our objective ("Set Objective"), we specify the orange objective cell.  Since the objective represents the total distance, and we want to minimize the total distance, we select the "Min" radio button below that.  For our decision cells ("By Changing Variable Cells"), we specify the yellow "Decision Variables" column.  In the constraints section, we specify that the yellow decision cells have to be integers that equal 0 or 1.  We also specify that the "Current" row has to equal the "Target" row, to ensure that the path begins and ends at the correct rooms.

    Before we solve, note that "Select a Solving Method" at the bottom has "GRG Nonlinear" specified instead of the usual "Evolutionary" solver.  We'll have a more detailed discussion of the different solver types in a future episode, but for now, suffice it to say that the GRG Nonlinear solver ("GRG" stands for Generalized Reduced Gradient) sometimes handles problems of this type much better than the Evolutionary solver does.

    Now, we hit Solve, and Solver fills in '1' values for the decision variables associated with A->B, B->C, C->D, and D->F, for a total path cost of 8 (note that Solver may take a few minutes to find this solution).  You can verify by hand that this is the correct answer by adding up all of the path costs of the other possible paths, which are all greater than 8.

    You can find this solution in the "Sample solution" worksheet of the attached spreadsheet.

    Searching in the Metroid World

    With that framework in hand, let's generalize it to the large Metroid sample world above.

    One big change in this version is that this example includes bidirectional links instead of directed arcs between rooms.  This means our decision variables will no longer simply be '0' or '1' to indicate whether an arc forms part of the shortest path; instead, we'll also use '-1' to indicate that the path is traversed backwards.

    [Note that this approach only works because all of the arcs in the Metroid example are bidirectional.  If we had any directional arcs in our example, we would have to use the previous approach, and specify any bidirectional arcs as two separate rows in the spreadsheet (for example, we'd have to specify "Lab -> Oculory" and "Oculory -> Lab" on two separate rows to indicate that the player can move between the two rooms in either direction).]

    Our spreadsheet looks similar to the previous one, except that we now add two columns, "Traversal direction" and "Absolute value of decision variables."  "Traversal direction" is just a visual assistant to indicate which direction we'll traverse a link, with a decision variable value of '1' translated into "Forward" and a value of '-1' translated to "Backward."


    We also change the objective function so that it multiplies the total distance column by the "Absolute value of decision variables" column rather than the decision variables themselves (since traversing a link backwards gives us a '-1' in the "Decision Variables" column, and multiplying this by the distance value would give us a negative distance).

    We also need to change our constraints so that it accepts integers between -1 and 1 in the "Decision Variables" column instead of 0 to 1.

    In the "Target" row below the room source/destination matrix, we enter a '1' for the Library and a '-1' for the Sanctuary to ask Solver to figure out the shortest path from the Library to the Sanctuary.

    After these changes, we solve again.  Note that because this is a much more challenging problem, we now have to tweak the Solver options a bit.  In the Solver dialog, we hit Options, select the GRG Nonlinear tab, and then check "Use Multistart" and set "Population Size" to 20 (see this link for more info).  This will make Solver do a much more exhaustive search and will make it much more likely to find the global optimum, and the expense of taking a bit more time to solve the problem.  With this option set, Solver may take 3-5 minutes to find the correct solution.



    After Solver finds a solution, we scan the "Traversal direction" column to make sense of the solution that Solver came up with.  We get the following as the shortest path:

    Library -> Sanctum -> Plaza -> Starport -> Chapel -> Sanctuary
    ...  for a total cost of 21.

    You can find this setup in the "Metroid world solution" worksheet of the attached spreadsheet.

    Adding Movement Constraints

    Of course, this still doesn't quite give us what we want.  The actual Metroid worlds have complex movement requirements that limit the player's access at any point depending on the exact combination of equipment he has acquired.  What we really want is a way to limit the search to only those rooms that are valid with a given combination of equipment.

    There are a lot of different ways to do this, but for the sake of simplicity, we'll just assume each room in the Metroid world graph above requires one particular type of equipment.  Then we'll solve that problem and leave any more sophisticated implementations as an exercise for the reader.

    We will assume the following colors in the graph have the following meanings:


    • Pink rooms (Library, Ruins, etc) don't require any special equipment.
    • Green rooms (Sanctum, Plaza, etc) require the player to have the morphball technology
    • Blue rooms (Courtyard, Throne Room, etc) require the player to have the Varia suit upgrade
    • Red rooms (Chapel, Furnace, etc) require the player to have access to missiles


    The goal is to use Solver to help us figure out how the optimal path for the player changes depending on whether or not he has the morphball, Varia suit, and/or missiles.

    We'll start by adding an "equipment required" table near the top of the spreadsheet:


    This table uses a '1' for each cell to indicate that the player currently has access to that technology, or a '0' if he doesn't.  So far, we've been assuming that the player can travel anywhere, so we've filled in a '1' for each technology.

    Now, we add two rows directly below the arc matrix, "Room category" and "Multiplier."


    Room category specifies the equipment type of the room listed in the same column -- None ('0'), Morphball ('1'), Varia suit ('2'), or Missiles ('3').

    The Multiplier row contains a formula that checks the room category in each column against the "Equipment required" table above.  It produces a '1' if the player possesses the appropriate equipment, and a '0' otherwise.

    The grey cells below that are a table that combines the arc reachability table above with the "Multiplier" row.  It produces a '1' if the room in the same column is included in the path for the corresponding row, and the multiplier in the same column is 1 (in other words, it multiplies the absolute value from the arc reachability table by the multiplier in the same row).

    We also add an additional column to the table just to the right of the "Total distance" column: "Traversable with current equipment."  This column will produce a '1' if both rooms in the arc are reachable with the player's current equipment.  If not, it will produce a value of '999' in order to make the arc prohibitively expensive.



    Finally, we change our objective cell (the orange cell called "minimum total distance") to also include this column in its SUMPRODUCT() formula.

    Now, we run Solver exactly as before.  Make sure you have the Options set as specified above (Use Multistart = TRUE with a Population Size of at least 20), or you may not get the desired results.

    First, we'll set the value for "Morphball" in the "Equipment required" table at the top of the spreadsheet to 0 and re-solve (note that this may take 3-5 minutes to solve).  This is the optimal path with no morphball:

    Library -> Ruins -> Survey Room -> Courtyard -> Lab -> Oculory -> Chapel -> Sanctuary
    ...  for a total cost of 25.

    Next, we set "Morphall" back to 1 and set the cell below it to 0 to find out the optimal path when the player doesn't have the Varia suit:
    Library -> Sanctum -> Plaza -> Starport -> Chapel -> Sanctuary
    You'll notice that this is exactly the same as the solution we found in the previous worksheet, before we began taking the player's equipment into account.

    What happens when we set both of these to 0, so the player doesn't have the morphball or the Varia suit?  Re-solving, we get:
    Library -> Ruins -> Foyer -> Mausoleum -> Sanctuary

    for a total cost of 41.  As you can see from the graph above, going down the very expensive Foyer -> Mausoleum arc (with a cost of 27) is the only option available when both the morphball (green) and Varia suit (blue) are disabled  ... and this is, in fact, the shortest path that includes that link.

    Problem solved!

    You can find this spreadsheet in the "With equipment requirements" worksheet of the attached spreadsheet.


    Conclusion

    In this example, we've shown how you can use decision modeling and optimization techniques as a powerful tool to solve graph search and reachability problems.  This particular Metroid game world example is of course only one application of this technique; there are many more.  You could just as easily use it to find the shortest path through a star system in a space game with direct links between stars, for example, or the shortest path along a flight path network in an MMO such as World of WarCraft.

    Tune in next time, when we'll show how you can use decision modeling and optimization techniques to not only search through game world configurations, but to help design those configurations in the first place.


    -Paul Tozour

    This article was edited by Professor Christopher Thomas Ryan, Assistant Professor of Operations Management at the University of Chicago Booth School of Business.
    Posted by at No comments:
    Labels:
    Subscribe to: Posts (Atom)