[BitmapData.compare]

I would assume that the downside of using the BitmapData.compare function is that it will not stop once it has found a single difference because, it assumes you want to know the location of all the differences between the images.

So the question is if the wasted time of checking the rest of the images after a difference has been found is made up for by the speed improvement over 'manually' checking.

Sounds like time for BENCHMARKS!

Basic test program:

Code:

package 
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.KeyboardEvent;
import flash.utils.getTimer;

public class Test extends Sprite
{
private var one:BitmapData, two:BitmapData;
private const w:int = 1000, h:int = 1000;
private const numberOfRepeats:int = 1000;

public function Test()
{
if (stage != null)
{
init();
}
else
{
addEventListener(Event.ADDED_TO_STAGE, init);
}
}

private function init(e:Event = null):void
{
//make a large BitmapData filled with pretty colours.
one = new BitmapData(w, h, true, 0);
one.perlinNoise(10, 10, 3, 123, false, false);

//make a second BitmapData, and either..
//have it be identical:
two = one.clone();

//make it very slightly different:
//two = one.clone();
//two.setPixel32(w / 2, h / 2, 0);

//make it very different:
//two = new BitmapData(w, h, true, 0);
//two.perlinNoise(50, 50, 3, 456, false, false);


//..and because a .swf that doesn't display anything is boring:
addChild(new Bitmap(one));

//press any key to perform the comparison.
stage.addEventListener(KeyboardEvent.KEY_UP, doCompare);
}

private function doCompare(e:Event = null):void
{
var timeAtStart:int = getTimer();
var areSame:Boolean;
for (var repeat:int = 0; repeat < numberOfRepeats; repeat++)
{
/*
*
* Insert comparison code in here.
*
*/
}
var timeAtEnd:int = getTimer();
trace("result:", areSame);
trace("time:", ((timeAtEnd - timeAtStart) / repeat).toPrecision(3));
}
}
}

We vary what's in the doCompare function to try out different techniques.

As you can see it's testing two 1000x1000 BitmapData objects filled with Perlin noise.  Test cases will be:
When they are identical
When they are completely different (both filled with different Perlin noise)
When they have a single pixel (right in the middle) different.

Each test is repeated 1000 times and the time given below is the mean execution time for a single test.

BitmapData.compare

Code:

if (one.compare(two) as Number == 0)
{
areSame = true;
}
else
{
areSame = false;
}

(I added on the "as Number" for the sake of clarity)

With identical bitmapData objects:
4.03ms

With slightly different:
5.38ms

With totally different:
34.0ms

I suspect the increased time when there are differences (especially when there are large differences) is the time taken to create the new BitmapData object used to report what the differences are.  Which is a shame, because our program isn't using that data.

BitmapData.getPixel32

Code:

areSame = true;
checkSameness:
for (var bx:int = 0; bx < one.width; bx++)
{
for (var by:int = 0; by < one.height; by++)
{
if (one.getPixel32(bx, by) != two.getPixel32(bx, by))
{
areSame = false;
break checkSameness;
}
}
}

Using identical:
226ms

Using slightly different:
116ms

Using very different:
0.001ms

I had to limit the number of repeats for the first two conditions so as to avoid timeout errors.  As you'd expect manually checking each of a million pixels does indeed take a while.  Also unsurprising is that if you can end the check after just one pixel it gets very fast.


Custom Shader

The PixelBender shader

Code:

<languageVersion : 1.0;>

kernel TestDifference
<   namespace : "";
    vendor : "";
    version : 1;
    description : "Compares two images. If the pixels matche, the result is coloured black and if they differ it is coloured white.";
>
{
    input image4 one;
    input image4 two;
    output pixel4 dst;

    void
    evaluatePixel()
    {
        float2 here = outCoord();
        float4 fromOne = sampleNearest(one, here);
        float4 fromTwo = sampleNearest(two, here);

        //(fromOne == fromTwo) works in PixelBender, but not when compiled
        // and run through Flash. So I have to check each channel instead.
        if (fromOne.r == fromTwo.r && fromOne.g == fromTwo.g && fromOne.b == fromOne.b && fromOne.a == fromTwo.a)
        {
            dst = pixel4(0.0,0.0,0.0,0.0);
        }
        else
        {
            dst = pixel4(1.0,1.0,1.0,1.0);
        }
    }
}

The comparison function:

Code:

var testDifference:Shader = new Shader(new MyEmbeddedShader() as ByteArray);
testDifference.data.one.input = one;
testDifference.data.two.input = two;
var result:Vector.<Number> = new Vector.<Number>();
var differenceJob:ShaderJob = new ShaderJob(testDifference, result, one.width, one.height);
differenceJob.start(true);

if (result.indexOf(1, 0) == -1)
{
areSame = true;
}
else
{
areSame = false;
}

Shaders are designed to operate on images.  Here I am pushing the result of the shader into a vector instead. My hope is that the necessary search is faster on a Vector than on a BitmapData, mainly as Vector.IndexOf() can stop its search as soon as it finds a matching instance.

Using identical:
55.2ms

Using slightly different:
39.5ms

Using very different:
21.5ms

I had to again use fewer repeats for these tests to avoid running out of memory.  Would have thought the garbage collector could collect some garbage between iterations, but I've never really studied Flash's garbage collection.  The extra time taken in the cases of similar images must be due to the extra time the IndexOf() function takes to find evidence of difference.  I tried repeating the test using LastIndexOf() and found just the same results.

Shader with analysis through BitmapData

Same shader as above, but new comparison function:

Code:

var testDifference:Shader = new Shader(new MyEmbeddedShader() as ByteArray);
testDifference.data.one.input = one;
testDifference.data.two.input = two;

var resultBmd:BitmapData = new BitmapData(one.width, one.height, true, 0);
var differenceJob:ShaderJob = new ShaderJob(testDifference, resultBmd);
differenceJob.start(true);

if (resultBmd.getColorBoundsRect(0xffffffff, 0xffffffff, true).isEmpty())
{
areSame = true;
}
else
{
areSame = false;
}

Just as above, the shader checks if each pixel is the same.  When it finds a difference, it sets the corresponding pixel on resultBmd to be white.  getColorBoundsRect is then used to find if there are any white pixels in resultBmd.

Using identical:
14.8ms

Using slightly different:
13.4ms

Using very different:
11.9ms

As these times are less than even the fastest example of using a Vector to hold output from the shader it seems that forcing a shader to fill a Vector instead of a BitmapData slows it down.  The wide variation in times for searching through the Vector shown in the previous test shows that the IndexOf() function is pretty slow, at least compared to BitmapData.getColourBoundsRect.

getColourBoundsRect is VERY fast it seems - skipping it only increases the execution time by around 1ms.

Summary
Yeah, BitmapData.compare() is pretty good.  It showed a dramatic slowdown when given completely different images but I am fairly sure that was due to the time taken to generate a new huge BitmapData object.  It would be nice for BitmapData.compare() to take a parameter that told it not to bother making the BitmapData showing where the differences lie, and instead just return its number codes.

Choosing which areas of the image to compare first is nice smart thinking, but given that BitmapData.compare() can examine a million pixels in a handful of milliseconds it is unlikely to be a necessary optimisation (see also: root of all evil).  Especially as I assume this process would only be performed once when the animations are first loaded, or at least wouldn't need to be repeated each frame.

It was interesting trying to do some of the work on a shader, but they're really just not designed for this kind of task.  Like BitmapData.compare() the shader has to produce a new image full of information which isn't actually required by the task at hand.  Custom shaders in Flash are also still freaky - the times above would likely at least double when running on a Mac for instance.

So there you go, a comprehensive answer to a question no-one asked! 

I still don't see how a partial test can return an accurate result. Without examining the entire BitmapData, you've no way of knowing if there may be pixels astray.

I don't think he's suggesting that.  Rather, you would start your search at areas which you happen to know are likely to be different.  If they are different then you can stop checking.  If they're the same, then you go on to check everywhere else to be sure.

For example, an animation of a rocket ship - start your search for changes at the "engine flame" area which you know is very likely to be different between frames.

Unless you're comparing huge images very often such cleverness is probably just not going to be needed.  It's a good technique that can be reused in other applications though!

this sounds more like you're not good at liking humans. i personally enjoy reading the comments on cute kitten videos, for instance. i also think that everyone has interesting things to say. this kind of reads to me like 'i'm cynical, i don't like people, so why should i like sites where people talk about their petty mundane matters'

I agree with your reading

I think there's a wide spectrum of the types of social interactions that particular individuals are interested in and comfortable with.

I'm over on that end,
whilst Formspring (and I daresay you) are way over there

Which kind of raises the question of why I'm posting in this thread!  Some kind of para--

Could you elaborate? I don't see that much wrong with it as a concept, to be honest, especially nothing that could be projected large enough to be symbolic for all that is wrong in the digital world.

Just what I find terrifying!  I genuinely don't mean anything against those that use it; it is just really not something I am interested in.  But to elaborate:

Signing up for an account is implying that your views are sufficiently interesting for strangers to want to probe.  Some people are that interesting!  Many are not.  The Modern Internet encourages everyone to think that what they have to say is worthy of being read by multitudes of strangers.

Someone makes a perfectly reasonable video of a kitten falling over, and then there's 1,364 comments about it.  It is not possible that any of them are worth reading - what worthwhile thing could possibly be said in that context?  Yet all those people must have thought that someone would want to read that they too found it to be cute.  Anonymous or effectively anonymous comments only serve to create a false sense of community, which our primate brains are so keen to grab on to.

Formspring neatly mixes in the common obsession with celebrity.  Now you can not only tell the world what your favourite Digimon is, but you can feel like they actually want to know.

From what I have seen the actual questions posed tend to be simplistic or just mindless, and so the answers rarely have a chance to be interesting.  The format of the site is a one question at a time deal which again discourages in depth questioning.

Interviews can be interesting.  Interviews in which the questions are posed by anyone that happens to wander by and are selected by the interviewee tend to be nothing more than a means for the interviewee to talk about what they feel like.  That kind of thing can be kept to Twitter.

I enjoy reading what many members of this community have to say about game development.  But forums with the occasional carefully crafted external article seem to work better for that purpose.

In summary: I'm not good at being a human.

As Increpare said waaaaay back at the front of this thread, the OMG UR LIVING IN A COMPUTER PROGRAM AND NEVER NEW IT!!! philosophy of The Matrix is about as old as philosophy itself.  It's maybe exciting and new when you're entering adolescence* (see also: MAYBE EVERYONE IS A ROBOT JUST PRETENDING TO BE A HUMAN AND I'M THE ONLY REAL PERSON.)  But posing that and ignoring the hundreds of years of more nuanced human thought that came in its wake isn't doing a good job of presenting philosophy.

*Or are most film critics, apparently.

Formspring neatly encapsulates everything I find terrifying/terrible about the modern internet. 

I think toy games are great.  I also think they deserve separate categorisation from sandbox games.  Toys are further along the sandbox spectrum than most games which are given that label.  A toy is (almost?) completely devoid of designed goals, and instead presents something for the player to interact with on their own terms.

I think there are two key requirements for a good toy game.  Firstly it should offer a wide possibility space for the player's actions, and cope gracefully with however the player interacts with that space.  GTA3 does this well, mostly thanks to some very nifty physics and AI.  The game is set up to expect high speed police chases along roads, but if I run off into a warehouse complex the AI copes with that and produces an interesting combat situation.  The cars that were chasing pull up outside and the officers find their way up to me, taking cover behind suitable objects (including the wrecked car I left outside) and engaging in firefight behaviour.  This is fun times.  If this were a scripted event then the animations would be a little neater, and the warehouse would be better laid out for gunfights, but it wouldn't feel anywhere near as real; even if technically it looked more realistic.

The second requirement - often overlooked by sandbox games - is that it should spark off the creation of game goals within the player themselves.  Consider SimCity, or Dwarf Fortress (see how it rears over the sandbox, glistening with terrifying beauty) and their ability to keep a player interested without ever having to tell them what to do next.  Consider World of Warcraft, and its obsessive need to tell you how many more cursed owl giblets you need to collect, where to find the cursed owls, and where to deposit the stinking mass to get your reward.  Warcraft needs to tell you what to do all the time because a player getting lost and wandering off will tend to get bored.  A player effectively does nothing but wander in a toy game; the difference is that they will find things about the world that interests, excites and encourages play.

I believe the key to toy games is understanding what about a particular game will make it spark the creation of goals by the player.  I think the themes of ownership and deep (longlasting/significant) interaction will turn out to be important.

On the subject of goals as valuable end-points, I think it depends on how one approaches the game as a source of entertainment.  The idea of a game that goes on forever is not at all appealing to me, but a game that goes on for just as long as I'm entertained by it sounds good.  The danger with end goals is that a player may find themselves slogging through a part of the game that they don't like just so that they can get to the end.  I stumbled on some blog entry recently which said their new year's resolution was to finish up playing a bunch of games, like it was cleaning the bathroom.  That isn't the relationship with games I am looking for.

I will not write about connections between dominating attitudes towards games (desiring to beat and then discard,) gender politics, and the male bias in video game production and consumption.  Because that would be silly.

Hello!

It feels like the camera is making basically the same movement again and again, just centered on a different ship each time.  Varying between a selection of such pre-defined movements would help keep it interesting.  Sometimes a zoom, sometimes a pan, sometimes attach the camera to the hull of a ship so you can watch it zoom about (or if the ship models have the level of detail; show a battleship's laser guns swing around and blow something up.)  Don't be afraid to add camera shake when there's an explosion near the camera's position too.

If you want to have a more recent sci-fi feel to the cinematic camera, consider having it behave much more like it's attached to a physical object that's moving through space rather than being a purely abstract position vector.  Consider how the camera moves in the Firefly series or Serenity film when it shows ships flying around - it gets knocked, rocked around and the camera seems to struggle to track fast moving ships, which creates a powerful physical sense of these ships actually existing.  Compare this with Star Trek:TNG era sci-fi, which has perfectly smooth camera pans and tracking much like your current camera system.  Smooth and well controlled cameras are a great asset during standard gameplay, but for this kind of optional cinematic camera you can afford to concentrate more on neat effects at the expense of practicality.

Is the direction that the camera ends up pointing random?  Would be nice if it more clearly showed what the ship is engaging.  I really know nothing about film directing, but I think there are various techniques for showing conflict between characters by their positions on screen.  At least aim to have the camera's set up take into account the position of a ship and their target.

An example of a cinematic camera that occurred to me was the one used in GTA4.  It was completely impractical for actually playing the game (too often failing to show where the player was headed) but it had a good variety of camera positions and movements which kept it interesting to watch.  If you're able to check that out it may give some useful ideas.

The effects are pretty nice, and I'm glad to see at least fairly colourful planets and space backgrounds.

I notice on the blog post you talk about how particular ships take much more damage to destroy.  I wasn't able to see this from the video. I think this is due to the camera cutting to a new sweeping movement all the time, which made it hard for me to keep track of where a particular ship was; let alone its relative health.  This isn't necessarily a problem, as the cinematic camera would be for getting neat views of the battle rather than being the primary means of getting information about what's going on.

The fight itself feels very static.  Obviously the game is still in development, but as a potential player I would be worried that it looks like combat is just lining up ships and watching lasers.  Show light fighters darting around the hulking battleships and missile frigates lurking at the back hurling attacks from range.  It is quite possible that these things are happening in the video, but I wasn't able to see it.

Showing some tactics in action throughout the video would be nice too, telling a simple story through the video.  It's a strategy game, so be sure to show potential players some strategy in action!

Now you should really introduce yourself!  Hang around, give feedback to other people, discuss art stuff, technical stuff, argue with Paul Eres.  It'll be grand.

[not]

A very simple trick is to not do the SQRT when calculating distance.  This will mean you wil actually calculate distance², but that's fine as whatever waypoint has the smallest distance will also always have the smallest distance².  Just make sure you're always comparing distance² with distance².

distance = SQRT( (dx * dx) + (dy * dy) )

distance² = (dx * dx) + (dy * dy)

Just adding the differences in X and Y coordinates would not give you a value that you can reliably use for comparing distance.  Consider one waypoint that is at (5,0) and another at (3,3).  Which is closer to (0,0)?  Looking at just the sum of the difference in position, (5,0) would seem to be closer.  Work out the true distance and you find that (3,3) is considerably closer.

Handling flat roofs (or rather flat sections of roof, allowing for trapezoid shapes) would probably be a sensible addition.

Unrelated, but the following roof doesn't render quite right:


layer 0
#######
#     #
#     #
#     #
#     #
#     #
#     #
#     #
#######

layer 1
 ######
 #    #
##    #
#     #
##    #
 #    #
 ######

layer 2
  #####
  #   #
###   #
#     #
###   #
  #   #
  #####

layer 3
   ####
   #  #
   #  #
####  #
   #  #
   #  #
   ####

layer 4
    ###
    # #
    # #
    # #
    # #
    # #
    ###

layer 5
     ##
     ##
     ##
     ##
     ##
     ##
     ##

Well, quite a few roof designs don't render quite right, but I think this one displays an error fairly clearly.  One of the walls of the part that sticks out to the left is being rendered as if it were closer to the camera than the main sloped roof.  I suspect other odd looking roofs I've seen are coming from a similar z-order error, probably.

It's generally rather nifty though.  I really should be asleep - hope this makes sense and even is useful.

Hi!  This is insane and confusing, and great.

You should totally post a little introduction in this thread.  Doesn't need to be anything fancy, but it's tradition, and gets rid of that Manbaby thing under your username.

I really love the sense of scale you get from picking one voxel from a vast landscape, and finding that it contains a whole landscape of its own.  Wonderful!

I think a lot of the speed/timing is off for me, possibly because I have quite a speedy processor?  I experienced the dark shadow passing over, but it was more a flash of darkness than a creeping eclipse.  Things just happening very fast made it a little overwhelming/confusing when I first became the Orange; that's rather part of the fun though I guess!

I can understand why the game switches to "turn based" movement during a jump, but it is kind of jarring.  I can well understand that it would be a huge task to get movement working smoothly in full realtime, but I think that it would be a very strong addition.  Allowing the player to move freely outside of the grid would be really amazing - I can't help but imagine a little Mario64 clambering around the hills.

I'm not sure if water blocking your movement during rain storms is a problem or actually a nice addition to the atmosphere.  It certainly makes you pay attention to the weather.

I found that water tended to flood areas a bit too easily.  I very much liked that after a rain storm little dimples in the landscape became ponds, and valleys became lakes.  But it seemed that after a few storms everywhere was gradually being covered in permanent water.  Maybe I was just somewhere particularly prone to floods.

I like that digging involves having to carry out the dirt you just dug up.  Games so rarely obey the conservation of mass.

It would be nice if the alternate camera modes you get from pressing C would show a cross-section of the rock, rather than allowing you to see through into the hollow landscape.

I'd say don't worry too much about making it into 'A Game' with missions and highscores, and all that junk.  Just keep adding things you find interesting and let people explore the worlds it creates.  I've really enjoyed my brief wander around so far, keep it up!

I always thought of the Zelda games as being multiple retellings of a legend (rather hinted at in the full title.)  It's a game series about how history becomes story.

Once there was a duke named Ganon who tried to muscle in on a young princess but was beaten and shamed in a duel by some upstart peasant.  The masses unsurprisingly liked the story better than all those about how great the King is, and so it was popular fodder for storytellers and bards to retell and adapt.

The sword and triforce probably came in from another legend to help make sense of how a peasant could win such a fight.  Admitting that Link could have just been a better fighter would get the storyteller in trouble with the current ruling class for inciting more upstart peasants.  Notice how Link always needs a whole mass of magical items to stand a chance (less so in the first game.)  Although the story is of a young boy fresh from the beach/forest/farm facing up to oppression. it takes care to avoid encouraging the masses to rise up against a similar Ganon figure today.  Defeating evil is the work of heroes in green tunics wielding the Master Sword, not the likes of you.

As dbb said, it's very simple to do in the UK: Declare yourself as a "sole trader" to the tax people, and you're recognised as being self-employed.  They send you a self-assessment tax return to fill out each year where you have to declare any/all earnings as well as expenses (you can't just skip it and assume your earnings are less than your expenses.)  How you get the money really doesn't matter - if you write "donate" or "pay what you think it's worth" on a payPal button, it's still income.  The only fixed cost is type 2 national insurance payments, which are tiny.  Obviously if you're self-employed then you can't go claiming unemployment benefits, but may be eligible for other help if you earn very little.

Of course you'll have a totally different system, so none of that is any use!  What I would say is make sure there's not a cheaper alternative to starting a company.  Starting a company does cost at least some money in the UK too.  But unless you need to be borrowing capital to get your business started (who needs money to make games?) there's no need to be a company.  It just seems kind of crazy if you absolutely have to form a company.  How does a solo window cleaner manage it?

[edit]

edit An expanded version of this post is available at my site here. /edit

The bitwise technique basically does the same as a huge if/else statement, but saves on typing.

Much easier to first think of it first for a map with just two types of terrain - let's say rock and open air.

A simple map might look like this, with the filled tiles being where there's rock:



The key to the bitwise method is to assign a value to each tile depending on its neighbours.  For this example let's use the following values:



We visit each tile that is meant to be filled with rock, and examine its immediate neighbours to come up with a number for that tile.  If the tile directly above this one is also filled then the number is 1.  If the tile directly above AND the tile directly below is filled, then the number is 1 + 4 = 5.

Here's that tile map filled out with the correct numbers.



The clever bit is we can now directly convert those numbers into graphical tiles, so skipping having to write a huge if/else statement.  Here is a tileset, laid out in the order matching the valuing system we picked:



See how each tile graphic matches what would be expected of its corresponding number?

Now our game can just look at the number calculated for each filled tile, and pick out the correct tile to place there:



It would be the same principle even if you want to consider diagonal neighbours, or more varied types of terrain.  You'll just end up with a larger range of numbers.

The reason it's referred to as bitwise is because the values we're assigning to neighbouring tiles follows the same 2^n pattern as binary numbers.

Hello!

You seem to have posted the same link twice.

Saying that, I really like the music - would be interesting slowed down for a creepy-crawly type animation.

Very glad to hear you like it!

Please find a meandering part two added above.

So how did this end?

It ended with a sponsorship deal with box10.com!

Sadly for my neat little chart, they've insisted that I keep the actual amount to myself.

I learnt a whole lot from the experience which is nice.  My main advice to anyone using FGL is to only put up your game at least a day after you're sure it's totally finished.  For the first couple of hours I had a bugged version uploaded, which a couple of sponsors played.  Dragging them back with promises of "it's better now, honest" unsurprisingly didn't work.

Once you have sponsors interested, my advice becomes to know what you're looking for in a deal and to know exactly what deal the sponsors are offering.  I fell into the trap of thinking that small details didn't really matter, and could be sorted out after the bidding.  They were sorted out after the bidding just fine, but by then I was in a poor negotiating position - the other interested bidders had seen the game sold and moved on to other things, so I was pretty much stuck with my top bidder.  Of course I wasn't contractually obligated to do anything until those small details were sorted out, but going through the hassle of changing sponsor didn't seem worth it for what were after all such small details.

It didn't turn out to be much of a problem in my case, the only change they wanted which I wasn't totally happy with was the removal of code to track where it's spread to. Financially this is no problem as it was distributed without ads (which I was happy with) but it would have been nice to watch it spread and have some idea of how many people are actually playing my game.  Instead my only way to monitor it is googling and hoping for pages that list number of hits, or checking the online score system for one section of the game.

I'd also have loved to include some tracking of how players moved through the options of the game.  The game has two play modes but I'm fairly sure the second mode is ignored by the vast majority.  Some numbers for that would be very interesting.  Similarly, knowing some detail of when and where players click links to sponsor's pages.  I added links not only to just the homepage, but to a "tips and tricks" page specifically for this game which I would be very interested in knowing the popularity of.

Keep in mind that small details can mean a reasonable difference in your total income from a game.  Losing out on $100 of ad revenue isn't a huge deal, but it's quite likely that your top bidder was only offering $100 more than the next who might have handed the ad revenue straight to you.

That was a lot for a five word question!

Where can I find all the music?

Incompetech.com

At the moment there's a news post on the front page that lists the tracks used by this game.

It's a wonderful site where one guy makes available for free (with a very liberal license) a huge collection of music that he has made for various projects.  You can also hire him to make music specifically for your project.

The fact that his site exists and he seems to not be starving to death makes me very happy.

The Tiny Worlds game also made me very happy!  For what it's worth, I found the jumping fine.  Probably they should have freed the player from the "pixel" grid though, as obviously many people didn't like it.  Add in some gentle collision response to nudge the player down narrow passages, and it should work out.

Afraid I can't offer much help, but I made a very simple platformer using a similar system to you.

I fed it a collision map like this:


and it used a tileset:


to produce a finished map you could jump around on.

I didn't do anything very clever to do it, just looping through the collision map using getPixel and populating a 2D array (I'd use a Vector instead now I know of them) to use for collision checking.  The tile to use at each location was determined by a simple examination of its neighbours.  Then a very ugly platformer physics engine stuck over the top.

Unfortunately it was one of the first things I made in Actionscript, and reading my source wouldn't help anyone.  Best of luck though

[Applying shadows using Blendmode]

Applying shadows using Blendmode
In Part One we drew out some plain black shadows, but we want to use these shadow shapes for something more than drawing black areas on the screen.  As everyone* knows, shadows aren't black but just darken whatever would normally be there.  Flash can do this nice and speedily by using BlendModes.

Very briefly, the BlendMode of a display object decides how it is drawn on top of other objects.  By default everything has BlendMode.NORMAL which just draws objects over one-another.  But there are a wide variety of BlendModes available which vary how the colours of overlapping objects will be mixed or combined to produce the finished image.

We are interested in using BlendMode.HARDLIGHT.  A display object set to HARDLIGHT will have its colours altered as if it were illuminated by whatever colours lie "beneath" it.  Stick a picture of a nebula over the demo from Part One, and set that picture's blendmode to HARDLIGHT, and you get:



Easy.  To be more exact on how this BlendMode works: Any colour value 128 (80 in hexadecimal) or over will cause the corresponding colour value in the image on top to be increased, colour values below that will cause a decrease.  It's easiest to understand thinking of a greyscale "shadow map" placed under your pretty image.  Dark areas on the shadow map will darken the image, light areas will lighten it.  It's an extreme effect, with any black areas on the shadow map resulting in a black area on the finished image and white areas producing pure white.  Generally your shadow map should vary between 0x303030 for dark but visible areas and 0x7f7f7f for fully lit areas.

Limited range lights
In Part One we dealt with just drawing shadows in what was assumed to be an infinitely large pool of light.  It is very simple to adapt this to drawing an illuminated area that contains shadows.

Each frame, instead of just clearing the area you draw the shadows to instead fill it with a dark "ambient light" colour.  Now draw on a circle (or cone, or whatever torchbeam-like shape you like) of light colour.  Then just draw on your shadows as normal in the dark ambient light colour.

You now only need to draw the shadows of objects which lie within your circle of light.  For instance box2D's World class provides a Query function which will allow you to find all the objects that fall within a specified area.

Extending shadows
Depending on the effect you wish to create, you may prefer your shadows to project out to the edge of your lit area.  Sadly I have been unable to find a neat and tidy way of doing this.

It is possible to project each point of the shadow you are drawing to the edge of the ring of light by changing your projectPoint function to:

Code:

private function projectPoint(point_:b2Vec2, light_:b2Vec2, lightRadius_:Number):b2Vec2
{
var lightToPoint:b2Vec2 = point_.Copy();
lightToPoint.Subtract(light_);

var extraLengthNeededToReachRadius:Number = lightRadius_ - lightToPoint.Length();

var vectorToAdd:b2Vec2 = lightToPoint.Copy();
vectorToAdd.Normalize();
vectorToAdd.Multiply(extraLengthNeededToReachRadius);

var projectedPoint:b2Vec2 = point_.Copy();
projectedPoint.Add(vectorToAdd);
return projectedPoint;
}

However as this projects the points that mark out the corners of the shadow shape that is then drawn using straight lines, there will be small segments of the light circle left unshadowed which should be in shadow.



My best solution so far is to fluff it and just add "a bit" on to the length of the projection vector so that the shadow shape is pushed far enough out.  I'm still working on other possibilities though.

Tile-based shadows
Sticking games in tiles is very popular, because it makes most things easier.  Good news is it makes shadows a little easier too!

Let's assume you have a tiled world something like this:


The red tiles are solid walls, which we'll assume block all light.  We can make it work by just considering each wall tile as a square which will cast a shadow just like any other polygon.  But there's plenty of opportunity for speeding things up!

Firstly we know that the edges of the wall tiles are always going to be straight along either the X or Y axis.  This means we can replace the fiddling about with vectors that was needed for polygons to determine if each edge should cast a shadow with some even simpler less-than and greater-than comparisons.

The biggest optimisation will come from being able to ignore some edges entirely.  This image shows all the wall tile edges present in our example:


That's a lot of edges.  By running the map through a simple trimming algorithm, a very large number of them can be ignored.  For each wall tile, check if the neighbour to its right also blocks light; if it does, then the wall tile's right edge can be ignored.  Repeat that for all the wall tiles and for all their edges and you'll end up with:



Depending on the size of your map this can take a while (it quickly becomes a huge number of checks to perform once your map is of a reasonable size.)  But the operation only needs to be performed when the map is first generated/designed.  Should your game involve the creation or destruction of walls, then you'll need to repeat the check on the neighbours of any tile that is changed.

You could further reduce the number of edges by joining adjacent edges to make a few long continuous straight edges.  I prefer not to do this, and instead keep things on a per-tile basis so that I can more easily limit what section of the map the game is having to deal with at any one time.

A further optimisation would be to perform LoS checks on tiles, so that those which are completely hidden from the lightsource by other tiles will not have their shadows drawn.  As I use quite large tile sizes, I found that this check would rarely eliminate more than a couple of tiles on the screen so I felt that it wasn't worth pursuing.  However if you use a smaller tile size, and tend to have certain types of level design then this check would become much more worth while.  The classic Rogue style levels of large open rooms connected by narrow passages would particularly benefit from LoS checking on tiles as you could often safely exclude whole rooms.

Visual consistency
This is a big topic.  Visual consistency deals with making sure your shadows make sense to the player.

In 3D graphics it's easy to make shadows make sense as they just need to appear as they do in real life or as close to that as you can manage with your technology.  The point is that there's an obvious end goal - to get as close to how the shadow really looks.

In 2D graphics making shadows look "right" depends a great deal on other aspects of the game's visual design.  The main problem is very few games are really showing a 2D world.  Instead they show a 2D view of a strangely flattened 3D world.  A good example to pull out at this moment are most the 2D Zelda games:


(image copyright Nintendo)

The walls look fine, until you think about them too much.  This room would need to have some deeply odd geometry for the view seen in the screenshot to be actually possible.  Try projecting realistic shadows over it and you'll just highlight how the graphical presentation shows a world that doesn't make sense.

Know what you're dealing with
It's important to have a clear understanding of what assumptions you're making about the world you're depicting in your game; otherwise you risk going against those assumptions when you add shadows and producing something that feels wrong to the player.

Let's take the example shadow caster from Part One and see what the shadows are telling the player about the world:



The shadow from each object has an end.  This means that the light source must be positioned higher (closer to the player's viewpoint) than the tops of the objects.

The shadows from all the objects are the same length when they're the same distance from the light.  This means all the objects are exactly the same height as one-another.

The shadows start at the base of the objects.  This means that the objects are sat on the surface that they're casting shadows on.

The shape of the shadows is determined only by the relative position of the light compared to the objects.  This means that the surface the shadows are being cast on is perfectly flat.

If this shadow caster was used in a game which broke any of these assumptions, the player will notice.  They may not realise what they're noticing but they'll almost always get a "this isn't quite right" feeling.  A huge slab of the human brain is dedicated to visual processing, and extracting information from things like shadows is something we're very good at - even if we're not aware of it.

Shadows on shadow casters
This is a problem I've wrestled with a great deal.  To know what I'm talking about, let's consider the walls I talked about in the tile-based section:



Wall A has a shadow being cast upon it, so shouldn't it be dark?  But how much of it should be dark?  Consider also how the wall which is casting the shadow should be shaded.  The edges facing the light source should be lit up, but the shadow casting sides should be in shadow.  Often the tops of walls are drawn on in these kinds of top-down views, but how should that be illuminated?  If we're being realistic about it, no light from below the wall's level would ever reach it and so it would be in total darkness.

These are difficult problems that need to be carefully considered, and your solutions to them are likely to have wide-reaching implications within your game.

Thankfully there is a cop-out that generally looks okay: Simply have all shadow casters be unaffected by shadows.  It's surprising how little this impacts the perceived quality of the finished image.  But do take care to have the colours of the shadow-casters be fairly muted, else they'll stand out too much from the rest of the shaded world.  Similarly avoid the use of very deep shadow else they will look out of place.

Here's a graphical Rogue-like prototype making use of the cop-out:



In this case the walls should have been a darker colour so that they do not stand out so clearly against the shadowed floor areas.

Avoiding the cop-out
Cop-outs are useful, but let's be awesome instead.

Choosing the right graphic style can make incorporating shadows much easier.  For this example I am using a pixel-art "2.5 topdown" view.  This means that it's kind of a top-down view, but one of the vertical sides of objects are visible to the player.

Here's shadow casting in the same prototype without the cop-out:



Not bad really, but there's a couple of problem areas.  Area A shows where a shadow overlaps the vertical section of a wall.  Area A doesn't look too shocking, but it is wrong - a shadow will not form the same shape on a vertical section of wall as it would on the horizontal floor.  Area B is more of a problem; here a wall casts a shadow but the wall on the shadowed side is still brightly illuminated.

The good news is we can fix both areas with the same technique.  We will simply project the shadow as it appears at the base of the wall up the full height of the wall.  Just loop along the length of the wall, reading the value of the shadow map at the base (using BitmapData's getPixel function) and fill in the row of pixels directly above it.  It's faster to use fillRect to do that rather than multiple setPixel calls.  Hey, I actually mentioned some Flash stuff!

As if by magic:



It isn't perfect of course.  It should be possible to position the player so that her shadow ends half way up the wall, but that will never happen using this system.  To get that effect you would need to work with the relative heights of the light source and shadow casting object, as well as volume information on the form of the shadow caster.  But that's just making a 3D game, which is cheating.

If you have vertical parts of the wall visible on all four sides of a tile (or just two sides, as in an isometric view) then you can use just the same technique for projecting shadows up those walls.  I made a prototype for a "all four sides visible" top-down view but wasn't quite satisfied with the results.  The technique should work quite nicely with an isometric view.

Not shadowing the character
Having shadows cast by an irregularly shaped object such as the player character not overlap with the character sprite itself is a fiddly business.

This problem doesn't occur in the case of walls or polygons, as the shadows only start at the far edge of the shape.  However the character is casting a shadow as if she were a simple polygon, when she is actually a quite different animated image.

My solution is that when the shadows from the character are drawn, the sprite is then drawn over the shadow using BlendMode.ERASE.  This effectively takes a character-shaped bite out of the shadow being cast by her.

It is possible for this to backfire, with this hole in the shadow being visible even if the character is actually hidden behind another object.  Sadly I haven't been able to find a more satisfactory solution.

Matching your graphics
You may notice that in the screenshots above the shadows all have rough edges rather than the nice anti-aliased lines of the demo from Part One.  Similarly there is a uniform pool of light, rather than a more realistic gradient fading out as it moves from the light source.  These are both efforts to keep the shadows fitting in with the visual style of the rest of the game.  Just because you're doing clever programming doesn't mean you can ignore the fact that gradients and pixel art don't mix, or that aliased and anti-aliased lines don't mix.

Similarly, you will need to keep in mind the impact that covering much of your graphics with light and shadow effects is going to have on their appearance.  Similar colours will look all the more similar when seen in shade, which may cause you to lose details - make sure those details aren't important to the player.  If you light a dungeon with moody orange light from candles, then everything will take on that orangey tone.  These can be great at building atmosphere, but you need to keep the effect of lighting in mind when you're making your assets.

Multiple lights
What's better than one pretty light effect?  TWO pretty light effects!



This is two identical candles sat next to one-another.  We want areas where light from both reach to be brighter than areas which get light from only one.  To achieve this, we first draw out the light/shadow effect for each candle separately:


And add them together!



Oh dear.  The problem here is that the sum of the light from two candles is actually over 100% illumination.  Being able to create over 100% illumination is useful for special effects (nuclear blasts, flashbang grenades, or walking from indoors to out in a 'next gen' game.)

With a bit of clever use of layering and blendmodes, we can cap the brightness of the light map:

Code:

var lightMapLimiter:Bitmap = new Bitmap(new BitmapData(vWidth, vHeight, false, 0x7f7f7f));
var shadowLayer:Sprite = new Sprite();
shadowLayer.addChild(lightMapLimiter);
shadowLayer.addChild(lightMap);
lightMap.blendMode = BlendMode.DARKEN;

addChild(gameLayer);
addChild(shadowLayer);
addChild(HUDLayer);

shadow.blendMode = BlendMode.HARDLIGHT;

Here lightMap is the end product of drawing all the scene's lights using blendMode.ADD, gameLayer is where the walls, player and everything else in the game world is drawn.  lightmapLimiter is just a big block of colour the size of the screen - whatever colour it is will be the cap for lightMap.

And something to play with
Finally you can wander around that rogue-like prototype if you like, though there's nothing to do but walk around looking at shadows.  Press space to make your faerie companion light up.

Click here

I feel like this post was a bit wandering, and long.  Hopefully there's useful parts in it for some people.

Further reading
Some discussion and further explanation of this tutorial.
A fine person made a shadow caster with a little help from this tutorial using HTML5's Canvas thing!

Right--forget seeding for a sec. How does one write the random number generator itself? From this article I read on the creation of Elite, I gather that you want to write a "Fibonacci-derived mechanism." I can conceptualize it in my head, but I'd like to see how it gets implemented in code.

A linear congruential generator is your best bet.  Wikipedia

I recently made a simple one in Actionscript:

Code:

package 
{
/**
* ...
* @author Salt
*/
public class rng
{
//this is a naive implementation of a Linear Congruent Generator.

private var _seed:int;

//m > 0
//0 < a < m
//0 < c < m
//0 < seed < m

//m determines the number of possible results the generator can give.
private const m:int = Math.pow(2, 12);

//a-1 should be divisible by all prime factors of m
//if m is a multiple of 4, then a-1 should be a multiple of 4
private const a:int = 17;

//c should be a coprime with m
private const c:int = 3;         

public function rng()
{
_seed = int(Math.random() * m);
}

public function set seed(val_:int):void
{
if (val_ >= 0 && val_ < m)
{
_seed = val_;
}
else
{
trace("rng.as tried to set a seed outside valid range.", val_);
}
}
public function giveNumber():Number
{
_seed = ((a * _seed + c) % m);
return (_seed / m);
}
}
}

The trick is picking good value for the constants M, A and C.  Poorly chosen values will cause it to produce only a few potential numbers, and they'll repeat in an obvious pattern.  Even the most carefully chosen values will inevitably result in repeats, but you aim to have that happen after a few hundred thousand iterations rather than half a dozen.

Many languages/libraries/whatever will have their own random number generator, and most will let you seed it yourself (often it'll be automatically seeded with the current time to be "random".)  Flash is one of those that doesn't let you seed its RNG, and the documentation doesn't reveal how it generates its results.

I actually initially seed the above random number generator using the built-in Math.random() function.  But if I manually seed it with (for instance) 123, its giveNumber() function will always produce:
0.51123046875
0.691650390625
0.7587890625
0.900146484375
0.30322265625
0.155517578125