No longer updated: new and updated blog (including old content) at http://roy-t.nl

Archive for http://roy-t.nl, please update your bookmarks

Posts Tagged ‘C#’

Quick Tips: C# inline event handlers and Reordering method / constructor parameters

Posted by Roy Triesscheijn on Thursday 15 October, 2009

I always hate having to write an extra method to deal with event handlers and today it irritated me more than ever. The extra event handlers all consisted of just one line of code, it’s also harder to read what is going on if you have to scroll down all the time to check what that event handler is doing.

So today I finally typed in “C# inline event handlers” in Google. And the first website I clicked already gave me what I was looking for. Apparently this was added in C# 2.0 and it basically boils down to this:

this.button1.Click +=
  delegate(object sender, EventArgs e)
  {    MessageBox.Show("Test");   };

Quick easy and very handy!

Another thing that I found out recently is that you can easily reorder method and constructor parameters using Visual Studio 2008’s built in refactoring tools. All you have to do is right click the method/constructor and select Reorder parameters. Very easy and very handy. Just the kind of trick you have to know that is there to be able to use it.

Reorder context

You’ll get a nice form which allows you to reorder your parameters, Visual Studio will automatically update all callers.

Of course these are all tips that are simple and are well documented on the internet, if you look for them,  but maybe I’ll make a few of you guys happy with these.

Advertisements

Posted in Blog, General Coding, Tips | Tagged: , , , , , , , , | 4 Comments »

Computermanagement software

Posted by Roy Triesscheijn on Monday 12 October, 2009

Lately I’ve been bussy working at the Rijksuniversiteit Groningen as ‘one day a week’  systemadministrator/programmer.

One of the first jobs that was assigned to me was reorganizing a set of 14 computers. These computers run ‘exhibits’ so people interested in going to the university can see what we do. The old setup was kinda odd, all computers where attached to 4 remote controlled powerinterupters and each morning someone at the reception, or me turned on then powerinterupters and each computer turned on because “wake on power” was turned on in their bioses.

Each afternoon someone would again turn off the powerinterupters and each computer would just stop because the power ran out.

If there was something wrong with a computer, you’d just pick up your keys, keyboard and mouse and sat in front of the damn thing until it worked again.

I quickly started working on laying networkcables between all computers, setting up remote desktop configurations, configuring a sever to become a proxy/dhcp server/webserver and setting up all computers to “wake on lan.” After that the administration began, find each computers username, password and mac adress, and setting a helpful computername.

After these changes I could remote desktop to the server, and from there remote desktop to each connected computer, configure it, install new software, reboot it, etc… The proxy server blocked all websites except for the websites of the university so the computers could no longer be used for ‘bad browsing’.

There was still one thing that bothered me though, and that was not being able to see which computers where still working without logging in to each and every one of them. I also wasnt happy with still having to login in to the server to send the wake on lan packets in the morning, and shutting every computer down by login in again in the afternoon.

To overcome this problem I wrote two programs, creatively called ComputerManager and ComputerMonitor. ComputerMonitor is a small application that runs in the background and sends a “I’m alive” packet to ComputerMonitor every 2minutes, it also has a small listenserver running to listen to shutdown and reboot commands. I installed this on all 14 pc’s.

The ComputerManager program listens for those “I’m alive ” packets and keeps track of which computers have not send an “I’m alive” packet for 5 minutes and adds these to a “red list”. The computers that keep responding keep being updated in the “green list” with their last update time, computername and ip-adress.

The program also allows for saving mac adresses of computers. These mac adresses are used to wake-up all computers on 8:55 am. The program also sends a shutdown message to every computer on 6:05pm. This way my job got allot easier. Ofcourse it was allot of work at first but it was worth my effort.

As a final touch I created one more little program that can be run by an exec command in a php script. This allowed me to make a secure webpage where people other than me can only press two buttons: “Turn all on” and “Turn all off”.

I’m releasing the sourcecode of ComputerManager and Monitor to everyone. Allot is still hardcoded, and there are probably some bad design descissons here and there but it might be useful to someone. The asynchronous listen server is solid and a good learning example. There’s also allot of code dealing with win32 calls like shutdown and reboot.

The most recent version can be downloaded here

I won’t be actively updating or supporting this program since it was just written for my personal use, but if you got any questions or comments, feel free to ask.

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

New Version A* pathfinding in 3D

Posted by Roy Triesscheijn on Tuesday 7 July, 2009

Note: since the 1st of December 2009, this blog was moved to www.roy-t.nl, 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.

Sincerely,

Roy Triesscheijn

Intro and thanks.

Ok so let’s quickly forget the debacle around the first release of this code sample, I wan’t to delete the entire post about that one but I would’nt  have know that I made an error (until much later on) if it wasn’t for some people spotting it instantly! So I would first like to thank some of my visitors who spotted the errors:

-Oscar for spotting possible performance problems.

-Ryan for suggesting possible HashSet’s (altough I didn’t use them in the end, see below why).

I would also like to thank posters from http://www.tweakers.net  who helped me get this version of A* so fast, especially (on post order):

-Phyxion & Mammon for their one line version of Equals()

-Nick The Heazk for spotting that I totally forgot the Heuristic part for scoring (doh, I swear I had it in my draft)

-pedorus &  jip_86 for suggesting to use a Binary(Min)Heap

-Marcj & NotPingu for pointing out a 3D version of Pythagoras

-Soultaker for letting me think more about efficiency of containers (O(?) of add, extract and contains))

-.oisyn & pedorus for suggesting to combine a binary heap and a HashSet (altough I didn’t use it in the end, see why below)

-PrisonerOfPain for suggesting to use binary flags instead of extra HashSet’s (that’s why I didn’t use them).

Why is this version faster?

A lot was changed from the previous version, let’s start with the openList, checking if an item is in the openList costs O(n) iterations and checking which item has the lowest score costs O(n) and removing an item costs O(log(n)). So I’ve replaced the openList with a BinaryHeap for checking the lowest score and removing/adding. These operations cost O(1), O(log(n)). That’s allot faster already.

As for checking if an item is in an openList (or closedList) all I did was add a boolean flag to the BreadCrumb class (onOpenList and onClosedList).  Checking this flagg is O(1) so that really makes checks allot faster.

Also all I needed the closedList for was checking if items where already in there, so with the boolean flag I could completely remove the closedList.

Another new feature is that we immediatly return from the FindPath function when we find the finish, this also saves some operations.

I also made sure that I don’t  create to much new objects but re-use them after they where first indexed (this was  also the cause for a small ‘score’ bug) and I’ve re-aranged some ifs.

For the algorithm itself I now use DistanceSquared for the (forgotten) Heuristic part of the scoring which is allot better than ManHattan distance which is slightly biased. I’ve also changed the cost (G) to move from the current node to the next node to incorporate these squared cost  (so instead of 1,  1.4 and 1.7 I can now use 1,2,3 for these scores. I also don’t have to multiply all these numbers by 10 since 1, 2 and 3 are integers.

A final additon is the class Point3D which allows us to use only Integers instead of floats (which are slower for a cpu).

All in all this made this code about 200x faster (yes really!). But that is not completely fair since the first code was broken. If you count from after I fixed the heuristic part of the code the code is ‘only’ about 30x faster.

Benchmark results.

And before we get to the exciting part (the code!).  Let’s first show some benchmarks.

Situation:

World: 10x10x10

Start: 0,0,0

End: 9,5,8

Nodes blocked: 300

Time:

Total (100 iterations) : 134ms

Average:  1.34ms

Lowest:   < 1ms

Highest:  17ms

Note: as you can see because we did this test 100 times there is quite allot off difference between the lowest and highest time we needed to calculate this route, that’s because sometimes the cpu stops executing this program, and starts handleing an irq or doing something else, that’s why it’s important to always take a big number of benches to be representative. We can see from the average that this code is extremely fast.

Efficiency:

A* is an extremely efficient algorithm, consider we would’ve liked to brute-force this problem instead of using A*. That would’ve cost us 10^10^10 = 1,e+100 iterations. However with an (this) A* implementation we only needed 119 iterations (in which we checked 3094 nodes).

So, on to the code!

The code.

Well since I’ve divided every thing in much neater classes it’s a bit of a problem adding showing off all these as code-listings as I usually do. So I will only show the most important method here, the rest of the classes, and an example  you can download at the bottom of this article or by clicking here

        /// <summary>
        /// Method that switfly finds the best path from start to end. Doesn't reverse outcome
        /// </summary>
        /// <returns>The end breadcrump where each .next is a step back)</returns>
        private static BreadCrumb FindPathReversed(World world, Point3D start, Point3D end)
        {
            MinHeap<BreadCrumb> openList = new MinHeap<BreadCrumb>(256);
            BreadCrumb[, ,] brWorld = new BreadCrumb[world.Right, world.Top, world.Back];
            BreadCrumb node;
            Point3D tmp;
            int cost;
            int diff;

            BreadCrumb current = new BreadCrumb(start);
            current.cost = 0;

            BreadCrumb finish = new BreadCrumb(end);
            brWorld[current.position.X, current.position.Y, current.position.Z] = current;
            openList.Add(current);

            while (openList.Count > 0)
            {
                //Find best item and switch it to the 'closedList'
                current = openList.ExtractFirst();
                current.onClosedList = true;

                //Find neighbours
                for (int i = 0; i < surrounding.Length; i++)
                {
                    tmp = current.position + surrounding[i];
                    if (world.PositionIsFree(tmp))
                    {
                        //Check if we've already examined a neighbour, if not create a new node for it.
                        if (brWorld[tmp.X, tmp.Y, tmp.Z] == null)
                        {
                            node = new BreadCrumb(tmp);
                            brWorld[tmp.X, tmp.Y, tmp.Z] = node;
                        }
                        else
                        {
                            node = brWorld[tmp.X, tmp.Y, tmp.Z];
                        }

                        //If the node is not on the 'closedList' check it's new score, keep the best
                        if (!node.onClosedList)
                        {
                            diff = 0;
                            if (current.position.X != node.position.X)
                            {
                                diff += 1;
                            }
                            if (current.position.Y != node.position.Y)
                            {
                                diff += 1;
                            }
                            if (current.position.Z != node.position.Z)
                            {
                                diff += 1;
                            }
                            cost = current.cost + diff + node.position.GetDistanceSquared(end);

                            if (cost < node.cost)
                            {
                                node.cost = cost;
                                node.next = current;
                            }

                            //If the node wasn't on the openList yet, add it
                            if (!node.onOpenList)
                            {
                                //Check to see if we're done
                                if (node.Equals(finish))
                                {
                                    node.next = current;
                                    return node;
                                }
                                node.onOpenList = true;
                                openList.Add(node);
                            }
                        }
                    }
                }
            }
            return null; //no path found
        }

(note the class also has a normal FindPath() method that switches start and end for you).

Download.

In case you missed the download link in the middle of the text, download the entire example:  here

kick it on GameDevKicks.com

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

A* 3D update

Posted by Roy Triesscheijn on Tuesday 7 July, 2009

Just a small update so to keep you all who’ve been anxiously waiting for the updated version of A* happy :).

I’ve been working on implementing A* more efficiently using a MinHeap for storage instead of Lists<> add this time I made sure that I didn’t forget the H (heuristic) part of the scoring (silly me). To give you a bit of an idea how much better the algorithm is now.

Situation 10x10x10 grid, 1/3 of the nodes blocked, find a path from 0,0,0 to 9,5,8

Old code: +-600ms (If I’d just have profiled it before I would’ve known something was wrong)

New code: 8.86ms 6.82ms 5.27ms averaged over 100 runs.

So yeah that is allot better, however when decreasing the number of blocked nodes the time goes up slightly (average 19ms for 0 nodes blocked). And I really want to get that lower, so I’ve asked some people at http://gathering.tweakers.net if they saw more room for optimalisation and there are still a few tips that I haven’t explored there. So I’ll be releasing the new (correct/fast) source code soon, but not untill I’ve made sure that I’ve cramped out all the speed that I can.

There is atleast one method that will speed everything up significantly. A player can now make a step over 3 axis at the same time (x,y,z) ofcourse that is more expensive but sometimes gives a better path, however this means that each node has to consider 26 neighbours instead of just 18. I’m playing with the idea to restrict motion a bit for a faster algorithm.

Maybe I’ll build in some different motion types for speed, best path, or some average.

Posted in General Coding, 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 www.roy-t.nl, 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.

Sincerely,

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 tweakers.net 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.

[Serializable]
    public class Status
    {
        [NonSerialized]
        public Socket Socket;
        [NonSerialized]
        public List<byte> TransmissionBuffer = new List<byte>();
        [NonSerialized]
        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...");
allDone.Reset();
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.Socket.EndConnect(result);
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.");
Console.ReadLine();
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...");
allDone.Reset();
listener.Listen(100);
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++)
{
status.TransmissionBuffer.Add(status.buffer[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!");
}
else
{
Done(status);
}
}
else
{
Done(status);
}
}

///
/// Deserializes and outputs the received object
///
public void Done(Status status)
{
Console.Out.WriteLine("Received: " + status.msg);
Status send = status.DeSerialize();
Console.WriteLine(send.msg);
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 »

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 www.roy-t.nl, 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.

Sincerely,

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 Netbeans.org 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 http://www.cygwin.com/setup.exe 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 Netbeans.org 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:
–binutils
–gcc core
–gcc g++
–gcc g77
–gcc mingw core
–gcc mingw g++
–gcc mingw g77
–gdb
–make
–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*!

Art

(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
 {
 get
 {
 return passwordHashed;
 }
 set
 {
 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).

CREATE PROCEDURE InsertUniqueUser
@Username nvarchar(50),
@Password nvarchar(50),
@LastName nvarchar(50),
@FirstName nvarchar(50),
@Email nvarchar(50),
@UserID int OUTPUT
AS
IF NOT EXISTS(SELECT Username FROM Users WHERE Username=@Username OR Email=@Email)
 BEGIN
 INSERT INTO Users
 (Username, Password, LastName, FirstName, Email)
 VALUES (@Username, @Password, @LastName, @FirstName, @Email)
 SET @UserID = @@IDENTITY
 END
ELSE
 BEGIN
 SET @UserID = -1
 END

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;

try
 {
 connection.Open();
 command.ExecuteNonQuery();
 newID = (int)command.Parameters["@UserID"].Value;
 }
 catch (Exception ex)
 {
 //trace error
 string log = ex.Message;
 }
 finally
 {
 connection.Close();
 }
 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 »

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 www.roy-t.nl, 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: http://roy-t.nl/index.php/2009/07/07/new-version-a-pathfinding-in-3d/ which is greatly superior and faster than this version.

Sincerely,

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

http://www.policyalmanac.org/games/aStarTutorial.htm

http://en.wikipedia.org/wiki/A*_search_algorithm

http://en.wikipedia.org/wiki/Dijkstra’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 policyalmanac.org )

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:

Art

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 policyalmanac.org at the top of this article for a very detailed explanation of A*

Speed.

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

Download.

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 GameDevKicks.com

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

Introducing Toppers

Posted by Roy Triesscheijn on Monday 9 February, 2009

I totally forgot about this project, but after I was feeling like coding I’ve updated Toppers to 2.002 and decided to release it to the general public.

Toppers is a program I made for SusanneK.  a good friend of mine. She’s always making little ‘top-lists,’  say: which of last years song she preferred. Of course she can put them in word/excel or on plain paper and figure out which one is best, but her top-lists where becoming quite long. And to make a statistically correct ordered list of only 10 items, you need to ask yourself 45 questions (10 nCr 2).

To aid her in her list-making she asked me to make a small program that would help her determine the best order! After a few hours of juggling with code the first incarnation of Toppers came alive. Now after some good feedback and a code-cleanup I present Toppers 2!

Here is a list of features, you can download the program, an example TopList listing of some musical genres and the full source-code licensed under the MIT X11 license (see license.txt) for free from my SkyDrive account listed at the bottom of the article (you don’t have to register/login to download it).

Introduction:

Toppers is a free program for making lists and comparing data from these lists.  After a total or partial comparison the program will show you in text and graph the calculated ranking of your list items!

Edit

Creating lists is very easy in Toppers’ intuitive interface. You can also load and save plain text files (*.txt) where each line will represent a list item, this allows for the rapid creating of larger lists.

Save

Once an appropriate list has been loaded or created the user has two different options to start the test. The first option is the full test.

FullTest

In the full test each list-item is compared to all other list-items, on larger lists this will bring up allot of questions, but the end result is a perfect representation of what you think of each item.

For a quicker tour around large lists there is the Random Sample Test. This test will query the user, and ask how many questions he/she wants to be queried with. This allows users of generating a rapid result in large lists without the need to answer allot of questions. A specially devised algorithm will give scores even to items that haven’t been compared to all other items by taking into account relative scores for maximum accuracy. (Please note that a full test will always be more precise).

Save

For very large lists there is the option to save while answering the questions. This allows a user that is in the middle of a quiz to save, exit and continue at another time, this way big lists don’t get dull.

ResultGraph

After completing a test, be it a full or a random sample test, a self-scaling result graph and textual output will be showed, and you can save the outcome as a jpg-file so you can e-mail the graph or show the results on the internet. (You can also copy/paste the text and e-mail it or post it here!).

To run Toppers you will need a PC with Windows XP, Windows Vista, or higher. You will also need the Microsoft .Net 3.5 framework, the installer will install this when needed. The program also requires a modest 2MB of free harddisk space.

Download Toppers 2.002 Now:

Download a sample TopList that will tell you what musical style you like best:

Or download the source code (The full Visual Studio 2008 Express solution, all the code was written in C#)

View The license here

if these links don’t work correctly you can try:

Installer, Genre Toplist, Source Code, License

Be sure to post your funny/cool/brilliant/enlightening TopLists here! I will feature the best ones and might even incorporate them in a possible next version of Toppers!

Also if you encounter any bugs or have a feature request, post here as well, I’ll try to answer and fix/implement them as quickly as possible!

Best regards and I hope everyone has fun with this one, like Susanne and I have!

Posted in Blog, General Coding | Tagged: , , , | 1 Comment »