Psychochild's Blog

A developer's musings on game development and writing.

14 December, 2005

Random enough for ya?
Filed under: — Psychochild @ 1:02 AM
(This post has been viewed 4906 times.)

Occasionally I have to post a programming-related bit to remind everyone that I really am a programmer. :) Well, here's one of those articles.

A recent Terra Nova article by Nate Combs talks about randomness and fun in games. Is true randomness really fun? The article referenced David Kennerly's article about Randomness without Replacement, talking about how using a system similar to drawing cards (no replacement) is more interesting than a system like a die roll (with replacement). Nearly a year ago, Jeff Freeman posted a similar blog entry about how true randomness really wasn't all that much fun and argued for a similar system that had no replacement.

I think the point made by everyone is valid: it's not very fun if things are too random. Most of us have probably played an online RPG where we have to go kill creature to get some specific drop. Sometimes the drops come quick, sometimes it seems to take forever. Frustration sets in when you think you've killed too many creatures without enough drops. You can see this in other areas, notably in the hit/miss ratios as David talks about in his article. It's a lot less frustrating when your odds seem reasonable; if you only have to kill a maximum of X creatures to get the drops you need, it doesn't seem so bad.

Back when Jeff posted his entry, I decided to work up some code for a system he described. It's a simple little C++ class that takes a defined set of odds and gives true/false results based on those odds. So, if you set the odds as 5 out of 7, every series of 7 results will have 5 "true" returns.

However, there's still a lot of flexiblity here. Say you want to have a person collect 10 items while killing 20 creatures (50% drop rate). Instead of making it a "random(1,100) less than 50?" check, you can use the class I've defined. But, do you set the odds to 10 in 20? Or, do you set the odds to 1 in 2 and use the class 10 times? With the former you've essentially just set a maximum number of kills required; it can still be frustrating if I get 9 drops, 10 kills with nothing, then my last drop on number 20. Unlikely, but possible. With the latter you get a lot more stability, but it can be a bit too predictable. Perhaps a better compromise would be to set the odds to 5 in 10 and use the object twice. Or, perhaps set 3 in 5 odds and stop when the player reaches 10. All sorts of possibilities.

Anyway, I figured I'd share my code with everyone. It's not super-impressive, but it does show a way to implement such a system fairly painlessly. The code works fairly well, but I won't guarantee it 100%. This is released under a BSD-style license which boils down to: use it however you want, just give me credit as appropriate.

This system uses the wonderful Mersenne Twister random number generator; the appropriate header file (with inline function definitions) is included with the download and is also under a BSD-like license. I've also included a main file with a very simple testing system.

Download the whole package in .zip format here. This archive contains four files, which are all you need to compile and run the system:
main.cpp
MersenneTwister.h
RandomOdds.cpp
RandomOdds.h

Here are the two code files I wrote.


/* RandomOdds.h ***************************************************************

/* This is a definition of a class that takes certain odds and provides
** an object that will give you a series of boolean values based on those odds.
** For example, if you want the odds to be 5 out of 13, then in a group of
** 13 consecutive calls you will get exactly 5 successes.  Note that this does
** not mean that you will have 5 successes in *any* 13 calls.  This may be an
** interesting extension.
*/

// Copyright (C) 2005, Brian 'Psychochild' Green
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
//   1. Redistributions of source code must retain the above copyright
//      notice, this list of conditions and the following disclaimer.
//
//   2. Redistributions in binary form must reproduce the above copyright
//      notice, this list of conditions and the following disclaimer in the
//      documentation and/or other materials provided with the distribution.
//
//   3. The names of its contributors may not be used to endorse or promote
//      products derived from this software without specific prior written
//      permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef RANDOMODDS_H
#define RANDOMODDS_H

/* Includes */

// Included for random numbers
#include "MersenneTwister.h"

/* classes */

class RandomOdds
{
public:
   RandomOdds(int iSuccesses = 1, int iOutOf = 2);
   ~RandomOdds();

   // Resets odds.  If parameter values are non-positive, it will not change
   //  that value.  Call with default parameters to reset the counts.
   // Conditions: iSuccesses <= iOutOf
   // Returns: true if reset, false if not.
   bool ResetOdds(int iSuccesses = -1, int iOutOf = -1);

   // Call to get either a true or false value, depending on the number of
   //  successes and failures before.
   bool GetChance();

private:
   // The set odds
   int miSuccesses;
   int miOutOf;
   // The current tally
   int miNumSuccesses;
   int miNumRolls;
   // Our random number generator
   MTRand* mpRandom;
};

#endif // #ifndef RANDOMODDS_H

/* RandomOdds.c **************************************************************/

// Copyright (C) 2005, Brian 'Psychochild' Green
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
//   1. Redistributions of source code must retain the above copyright
//      notice, this list of conditions and the following disclaimer.
//
//   2. Redistributions in binary form must reproduce the above copyright
//      notice, this list of conditions and the following disclaimer in the
//      documentation and/or other materials provided with the distribution.
//
//   3. The names of its contributors may not be used to endorse or promote
//      products derived from this software without specific prior written
//      permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "RandomOdds.h"
// Included for time.
#include <time.h>

RandomOdds::RandomOdds(int iSuccesses /*= 1*/, int iOutOf /*= 2*/)
{
   if (!ResetOdds(iSuccesses, iOutOf))
   {
      ResetOdds(1,2);
   }

   // Seed the random number generator.
   mpRandom = new MTRand((unsigned long)time(NULL));

   return;
}

RandomOdds::~RandomOdds()
{
   delete mpRandom;

   return;
}

bool RandomOdds::ResetOdds(int iSuccesses /*= -1*/, int iOutOf /*= -1*/)
{
   // local variables for storing information.
   int liSuccesses;
   int liOutOf;

   if (iSuccesses > 0)
   {
      liSuccesses = iSuccesses;
   }
   else
   {
      liSuccesses = miSuccesses;
   }

   if (iOutOf > 0)
   {
      liOutOf = iOutOf;
   }
   else
   {
      liOutOf = miOutOf;
   }

   if (liSuccesses > liOutOf)
   {
      // Bad values, don't change anything.
      return false;
   }

   miSuccesses = liSuccesses;
   miOutOf = liOutOf;
   miNumSuccesses = 0;
   miNumRolls = 0;

   return true;
}

bool RandomOdds::GetChance()
{
   // Local variable containing current odds.
   double ldOdds;
   double ldRandom;

   // Do we need to reset the odds because we've already rolled enough?
   if (miNumRolls >= miOutOf)
   {
      ResetOdds();
   }

   // Calculate current odds.
   ldOdds = (double)(miSuccesses - miNumSuccesses) / (double)(miOutOf - miNumRolls);
   ldRandom = mpRandom->rand();

   miNumRolls++;

   if (ldRandom > ldOdds)
   {
      return false;
   }

   miNumSuccesses++;

   return true;
}

--


« Previous Post:
Next Post: »





7 Comments »

  1. Game Random Events

    Brian Green has an posted a nice bit of BSD licensed C++ code for handling random events in computer games in response to Terro Nova’s comments on the subject.
    ...

    Trackback by Make Mac Games — 14 December, 2005 @ 9:59 AM

  2. My problem with random numbers is, well, I am cursed with legendary bad dice rolling. My dice rolling is so bad as to make atheists consider the possibility that there really is a God. I warned my boss, when we began playtesting on paper, and he didn't believe me. After two play sessions, he forbade me to playtest any further, because I was so badly skewing his results. Another time, I sat through an entire Earthdawn session, which was almost non-stop combat, and never succeeded on a single roll. My character, in desperate frustration, threw herself on top of her nearly dead best friend, because it was all she could do to save him.

    In light of that, no-replacement systems are considerably kinder to me, since my rotten luck is guaranteed to turn around, given enough time.

    One thing that I love toying with in my own pet designs is normalized randoms. The classic D&D 3d6 is a crude emulation of this. Most of the time, things are normal, but on rare occasion, you hit an outlier. It's very satisfying for the gambling part of our brains. It's also very handy for functionally generating both natural phenomena and man-made creations. One wall of a room will have a random size around n with a standard deviation of s. The other will have the middle of its curve fed to it by the first wall's resulting size. Thus rooms will tend toward square-ish, and will often be mildly rectangular. In extremely rare cases, they will be long and skinny.

    Comment by Tess — 3 January, 2006 @ 8:36 AM

  3. Nice idea, couple of code tweaks.

    No. 1, you should make your RandomOdds() explicit to avoid implicit conversions from int. Probably won't ever come up, but it's lots of fun finding the code that caused the problem when it does come up.

    No. 2, I'm not sure I like the semantics on ResetOdds and the RandomOdds paramaters. I think using unsigned values would be better. To just reset the die roll without changing the number of successes or failures, perhaps you could provide a no parameter version of ResetOdds. You would lose the ability to change just one parameter, but if that need still exists, you could add getter functions for the "successes" and "outof" parameters. The only real error checking cases left after that are where successes > outof and when outof == 0. Checking for the successes > outof case is optional, as it gives strange, but understandable semantics with your existing code (successes > outof implies a greater than 100% chance to succeed, you give 100%). You would still have to check for outof==0 to avoid division by 0 though.

    Of course, even with unsigned values, you could still use "-1" to keep your current reset semantics.

    Comment by Notin — 3 January, 2006 @ 8:41 PM

  4. Python randomness

    In a previous entry (http://blog.psychochild.org/?p=102), I discussed a random number generator without replacement. I recently wrote a Python version of the RandomOdds class I thought some people might find interesting.

    ...

    Trackback by Psychochild's Blog — 3 February, 2006 @ 9:07 PM

  5. Predictable randomness

    [...] I promised to spend time over the weekend working on a proof of concept of random terrian generation. Here is the first fruit of my labor, a Mersenne Twister pseudo-random number generator. Psychochild has already written about this kind of PRNG, so I looked it up and found that it provided exactly what I needed–I also considered Yarrow, but wanted something simpler and I only needed statistical randomness. [...]

    Pingback by Mischiefblog — 13 March, 2006 @ 2:04 PM

  6. I uploaded a new .zip archive with updated information in the MersenneTwister.h file, notably updating the location of the Mersenne Twister project website.

    Comment by Psychochild — 13 March, 2006 @ 3:59 PM

  7. Weekend Design Challenge: Random Numbers

    A bit late today, due to some other deadlines in my life.
    This challenge deals with random numbers, something I've talked about before. Here's the challenge: Give specific examples of mechanics where it is better to use rolling with replacement or...

    Trackback by Psychochild's Blog — 15 April, 2006 @ 2:26 PM

Leave a comment

I value your comment and think the discussions are the best part of this blog. However, there's this scourge called comment spam, so I choose to moderate comments rather than giving filthy spammers any advantage.

If this is your first comment, it will be held for moderation and therefore will not show up immediately. I will approve your comment when I can, usually within a day. Comments should eventually be approved if not spam. If your comment doesn't show up and it wasn't spam, send me an email as the spam catchers might have caught it by accident.

Line and paragraph breaks automatic, HTML allowed: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <div align=""> <em> <font color="" size="" face=""> <i> <li> <ol> <strike> <strong> <sub> <sup> <ul>

Email Subscription

Get posts by email:


Recent Comments

Categories

Search the Blog

Calendar

April 2014
S M T W T F S
« Feb    
 12345
6789101112
13141516171819
20212223242526
27282930  

Meta

Archives

Standard Disclaimer

I speak only for myself, not for any company.
(More information here)

My Book





Information

Around the Internet

Game and Online Developers

Game News Sites

Game Ranters and Discussion

Help for Businesses

Other Fun Stuff

Quiet (aka Dead) Sites

Posts Copyright Brian Green, aka Psychochild. Comments belong to their authors.

Google