No longer updated: new and updated blog (including old content) at

Archive for, please update your bookmarks

Article updated and moved! (A* 3D)

Posted by Roy Triesscheijn on Monday 29 June, 2009

Because there where some serious issues with the first code I decided to take it offline and do some more research before posting it again.

Recently I’ve updated this code to a now good working and extremely fast piece of code which is well documented and has an interesting article about the speed optimizations. This page just serves for people who got linked here to get redirected to the new article.

You can find the new article here

(note: I’ve removed comments from this page but I’ve thanked everyone thoroughly at the new article)


Posted in Blog, General Gamedesign, XNA | Tagged: | Leave a Comment »

Upcomming A* pathfinding in 2D and 3D code updated

Posted by Roy Triesscheijn on Monday 29 June, 2009

So allot of people have commented on my A* tutorial I posted here a while ago, but they’ve also pointed out a few flaws in the design so I’ve been working on a new version.

The new version also incorperates 2D AND 3D worlds so you can use this class for both, I’ve also optimized a bunch, made everything allot more clear replaced those dodgy ints with nice structs and fixed an unseen bug.

I hope to be able to get it online tomorrow, there’s just to much to polish atm to post it right now, but I’ll keep you guys updated!

Posted in General Gamedesign, XNA | Tagged: , , , , , , | Leave a Comment »

Sending objects via high speed asynchronous sockets in C# (Serialization + Socket programming)

Posted by Roy Triesscheijn on Sunday 31 May, 2009

Note: since the 1st of December 2009, this blog was moved to, all content here should be considered archived, new content, updates, comments, etc… will no longer be released here. A fresh copy of this article exists at the new website, here you can post comments and ask questions which I will try to answer asap.


Roy Triesscheijn

Well a while has past since my last useful post here, but here I am at it again a post filled with usefull source code to use in your everyday C# programs.

I was very curious how games work with async sockets to keep everyone communicating smoothly so I set up a simple test app to test async sockets in C#, however this seemed quite a bit harder than I thought and after some help at the Dutch website I finally had everything working. (I finally figured out that I shouldn’t be using the beginsendpacket but the beginsend methods). Anyway let’s get straight to business.

I first made a small object that we want to send over the network, let’s call it Status, below is the source code for that object, let’s make a couple of stuff clear.

    public class Status
        public Socket Socket;
        public List<byte> TransmissionBuffer = new List<byte>();
        public byte[] buffer = new byte[1024];

        public string msg;     //the only thing we really send.

//Usually you shouldn't but these 2 methods in your class because they don't operate specifically on this object
//and we would get allot of duplicate code if we would put those 2 methods in each class we would like to
//be able to send but to not wind up having to write a couple of utility classes (where these should reside)
// I let them reside here for now.
        public byte[] Serialize()
            BinaryFormatter bin = new BinaryFormatter();
            MemoryStream mem = new MemoryStream();
            bin.Serialize(mem, this);
            return mem.GetBuffer();

        public Status DeSerialize()
            byte[] dataBuffer = TransmissionBuffer.ToArray();
            BinaryFormatter bin = new BinaryFormatter();
            MemoryStream mem = new MemoryStream();
            mem.Write(dataBuffer,0, dataBuffer.Length);
            mem.Seek(0, 0);
            return (Status)bin.Deserialize(mem);

As you can see the class is marked serializable with [Serializable] this signals the compiler that we should be able to serialize this object. (Get it from memory, place it in a byte array and send it anywhere (harddrive/network/etc..). Stuff that shouldn’t be send with it like external classes that we would like to send later should be marked [NonSerialized] (the Java equivalent for transient). This way we can cut of some dependencies and keep the overhead low. (For example no matter what the TransmissionBuffer referenced to, because it’s nonserialized it’s reference will not be send aswell and it will appear on the other side as “null”.

As you can see the only real data this object hold is a small string called msg the other objects are for administrative purposes as we will see soon.

Now there are allot of examples out there that show how to send a string, you can easily get the bytearray from a string and send it anywhere, for an object that is slightly harder, as you can see in the serialize() method we have to create a binarrayformatter, this binarray formatter is then fed a direct stream to the memory where our object resides and a reference to our memorystream, the object is serialized in our memorystream’s buffer as a bytearray and then we can do anything we want with it. This method just returns the buffer so we can set it over a network. The deserialize method does exactly the same but then the other way arround except for the mem.Seek(0,0); we see right before return, this seek sets the pointer of the stream at the start of the stream so the binarrayFormatter can start reading and deserializing from the start of the stream. (Forgetting this would give an error telling that the end of the stream was found before deserialzing was completed, which makes sence if you think about it).

Anyway before we get to the real workhorse of the code let’s take a look at the client.

public class Client
ManualResetEvent allDone = new ManualResetEvent(false);

/// Starts the client and attempts to send an object to the server
public void Start()
while (true)
Console.Out.WriteLine("Waiting for connection...");
Socket sender = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);
sender.BeginConnect(new IPEndPoint(IPAddress.Loopback, 1440), Connect, sender);
allDone.WaitOne(); //halts this thread until the connection is accepted

/// Starts when the connection was accepted by the remote hosts and prepares to send data
public void Connect(IAsyncResult result)
Status status = new Status();
status.Socket = (Socket)result.AsyncState;
status.msg = "Hello webs";
byte[] buffer = status.Serialize(); //fills the buffer with data
status.Socket.BeginSend(buffer, 0, buffer.Length, SocketFlags.None, Send, status);

/// Ends sending the data, waits for a readline until the thread quits
public void Send(IAsyncResult result)
Status status = (Status)result.AsyncState;
int size = status.Socket.EndSend(result);
Console.Out.WriteLine("Send data: " + size + " bytes.");
allDone.Set(); //signals thread to continue so it sends another message

Don’t mind the manualreset events to much, they’re there so the application doesn’t go to fast so we can see what happens instead of 2 console windows just printing text like mad :). (Remember that they will send as fast as possible because they are asynchronous and don’t have to wait for the first send to complete so yeah some pause points are quite handy for now, in a real client you wouldn’t use while(true) but something more sophisticated like an update interval or when something changed.

As you can see the start method creates a socket and tries to send some data nothing super special here except for that the beginconnect method references the connect method. When the server is ready for a connection the connect method is executed, we create a new status object and place the socket we get returned from the endAccept method in there for bookkeeping (we need it later to send data else we don’t know which socket we where using, this is also why the socket is [unserialized] we don’t need to send it the other way). We also fill the msg of the object and then serialize it to a byte array, we place that bytearray in the beginsend method.

When the server is ready for receiving data the Send method is called. This method uses the socket in the packet to call endsend and read how many bytes where send.

And now, the server!

public class Server
ManualResetEvent allDone = new ManualResetEvent(false);

/// Starts a server that listens to connections
public void Start()
Socket listener = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);
listener.Bind(new IPEndPoint(IPAddress.Loopback, 1440));
while (true)
Console.Out.WriteLine("Waiting for connection...");
listener.BeginAccept(Accept, listener);
allDone.WaitOne(); //halts this thread

/// Starts when an incomming connection was requested
public void Accept(IAsyncResult result)
Console.Out.WriteLine("Connection received");
Status status = new Status();
status.Socket = ((Socket)result.AsyncState).EndAccept(result);
status.Socket.BeginReceive(status.buffer, 0, status.buffer.Length, SocketFlags.None, Receive, status);

/// Receives the data, puts it in a buffer and checks if we need to receive again.
public void Receive(IAsyncResult result)
Status status = (Status)result.AsyncState;
int read = status.Socket.EndReceive(result);
if (read &gt; 0)
for (int i = 0; i &lt; read; i++)

//we need to read again if this is true
if (read == status.buffer.Length)
status.Socket.BeginReceive(status.buffer, 0, status.buffer.Length, SocketFlags.None, Receive, status);
Console.Out.WriteLine("Past niet!");

/// Deserializes and outputs the received object
public void Done(Status status)
Console.Out.WriteLine("Received: " + status.msg);
Status send = status.DeSerialize();
allDone.Set(); //signals thread to continue
//So it jumps back to the first while loop and starts waiting for a connection again.

Well start and accept basically do the same as the client but then the other way around, the only big difference we have is the receive method which endreceives() the data, but it’s not done yet, first it has to check if all the bytes where received if not we have to put the object in a listening state again to get the rest of the bytes from the networkcard. Then when all the bytes are safely inside our Transmissionbuffer we deserialize our object and print the msg we place in it.

Allot of work to just send a string accros, but this code will work any object and make your server nonblocking which could make it much faster, just instead of putting “string msg” in your status object put “TheObjectYouWant obj” in your status object and you are free todo as you please.

Feel free to ask questions and comments, the full sourcecode is available here: AsyncSocketServer+Client.rar

Posted in Blog, General Coding | Tagged: , , , , , , | 14 Comments »


Posted by Roy Triesscheijn on Thursday 23 April, 2009

Recently I’ve opened a new website: at this website you can hire me for freelance programming work. Prices are very low (only 18,50 Euros per hour, no extra costs, pay when it’s done, and only if it’s done properly). Feel free to negotiate for lower or fixed prices if you have an interesting project that you wan’t me to do.

Dutch people can just click that shiny link. And for people who don’t speak Dutch, feel free to check the (limited) English portion of the website or e-mail to .

People can pay via PayPal or by wiring money to the bank.

I hope I can help allot of you people with interesting projects, If you’ve read this blog you’ll probably know what technologies I’m using but let me list the most important ones quickly here:

• C# and XNA
• VBA (Visual Basic for Applications)
• Visual Basic 6
• MS Access
• MS SQL Server

I’m also adding a donate button to my website, feel free to dontate a small sum of money (really anything is welcome) if one of my tutorials made your life easier or saved you allot of time.



Update: the donation link is in the link categorie at the top right of the page, or you can just click here at the paypal button.
PayPal Donate!

Posted in Blog | 3 Comments »

Configuring Cygwin C/C++ compiler for Netbeans 6.5 (under Windows)

Posted by Roy Triesscheijn on Friday 20 March, 2009

Note: since the 1st of December 2009, this blog was moved to, all content here should be considered archived, new content, updates, comments, etc… will no longer be released here. A fresh copy of this article exists at the new website, here you can post comments and ask questions which I will try to answer asap.


Roy Triesscheijn

Today I tried setting up Netbeans as a C IDE, it has built in support for C, but unfortunately enough you have to manually configure a compiler so that you can actually debug / build your C/C++ programs.

Fortunately there is this helpful page at to help you install Cygwin, a very popular UNIX/Windows C/C++ compiler. However, this helpful page isn’t as helpful as I’d hope at all! It will point you in the right direction to download Cygwin, and will tell you what packages to select for download, it will even tell you to set up your PATH environment variable for Cygwin, but it will assume Netbeans auto detects the correct settings, which it unfortunately doesn’t do. (Well at least at my pc, and I’ve seen a few threads with the same problems around).

So here is my attempt at a more complete overview on installing Cygwin for Netbeans 6.5.

Go to and download the small setup program. Run it (if your using Vista, set the compatibility options to XP SP2, and run it as administrator). Follow the pretty standard steps until you get to choose the installation packages. If you thought just pressing next would install the most common Cygwin apps, like the compiler (gcc.exe) and the make implementation, unfortunately Cygwin, is not just a C/C++ compiler, it even includes a java compiler, games, documentation, text editors etc. . Ok so just install everything, well that will install the compiler etc., but also 3GB of (for us) useless data. So don’t make the same mistake I did there. We are going to search for the few packages that we actually need. According to the these are:

select gcc-core: C compiler, gcc-g++: C++ compiler, gdb: The GNU Debugger, and make: the GNU version of the ‘make’ utility.

Unfortunately these aren’t easy to find. For example there is no core package directly visible (we do have base and development though).  It took me a while but I think I’ve nailed it down. Select the following packages by clicking the weird “refresh” icon next to them until it says install:

-The entire base package
-In the development package select:
–gcc core
–gcc g++
–gcc g77
–gcc mingw core
–gcc mingw g++
–gcc mingw g77
–mingw runtime

(note I’m not sure about the mingw packages, this seems to be a seperate C compiler but it doesn’t seem to harm)

After that go to windows configuration screen->advanced->environment variables. And add “C:\Cygwin\Bin” to the PATH variables (or wherever you have located your Cygwin\bin folder, (make sure to separate it from the last one with a ‘;’).

Start Netbeans, navigate to tools->options->C/C++. Check to see if Cygwin is in the list on the left panel. Select it, and then fill in the options as following: (I assume that you’ve installed it in C:\Cygwin)

Base Director: C:\Cygwin\bin
C compiler C:\Cygwin\bin\gcc.exe
C++ Compiler: C:\Cygwin\bin\g++-3.exe*
Fortran Compiler: C:\Cygwin\bin\g77-3.exe*
Make Command: C:\Cygwin\bin\make.exe
Debugger: C:\Cygwin\bin\gdb.exe

(* marks optional)

Now make a new C project. And add a new main file to it by right clicking the source directory and selecting New->Main C file. There is an odd chance that the include directives will be underlined with red. This is not a problem, as you will see the program will compile and run fine, but you can’t use intellisense this way so we are going to fix it. (First make sure your PATH variable was correctly set!).

Right click on your project and select properties. Go to build->C compiler (or C++ compiler if you are doing C++).  Select the “…” button after Include Directories. And add the “C:\Cygwin\usr\include” directory to the include directories. Save your settings and reload your project. The red lines should’ve disappeared now, leaving you behind with a fully functional C/C++ IDE and compiler in Netbeans. *Yay*!


(I wish someone else would’ve written this before me, so that I wasn’t busy uninstalling a couple of gigabytes of C/C++ tools/compilers/utilities/fonts and text editors!)

Posted in Blog, General Coding | Tagged: , , , , | 161 Comments »

Fun with stored procedures: insert only if unique. (Transact-SQL/MS SQL)

Posted by Roy Triesscheijn on Tuesday 10 March, 2009

As I’ve said in my previous post stored procedures are allot more powerful than I thought. And really have their own scripting (compiled scripts that is) access to the database.

Stored procedures are often used to enhance the speed of queries that are performed very often, however modern database systems nowadays track queries and store/compile queries that are performed allot of times. So what are the modern day uses for stored procedures?

Stored procedures:

-Save roundtrips  (if you want to do a query based on the result of another query, you can compact those two queries in one).

-Can batch work (if you always do 2 queries at the same time you can call them in only one trip to the database).

-Are Save (in most modern database systems stored procedures are called using parameterized queries or special objects that already wrap/escape dangerous user input).

Can put extra constrains on data (first check if some other value in the database is not interfering with the soon to be executed query)

Can synchronize across multiple applications (stored procedures can lock fields/rows/columns/tables for a short amount of time for better concurrency support)

Today I’m going to show a very simple stored procedure written in Transact SQL Microsoft and Sybase’s proprietary SQL dialect, and C# that hopefully demonstrates all except for the last of the previous points.

First I’ve created a small class that represents a user. The class has the following standard props:

public String UserName { get; set; }
public String FirstName { get; set; }
public String LastName { get; set; }
public String Email { get; set; }

And a special prop that handles password hashing (never save a password as plain text in a database, always save a hash) (note: be sure to add a using directive for System.Security.Cryptography;)

public String Password
 return passwordHashed;
 UTF8Encoding encoder = new UTF8Encoding();
 MD5CryptoServiceProvider hasher = new MD5CryptoServiceProvider();
 passwordHashed = encoder.GetString(hasher.ComputeHash(encoder.GetBytes(value)));
 private string passwordHashed = "";

Now start up SQL Server Management Studio (Express/Basic) and navigate to your database, then select the folder programmability->stored procedures and right click to insert a new stored procedure. (Also make a user table if you haven’t got a table yet where you want to try this out on, I’m using a simple table with all the values as nvarchar(50)’s and the id as an int.)

Normally before you insert a user you first verify that the input is legit (a valid email address, strong enough passwords and a username exceeding some minimal length). That can all be handled client and server side using .Net’s validation controls.  Once you’ve done that you would query the database if the username and email address already exist. If not you would run another query (insert) to input the actual data.  Because when inserting a user you will always have to do the ‘check if exists’ query first, and inserting users might be a common task, there is room for improvement here.

I’ve done that using the following stored procedure:

Note: when multiple pages/threads call this sp it might suffer from race conditions, for more information about race conditions see the comments section. (Especially the first comment by Alister).

@Username nvarchar(50),
@Password nvarchar(50),
@LastName nvarchar(50),
@FirstName nvarchar(50),
@Email nvarchar(50),
@UserID int OUTPUT
IF NOT EXISTS(SELECT Username FROM Users WHERE Username=@Username OR Email=@Email)
 (Username, Password, LastName, FirstName, Email)
 VALUES (@Username, @Password, @LastName, @FirstName, @Email)
 SET @UserID = -1

Be sure to execute this procedure to insert and compile the actual stored procedure.

As you can see this stored procedure has 5 inputs (Username etc..)  and one output: the UserID.  The syntax is pretty simple. First an internal (thus fast) query is performed to check if there exists a record that either has a username same as the input username or an email address same as the input email address. If this is not the case the actual work begins and we do a normal insert query. At the end of the query the UserID output value is set to either the identifier of the inserted record or –1 if there was no record inserted.

This procedure saves a round trip to the database, batches work, put’s extra constrains (and validation) on the data in the database and is safe (as we will see shortly after)

To use this fine stored procedure we will have to create a special form of a parameterized query in C# that looks like this:

int newID;
 SqlConnection connection = new SqlConnection(connectionString);
 SqlCommand command = new SqlCommand("InsertUniqueUser", connection);
 command.CommandType = System.Data.CommandType.StoredProcedure;
 command.Parameters.Add(new SqlParameter("@Username", System.Data.SqlDbType.NVarChar, 50));
 command.Parameters["@Username"].Value = user.UserName;
 command.Parameters.Add(new SqlParameter("@Password", System.Data.SqlDbType.NVarChar, 50));
 command.Parameters["@Password"].Value = user.Password;
 command.Parameters.Add(new SqlParameter("@LastName", System.Data.SqlDbType.NVarChar, 50));
 command.Parameters["@LastName"].Value = user.LastName;
 command.Parameters.Add(new SqlParameter("@FirstName", System.Data.SqlDbType.NVarChar, 50));
 command.Parameters["@FirstName"].Value = user.FirstName;
 command.Parameters.Add(new SqlParameter("@Email", System.Data.SqlDbType.NVarChar, 50));
 command.Parameters["@Email"].Value = user.Email;
 command.Parameters.Add(new SqlParameter("@UserID", System.Data.SqlDbType.Int, 4));
 command.Parameters["@UserID"].Direction = System.Data.ParameterDirection.Output;

 newID = (int)command.Parameters["@UserID"].Value;
 catch (Exception ex)
 //trace error
 string log = ex.Message;
 return newID;

As you can see we are building a pritty normal stored procedure. be sure to System.Data.SqlDbType values for the SqlParameters. Also note that in the last line before the try we set the Direction of the “@UserID” parameter to Output. This way the stored procedure can store data in UserID.

If you build a small webpage/winforms app around this you will see that the newID returned is the ID value of the the newly inserted record in the database if there where no duplicates, or that the newID was –1 and that there haven’t been made new records.

Posted in Blog, Databases | Tagged: , , , , , , | 10 Comments »

Book review: Pro ASP.NET 3.5 in C# 2008 and my reasons for reading it!

Posted by Roy Triesscheijn on Tuesday 10 March, 2009

Well instead of studying I’ve lately become obsessed with ASP.Net and started reading the book named in the title! Although the book is written by a different author than the Pro C# 2008 and the .Net 3.5 Framework, the style is quite similar, and the quality is very high! I’m one of those weird freaks who tries to read books like these from the beginning to end as to learn all the tips and tricks contained in those 1500 pages.

I’m a bit surprised by the ordering of the chapters, of course allot of pages are dedicated to the ever important techniques for the DAL (data access layer). I’m a bit struck that authentication, security and log-ins/profiles are pushed back to the end of the book and complicated techniques like caching are in the first third of the book. (Btw I really love how ASP.Net makes caching easy!).

The authors explain everything brilliantly simple and there are allot of code examples (and a big plus here is that each code sample really provides you with a new technique or thought pattern, where the Pro C# book would some times have useless code examples). I’m also pretty sure that after reading this book you know how to write a good webpage. Many best practices are explained (in code and text) and each new technique starts with an overview of how was it done before. Of course every (new) technique has drawbacks or scenarios where it’s not the best tool for the job. Matthew MacDonald and Maria Szpuszta save you the time of weighting each technique by providing nice tables with pro’s and cons.


Anyway (not sure if I’ve told this in my Umbraco rant), I’ve started becoming interested in ASP.NET because Argeweb, in cooperation with Microsoft, provides all Dutch students entitled to SurfSpot a free .nl domain name and adequate Windows Server 2008 hosting (IIS7, ASP.NET.3.5, SQL Server 2005 and even PHP and MySQL support). So I’ve registered a nice domain name and started to joke around.

I sure hope I can show you guys something soon!

5 out of 5 stars 🙂

Oh did I mention they also give a pretty thorough explanation of stored procedures, damn I had no idea you could do so much in DB code. The follow up to this article is a small stored procedure sample for inserting users only if they have a unique username and e-mail address without additional round trips.

Posted in Blog, Webdesign | Tagged: , , , , , , | 1 Comment »

The horrors of Umbraco 4.0.0

Posted by Roy Triesscheijn on Thursday 5 March, 2009

Examining the title of this blog entry will reveal two things:

  • I tried to install the CMS Umbraco 4.0.0 (check it out here )
  • I wasn’t successful

Lately I’ve gained access to a ASP.Net 3.5 shared hosting solution provided by and sponsored by Microsoft via Surfspot (a kind of dreamspark for Dutch students, not only for Microsoft products).

Alright it all seemed great. Windows Server 2008, IIS7, ASP.Net 3.5. All very much up to date technologies.

I  was first thinking about building my own CMS in ASP.Net/C#. But as you might know that is quite allot of work. So I went searching for a free .Net based CMS to start with, that I could later extend.

Quickly I found Umbraco, and after trying the demo site I was sold. The used techniques seemed solid, adding new features seemed easy, the source code was freely available and everything was written in ASP.Net 2.0.

I was sure installing it would be a breeze. I created a new database at my management panel at Argeweb and started uploading Umbraco to my websites root folder.

Quickly I encountered quite a few problems with the Web.config file that Umbraco provided. Apparently the Web.config file wasn’t compatible with IIS7’s default application pool, and since my hosting is shared I can’t change IIS’s settings. After allot of testing/googling I finally found 3 tweaks to make this config file work, but quickly NullReference and PermissionDenied exceptions where thrown.

After spending allot of time on the Umbraco forums I found out about a better config file that was IIS7 /ASP.Net3.5 compatible and installed it. All I now got was a permission exception. This seemed to be common in Medium Trust environments and I could simply delete the accused file. I also spoke to Argeweb and the agreed to check out the permissions. A few hours later they mailed that the permissions should be good enough for Umbraco. And they told me that Umbraco 3 was running on their shared host solutions. Of course I wanted Umbraco 4!

After allot more fiddling I finally got the installation screen to show up. I quickly accepted the licence and input my database settings.  A new error occurred stating that Umbraco couldn’t change the Web.config file (if it could that would be one hell of a security problem!) and that I had to change the connection string manually.  I quickly did so and restarted the installation. In the database step all fields where already filled in with the settings I put in the Web.config file, but it still wouldn’t let me pass because it couldn’t save my settings again!

After some searching I found a modified version of the database step *.asx file uploaded it and I could finally choose install.

Umbraco would install fine into my database (so the settings where correct). Great I thought! Now I should be getting somewhere. However the next step I had to change my admin password, ok great, Umbraco has DB access so this couldn’t possibly be a problem. Of course after pressing OK I was proved wrong, and another error occurred. This time in one of the role providers. Unfortunately I still haven’t found a way to work around this. I even edited the Web.Config file to think that the installation was done (yes this too was in the Web.config file and thus totally un-settable for Umbraco). But all I got was a redirect stating that my nodes are empty and that I should add a page. A fancy “start Umbraco” button was provided, but unfortunately this button did absolutely nothing…

After spending two days I still haven’t been able to install Umbraco. In the forums not even the developers know what permissions Umbraco exactly needs and they just state “Full Trust will do the trick.” or “Better change hosts.” But I don’t want to change hosts! Argeweb was very helpful and did all they could to get this working, and I understand that they wont elevate my account to Full Trust, which is quite a security hole.

I wasn’t the only one with all these problems, the forums are swarmed with it, and frankly it seems impossible to install Umbraco at a server you don’t control directly. (I tried to install in the root folder, which gave me all these problems. Installing Umbraco in a nice virtual folder like would cause even more problems according to some users (and probably the end of the world as we know it).

To bad that Umbraco is the only real free solution that had the features that I wanted. At the moment it seems that I’m going to delve into ASP a bit more and see if I can come up with a very very very very very simple CMS.


I hope some one out there has more luck with Umbraco than me, it really seems to be awesome technology!



(if you even dare to try to reinstall Umbraco you’ll get a nice NullReferenceException)

Posted in Webdesign | Tagged: , , , , , | 15 Comments »

Implementing A* path finding in C# (and XNA): source-code (can we cut the corner?)

Posted by Roy Triesscheijn on Tuesday 24 February, 2009

Note: since the 1st of December 2009, this blog was moved to, all content here should be considered archived, new content, updates, comments, etc… will no longer be released here. A fresh copy of this article exists at the new website, here you can post comments and ask questions which I will try to answer asap. I also wrote a new version of my A* implementation here: which is greatly superior and faster than this version.


Roy Triesscheijn

Update: there is a new fully 2D and 3D version of this article now available that fixes many issues some of you where having, and having a much faster and more readable codebase, get it here!

Please excuse my grammar in my last post, I was quite tired and well, let’s not talk about it anymore 🙂 .

Anyway, as I’ve said I’ve been working on an A* path finding algorithm in C# for one of my XNA projects. I’ve cleaned up the garbage and refactored the algorithm into one nice .cs file (2classes)

Today I will give a short explanation of the A* path finding algorithm and my implementation of it, specifically the extra point about cutting corners. You can download the source code at the end of this article. The source-code can be used in any C# project, and doesn’t use specific XNA classes. (All it really uses are Point’s, generic Lists and a couple of ints and bools).

Note: For more in depth information check out the following links*_search_algorithm’s_algorithm (A* is an extension on Dijkstra’s algorithm. (You could view Dijkstra’s algorithm as A* where H is always 0, more about H later))

Note 2: I will use the terms square and node interchangeable in this article because in my A* implementation my nodes are square, however you can use A* for any kind of shapes for the node, and my code is easily adjustable to accommodate that.

A* generally works the following way  (source: Patrick Lester from )

1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

c) For each of the 8 squares adjacent to this current square …

– If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.

– If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.

– If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you:

Add the target square to the closed list, in which case the path has been found (see note below), or

Fail to find the target square, and the open list is empty. In this case, there is no path.

3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

The costs F which is  G+H might not be evident at first. But is calculated the following way:

G is the movement cost from the start point to that square, and H is the estimated cost from there to the end square.

G is calculated as  TargetSquare.G =  parent.G + 10  or + 14 if the square is diagonal from the parent. (That’s because the square root of 2 is 1.4 and we try to keep the numbers integers here)

H is calculated (in my implementation) as the Manhattan distance from the target to the end.  Which is something like (Math.Abs(G.x – H.x) + Math.Abs(G.y – H.y) ) * 10.

The algorithm keeps checking of squares that are on the open list can be reached cheaper from the current square.

Corner Cutting.

Now about the corner cutting: my implementation adds one new situation before the first point of 2.C.

-If the node is diagonal from the current node check if we can cut the corners of the 2 others nodes we will cross. If so this square is walkable, else it isn’t.

A picture might explain better why this is important:


square A is our current square and we are considering if we can walk 2 square B. Square B’s walkable attribute is set to true, so we might think that we can continue to (now point 2) in c, adding it to the open list etc… However if the object that is going to walk the path is going to get to B, a part of it will be at with red indicated areas of squares C and D.  Imagine square D represents a house, that exactly fills the square, this way our object is going to traverse trough a house! However if squares C and D represents a well, centred in a square filled with grass, we can easily cut the corner to get to B.

The rest of my algorithm isn’t any different than general A*. The code is well commented and all the pitfalls are avoided as much as possible. However why the code works might not be evident if you haven’t studied A* first. I suggest you check the link to at the top of this article for a very detailed explanation of A*


A* is a very fast algorithm, I’ve tested it on a grid with 64 nodes and the general search time was under 1ms.


You can download the source code via this link: (My Skydrive)

Don’t be afraid to post your optimizations, notes, questions or other comments here!

kick it on

Posted in General Gamedesign, XNA | Tagged: , , , , , , , , , , , | 32 Comments »

Implementing A* into XNA

Posted by Roy Triesscheijn on Sunday 22 February, 2009

Edit: the full article + source-code is now available here.

Most of the day I’ve been toying around with the implementation details of A*.  A* is both easy and hard at the same time, small errors in the function that calculates the cost of each node can really break the algorithm (and especially an ‘<’ instead of an ‘>’ and a faulty initialisation can break it, of which I’m, after a good old debugger session, am now painfully aware.

I’m not ready to post my code yet (it still has a nasty quirk, diagonal tiles are somehow very rarely considered even if you try to go from 0,0 to 5,5 without obstacles where a diagonal path (1,1  2,2 3,3 4,4) would be the fastest.  I think I’ve found the piece of code where it goes wrong though)  But I’ll soon do once I eliminated all the bugs and optimized/refactored the code.

Meanwhile have a look at it’s a very good beginners tutorial (not tailored to any language) be sure to read it front-to-end before implementing it .

Posted in Blog, General Gamedesign | Tagged: , , , , | Leave a Comment »