Procedural Generation, Intro

This is the first of what I hope to be many posts exploring the topic of procedural generation, particularly as it applies to game development and art.

At it simplest level, procedural generation (pg) is the use of a small amount of code, or an algorithm, to create a result, rather than creating that result by hand. Randomness and pseudo-randomness generally figure into the process, as well as set theory, emergence, and a wide variety of mathematical concepts such as fractals, the Fibonacci sequence, cellular automata, Perlin noise algorithms, and occasionally cryptography.

PG starts with the creation of a series of bits or numbers, then branches out into the myriad uses to which that series can be applied. How the numbers are chosen is just as important. So PG starts a level lower, at the algorithm which creates the data.

A list of numbers can mean almost anything depending on its context. But for a given context, not all sets of numbers will work. Therefore it is important to have a number generator which will produce useful data for a given task. This is where experimentation comes in to play.

But enough of the high-level stuff.

I have several years of notes, graphics, experiments, and source code through which I am currently sorting. Over the upcoming months I will post breakdowns of some of them, particularly those which can be applied to game development. And in those, I will be providing ideas about how to make PG useful, and how to tweak things so that using this method actually saves time and effort. Here are some of the ideas which I will cover:

  • terrain generation
  • town placement
  • resource placement
  • maze generation
  • cave/dungeon generation and population
  • place name generation
  • graphics creation
  • plant/tree generation

…and various combinations of the above.

In the meantime, click here to see the nearly 30 old entries I have made in this blog regarding procedural generation.

Hardy Dam Rustic Nature Trail

Hardy Dam Rustic Nature Trail sign

Back in mid-August my girlfriend and I spent an afternoon in Newaygo, walking along the Muskegon river just downstream from the Hardy Dam. The local Boy Scouts worked with Consumer’s Power to mark out an interpretive path called the Hardy Dam Rustic Nature Trail.

Stream from the woods

The trail is short – not quite three miles, round-trip – and is reasonably well marked. When we went the ground was wet from several inches of rain over the previous couple of weeks, so we got a little muddy. Still – a beautiful walk in the woods.

Red-backed Salamander (Plethodon cinereus)

One of the highlights was the discovery of at least a dozen red-backed salamanders. There seemed to be at least one under ever fallen limb. Since they are an indicator species, I take that to mean that the ecology of the Muskegon River is quite healthy.

Click on any of the photos to see the rest of the set on Flickr, or click here to start at the beginning.

Wikipedia as a Life Line for the Creative Urge

If you are like me – and I know I am – then you know that when the creative urge strikes, it doesn’t always come hand-in-hand with ideas. You know you want to do…SOMETHING… but have no idea what that thing is. Much like the adrenaline high of a sudden scare which leads nowhere, the creative juices which were so powerful in the morning sit unused, and gradually sour into an afternoon of sitting fatassedly on the couch, watching television.

While browsing through Wikipedia the other day in the grip of post-urge ennui, I realized that the “On this day…” link on the right side of Wikipedia’s main page is a treasure trove of disparate events, united by the theme of having happened on this particular date, offset by a certain number of years. What if someone was to take a random-ish handful of the events which happened on a day, and from them construct a story, or a poem, or the plot to an adventure game? I tend to look at things through the lens of a semi-practicing Buddhist, so the idea of cycles and recurrence appeals to me, and the filter of requiring a specific date makes the data set manageable – it provides the constraint which helps stave off the onset of option paralysis.

Putting this idea into practice, look at the page for September 25. A lot happened on this date in history. Here is a (very) small sample:

275-Tacitus becomes Emperor of Rome.
1513-Balboa reaches the Pacific Ocean.
1775-Ethan Allen surrenders to the British.
1789-Creation of the Bill of Rights.
1972-Norway rejects membership of the European Union.
2008-China launches the spacecraft Shenzhou 7.

Fletcher Christian was born in 1764, Lu Xun in 1881, and Catherine Zeta-Jones in 1969.

Johannes Secundus died in 1536, Pope Clement VII in 1534, and George Plimpton in 2003.

Coincidence? I THINK NOT!!!

But you can see where I am going with this. Narrative frameworks could be constructed which follow specific threads or sub-filters of the information on that page – say, only the events which are political in nature, or only the deaths of artists, or only the births which happened in years evenly divisible by 10. Start with a set of disjointed data. Apply an arbitrary filter. Come up with a loose narrative which allows for a significant number of the events in the filtered set. Apply a second filter. Tighten the narrative. A third filter. Now the narrative either falls apart, or contains within it the seeds of a story.

While it can be difficult to pull a complete story out of such an exercise, it can provide the seed of something much more complex. Or, perhaps there is a poem somewhere in the mix. Or the framing story of a game. Or even a film script.

At its simplest, constructing a coherent story from such an arbitrary list of data is a good thought experiment. With National Novel Writing Month starting in a few days this could be the seed of something amazing.

Circular HTML Elements Using CSS3 Border Radius

If you are using a “modern” browser, you should see a box full of circles.

 

abcde fghij klmno pqrst uvwxy z

If not, you need to upgrade your browser.

The circles were created using the new CSS3 border-radius property. The markup I used looks something like this:

<div id="post-20111013-a">
<span>a</span><span>b</span><span>c</span><span>d</span><span>e</span>
<span>f</span><span>g</span><span>h</span><span>i</span><span>j</span>
<span>k</span><span>l</span><span>m</span><span>n</span><span>o</span>
<span>p</span><span>q</span><span>r</span><span>s</span><span>t</span>
<span>u</span><span>v</span><span>w</span><span>x</span><span>y</span>
<span class="s2">z</span>
</div>
#post-20111013-a {width:640px;height:480px;outline:1px solid #999;background:#ffffff;}
#post-20111013-a span {
	float:left;
	width:50px;
	height:50px;
	margin:14px;
	border:1px solid red;
	background:#999999;
	-webkit-border-radius: 27px;
	-moz-border-radius: 27px;
	border-radius: 27px;
	text-align:center;
	line-height:50px;
}
#post-20111013-a span.s2 {
	float:none;
	clear:both;
	display:block;
	margin:20px auto;
	width:100px;
	height:100px;
	line-height:100px;
	-webkit-border-radius: 54px;
	-moz-border-radius: 54px;
	border-radius: 54px;
}
#post-20111013-a span:hover {
	-webkit-box-shadow: 5px 5px 5px 0px rgba(0, 0, 0, .5);
	-moz-box-shadow: 5px 5px 5px 0px rgba(0, 0, 0, .5);
	box-shadow: 5px 5px 5px 0px rgba(0, 0, 0, .5);
}
#post-20111013-a span.s2:hover {
-webkit-box-shadow: 0px 0px 20px 20px rgba(255, 0, 0, .5);
	-moz-box-shadow: 0px 0px 20px 20px rgba(255, 0, 0, .5);
	box-shadow: 0px 0px 20px 20px rgba(255, 0, 0, .5);
}

The first block is the HTML which makes up the above demo, and the second is the style sheet. Pretty self-explanatory. I set the border radius to slightly more than half of the diameter of the circle (width/height of the element). Putting the border radius at exactly half of the diameter renders as a very slightly squarish circle. You can play around with border-radius on this page at the w3schools. You can read more about the browser compatibility and best practices at The Art of the Web.

Unfortunately the hit area for each element is still a rectangle large enough to contain the circle, so in that sense it is not much of an improvement over using a background image. Still, it is a huge step in the right direction.

Mersenne Twister in Actionscript

A few years ago I attempted to create a game for the GameDev.net Four Elements Contest. I had an idea that I wanted the game to be a cross between Nethack and Elite – and maybe a little Spore – which is to say, loads and loads of procedurally generated content. I never got past a very rough prototype of the world-building engine, but I learned a lot about procedural generation, and game development in general. Specifically, that it takes a lot more time than I generally have available.

One of the artifacts of this experiment was an extremely useful Mersenne Twister class, which I ported over from a C class I found on Wikipedia. A Mersenne Twister is a seeded pseudo-random number generator. In other words, for a given input n and a range r, it will return a random number between 0 (or whichever number you designate as the lower bound) and r, using n as the seed.

How is that useful? If you want to be able to, for instance, save a game which is based on random number-seeded procedural content, you want to be able to return the same seed every time. And if someone wants to start a new game, you want that seed to be different, but also repeatable. If you can’t reload a saved game and have it be based off the same random number as before, then loading a game would be no different from starting a new one.

Anyway. Here is the Actionscript 3 class:

/*
   A C-program for MT19937, with initialization improved 2002/1/26.
   Coded by Takuji Nishimura and Makoto Matsumoto.

   Before using, initialize the state by using init_genrand(seed)
   or init_by_array(init_key, key_length).

   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
   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.


   Any feedback is very welcome.
   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
   email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)

     -------------------

     Converted to Actionscript 2005 by John Winkelman
     Feedback welcome at john.winkelman@gmail.com
*/


/* Period parameters */
package org.eccesignum.utilities {
    public class MersenneTwister {
        private var N:Number = 624;
        private var M:Number = 397;
        private var MATRIX_A:Number = 0x9908b0df;   /* constant vector a */
        private var UPPER_MASK:Number = 0x80000000; /* most significant w-r bits */
        private var LOWER_MASK:Number = 0x7fffffff; /* least significant r bits */

        private var mt:Array; /* the array for the state vector  */
        private var mti:Number;

        private var seed:Number;
        private var returnLength:Number;
        private var maxSize:Number;

        private var returnArray:Array;


        public function MersenneTwister():void {

        }

        public function twist($seed:Number,$returnLength:int,$maxSize:int):Array {    //    seed number, number of values to return ,max size of returned number
            seed = $seed;
            returnLength = $returnLength;
            maxSize = $maxSize;
            mt = [];

            returnArray = [];

            mti = N+1; /* mti==N+1 means mt[N] is not initialized */
            var i:int;
            //var initArray=(0x123, 0x234, 0x345, 0x456);    //2010.04.20    modiied to the below
            var initArray:Array = [0x123, 0x234, 0x345, 0x456];
            init_by_array(initArray,initArray.length);
            for (i=0; i<returnLength; i++) {
                returnArray[i] = genrand_int32()%maxSize;
            }
            //returnArray.sort(16);
            //trace(returnArray);
            /*
            trace("\n1000 outputs of genrand_real2()\n");
            for (i=0; i<returnLength; i++) {
              trace(" " + genrand_real2());
              if (i%5==4) trace("\n");
            }
            */
            return returnArray;

        }


        /* initializes mt[N] with a seed */
        private function init_genrand($seed:Number):void {
            mt[0]= $seed & 0xffffffff;
            for (mti=1; mti<N; mti++) {
                mt[mti] = (1812433253 * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
                mt[mti] &= 0xffffffff;
                /* for >32 bit machines */
            }
        }

        /* initialize by an array with array-length */
        /* init_key is the array for initializing keys */
        /* key_length is its length */
        /* slight change for C++, 2004/2/26 */
        //    void init_by_array(unsigned long init_key[], int key_length)

        private function init_by_array($seedArray:Array,$seedArrayLength:Number):void {
            var i:Number = 1;
            var j:Number = 0;
            init_genrand(seed);
            //init_genrand(19650218);
            var k:Number = (N>$seedArrayLength) ? N : $seedArrayLength;
            for (k; k>0; k--) {
                mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525)) + $seedArray[j] + j; /* non linear */
                mt[i] &= 0xffffffff; /* for WORDSIZE > 32 machines */
                i++;
                j++;
                if (i >= N) {
                    mt[0] = mt[N-1];
                    i=1;
                }
                if (j >= $seedArrayLength) j=0;
            }
            for (k = N-1; k; k--) {
                mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941)) - i; /* non linear */
                mt[i] &= 0xffffffff; /* for WORDSIZE > 32 machines */
                i++;
                if (i>=N) {
                    mt[0] = mt[N-1];
                    i=1;
                }
            }

            mt[0] = 0x80000000; /* MSB is 1; assuring non-zero initial array */
        }

        /* generates a random number on [0,0xffffffff]-interval */
        private function genrand_int32():Number    {
            var y:Number;
            var mag01:Array=[0x0, MATRIX_A];
            /* mag01[x] = x * MATRIX_A  for x=0,1 */

            if (mti >= N) { /* generate N words at one time */
                var kk:Number;

                if (mti == N+1)   /* if init_genrand() has not been called, */
                    init_genrand(5489); /* a default initial seed is used */

                for (kk=0;kk<N-M;kk++) {
                    y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
                    mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1];
                }
                for (;kk<N-1;kk++) {
                    y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
                    mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1];
                }
                y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
                mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1];

                mti = 0;
            }

            y = mt[mti++];

            /* Tempering */
            y ^= (y >> 11);
            y ^= (y << 7) & 0x9d2c5680;
            y ^= (y << 15) & 0xefc60000;
            y ^= (y >> 18);

            return y;
        }

        /* generates a random number on [0,0x7fffffff]-interval */
        private function genrand_int31():Number    {
            return (genrand_int32()>>1);
        }

        /* generates a random number on [0,1]-real-interval */
        private function genrand_real1():Number    {
            return genrand_int32()*(1.0/4294967295.0);
            /* divided by 2^32-1 */
        }

        /* generates a random number on [0,1)-real-interval */
        private function genrand_real2():Number {
            return genrand_int32()*(1.0/4294967296.0);
            /* divided by 2^32 */
        }

        /* generates a random number on (0,1)-real-interval */
        private function genrand_real3():Number    {
            return ((genrand_int32()) + 0.5)*(1.0/4294967296.0);
            /* divided by 2^32 */
        }

        /* generates a random number on [0,1) with 53-bit resolution*/
        private function genrand_res53():Number    {
            var a:Number = genrand_int32()>>5;
            var b:Number = genrand_int32()>>6;
            return(a*67108864.0+b)*(1.0/9007199254740992.0);
        }
        /* These real versions are due to Isaku Wada, 2002/01/09 added */
    }
}

And it is called like this:

var twister:MersenneTwister = new MersenneTwister();
twister.twist(17436,100,50000); // seed number, number of values to return, maximum size of a given value

Since I wrote this, many other people have made versions in Actionscript. There is a comprehensive list on the Mersenne Twister page at Wikipedia.

Hiking in the Saugatuck Harbor Natural Area

Marsh in the Saugatuck Harbor Natural Area

Over the Labor Day weekend Cynthia and I spent a day hiking in the Saugatuck Harbor Natural Area. If you haven’t been, or haven’t heard of it, I can’t recommend it highly enough! It starts at the north edge of Oval Beach in Saugatuck, and extends north along Lake Michigan to the Kalamazoo River channel. There are several marked trails in among the dunes. You can see it on a map here.

Click the photo to see the rest of the set on Flickr.

Another PhotoFly Test

Here is another PhotoFly test. This is a stone bench outside of GRCC. PhotoFly found enough texture in the concrete that it was able to create the scene in one go, without me having to manually designate common points in any of the photos. You can see where PhotoFly still has problems with some areas, particularly where the texture in the foreground is too similar to the texture in the background. Notice the distortion on the bottom of the right underside of the bench. Also in the close-up of the underside there are a couple of small holes.

One improvement for PhotoFly would be the option to go back and fix errors which it has made when stitching photos. Alternately, re-render the scene, perhaps having the rendering engine run through the photos in a different order so it comes up with different “assumptions” about how the points in the photos fit together.

Bench 13

Also, here is one of the photos I used to create this render. Click it to see the rest. There are 23, and they are all of the bench. Not terribly exciting, but you will get an idea of how PhotoFly pulls information to create a 3d object.

Targeting Flash Player 11 in the Flex SDK

Here are instructions for setting up the Flex SDK to allow Flash development targeting the new Flash 11 player, and how to set up the HTML in which it is embedded to allow for use of hardware acceleration, where appropriate.

  1. Download the Flex 4.5 SDK from here: http://opensource.adobe.com/wiki/display/flexsdk/Download+Flex+4.5
  2. Download the new playerglobal.swc from here: http://www.adobe.com/support/flashplayer/downloads.html
    1. If it is named anything other than “playerglobal.swc” change the file name to “playerglobal.swc”
  3. In the Flex SDK files you just downloaded, create a new folder here: [FLEX SDK]/frameworks/libs/player/11.0
  4. Place the playerglobal.swc you just downloaded into the new 11.0 folder
  5. Target the Flash 11 playerglobal in the flex-config.xml file as follows:
    1. in a text editor, open [FLEX SDK]/frameworks/flex-config.xml
    2. change the <target-player/> value to 11.0
    3. change the <swf-version/> value to 13
  6. Download the standalone Flash 11 projector from here: http://www.adobe.com/support/flashplayer/downloads.html
  7. Update the flash player in your browsers as follows:
    1. Google Chrome – click on the wrench icon in the upper right of the browser, then click on “About Google Chrome”. This will force Chrome to automatically update itself, which will include the new version of the Flash plugin
    2. Firefox – visit this url: http://get.adobe.com/flashplayer/ and follow the directions therein
    3. Internet Explorer – visit this url: http://get.adobe.com/flashplayer/ and follow the instructions therein
  8. In order to take advantage of hardware acceleration in your new Flash movies, be sure that in the <object/>and <embed/> tags, you set the wmode attribute to direct. This is the only way that hardware acceleration will work.
  9. If using SWFObject or jQuery or some other JavaScript library to dynamically embed the Flash movie, refer to the appropriate documentation to find out how to change the wmode parameter
  10. Create a new .swf and run it in the new player. See how much faster it runs!