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 the ‘XNA’ Category

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 »

Article updated and moved! (A* 3D)

Posted by Roy Triesscheijn on Monday 29 June, 2009

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

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

You can find the new article here

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

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

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

Posted by Roy Triesscheijn on Monday 29 June, 2009

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

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

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

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

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 »

Why you should complain about (open-source/free) software!

Posted by Roy Triesscheijn on Thursday 1 January, 2009

With the new (beta) release of blender 2.50 we could finally take a look at the new user interface. And frankly I was a bit disappointed (although I believe allot of work has been done, some of the in my eyes ui-flaws that really need improvement are still there. For example: resizing buttons still don’t work properly and you still have to drag panels and menu bars around to see all the options. This is against all user-interface guidelines on all common operating systems!)

However, the reason I am writing this, is not Blender. (There are people far more into Blender who can write about it, and maybe give us an idea of the changes in the code behind).

The reason that I am posting this where comments after my rant at the new Blender UI.

“I suggest you make those changes yourself then” “you should not complain about something that is free”

Blender, being open-source software, allows me to change it myself. But does this mean I can’t have critique at open-source software?

I believe that is not the case. Open-source software is like a good friend who helps with a paint job. You can do it yourself, you don’t have to pay, but if your friend does a sloppy job you can complain and tell him/her to improve his efforts.

If you can’t complain about open-source software, there wouldn’t be anything in it. Each software package would be complain free at the moment it hits the download spot. There would be no incentive to improve anything. I call that empty and soulless software, since I believe there is always room for improvement.

Of course just ranting away isn’t going to help either. If we still take the paint example, you could show your friend how to do it (for example with a mock-up, or by doing some painting for him). Critics are not going to help if they don’t come to the right people.

 

But please keep complaining about (open-source) software, do you think that a feature is missing, do you think that the UI sucks, that the program is unstable when doing action X. Complain!! Tell the devs, make some mock-ups write some example code or even participate and commit to the SVN/VSS etc..

Posted in XNA | 3 Comments »

Todo

Posted by Roy Triesscheijn on Monday 8 December, 2008

Well haven’t posted here for 2 weeks, really that is because I haven’t got anything new to show. I was going to work out 3D collision detection and response for my racer game (which I posted the youtube vid from) but it seems that 3D collision response is going to be allot harder than I thought 😦 .

I just cant get myself to it to grind all thos details down and make them work. So I’ve been slacking 🙂

Instead I am going to post how awesome the new WordPress dashboard is, I really started to hate the old one, this one is soooo much better, I dont understand anyone whining they want the old stuff back.

I hope they fix Windows Live Writer support soon because I was just about to checking that out. 🙂

Greetz!

Posted in XNA | Leave a Comment »

Youtube

Posted by Roy Triesscheijn on Tuesday 25 November, 2008

I today uploaded my first youtube video *yay*.

Was just trying to test some stuf, and some dudes at the #XNA channel would like to see it. It took me almost an hour to get all the proper tools and codecs to make a normal size video (the original was 500MB of RAW avi)

However here it is, nothing fancy but it’s just a show of of the driving mechanics for my little racing game.

edit: oops didn’t know there was a wordpress shortcode to embed youtube video’s

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

Creating Animated Textured Models for XNA – Part2: trueSpace Online at Ziggyware

Posted by Roy Triesscheijn on Tuesday 11 November, 2008

Ah,

Ziggy was a swift beast this time, you can view my most recent article at

Ziggyware (direct link)

In this article it’s trueSpace’s turn to show what an excellent modelling tool it is. All relevant parts for building and exporting a basic UV-textured model will be covered, including sample source code and the finished trueSpace project. This tutorial will help give your game a bit of body right from the start. By Roy Triesscheijn

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

Creating Animated Textured Models for XNA part 2: that was fast!

Posted by Roy Triesscheijn on Monday 10 November, 2008

Well only half a day ago I posted a progress report for this part of the modelling for XNA tutorial series. And well here I am again! I’ve finished the entire article and found out even more about UV-texture-editing in trueSpace. Damn that UV-Editor has some powerfull tools!

I hope Michael from Ziggyware.com will be able to put part 2 online fast. As the Blender article it is a long one. (15pages in word, and over 30 images explaining what to do and where to find the buttons and toolbars 😉 ).

I’m sure you’ll all like it!

I’ll write a new post as soon as Michael puts it up!

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