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

Archive for February, 2009

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

Advertisements

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 http://www.policyalmanac.org/games/aStarTutorial.htm 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 »

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 »

Update

Posted by Roy Triesscheijn on Monday 9 February, 2009

Well, as you’ve all noticed, it’s been a while since I’ve posted here!

I’m currently not to busy with XNA or any other programming work for that matter. I’m trying to focus on my study (Computer Science at the RuG, Groningen, the Netherlandes). Unfortunately all the courses I’m getting at the moment is programming correctness (utilizing logic and math to prove code is correct) and abstract math, needles to say I’m not coding anything worth posting about. And I’ve yet got to see the first XNA game that used programming correctness (PCOR) to verify that there are no bugs! (Ha that would be a first!).

I am toying around with PHP though, I know you are going to ask why, and yes I know it’s ugly but still it’s quite a learning experience programming in a loose-typed language. I’m also intrigued by all the markup (CSS) and database (MySQL) integration that I’m currently utilizing in PHP.

My small project is trying to create the most simplest CMS possible:

-User creation and logging in.

-Posting new items

-Commenting on items.

(Might hack a forum togheter from these components just for fun).

I’m trying to broaden my not-so-broad perspective of programming languages, the only real languages I’ve been working with for more than a few hours are (in chronological order):  Visual Basic 6, C#, Java, VHDL (made my cry), 68Kasm (I hated that!),  and now PHP. I hope i can add C++ and Delphi to that in the near future (and maybe even Haskell or F#).

Oh well, I’ll make sure to post and release the source-code of my crazy-cms,  it might contain something usefull for people starting with PHP. 🙂

I hope It won’t take me this long again to post another item, I want to update you guys on a small project I might be working on in the near future that could be off help to programming/game enthusaist near Groningen. I’ll keep you guys posted!

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