Friday, August 26, 2011

Balls to the Canvas!

To play around a bit with the canvas element, I decided to write this:



You can increase or decrease the number of balls on screen using the UP and DOWN arrows respectively.

View it in action


The source is here: https://github.com/dreasgrech/balls

Some implementation details

The background

To implement the colorful background, I'm using a cylindrical-coordinate representation of the RGB color model, known as HSV (Hue Saturation Value). Keeping the saturation and value to a constant 100 (max), I'm iterating through values 0-360 for the hue thus achieving the blending of colors. When the hue reaches 360, I reset it back to 0 and the cycle starts over.

The initial value of the hue is randomly chosen at the beginning.

Balls

All of the balls' attributes are randomly generated i.e. the initial position, size, color, speed and angle.

Since collision detection is only applied once the balls hit the edges of the browser window and the edges are axes aligned, I'm simply inverting the part of the velocity's depending to which edge is hit.

If the ball hits either the left or right edge, the x is inverted and if the ball hits the top or bottom edge, the y is inverted.

Resizing the window

I'm hooking to window.onresize so that once the browser window is resized, I adjust the width of the canvas appropriately and also remove the balls that are now out of screen.

Saturday, May 14, 2011

Solving systems of linear algebra with Wolfram Alpha

I recently needed to verify an answer to some problems I was solving at the time, and for that, I used Wolfram Alpha.

Say we want to graph the following system of equations:


The syntax would be:

solve 2x + y = 3 , x - 3y = 0

The general format would be:

solve <equation 1>, <equation 2>, ... , <equation n>

And the search engine will provide you with something like this:

Saturday, April 2, 2011

Writing brainfuck in Bitmap format

Inspired by this beautiful answer from Stack Overflow, I decided I'd do something similar.

The following is a bitmap image I drew in Paint visually showing a working brainfuck program:


Download the image, feed it to your brainfuck compiler and then execute the compiled executable.

If everything goes well, you should get something like this:

Sunday, March 27, 2011

Finding the Answer (ab)using JavaScript

This is my little tribute to Douglas Adams (and also my first go at obfuscation):


vI=0x2A;(o=eval)((r=unescape)("%5F%5f%"+vI/+(+vI+'')[1]%6+"D%36%3b"))+o(r("%"+__+"1\
%6"+(ww=String["fromCharCode"])(69)+"%73%77%65%72%3D")+((~~[]+011>>!~~~(J=Math)[""]+
(Jan=isNaN)(+/\//[+[]*+-"1"]+""[-1])*~!-+(___=__/2)+2^!+!J['round'](![H=undefined]+1
+o((J+1).substr(!+(B=alert)+-!B+7<<.9-1,!/^/.$-~255>>(2*!o('('+(F='function(')+'ema\
cs){if((dreas=vI)>emacs){always=1}}(vI-5))')-~1*1-(+!(function(){o(arguments[__['co\
nstructor'].prototype*9]+"='"+arguments[0]+"'")}('$'+__))))*2)+"Magnum/* */"[!+''+7]
+".PI")^!H*!Jan(Jan)-+2+1))<<(!0x0-[010][dreas%2]/2+(4&4)+o("'.'+o(((1|__^4*2)+\"\"\
)[1])")<<+!+(c=NaN)<<1^~+!c*-___+(+J['floor'](~2)^-4))|/**/!![,]["le"+($$$=(parseInt
+2))[2]+"g"+$$$[4]+"h"]/**/*(o("o('~1+010+/*~*/~([][0,+$6[1]+2]-always|!{a:1}[0]+24\
<<1)%15<<~!J.ceil.call.apply(J.ceil,[1..toString()])+1')")+0xE^3<<1)>>+!o('('+F+'){\
_:if(!(_=!1)){return}}())')>>!null+_));o(r(["%42",(o+'')[13],answer,(r+'')[18],ww(59
)].                                   join                                    ('')))


If the layout screwed up, here's how it should look like:


Click here to run it.

Why?


tl;dr: it was fun.

Now basically, the code does 'nothing' except alert the number 42. Actually, the majority of the code is doing a calculation to come up with the number 42, and then alert it.

Removing a single character from the above code will either invalidate the output or invalidate the code itself with a syntax error (except from that redundant whitespace on the last line)...and that was actually quite tricky to do (and may not have fully achieved since it wasn't the plan from the beginning), but was part of the fun in creating this.

I was actually writing a script that would run through my code removing a single character each time and then running (eval) the script, but I didn't finish it because as it turns out, complicating shit can be pretty fun so I switched back to this.

But the major part of the fun was finding creative ways of complicating things. Yup, complicating things! It felt refreshingly good trying to, for a change, obscure the code as much as possible given that every character is needed for the ultimate outcome.

How?


For example, let's say I had a calculation which involved the number zero. Now, the way a sane programmer would represent a zero is by using the 0 literal representation. But that's obviously too boring for a project like this, so I would try and find new ways of representing the value of zero. An example would be something like +!!NaN, or maybe -{}>>1.

Of course, there's a reason why both those obscure representations evaluate to 0 and how my above code manages to compute and alert the number 42, and one way of finding out those reasons is by painstakingly analysing the spec.

If you don't have time to carefully go through those 252 pages, what you really need to grasp is JavaScript's type coercion rules due to weak typing...and then, abuse them mercilessly!

I'm not really going to get too much into JavaScript's type system in this post, but I will briefly explain why the above two examples I mentioned evaluate to 0.

Let's take -{}>>1 first. According to JavaScript's operator precedence rules, the unary negation sign is evaluated first, thus coercing {} into the special NaN value. Then the bitwise shift coerces the NaN value into a 0 (since NaN is falsy) and 0 >> 1 is 0.

Now for +!!NaN, starting with !NaN evaluating to the boolean value true because the logical not sign coerces the NaN value to the boolean value false, and the negation (logical-not) of false is true, so !!NaN evaluates to false because double negating false evaluates to true. Finally, since the + here is used as a unary operation and not binary, it coerces false to 0; and that's it!

Splitting it up


Up until the end, I was working on a single line with no whitespace but when I was sort of ready with obfuscating, I needed to split the lines up into some shape (remotely representing something)...a task which I figured to be trivial at best. But as I came to realize, splitting the code into multiple lines without introducing errors is far from trivial.

Reason being of course that you can't just split the line in whichever point you want because naturally keywords cannot be split and other restrictions of the language syntax restrict you from splitting certain constructs directly into multiple lines.

For example, say you have function(){return}, you can't for example split in the middle of the word function:
fun
ction(){return}

That will not compile, and neither will compile if you split the return keyword; you can split at any other part of the line though.

But I actually had the most trouble splitting property calls. Say you had to split [].constructor.prototype; now that's a bitch because of the two relatively long keywords in the expression.

How did I get around this? Simple. I switched from using dot-notation to subscript-notation, and since strings can be successfully split into multiple lines, it was much easier:

[]['constructor']['prototype']

Now if we wanted to split:

[]['construc\
tor']['prototype']

To split strings into multiple lines in JavaScript, just add the backslash symbol to the end of the unterminated string literal, and now, your splitting task is much easier.

Although using the subscript-notation made the lines easier to split, it introduced a new problem.

Say I have ['ab'] and I need to split between the ' and the a characters.

You can't split like this:

['
ab']

because now you have an unterminated string, which results in an error; but you also can't do this:

['\
ab']

because although it runs successfully, you have now added an extra character (\) to the previous line and that would invalidate your box-line shape of the code. And of course, can't also do this:

[
'ab']

because, as mentioned previously, although it runs, you have now removed a character from the previous line which would invalidate the box.

This one was a bit more annoying to deal with because, to my knowledge, there is no way around it...but still, this was all part of the challenge involved and it was fun.

Saturday, February 26, 2011

Adapting to Farseer Physics Engine's Meter-Kilogram-Second (MKS) system of units

Recently switched to version 3.x of Farseer Physics Engine and have been experiencing slow simulations since? Can't get anything to accelerate past a certain point because everything looks like it's floating in a damn aquarium? Are you frustrated and tearing your hair out because you think this new version "sucks" !? Don't worry, you're not alone.

Now, take a deep breath and carry on reading...(tl;dr: demo)

Starting with 3.x, FPE now uses the MKS (Meter-Kilogram-Second) system of units and this has been the source of confusion for both people who were working with version < 3 and also people who were new to FPE.

Note: Other people have already written about this topic but I feel that, since this has been a major source of confusion for many, it hasn't been given the attention it requires.



To begin with, let's be naive and try to create a Body like such:

float width = 200f, 
      height = 100f,
      density = 10f;
Vector2 position = new Vector2(300, 400);

Body body = BodyFactory.CreateRectangle(world, width, height, density, position);

In the Draw method, I (naively) draw the texture at the body's position as follows:

spriteBatch.Draw(texture, body.Position, Color.White);

What I'm doing above (or what at least I think I'm doing) is create a 200x100 pixel rectangular body positioned at (200, 300) pixels on the screen and then drawing it at wherever the body is at the current moment, starting from our initial (300, 400).

But because now Farseer Physics Engine uses the MKS system of units, what we are actually doing is creating a 200m wide and a 100m high rectangle rectangle positioned 200 meters from the right and 100 meters from the top! And Box2D (since Farseer is based on Box2D) tells us that we should keep our bodies (especially if they move) in the 0.1 - 10 meter range.

This means that we now have to split the way we position physics objects on screen and the way we draw their corresponding textures.



To accomplish this, we can use the ConvertUnits class found under Samples\Samples XNA\Samples XNA\ScreenSystem.

ConvertUnits is a helper class that lets us switch between display units (pixels) and simulation units (MKS) easily.

So let's go back to that previous example and fix our code by first converting our display units to simulation units with ConvertUnits.ToSimUnits:

float width = ConvertUnits.ToSimUnits(200f), 
      height = ConvertUnits.ToSimUnits(100f),
      density = 10f;
Vector2 position = ConvertUnits.ToSimUnits(300, 400); // ToSimUnits has an overload which returns a vector given two floats.

Body body = BodyFactory.CreateRectangle(world, width, height, density, position);

Now to draw our body on screen, we need to convert the simulation units back to display units by the appropriately named method ConvertUnits.ToDisplayUnits:

spriteBatch.Draw(texture, ConvertUnits.ToDisplayUnits(body.Position), Color.White);



Still can't get it? No worries, because I created the simplest Farseer Physics 3 example you can find which demonstrates what I said above: https://github.com/dreasgrech/SimplestFarseerPhysics3Example

The example creates a rectangle and lets gravity do its part; that's it! I've compiled it for both the Windows and the Windows Phone 7 XNA versions.

Another note: Since FPE is currently undergoing the upgrade to 3.3, the above code example can break if used with a different version of the engine. I've compiled the example with the version from Changeset #85352.

Sunday, February 13, 2011

StringEvolver: Evolving strings with a genetic algorithm

This is my first attempt at experimenting with a genetic algorithm. The following is an application that evolves a string given a destination to converge to.



Here is an example run:
> StringEvolver -m 0.25 -s 0.6 -c 2000 -e 0.1 --fitness=hamming --ctype=one -t 0.3 "Charles Darwin was right!"

Evolution Destination: Charles Darwin was right!
Mutation Rate: 25%
Crossover Rate: 60%
Truncation Rate: 30%
Chromosomes / population: 2000
Elitism / population: 200 (0.1%)
Fitness Calculator: Hamming Distance
Crossover Type: One Point

    1: L<eI`Y@ D#raF'JKJ7DUAg"GR
    2: L<eI`Y@ D#raF'JKJ7DUAg"GR
    3: chNOLe"5]={Iiyrgk*,rEpE/!
    4: L<eI`Y@ D#ra nR$C1SrYqha+
    5: L<eI`Y@ D#ra nR$C1SrYqha+
    6: lpa5`Y@ D#ra nR$C8y.iqrt5
    7: C]Y&hJ1 %aRwi< aaB,r_Zh68
    8: 1s[r.ts %aGwi< _a"=rjXyN!
    9: chNOlFsyD#rwi< }aB,r_Zh68
   10: chNO9e" D#rwi< }aB=rPgh6!
   11: chNO9e" D#rwi< }aB=rPgh6!
   12: 1s[r.Ks D#ra n}way rAght!
   13: C}hplFs D#rwi.}way rPgh6!
   14: C'aclos Da{]inrwas r.ghx!
   15: C'aclos Da{]inrwas r.ghx!
   16: ChNrlFs Da>win}was  `gha!
   17: ChNrlFs Da>winlwas r;gh6!
   18: Ch[rlFs Da>wi< was rAght!
   19: Chacle@ D#rwin was rjght!
   20: Chacle@ D#rwin was rjght!
   21: ChNrles Darwin}was rAght!
   22: ChNrles Darwin}was rAght!
   23: Charles Darwin}was r`ght!
   24: Charles Darwin}was r`ght!
   25: Charles Darwin was rAght!
   26: Charles Darwin was rAght!
   27: Charles Darwin was rAght!
   28: Charles Darwin was rAght!
   29: Charles Darwin was rAght!
   30: Charles Darwin was right!

Found in 30 generations
Time Taken: 00:00:00.4730271

Source

You can download the source from github: https://github.com/dreasgrech/StringEvolver

Command Line arguments

-m, --mutation=VALUE
A value between 0-1

The mutation rate determines the probability of how often a selected chromosome mutates. Mutation is very important in a genetic algorithm because it helps in keeping diversity in the population, thus avoid local minima which can slow or even halt further evolution.

The application currently uses a mutation operator called Single Point Mutation. For our current application, it works by randomly selecting a point in the string and switching the character at that point to another random character.

As an example, say the chromosome to be mutated currently contains the string "aBcdE". The single point mutation operator then randomly chooses position 2 (0-based) and replaces the character 'c' with the randomly chosen character 'W'.

This way, the chromosome "aBcdE" has now been mutated to "aBWdE".

-s, --crossover=VALUE
A value between 0-1

The crossover rate determines how often two selected chromosomes are sexually combined to produce two separate offspring.

For this application, there are two available crossover operations: One Point Crossover and Two Point Crossover. These operators are discussed further in the ctype argument.

-e, --elitism=VALUE
A value between 0-1

The elitism rate determines the number of the fittest solutions that are directly (untouched) transferred to the advancing population.

Elitism can help in preventing the potential loss of possibly good solutions and can lead to quicker convergence.

-c, --crcount=VALUE
A value greater than 1

The chromosome count determines the number of chromosomes that each population will have. The greater the number of chromosomes, the more time a population takes to advance to the next.

--fitness=VALUE
VALUE = sum, levenshtein or hamming

The fitness calculator determines which algorithm is used to calculate how fit a given chromosome is.

There are currently three fitness calculators to choose from:

Sum
The sum calculator calculates the ASCII difference between each character of the target strings.
public override double CalculateFitness(Chromosome ch)
{
    var distanceToTarget = Target.Select((t, i) => Math.Abs(t - ch.Value[i])).Sum();
    return 1.0 / distanceToTarget;
}
Levenshtein Distance
The Levenshtein distance between two strings is the minimum number of edits needed to transform one string into the other. The transformation can include insertion, deletion and substitution. This distance is also referred to as the edit distance.
public override double CalculateFitness(Chromosome ch)
{
    return 1.0 / LevenshteinDistance(ch.Value, Target);
}
Hamming Distance
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. The reason Hamming distance requires the strings to be of equal length is because unlike the Levenshtein distance, the Hamming distance only allows substitutions.

As an example, the Hamming distance between "janica" and "jenixo" is 3.
public override double CalculateFitness(Chromosome ch)
{
    if (ch.Value.Length != Target.Length)
    {
        return 1.0 / double.PositiveInfinity;
    }

    var difference = 0;
    for (int i = 0; i < Target.Length; i++)
    {
        if (ch.Value[i] != Target[i])
        {
            difference++;
        }
    }
    return 1.0 / difference;
}

--ctype=VALUE
VALUE = one or two

The crossover type determines which crossover operator is to be used when sexually combining two chromosomes.

There are currently two available methods to choose from:

One
The One-Point Crossover method chooses a random point (called a locus) in the string and all the data beyond that point in either chromosome is swapped between the parent chromosomes. The resulting two chromosomes are the children.
public Tuple<Chromosome, Chromosome> Crossover(Chromosome c1, Chromosome c2)
{
    var locus = random.Next(0, c1.Value.Length + 1);
    string ch1 = c1.Value.Substring(0, locus) + c2.Value.Substring(locus),
           ch2 = c2.Value.Substring(0, locus) + c1.Value.Substring(locus);

    return new Tuple<Chromosome, Chromosome>(new Chromosome(ch1, fitnessCalculator), new Chromosome(ch2, fitnessCalculator));
}

Two
The Two-Point Crossover method is very similar to the One-Point Crossover method but this one chooses two random points along the string rather than one. The data between the two points is swapped and the resulting chromosomes are the children.
public Tuple<Chromosome, Chromosome> Crossover(Chromosome c1, Chromosome c2)
{
    int locus1 = random.Next(0, c1.Value.Length),
        locus2 = random.Next(locus1, c1.Value.Length),
        distance = locus2 - locus1;

    string ch1 = c1.Value.Substring(0, locus1) + c2.Value.Substring(locus1, distance) + c1.Value.Substring(locus2),
           ch2 = c2.Value.Substring(0, locus1) + c1.Value.Substring(locus1, distance) + c2.Value.Substring(locus2);

    return new Tuple<Chromosome, Chromosome>(new Chromosome(ch1, fitnessCalculator), new Chromosome(ch2, fitnessCalculator));
}

-t, --truncate=VALUE
0 < VALUE <= 1

The Truncation value determines how many chromosomes of the current population should be kept and used for the selection, crossover and mutation operations. Note that before the truncation is performed, the chromosomes in the population are sorted in descending order by their fitness, so the fittest chromosomes are kept after the truncation.

A value of 1 uses all of the chromosomes and a value of 0.5 uses half of the population (the better half, of course)

Thursday, December 23, 2010

The A* algorithm in XNA

The A* search algorithm ("A star") is used for path finding and graph traversal. The following is my implementation in XNA.

The A* algorithm itself is very similar to Dijkstra's algorithm but the A* uses heuristics to achieve better performance.

Screenshots

Usage

Left Mouse Click - Create a barrier
CTRL + Left Mouse Click - Set the source
ALT + Left Mouse Click - Set the destination
Space - Toggle grid lines
Enter - Start pathfinding!
` - Open the developer console

Heuristics

The A* algorithm uses a heuristic to improve performance by trying to "guess" the best path, although this will not, unlike Dijkstra's which does not use a heuristic, guarantee the shortest path.
Diagonal Distance
public int GetEstimate(Point source, Point destination)
{
    return Math.Max(Math.Abs(destination.X - source.X), Math.Abs(destination.Y - source.Y));
}
Manhattan Distance
public int GetEstimate(Point source, Point destination)
{
    return Math.Abs(destination.X - source.X) + Math.Abs(destination.Y - source.Y);
}
Euclidean Distance
public int GetEstimate(Point source, Point destination)
{
    return (int)Math.Sqrt(Math.Pow(source.X - destination.X,2) + Math.Pow(source.Y - destination.Y,2));
}
Dijkstra
When the heuristic is 0, the A* algorithm turns into Dijkstra's algorithm
public int GetEstimate(Point source, Point destination)
{
    return 0;
}

Try it!

The source can be found on github: https://github.com/dreasgrech/AStarXNA