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

Blog on the move

Posted by Roy Triesscheijn on Saturday 28 November, 2009

Since for almost a year I have registered www.roy-t.nl however I’ve never gotten around to do something with it. Lately I’ve been feeling a bit bounded by using wordpress.com, although it’s a good free service I really wish to edit my themes and install more plugins. So I’ve decided to move my blog to www.roy-t.nl. So I’ve installed a fresh version of wordpress.org there, started scavenging for those useful plug-ins that are preinstalled here and updated the default theme. So now my ‘new blog’ mimmicks this one almost exactly. I even imported all the comments and posts made here to that new version.

I’m keeping this blog up so links don’t break down, but I will be moving my activity to the roy-t.nl so I’ve you got a bookmark or rss feed running, please update it🙂.

I hope to be adding some neat features soon, the new domain also gives me the ability to upload files, so you can download them directly at highspeed (so I wont have to use skydrive so much).

Oh anyway, I hope you’ll all find your way there!

 

Sincerely,

 

Roy Triesscheijn

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

Personal: Olympus E-520 Double Zoom Kit

Posted by Roy Triesscheijn on Friday 20 November, 2009

Luck

After working with my fathers’ old Pentax K1000 (which is really old as you can see here ) until it finally broke down a few years back (Leaky shutter). I haven’t been doing much photography at all. But recently my little brother bought a Canon 1000D and I found out that I just couldn’t resist not touching it🙂. So blood began to boil, a few weeks past and then I just had to buy myself a new camera.

Because my budget is pretty limited, being a student and all, I set myself the task to find the best possible camera €300,- could buy me. Quickly I narrowed it down to these camera’s:

Nikon Coolpix P90 (€290~410)
Panasonic Lumix DMC-FZ38 (€307~403)
Casio Exilim EX-FH20 Zwart (€280~350)
All good bridge camera’s in my price range. As an added bonus the Casio has an excellent film setting, the Nikon has great image quality (for a bridge camera). And the Panasonic just caught my eye as a nice all rounder. As you no doubt have noted hower, the title of this post is the Olympus E-520, which isn’t on this list, and isn’t a bridge camera. I looked at bridge camera’s because I didn’t think I could afford a nice DSLR. However after using tweakers.net excellent pricewatch to check if I had missed any cameras in my price range I came across the Olympus E-520 Double Zoom Kit package. At first I thought I was being fooled with, a fully functional DSLR, on par with the Canon 1000D, and two zoom lenses listed for less than €300,- by the cheapest store (Azerty, Netherlands) . After checking out the store reviews I came to realize that this was a reliable store and that this either was an insane offer or a mistake. Quickly I payed for the kit and had it send to me. And to my delight I really got it for only €285,-. Shortly after I bought the camera there though the normal price was restored and the kit is now listed there at €640,- (although there are a lot cheaper stores selling it for the more adequate €400,-, I guess they want to undo some of the damage🙂 ).

After toying around with the camera I really felt like a price winner. I’ve given a quick review on both tweakers.net and the store, but I’ll try give a more detailed one here as well.

The review

Facts / external reviews

First some basic facts. The kit I bought is the Olympus E-520 Double Zoom kit, featuring two zoom lenses by Zuiko Digital (Olympus’ daughter corporation that makes some of the most excellent kit lenses, outclassing those of Nikon and Canon).  The first lens is the Zuiko Digital 14-42mm 1:3.5-5.6 listed at dpreview.com here. The lens scores very good for a kit lens and gets the ‘recommended seal’.  The second lens is the Zuiko Digital 40-150mm 1:4.0-5.6. It hasn’t undergone a decent lens review yet but in a short summary here, dpreview.com says

“Covering a focal range of 40-150mm (equivalent to 80-300mm on a 35mm camera), this 3.8x zoom lens offers superb mid- to telephoto functionality at an attractive price. A fast f-stop of f3.5-4.5 gives Olympus E-300 owners ample opportunity to get creative by extending their telephoto capabilities.”

So,  excellent lenses! But ofcourse these lenses are useless if the body isn’t able to handle them. Luckily dpreview.com reviewed this camera in a 32 page review here. Listing it as just falling into the Highly Recommended category. I’ve taken the liberty of copying the most important pros and cons directly so you can view them without clicking through 32 pages🙂.

Conclusion – Pros
Good image quality at low ISO settings
In-body image stabilization means the benefit is seen with all lenses
Control panel display allows quick access to the important shooting parameters
Generally snappy performance (though it would be nice to disable SSWF at every startup)
Supersonic Wave Filter ensures no dust on sensor
Quality kit lens
Conclusion – Cons
Dynamic range limited compared to the rest of class – can lead to more easily clipped highlights
Small viewfinder
Disappointing high ISO performance
Menu structure a little longwinded (especially the setup menus)
Auto focus provides only three focus points, although AF performance good

So it’s not the camera to take with you on a nightly trip, but still it has a very good price/quality ratio.

Personal Experience

Well let’s tell something new instead of just copying dpreview.com (I can’t help it, they are just so thorough). When I first started using this camera I was a bit overwhelmed with options. Especially the setup menu was a bit cumbersome, leading me to frequently ‘wrong click’ which made the setup menu disappear. It was a bit strange walking trough context menus by pressing left and right. Some options really require to use the manual. For example I wanted to set the image format and quality the camera saves the photos in, and I just couldn’t find it. Turns out that instead of image format, or something else descriptive the menu option is hidden behind some kind of arrow icon. The settings weren’t very clear either, L/M/S and F/N (and RAW and RAW+JPEG with one of these combinations of options). After reading a bit trough the manual (which is very clear, and has a good index) I got the hang of it and selected the highest resolution and quality setting for JPEG.

After a bit of shooting I found out that I head a dead pixel in the sensor, these things can happen, it’s not easy to get 10M light sensitive ‘pixels’ on rectangle with a diameter 4/3rd of an inch. The dead pixel was always bright and began to annoy me. Right before I was sending the camera back for repair I came across a helpful fellow who told me to try the pixel mapping feature. (More about that here). This option tries to detect if there a haywire pixels in the sensor and turns them of and compensates for them. I tried as hard as I could but I can’t find any evidence now of there ever being a dead pixel. This option is really valuable!

So then the time came to really get some photos cracking. I love the way the shooting options are set via some sort of “super menu” on the display. By pressing ok once you can freely move over the tiles which represent options and pressing ok again allows you to change the current option to whatever you like. This gives an easy review of the settings you are shooting with, as well an easy way to change them. Of course the most important options are visible in the ocular piece as well.

I’m in love with the ‘paparazzi’ mode which lets you shoot about 3.5 photos per second. And if your CF or😄 card is fast enough you can keep doing this until the card is full. (You need at least a card capable of writing 20MB/s).  One oddity about those CF and😄 cards btw. Al tough the camera works fine with both😄 and Compact Flash, only😄 cards ‘unlock’ the panorama setting in the scene menu, very weird.

The photos seem very sharp in places where there is enough light. If there is not enough light the camera sometimes has trouble auto focusing, luckily you can always switch to manual focus with the touch of one button or set the flash to help focusing (even if you don’t want the flash to fire for the photo itself). The photos taken with flash don’t feel so worn out as usual, the white balance options really compensate a lot for this, and thus even flashed photos look warm and great. (But of course you can manually adjust the white balance settings and program).

I really love how feature full this camera is, it’s really a full grown DSLR, but in a pretty compact shape. Its’  body slightly smaller than the Canon 1000D and the lenses, thanks to the FourThirds system are a lot smaller, keeping everything very neat and compact. So this camera is definitely right for someone who wants to do more than just study/indoor photograph. The body and lenses are sturdy and feel less plastic than the Canon and Nikon starter DSLRs. However the camera is not weatherproofed (you’d need a few levels up in the Olympus product catalog).

I don’t know much about lenses so I don’t feel comfortable giving an outspoken opinion about them, so let’s get to the  conclusion.

I think the Olympus E-520 Double Zoom kit has an extremely good value for money. Because of the size of its sensor and the quality of the lenses this camera outclasses every bridge camera out there. It’s also a camera that can keep up nicely with the big boys (Canon and Nikon) in the starter segment of DSLRs. Great white balance, good quality lenses, a sturdy compact body and full featuredness are big pluses for this camera. Of course there are a few lesser points like the poor performance on high iso’s but I as a whole this camera is excellent. Especially if you consider what I paid for it.

Because I’m not a professional photographer, I haven’t shot any really nice pictures yet with this camera. However I can’t review a camera without posting at least one picture. So here’s a picture of one of our cats. The composition is not great but I hope you’ll be distracted by his smirk🙂. (Artifacts are largely due to the image upload service of tinypic)

Samson

Posted in Blog, Personal, Photography | Tagged: , , , , , , , | 4 Comments »

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.

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 »

Personal: One True Thing cd for sale again!

Posted by Roy Triesscheijn on Friday 4 September, 2009

Just a quick personal post to let all of you know that the CD Finally from One True Thing is ‘finally’ available for sale again. You can buy it at their record label Play The Assasin/. I’ve been bugging OTT a few times to see if I could buy their CD in Europe. Unfortunately the record label kinda broke down (website wasn’t updated and never heard from them again). Luckily after finding some youtube video’s and a topic about underrated music @ tweakers.net I double checked the website, and what-ya you know! It was updated and the store was opened again.

You can get the cd Finally for €12,- ($16,-) if you live in Europe and for $12.- if you live in the US.

I can really recommend this small band, I’m such a fan boy🙂.

Be sure to check their music at youtube.com, here are a few of my favorites.

😀 happy listening.

Posted in Blog, Personal | 3 Comments »

Review: NDepend

Posted by Roy Triesscheijn on Monday 17 August, 2009

Just at the start of the summer vaction I got an e-mail from Patrick Smacchia, Lead Developer of NDepend he asked me if I was interested to write something about their wonderfull code analysis tool, as said called NDepend.

I warned Patrick that I’ve never used code analysis tools and that’s also the reason why this blogpost about NDepend is kind of brief, I can’t really compare it to anything else. However this is a good opertunity to check out where code analysis tools are at.

After receiving a product key I downloaded NDepend from their website which almost screams “MVP” and all the companies that use NDepend. (Altough I had never heard of it before Patrick e-mailed me). Big companies like Microsoft and NASA.  The website features quite a big documentation/tutorial section which are also accesible from within NDepend.

Reporting

After downloading and following the really easy video tutorials (I so love video tutorials) the power of NDepend becomes clear, it’s not just a simple tool that just shows a nice graph with dependencies. It’s much more, NDepend generates a very nice statistical analysis of your .Net code. When the statistic analysis is complete you can print a nice report and know all sorts of things about your code. Starting with a quick overview of your code.

Excerpt from my racing game:

Number of IL instructions: 1796
Number of lines of code: 294
Number of lines of comment: 152
Percentage comment: 34
Number of assemblies: 1
Number of classes: 6
Number of types: 8
Number of abstract classes: 0
Number of interfaces: 2
Number of value types: 0
Number of exception classes: 0
Number of attribute classes: 0
Number of delegate classes: 0
Number of enumerations classes: 0
Number of generic type definitions: 0
Number of generic method definitions: 0
Percentage of public types: 75%
Percentage of public methods: 85,15%
Percentage of classes with at least one public field: 12,5%

Number of IL instructions: 1796
Number of lines of code: 294
Number of lines of comment: 152
Percentage comment: 34
Number of assemblies: 1
Number of classes: 6
Number of types: 8
Number of abstract classes: 0
Number of interfaces: 2
Number of value types: 0
Number of exception classes: 0
Number of attribute classes: 0
Number of delegate classes: 0
Number of enumerations classes: 0
Number of generic type definitions: 0
Number of generic method definitions: 0
Percentage of public types: 75%
Percentage of public methods: 85,15%
Percentage of classes with at least one public field: 12,5%

As you can see allot of information, and this is just the top of the report.

Another very usefull metric in the report is the “Assemblies Abstractness vs. Instability” graph. Which will warn you if you are soldering everything togheter,  or a just creating useless interfaces instead of working code.  (Luckily my race game was pretty centered).

There are ofcourse allot more things, I could list them all here but it might be easier to just check this http://www.ndepend.com/Features.aspx#Metrics page.

Main screen

Let’s get to the main screen (sorry about the big image but there is just so much information there)
Main screenMain screen

The main screen visually lists all parts of your project, hovering over the ‘code’ blocks on the right gives you more information on the bottom left of the screen. You can change the way the code blocks on the right are ordered. Right now they are ordered by method with lines of codes, but you can select a variety of views. But you can also view them as types with #IL generated instructions or other things.

Code Query Language

NDepend also has a feature called ‘code query language’. This CQL allows you to select things that are of special interest to you, possibly all the methods that have more than 50 lines of code. You this in a simple SQL’esque language “SELECT METHODS WHERE NbLinesOfCode > 50”. There are also allot of predefined CQL statements that you can use ranging from method sizes to code quality and design.

Conclusion

As you can see NDepend has a lot to offer, and really I’ve just skimmed the surface here. I see a lot of potential for NDepend in large project groups especially for software engineers who need to worry about the code quality and robustness but who can’t check each and every line of code themselves. For small projects and ‘one man teams’ like me this tool is plainly overkill but fun to play with. Unfortunately I don’t have knowledge of other code analysis tools so I can’t really compare it to anything else. However NDepend feels solid and gives allot of usefull (documented) information.

Oh and did I mention it is a stand alone app aswell as an integration with Visual Studio? This pleases me very much as a VS Express user.

Special Thanks to Patrick Smacchia for providing a NDepend licence.

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

Personal: CastleFest 2009

Posted by Roy Triesscheijn on Sunday 2 August, 2009

Organisational

As I’ve said in another blog post on my personal blog I’m going to merge my tech blog and personal blog because I hardly use my personal blog and would like to keep everything organized. So this will be my first non-tech related post here, jolly good isn’t it. I’ll mark these blog posts with “Personal” and will put them in the personal category so they can be easily filtered out for those people who read this blog for the tech stuff. ( I can totally imagine not everyone is that interested in everyone’s personal lifes, everyone is writing about everything these days, but well if find blogging a good way to relax a bit and somketimes you get those cheeky comments that it make it worth while).

CastleFest

Well now we’ve got all the bureaucratic crap settled let me tell you all about Castlefest. Castlefest is a small festival in Lisse, The Netherlands where for 5 years, like minded people meet.  The festivals main theme is ‘the medieval age’  but people can be seen wearing just about everything, from apropiate medieval pessant clothing to girls wearing commic-con like outfits. A pritty lass had a really cool Yuna (Final Fantasy) outfit.

However as I said the main theme is ‘the medieval age’ (hence Castle). Unfortunately my medieval costumes are ehm non-existent so I joined the “just wearing witty t-shirts” type of people with a t-shirt that praises leeks (the vegetable).

After some hours checking out all the little stores I was a bit disappointed. For women (and girls) there where the most beautiful dresses and outfits ranging from the year 1000 ‘cute’ peasant look to the 1800 victorian queen look to the  post apocalyptic scavanger girl look. Most of these outfits where hand made from leather and wool just stunningly beautiful.

For us man this was unfortunately quite different (okay I’ll ignore all the medieval weapons that where out there for now, a brave warrior has to wair clothes aswell you know).   There where some nice woolen cloaks that where affordable and there where some beautiful full leather outfits and brilliant napolean era costume but unfortunately these where quite expensive  (like €300,- for just the top expensive).  Normally priced shirts and pants where hard to come by.  (In the end I did get my hands on a cool thick-cotton shirt with leather ropes holding everything togheter but I really hoped that there would be some more man clothes in the affordable price range.)

Anyway later that day  the main reason why I came to castlefest revieled themselves: Valravn took the stage and they played like mad, for those who don’t know this band I really think you should check them out on youtube here.

(Quoted from last.fm) Eyes firmly on the 21st century, Valravn’s inspiration comes from the original Nordic music tradition. The band manages to organically blend the raw sounds from their ancient instruments with the smooth possibilities of electronic music. The fusion of the two yields a unique and powerful experience of the vigour and life, that lies hidden deep in the Nordic roots.

Valravn was really brilliant, looking at old youtube video’s it’s amazing to see how they’ve grown. The video I linked above is only a year old but damn the entire Valravn band seems pretty tame there while at castlefest they really rocked their harts out. They also played a few songs from their new cd which should be out soon(a friend of mine bought the cd right there but bol.com is still saying it hasn’t been released yet)! Brilliant and more energetic than their first album.

The day came to a closing by performing a heretic ritual togheter with the band Omnia, allot of my friends kept whining about Omnia being a bit arrogant and stuff (and I do agree) but their performance was memorable and it felt really as if people set them selves free during the ritual.

I had a great day at castlefest and I will surely go again next year, I might even put some more effort in dressing up and stuff. I can surely recommend these kind of festivals to everyone who enjoys a relaxed mood and doesn’t worry to much about people wearing funny clothes , the people at such festivals are just lovely.

I would’ve posted some photo’s but I didn’t bring my camera, I’ll see if my friend Mart has some pictures and if I can put them up here for a more general impression of what castlefest is.

Please let me hear your thoughts about this blog post and on mixing personal and ‘professional’ blog entries and how you’ve coped with this on your own blog(s).

Posted in Blog, Personal | Tagged: , , , , , , , | Leave a Comment »

Spell checking in Opera

Posted by Roy Triesscheijn on Monday 27 July, 2009

As some of you might know I use Opera as my main webbrowser and I always found it quite troublesome that it doesn’t have a spellchecker. I heard that version 10 would have a dedicated spellchecker so I went out to look for more information.

It turns out that by installing Aspell you can also have spellchecking in  Opera 9.x. I could describe the whole process but hey it’s all documented at the Opera website here: http://www.opera.com/browser/tutorials/spellcheck/ so go out there and have look🙂.

To bad though that it doesn’t work for wordpress (it doesn’t detect this field as an input field). Oh well I guesse it will just be forum posts that will be less messed up with errors for now🙂.

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

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 »