Jonathan Swift's Blog

Pathfinder using DirectX and Genetic Algorithms

Well, I've been threatening it for long enough, now it's time for some action : ) Over the course of the next few weeks I'll aim to build a simple 2D application that demonstrates how a Pathfinder application can be developed using genetic algorithm's. I'm going to use DirectX to render the 2D display because I've been messing about with it on and off for a while now and happen to think it's really cool. I'll aim to walk you through the code (of which there will be quite a bit) and so this example will be comprised of multiple parts, each covering a logical step in the example build.

This first step then will take you through creating the initial C++ application, registering and creating the standard window's bits (entry point, window, message loop, callback proc etc etc) and setting up and initialising DirectX, ready for use. I guess I'm hoping that even if you've never used C++ or DirectX before you'll find these instructions easy enough to at least follow, if not fully understand.

And with that, let's begin. The first thing to do is to make sure you have the latest DirectX SDK installed (currently DirectX 10), you can find this by browsing here. I'm assuming you have Visual Studio installed also. Kick off by creating a new C++ project using the 'empty project' template. As its name implies, this does nothing more than create a base project with nothing in it, a blank canvas if you will.

Next, you need to add a .cpp  to the Source Files directory to enable you to write your code, call it whatever you want - entry_point.cpp will do nicely and hey presto, you're ready to rock and roll. At this point I should add a bit of a disclaimer regarding the code I write - please don't consider it a shining example of best practice in any areas, it's simply sample code that demonstrates a number of concepts, nothing more. It's not layed out nicely or anything either, you've been warned.

Strap yourselves in, it's time to code. In this first step, we need to define an entry point for our application, from which everything else will follow. When writing a Windows application in C++, there are a number of different entry point methods that can be used. In our case, we're going to write a Windows application that may cater for Unicode support, and so we're going to use the _tWinMain entry point method. Under the covers, this generic entry point method will actually call either WinMain (non unicode support) or wWinMain (Unicode support) depending on whether the _UNICODE compiler flag has been defined.

int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{}

As you can see, this function returns data of type integer and has four parameters that are set for you when the application is loaded and started. The first parameter, hInstance is the instance handle for the current application. The next parameter, hPrevInstance will always be set to NULL in a Win32 application, and was used to identify an instance of the application already running in a 16-bit Windows application. Next up is lpCmdLine, which is a pointer to a null-terminated string containing the command line used to fire up the application. Finally you have nCmdShow, which can be one of a number of values that determines how the window itself will be shown.

Let's take a look at the contents of this function.

Silverlight 2 Book - Go Buy It!

OK, so it's finally finished. It's been a long time in the making and has consumed all of my spare time, so please go out and buy a copy. Judging by its dimensions it will make an excellent door stop, table leg prop, paper weight or of course Silverlight 2 guide.

http://www.amazon.co.uk/s/ref=nb_ss_b?url=search-alias%3Dstripbooks&field-keywords=silverlight+2+for+asp.net+developers

Get ready for some more blog posts!

Silverlight 2.0 For ASP.NET Developers

The more astute of you may have noticed that my blog has been a little 'sparse' over the past year or so. In fact, I still have a couple of half finished articles that I promised some time ago (Path Finder example using Genetic Algorithms springs to mind). The good news is I have a very good excuse for this - for about a year now I've been working on a book with some colleagues. The book is titled 'Silverlight 2.0 for ASP.NET Developers' and I think this title speaks for itself.

I'll post the link to the book as soon as I have it. It's not quite finished yet... still a lot of finishing off to do over the next couple of months, but once this is done I will finally get round to finishing the articles I started and replying to some of the queries posted (that I haven't already replied to).

Thanks for your patience : )

Composite WPF/Prism

So this week I've been involved in a workshop with the P & P team in Redmond evaluating and discussing ideas around Composite WPF and what deliverables might look like in this area. It's been very useful indeed, with some great feedback from the other delegates around what people liked/disliked about the CAB and SCSF and what was needed moving forward when building a composite application in WPF.

Key themes echo'd by all in the room were the need for a framework that was more flexible, simpler and easier to pick up and run with than the CAB and SCSF were. So a more pluggable architecture with better documentation and learning material would be great.

With this in mind, at the end of day 2 we got to look at three early spikes demonstrating the ability to swap in and out a DI Container of your choice (good work guys), an implementation of the replacement for Workspaces, called Regions, and a look at the possible replacement for the EventBroker, which provides type safety and is driven by interfaces rather than simple string topic names.

All in all I like what I've seen so far and the direction we're moving in is a good one. When the workshop is over I'll provide a full report, possibly including code samples if I can get them.

P & P Visit - Overview

During April 2007 I attended a week long workshop with the Patterns and Practices (P&P) team at Microsoft’s Corporate Headquarters in Redmond. The primary goals of the engagement were:

·         Better understand the P&P offerings and future direction

·         Ascertain the best approach to building and reusing application frameworks across an Enterprise.

·         Develop a more coherent UI strategy, considering the multiple recent offerings in this space

·         Learn from the experience of the P&P team, particularly with respect to Governance and Process

In addition to meeting the P&P team, sessions with key representatives from other groups were delivered, including:

·         Windows CardSpace with Richard Turner

·         WPF & SilverLight with Ian Ellison Taylor

·         CCF with Ming Chao

·         Project Acropolis with David Hill

During the course of the visit we discussed the origins of the P&P team, their Vision and Mission, their product offerings and how everything they engineer is ultimately customer driven.

We also discussed the problems they aim to address through the guidance they deliver and how this guidance can be delivered in many forms, from whitepapers to complete code packages and software factories. Primarily, they are targeting the common issues that face all development functions, for example:

·         Application Development takes too long

·         Mistakes are repeated and lessons relearned

·         Knowledge sharing is hard

·         Developers spend time on repetitive tasks

·         Best practices are not captured

·         There’s a lack of reuse and inconsistent approach

We also discussed how P&P specifically aim to address these issues by filling the ‘content gap’ in Microsoft’s offerings. That is, the space between the Microsoft Platform, Products and Technologies and a functionally rich, fully integrated and tested solution.

Vision and Strategy

“The world’s best guided development experience, delivered to teams building apps on the Microsoft application platform” is P&P’s vision statement. They also have a Charter: “The Microsoft source of guided development experiences for teams building app on the Microsoft Platform”.

Their strategy for delivering these is as follows:

·         Guided experiences spanning software engineering practices, development of applications and project execution patterns

·         Optimize for discoverability, evaluation and integration into the Visual Studio development environment

·         Make guidance customisable and extensible by the development teams

·         Create vibrant community of integrated guided experience developers

Portfolio 

The delivery itself takes one of four forms:

Guides consist of written guidance, either online or printed, covering topics that include patterns, application architecture, integration, performance, and security.

Application Blocks are actual deliverables that streamline development and currently include Caching, Cryptography, Data Access, Exception Handling, Logging, Policy Injection, Security, and Validation.

Process includes two Visual Studio Team System templates: MSF for Agile Software Development and MSF for CMMI Process Improvement. These process templates includes set of software development processes, practices, template documents, and associated queries, reports and project portal settings.

Software Factories are installable packages that extend Visual Studio Team System with a custom process for a specific type of deliverable supported by a set of integrated software assets.

Applications and Frameworks 

During the visit we hosted an open discussion with Edward Jezierski and Wojtek Kozaczynski on the best approach to building frameworks within the enterprise. The key questions to address were:

·         How can an Enterprise make the most of their assets through reuse?

·         Is a one-size fits all framework the best approach to take?

In order to achieve reuse across the group it is clear that teams need to collaborate in order to identify opportunities for reuse.  Further to this it also critical that a common vocabulary exists across the group.

The P&P approach to developing shared assets is to choose the most mature offering that entirely or most closely satisfies a given requirement, and to then incentivise one of the teams to deliver the full functionality required.

However, Ed And Wojtek both felt strongly that it is a mistake to start a greenfield ‘Framework’ project with the aim of satisfying all present and future requirements. It is best that these items evolve and follow an ‘Enable not Constrain’ ideology with regard to developers.

Genetic Algorithms Basics

So.. I've finally got around to blogging about Genetic Algorithms, apologies it's taken me so long. I'll kick off with a very brief tutorial around the theory behind genetic algorithms, before moving on to a concrete example showing how to solve the Path Finder problem in my next post. It's not an easy topic, but bear with me and I'll do the best I can to make sense of it for you.

So, first things first, we need to refresh our Biology knowledge regarding the theory of evolution and natural selection, as this forms the basis of Genetic Algorithms.

Evolution and Natural Selection

OK, Evolution is the term used to describe changes in a populations traits from generation to generation. These traits are encoded in segments of nucleic acid called genes, which connect together to form chromosomes. When species reproduce, their encoded traits, genes, are copied and passed on to their offspring in a process called Recombination, so for instance half of an offspring’s genes could come from one parent and half from another, the exact combination though is determined by the crossover rate. This is one way in which the traits of the next generation are determined.

Natural selection simply states that favourable traits in one population are more likely to survive and be passed onto subsequent generations. For example, a gene directly related to a predator have excellent sight would be more likely to be passed on to future generations as that predator would in theory be able to catch more prey and have a greater chance of survival (thereby living longer and reproducing more), passing it’s genes on (think ‘survival of the fittest’). As you’ll see further on in this tutorial, the concept of ‘fitness’ for an organism is absolutely critical and one of the most difficult things about Genetic Algorithms is defining and calculating the fitness for your conceptual organism.

As well as natural selection and recombination affecting the genes of subsequent generations, on occasion mutation can occur. Mutation could result in no change to the organism with regard to its fitness, it could affect it’s fitness negatively or it could have a positive effect on the fitness. Clearly a mutation that resulted in a usually four legged creature being born with three legs wouldn’t ‘stand it’ in good stead ; )

So how do we take advantage of this evolutionary process to solve problems?

One of the first things we need to do is decide upon a convention for representing possible solutions (guesses) to the problem in hand. You can represent these guesses in any way you choose, in this tutorial we will be encoding them as a binary string. These guesses will be our version of a chromosome (chain of genes). In very basic terms, here is how we will attempt to solve a problem:

1)      First off, we will need to create a starting population of random chromosomes to work with

2)      Following on from this we will take each one in turn and work out how good it is at solving our particular problem. The better the chromosome is at solving our problem, the higher a ‘fitness score’ we will give it

3)      We can then implement our version of recombination by selecting two chromosomes from the population. The fitness score directly relates to the chance of a chromosome being selected and effectively being allowed to reproduce in our program. There are different methods of selection that can be used in Genetic Algorithms (Roulette Wheel, Tournament and Elitism), we will use Roulette Wheel selection

4)      We then need to work out how the offspring chromosome will be made up from both parent chromosomes. This process is called crossover

5)      Evaluate the chromosome genes for mutation

6)      Repeat as necessary to create a population of the right size

Making any sense? I tend to find that the entire process only really starts to make some sense when the scheme used to encode a potential solution as a chromosome has been explained, as well as how to evaluate a chromosomes ‘fitness’ rating. So hang on in there for a short while yet J

In the process listed above, step 3 mentions the selection process for deciding which two chromosomes (remember these are our guesses) will get the chance to create offspring. The selection methodology we are going to use is Roulette wheel selection. The easiest way to imagine this method is to picture a pie chart in your head. Now... with that in mind, assign each chromosome a slice of the chart..... BUT.... the chromosomes with the higher fitness score will receive a larger slice of the pie chart than those with a lower fitness score. This will result in the higher scoring chromosomes having an increased, but not definite chance of being able to ‘reproduce’.

Now comes the interesting part.... how do the genes within each parent chromosome make up the genes in the offspring chromosome? Two things in our simulation will affect how this is made up, the Crossover and Mutation rate. More imagery will help illustrate this point. Consider the following two chromosomes in a hypothetical population that have been ‘selected’ to reproduce.

0011010001001100

0100101010101001

First off, we need to decide if the two chromosomes will ‘swap’ their bits. We use a constant factor to decide this, a good starting point being 0.6 or 0.7. If the decision is to swap,  we select a random point within the string of bits, let’s say 12, and then swap all the bits that follow. So, the chromosomes above will become:

0011010001001001

0100101010101100

We then evaluate the chromosomes to see if mutation needs to be applied to each bit in the chromosomes, the chance of this happening should be set to something very low as mutation should be a rare event.

And... that's the bones of it. I'll put together some source code that illustrates this in action and publish it asap. If anyone has any idea for applying this let me know and we can put something together if it's interesting.

P & P Workshop, Redmond

Hi all, I write this blog post from the comforts of the SAS lounge in Copenhagen airport, whilst I wait for my connecting flight to Seattle. The joys of a long haul flight await, let’s hope Alastair Reynolds book “Absolution Gap” keeps me occupied.

So... this post is just to set the scene for the workshop I’m running with the Patterns & Practices team in Redmond this coming week. Four days looking at the entire P & P estate in detail with a client, as well as in depth talks regarding CCF, WPF/e, CardSpace and Acropolis.

Throughout the four days I’ll keep this post updated with any points of interest, and perhaps a few photo’s also to break up the monotony of text. I’m particularly looking forward to some good debate around enterprise frameworks, the pros and cons of, if you have any thoughts you’d like to share please do so via the comments section. In particular, any experiences of putting together a framework for an Enterprise would be of interest. Was it successful? Was it overkill? Has it been reused by many applications?

Below is an example of some of the material we’ll be covering in the next four days. Specific updates will be provided asap after the event.

·         Web/Smart Client Software Factories, including Vision and Roadmap

·         AJAX within the Application Blocks

·         Enterprise Frameworks – General Discussion

·         Web Service Factory

·         Identity Platform

·         Workflow

·         CCF

·         WPF

Genetic Algorithms

I have seen a great example of solving the path finder problem with a genetic algorithm.... I'll modify it, write about it and put it on here by mid january.... promise!

Merry Xmas by the way

Customer Care Framework

I've been in Redmond all week checking out CCF with the product group. Some of my clients are looking at utilising its features and so I'm busy getting the lowdown on the CCF roadmap etc.

Not many people tend to have heard about it and its capabilities and so expect a blog post imminently with more information and perhaps some technical samples.

Oh and I won't forget to write a quick post about interop performance, honest! In point of fact, I'm still trying to get round to writing some game dev content for you. The best things come to those who wait right?!

.NET Interop - Freeing unmanaged memory

OK. Imagine you need to call an unmanaged function. Now imagine this function returns you a pointer to a block of unmanaged memory that it's allocated. The runtime will clear this up for you right? Wrong. Well, wrong a lot of the time anyway.

The runtime always attempts to free unmanaged memory using the COM method - CoTaskMemAlloc. So let's say we have a function that returns a pointer to unmanaged memory that we're going to marshal directly as a .NET type -  System.String. Once the System.String object has been created (the runtime uses a copy of the unmanaged data to build this), the runtime will attempt to clean up the unmanaged data with a call to CoTaskMemFree. This is all well and good providing the memory was allocated with CoTaskMemAlloc. If it wasn't though, you'll end up with a memory leak.

Luckily, the solution is simple. The only tricky item is finding out which method the function used to allocated the memory. If you find out the C runtime was used, you can pass the data back as an IntPtr and then pass this IntPtr to an unmanaged function you've written to be cleaned up properly. (You could of course re write the original unmanaged function to use CoTaskMemAlloc, but I'm assuming in most cases this isn't possible). Let's take a look at a very simple example.

Our unmanaged function allocates memory for a Unicode string and returns a pointer to this memory to us:

extern "C" __declspec(dllexport) wchar_t* GetString(const wchar_t* inString);

wchar_t* GetString(const wchar_t* inString)
{
    wchar_t* retValue = new wchar_t[wcslen(inString) + 1];
    wcscpy(retValue, inString);
    return retValue;
}

Now, when we write our DllImport statement to expose this function to our managed code, we might be tempted to simply cast the return value directly as System.String. However, this will leave us unable to clean up the unmanaged memory allocated above. Instead, we need to cast it as an IntPtr, which we can then pass to an unmanaged function written specifically to clean memory for us.

[DllImport("YourDLL", CharSet=CharSet.Unicode)]
public static extern IntPtr GetString(string inString);

Our unmanaged helper function for freeing memory might look like this:

extern "C" __declspec(dllexport) void FreeMemory(void* memToFree);

Leaving us with the small job of adding a DllImport statement for it (I'm sure you can manage this part yourselves - email me if you can't!) and then using it in code: 

IntPtr pUnmanagedMemory = NativeMethods.GetString("123456789");
string theString = Marshal.PtrToStringUni(pUnmanagedMemory);
Console.WriteLine(theString);
NativeMethods.FreeMemory(pUnmanagedMemory);

Note the Marshal.PtrToStringUni method. There are a variety of these PtrTo* methods for just such occasions as this. Of course (as in all my examples) you'd probably want to wrap the interop calls in try/catch blocks and place your cleanup code in the finally.

Enjoy!

Dynamically calling an unmanaged dll from .NET (C#)

This sample is in response to a question left on my previous post, namely how to call an unmanaged dll from managed code when the dll in question isn't known until runtime (for instance, the path is stored in the registry, or an xml file, etc etc).

Apologies if this sample seems a little hurried, but I have another presentation to write and so time is short!

So let's begin.

To start and to refresh our memories, let's create a very basic C++ dll that does very little..... your code should resemble the following (check out my previous post for more info on this):

Header file

extern "C" __declspec(dllexport) int MultiplyByTen(int numberToMultiply);

Source code file

#include "DynamicDLLToCall.h"

int MultiplyByTen(int numberToMultiply)
{
        int returnValue = numberToMultiply * 10;
        return returnValue;
} 

As you can probably infer from the function name, an int is passed into this function and it will return the number passed in multiplied by ten. Told you it would be simple.

Now comes the more interesting part, actually calling this dll dynamically from your C# source code. There are two Win32 functions that are going to help us do this:

1) LoadLibrary - returns a handle to the dll in question
2) GetProcAddress - obtain the address of an exported function within the previously loaded dll

The rest is rather simple. We use LoadLibrary and GetProcAddress to get the address of the function within the dll we want to call, and then we use the GetDelegateForFunctionPointer static method within the Marshal class to assign this address to a C# delegate that we define. Take a look at the following C# code:

Calling an unmanaged dll from .NET (C#)

OK, so this first example is going to show how to call an unmanaged dll from .NET (C#). There's no better way to explain how it all fits together than by example, so first off we're going to create an unmanaged dll in C++. The function we're exporting from the dll would obviously be of vital importance to your business in the real world and contain a wealth of logic, but for the sake of simplicity let's have a void function that takes a basic struct as an argument and does nothing more than alter the fields within it.

The header file in your project should contain the following definitions:

struct MyStruct
{
      int       SomeId;
      double SomePrice;
};

extern "C" __declspec(dllexport) void PassStructIn(MyStruct* myStruct);

OK, I'm hoping the struct decleration doesn't need any explanation, we're simply defining a structure that contains two fields, one of type int and one of type double.

Our function definition is a little more complicated however, so let's start from left to right and work our way through it.

In C++, because functions can be overloaded (differing not by name but by signature [mixture of name and parameters]) the compiler goes through a process of 'decorating' the names internally so it can uniquely identify them when they're called. To simplify this example, we want to use the function name as we've written it from within our C# code and not a mangled representation. Using extern "C" forces the compiler to use the actual function name (as it would in C). This prevents us from overloading this function but we're not bothered about that in this example.

On a related note, if you want to examine a dll to find out, amongst other things, exported function names, you can use the dumpbin command from the Visual Studio command prompt. Typing dumpin /exports filename will list the exported function names from the dll. Try it on our simple dll with and without the extern "C" keywords to see the decoration in action.

__declspec(dllexport) puts the plumbing in place that's actually going to allow our function to be exported from our dll. It adds the export directive to the object file so we don't need to bother around with a .def file.

void PassStructIn(MyStruct* myStruct); OK, so our function is void (doesn't return anything), is named PassStructIn and takes a single argument of type pointer-to MyStruct.

The actual function definition in the source file should look something like this:

COMing up..!

I've been asked by one of my clients to run a workshop that goes through .NET and COM interop, a subject I've done a fair amount of work on in the past. It's an interesting topic (at least I think so ; ) and as such I'm going to put excerpts on here for your viewing pleasure.

Hopefully by the end of today I'll have the first sample to post, basically showing how to call an unmanaged dll written in C++ from .NET. Then at some point later in the week I'll put one up showing how to call an unmanaged dll dynamically. See you then.

Welcome to my blog!

Hi there and welcome to my blog, admittedly sparse at present... Over the course of the next few months this blog will grow to include all manner of coding bits and pieces, ranging from Artificial Intelligence to Web Services.  Exciting huh?
Recently I've been spending a lot of my spare time looking into DirectX and games programming, so i've a feeling one of my first posts will be something to do with that, either in terms of rendering something cool using DirectX or looking at a Path-Finding or Collision-Detection algorithm.
Soooo... until then, check back often and hopefully something cool will appear!