Friday, 22 June 2012

Introducing a new thing. [Passwordle: what is it?]

So LinkedIn got hacked the other day. I (like many) received an email saying that my password had been obtained by some talented crackers. The passwords were hashed but there was no salt so many of the stolen passwords had been 'un-hashed'.

Turns out I'm a bit of a chump when it comes to passwords. I do tend to only use just a handful of passwords so if someone knows one it's pretty bad business for me. As a dev there's no excuse for reusing passwords.

I decided to do something about it but rather than creating a new password for each site I frequent I thought I'd write a little app to hash one master password with the URL of a website. That way I only need to remember one password but each site I visit gets a different hashed code.

Firstly I thought I'd see if anything similar already existed - standard - to my delight I found this: Did exactly what I wanted, not only that but it also contained a link to another version - sweeeet.

Trouble is: I think the passwords it generates are pretty weak. There is a version which uses a different hash algorithm but no version produces a password longer than 10 characters, nor do they guarantee upper and lower case, digits, symbols and letters. I decided to create my own.

Here it is:

It will always produce a strong password which will always contain digits, upper and lower case letters and symbols. The smallest length password it will produce is 16 characters, if the length of your master password is longer than 16 characters then the generated password will match its length.

I also added a 'name' field so you can add your initials or name or some other text to the generation process to ensure two users using the same master password can still generate different passwords.

I also interlace a mildly hashed version of the 'master' password into the generated passwords - just because I think it looks cool if the generated password vaguely resembles the original.

Wednesday, 11 April 2012

Alferd Spritesheet Unpacker. [Unpacking Algorithms]

During the end of 2011 I created a sprite sheet app called 'Alferd Spritesheet Unpacker' (you can download it here). It's a spriting tool which takes a single spritesheet bitmap and extracts each individual frame of animation and saves it as a new bitmap.

It looks like this:

I do get emails from users about the app from time to time, and I've had a few asking about the algorithm used in ASU to identify the frames. Rather than reply individually I thought I'd resurrect this blog and outline how it works.

Finding Boxes
  1. Firstly ASU iterates over every pixel in the Spritesheet to determine the most frequent colour. This colour then becomes the 'Background colour'.
  2. ASU then iterates over every pixel in the Spritesheet moving left to right, top to bottom. 
  3. When ASU finds a pixel that is a different colour to the 'Background colour' it creates a box. Fig. 1 below shows a Dan Hibiki sprite you might find in a Spritesheet bitmap.
    • The box's top left coordinate is the first non 'Background colour' pixel found during the previous step. 
    • ASU then iterates left to right until it finds the next 'Background colour' pixel. The number of pixels iterated becomes the box width. 
    • The height of the box is the number of pixels below the top left or top right of the box before we find a 'Background colour' pixel (whichever is greater).  Fig. 2 shows the first box found for this Sprite.
  4. ASU then repeats step 2 with the newly created box's top right pixel as the current pixel, until all pixels have been iterated over. (Fig. 3 below shows the progress of ASU having created 4 boxes.)

Creating Frames
  1. Once complete ASU now has a great collection of overlapping boxes (see fig. 4). ASU then calls a function which iterates over the collection of boxes until it finds two overlapping. When two overlapping are found they are both removed from the collection and replaced with a single box which covers the area of both. Once two boxes are 'combined' the function returns.
  2. If the previous step resulted in two boxes being 'combined' then the function is called again (the net result is this function being called until no two boxes are overlapping).

Once this is complete ASU has a collection of boxes covering every individual frame as in fig. 5.

Some sprite sheets have frames without continuous pixels (fig. 6) so in order to cope with this the function which combines two overlapping boxes doesn't just look for actual overlaps but any boxes which are very close (fig. 7). The default is within three pixels (it can be changed via the 'Distance Between Frames' option).

And that's it. 

Except to say for a quick performance gain this process actually first splits the original spritesheet into smaller tiles. The above process is run against each tile. Once all the tiles have been processed the tiles are re-combined back into a single sheet, and then the 'overlapping' boxes function is run again to combine frames which span multiple tiles.

I don't present this method as anything close to being optimal. This process is very greedy on resource. I am certain there are a thousand much quicker solutions, but I'm a big hater of Premature optimization. And I was happy with anything under a minute for the sprite sheets I use.

Tuesday, 24 August 2010

Why Doom is still the greatest game ever made. [The Doom Formula]

I’ve been moved to write this analysis of Doom i in response to, what I see as, a failure of the gaming industry to produce an FPS with any of the game mechanic gold introduced by Doom. Which was released way back in 1993. I hope to encapsulate what’s so great about Doom in the following passage – which is hypothetical but nonetheless represents a typical Doom experience – and then follow it with a concise summary of the definitive factors.

"Armed with a shotgun you spot a chamber up ahead and enter the room sideways. Sideways because a player can only shoot forwards and hours of play has taught you to always expect an ambush from the corners of a room.
Your fear is realised and the hiding zombie soldier is killed with a single shotgun blast. A quick 180 turn and a second zombie is also despatched.
You notice a health pickup and approach. As you approach the whirr of machinery signals the opening of an out-of-site door. Triggered by your advance on the health.
The noise of the door opening is punctuated with the hiss of a Cacodemon*. At close range dodging a Cacodemon's projectile is impossible. You must stop him attacking so you switch to the Chaingun (two taps of a shoulder button) and begin firing. The Chaingun's constant flow of bullets prevents a Cacodemon from ever attacking. Eventually the foe collapses... dead.
A box of rockets is discovered in the alcove concealed by the hidden door. You then make your way out the way you entered. Along the corridor and into a huge room visited several times before.
As you near a wall you notice bullets ricocheting off it and a green blob projectile.
The ricocheting bullets announce the presence of a Chaingun Zombie and the green blob a Hell Knight. Low on ammo you turn and, strafing to keep the Hell Knight between you and the line of fire of the zombie, attempt to get the zombie to shoot the Knight.
As planned the Chaingun Zombie's bullets start hitting the Hell Knight who turns to lob green globs towards the zombie; his new target. They get locked in a fight whilst you switch to the Rocket Launcher to end whomever emerges victorious."
*I think this exact behaviour may have been described in an article in the magazine ‘Computer and Games Video (C&VG)’ - though I think they failed to realise its general significance for the future of gaming.
[The Doom Formula TM ]:
  1. All deaths in Doom are avoidable.
  2. Enemies interact with each other - a lot - which adds a level of immersion and strategy. The player feels part of an atmospheric and living environment.
  3. The guns, such as the shotgun, have a real sense of power because they kill enemies with a single bullet and sometimes even groups of enemies, and when killed the death animations reflect this high amount of force.
  4. The weapons in Doom each have a purpose. In most modern FPS games ii the player merely uses the most powerful weapon available. When the ammo runs out the player simply switches to the next best. The player of a modern FPS never changes weapons based on the environment. In Doom each weapon has strengths and weaknesses affected by foes and environment.
  5. The armed gun sits directly below the line of site and not off to the corner like most FPS games iv. It improves the connection of the gun to the player. The majority of FPS break this paradigm further by providing a small crosshair in the centre of the screen. On-screen cross hairs limits the engagement to that of the 1987 arcade game Operation Wolf (below). A good example of gun placement in FPS is the 1999 PC game Hidden & Dangerous (below).
  6. Sound effects and visual cues, enrich the experience by arming the player with information to form tactics. Sound and visual affects are not extraneous but become additional tools for the player.
  7. The game uses recurring tricks and traps which evolve as the game progresses so the player not only battles the on screen enemies but also the game design as a whole. The game, in that sense, becomes tangible. The player is beating ‘the game’ as well as the enemies iii. There is a clear dialog between player and designer(s).
Operation Wolf

Hidden & Dangerous
What Doom doesn’t need:
  • Enemies made with 3D models
  • Improved AI
  • Scripted sequences of enemies breaking down walls and destroying surroundings
  • Vehicles
  • An involved story
  • Less enemies
  • Grenades
  • The ability to look up and down
  • A jump button

i The versions of Doom I have played most are the PSX editions Doom & Final Doom.
ii List of ‘modern’ FPS games including – but not limited to – Half Life (PC 1998), Chronicles of Riddick (Xbox 2004), Medal Of Honour (Multiple platforms, 1999-….)
iii This has also been noted by Sirlin in his article ‘The Secret of Donkey Kong Country 2’ analysing the SNES game Donkey Kong Country 2.
iv An example is BioShock (Multiple platforms 2007).