Tower Defense games in flash and silverlight

Yikes, it has been eons since I’ve posted.  Taking two classes this semester is considerably more work than I anticipated.

In some of my limited free time, I’ve been playing a couple of flash games.  There are many collections of links to these types of games, including onemorelevel, flashgames247, and gameprison.  For a list of “Top” games by genre, I found the list on TechCult to be pretty good.

The ones I’ve enjoyed the most are in the “Tower Defense” genre, where you need to build a series of defensive towers to defend against waves of attackers.  This genre grew out of the Warcraft 3 Tower Defense multiplayer game (which I believe evolved from a similar StarCraft game).  I used to watch my son play the Warcraft version and never understood the draw.  I guess that is because I hadn’t played it; now that I’ve started playing games in the genre, I definitely see the allure.

I’ve also been playing around a bit with Silverlight.  I wrote a Silverlight version of Conway’s Game of Life that I hope to blog about soon.  As another learning experience, I’m toying with the idea of writing a tower defense game in Silverlight.  I may never get around to it, but doing the research is a lot of fun.

I’ve managed to find one version already written in Silverlight, called Mountain Pass Tower Defense.  There is also a pathfinding experiment that the author describes as an early step in writing a tower defense game.

In the Warcraft version, the critters could attack the towers and knock them down.  I haven’t seen that in any of the flash versions.  That’s something I think I’d try to include.  I also tend to like the ones that are maze-like, where the critters follow a path, as opposed to the ones that are open areas (for those, I usually end up building my own maze).  Most games only include a handful of maps; it would be nice to be able to generate random maps (perhaps based on a seed that the user can enter to retry the same map later).

Anyway, here are my four favorite tower defense flash games.  I’m not saying these are the best, just that they’re ones I’ve enjoyed.

Bloons Tower Defense 3

Bloons Tower Defense 3

This is one that I’ve played quite a bit.  It is simple to play, humorous, challenging, and a lot of fun.

Vector Tower Defense

Vector Tower Defense

The graphics on this one reminded of the games I used to play years ago.  I also like the fact that it uses a grid layout, making placement of towers easy.  On some of the other games, it is possible to place a tower in a spot that prevents placing another tower nearby because you didn’t leave enough room.

Onslaught

Onslaught

One of the first, I believe, and very popular.  I’ve seen mention of a new version (Onslaught 2), but I’ve not played it.  Yet.

Canyon Defense

Canyon Defense

There were two things I liked about this game.  First, you needed to complete little “mini quests” to upgrade to better towers.  That not only helped with the learning curve (by limiting options in the early game), but it also forced me to build tower-types I probably wouldn’t have otherwise built.

Second, it included buildings (2 squares by 2 squares) that gave special abilities, such as building walls or launching big missles.  The missles have a cool down, but could be launched whenever you needed a little extra boost.

Stephen Lynch

Ok, I’m probably the last person to hear about him, but I was listening to pandora the other day, and decided to create a “Flight of the Conchords” channel, and pandora played a couple of songs by Stephen Lynch.  I liked those songs, so I picked up one of his CDs from amazon, and it arrived yesterday.  I’m really enjoying it.

To give you an idea, here is a youtube video of the song D&D off the CD (Superhero):

That video is PG…most of the other stuff on the CD is rated R…not that I mind, but fair warning.

Breaking CAPTCHA

I always figured there were ways spammers could get around CAPTCHA (Completely Automated Turing Test To Tell Computers and Humans Apart), but I’d never seen it discussed.  For those that might not be familiar with the name, a CAPTCHA is one of those weird text challenges where you have to type in some cryptic text to register on a site:

CAPTCHA Sample

I stumbled across an article describing a trojan that presents voyeurs with a woman doing a strip tease – each successful CAPTCHA entry removes another article of clothing.  One such trojan (HotLan) has been used to create more than 500,000 accounts on popular e-mail sites.

It struck me as a bit ironic that clicking on the “Discuss this article” link on that website prompted me with a registration form that included a CAPTCHA challenge.

The CAPTCHA web site acknowledges the issue, but deems it “not a concern”:

While it might be the case that some spammers use porn sites to attack CAPTCHAs, the amount of damage this can inflict is tiny (so tiny that we haven’t even noticed a dent!).

In spite of all this, I don’t see much of an alternative, and I’m sure I’ll continue to use CAPTCHAs on sites.  At least it makes it a lot harder for spammers…

Cardiac Physiology and Action Potential Movies

In Physiology class today, we talked about cardiac physiology and the action potentials for heart contraction.  it was a lot of information to soak up, so I went looking for some additional sources.  I found a handful of movies by Walid Aziz (aka hyperhighs) on youtube that are simple, but he has a knack for explaining things.  I’ve collected the links here that are relevant to my class, but he has posted many more videos on physiology and anatomy.

• Heart Physiology (Ventricular filling: part 1/6)
• Heart Physiology (Cardiac pressure-time curve: part 2/6)
• Heart Physiology (Cardiac output: part 3/6)
• Heart Physiology (Starling law: part 4/6)
• Heart Physiology (Length-tension plot: part 5/6)
• Heart Physiology (Dynamic heart plot: part 6/6)

• Cardiac Action Potential (Pulse propagation: part 1/6)
• Cardiac Action Potential (Pacemaker AP: part 2/6)
• Cardiac Action Potential (Autonomic effect: part 3/6)
• Cardiac Action Potential (Cardiomyocyte AP: part 4/6)
• Cardiac Action Potential (Electro-mechanics: part 5/6)
• Cardiac Action Potential (Sarcomere: part 6/6)

First BioSharp App – RestrictionFinder

I’ve started work on my first application that uses BioSharp.  It is called RestrictionFinder, and its purpose is to help find a pair of restriction enzymes that give distinct cleavage patterns when an insert is present in a plasmid in the forward direction, reverse direction, or absent.  It also has the ability to limit the search to pairs of enzymes with compatible buffers.

Here is a screen shot of the sequence entry form:

Sequence Entry Form

If the sequence contains uppercase and lowercase, the lowercase is assumed to be the insert, and the start/end positions are set automatically.

As part of the solution, I needed a small database (just a file, really) of enzymes and their buffers.  I could not find a readily available file for this, so I wrote a small console app that extracts the data from the REBASE web site.

This is still a work in progress, but the source code is checked into the BioSharp SVN repository.

BioSharp web site is live

I’ve uploaded the first incarnation of the BioSharp web site.  It is still a bit thin, but at least the API docs are available.

The next step in the project will be to work on an application that was the whole motivation for BioSharp.  As that progresses, I’m sure I’ll be continuing to port bits.  According to my port status page, I’m just under 5% done…only 1413 classes left to port.  Even at this point, though, the library has some useful functionality, as demonstrated by a few of my earlier posts.

If you are interested in seeing a specific module ported over, don’t hesitate to add a comment here to post in the forums.  I’ll also look at getting a mailing list set up sometime soon.

Finding and flipping a DNA sequence with BioSharp

The BioSharp port is still moving forward.  I have enough functionality now to be able to create a DNA sequence, find a subsequence with that sequence, and create a new sequence with the subsequence flipped around.

For example, it can take “aacgaa”, search for “cg”, flip it around, and create the new sequence “aagcaa”.  It would be trivial to do this just by string manipulation; hopefully the investment in the library will be worth it.

Here is a bit of sample code to do the search and flip.

private static void FindAndFlip()
{
    // Create our two bits of DNA
    ISymbolList bigDNA = DNATools.CreateDNA("acgatagatagctacgcatagctagctaagctacgactacgctacgctacg");
    ISymbolList subSequence = DNATools.CreateDNA("agctagctaagct");

    // Find the smaller piece within the larger piece
    KnuthMorrisPrattSearch search = new KnuthMorrisPrattSearch(subSequence);

    int[] results = search.FindMatches(bigDNA);

    if (results.Length == 0)
    {
        Console.WriteLine("subSequence not found!");
        return;
    }

    // Reverse the small piece
    ReverseSymbolList reverseSubSequence = new ReverseSymbolList(subSequence);

    // Make a copy of the big sequence that we can play with...
    ISymbolList reverseBigDNA = new SimpleSymbolList(bigDNA);

    // Overwrite the forward sequence with the reverse...
    Edit edit = new Edit(results[0], subSequence.Length, reverseSubSequence);

    reverseBigDNA.Edit(edit);

    // Print out the results...
    Console.WriteLine("subSequence:        " + subSequence.SeqString);
    Console.WriteLine("reverseSubSequence: " + reverseSubSequence.SeqString);
    Console.WriteLine("bigDNA:             " + bigDNA.SeqString);
    Console.WriteLine("reverseBigDNA:      " + reverseBigDNA.SeqString);
}

Here is the output from this snippet, with the flipped sequence highlighted in red:

subSequence:        agctagctaagct
reverseSubSequence: tcgaatcgatcga
bigDNA:             acgatagatagctacgcatagctagctaagctacgactacgctacgctacg
reverseBigDNA:      acgatagatagctacgcattcgaatcgatcgaacgactacgctacgctacg

Note that this is simply the reverse of the subsegment, and not the reverse compliment.  The reverse compliment would be just as easy to do, though…

You know your port is in trouble when…

In porting BioJava, I came across the following comment:

Don’t use this class directly. This class contains deep voodoo code. Run away while you still can.

Looking a bit deeper at the class, it generates code on the fly.  That wouldn’t, in itself, be too bad, except it doesn’t generate Java and compile it, it generates bytecode!

Here is a small snippet:

        GeneratedCodeMethod init = pclass.createMethod(
                "<init>",
                voidC,
                new CodeClass[]{
                  faceClassC,
                  projectionContextC
                },
                CodeUtils.ACC_PUBLIC);

        InstructionVector initIV = new InstructionVector();
        initIV.add(ByteCode.make_aload(init.getThis()));
        initIV.add(ByteCode.make_aload(init.getVariable(0)));
        initIV.add(ByteCode.make_aload(init.getVariable(1)));
        initIV.add(ByteCode.make_invokespecial(m_ourBase_init));
        initIV.add(ByteCode.make_return());
        pclass.setCodeGenerator(init, initIV);

Uh, yeah.  I can read and write Java, but I’m no expert, and I’ve certainly never looked at Java bytecode.  To make matters worse, the code uses the “continue label” construct, like the following (the “more code” placeholder is about 150 additional lines):

        METHOD_MAKER:
        for (Iterator methIt = faceClassC.getMethods().iterator(); methIt.hasNext();) {
          CodeMethod faceMethod = (CodeMethod) methIt.next();
          Set baseMethods = baseClassC.getMethodsByName(faceMethod.getName());

          if (baseClassC.getMethodsByName(faceMethod.getName()).size() > 0) {
            for(Iterator i = baseMethods.iterator(); i.hasNext(); ) {
              CodeMethod meth = (CodeMethod) i.next();
              if( (meth.getModifiers() & CodeUtils.ACC_ABSTRACT) == 0) {
                //System.err.println("Skipping defined method: " + faceMethod.getName());
                continue METHOD_MAKER;
              }
            }
          }

          // ...more code...
        }

I’m not saying it’s bad code; I’m just saying it’s not going to be much fun to port, especially given the lack of unit tests on these bits and the fact that I’ve never generated C# code on the fly, either.

Ah, well, at least they warned me with that comment up top.

So much to port…so little time.

I haven’t posted in a while, as I’ve been working on porting BioJava over to C#.  It is a big library (to say the least), and I’ve almost (hopefully) got enough code working that I can find restriction enzyme sites on a strand of DNA.  So far, I’ve ported about 150 classes, although a fair number of them still have a handful of NotYetImplemented exceptions lying around.

Within the next week or two, I hope to have some code to post here, along with a link to the initial web page for the project.

When are two HashSets equal?

It has been a couple of days since I’ve posted, as I’ve been trying to track down an elusive bug deep in the bowels of the C# port of BioJava.  I don’t have it fixed yet, but I’ve determined the root cause.

There are number of places in BioJava where they use a Set as a key in a dictionary, to handle things such as ambiguity symbols.  For example, in DNA, the symbol ‘N’ represents any base A, G, C, or T.  If a reverse lookup is done, asking for the ambiguity symbol for AGCT, it should always return the same symbol – N.

In the port, I goofed and used a List<> in a couple of places to port a Set.  When I went to fix that and replace it with a .Net HashSet<>, it didn’t resolve the problem, much to my surprise.  I wrote a quick test to try and figure out what was going on:

[Test]
public void HashSetAsKey()
{
    HashSet<int> h1 = new HashSet<int>();
    h1.Add(1);
    h1.Add(2);

    HashSet<int> h2 = new HashSet<int>();
    h2.Add(2);
    h2.Add(1);

    Dictionary<HashSet<int>, string> dict = new Dictionary<HashSet<int>, string>();

    dict.Add(h1, "hello");

    Assert.AreEqual("hello", dict[h2]);
}

This test fails, with a KeyNotFound exception.  The sets are equivalent, so why didn’t this work?  Time for another test.

[Test]
public void HashSetEquality()
{
    HashSet<int> h1 = new HashSet<int>();
    h1.Add(1);
    h1.Add(2);

    HashSet<int> h2 = new HashSet<int>();
    h2.Add(1);
    h2.Add(2);

    Assert.AreEqual(h1, h2);    // Why does this fail???
}

Even adding the items in the same order fails!  In fact, you can remove the four Add calls and compare two empty HashSets – the test will still fail.

After some digging, it turns out that the equality test I was expecting is implemented as a separate method, called SetEquals.  The following test will pass:

[Test]
public void HashSetSpecialEquality()
{
    HashSet<int> h1 = new HashSet<int>();
    h1.Add(1);
    h1.Add(2);

    HashSet<int> h2 = new HashSet<int>();
    h2.Add(1);
    h2.Add(2);

    Assert.IsTrue(h1.SetEquals(h2));
}

So, when are two HashSets equal?  It looks like the answer is: never.

Argh.

That makes the HashSet class useless as the key to a dictionary, unless I’m missing some other way to make it work.

I’m off to write my own Set class.