The A* Path Finding Algorithm (CSS's Code Repository)
-
I see. Well, why post it online at all then ? No matter what, even if it sucks, it's going to get ripped off somewhere.
Christian Graus Driven to the arms of OSX by Vista. Read my blog to find out how I've worked around bugs in Microsoft tools and frameworks.
He wont post it on CP because it is his, but provides a link to his private website. what a douche. Actually doesn't that count as advertising?
------------------------------------ I will never again mention that I was the poster of the One Millionth Lounge Post, nor that it was complete drivel. Dalek Dave
-
Why dont you just link to a better written and illustrated description ie http://en.wikipedia.org/wiki/A*_search_algorithm[^] It's a well known algorithm, what is it you think you *own*? You should mention alternative algorithms and list why this one is better or worse than each in particular circumstances. You should provide an analysis of the time complexity in Big-O notation. Choosing a path finding algorithm is usually a trade off between performance cost and accuracy. For some users a 'good enough' solution will be preferable if it is faster, others will want the absolute best path every time no matter the cost of calculating it. Most users will fall somewhere between those two. Your article should prompt people to think about what they need from a path finding algorithm. You should give a sample implementation. You could write a pretty interesting program that would display a little map of tiles, let the user set the start and end points and cost properties of the tiles and thenstep through the path finding algorithm. Your language and presentation are quite poor and will turn a lot of people away. Compare how well written and illustrated the wikipedia article is
modified on Tuesday, March 2, 2010 9:28 PM
-
Why dont you just link to a better written and illustrated description ie http://en.wikipedia.org/wiki/A*_search_algorithm[^] It's a well known algorithm, what is it you think you *own*? You should mention alternative algorithms and list why this one is better or worse than each in particular circumstances. You should provide an analysis of the time complexity in Big-O notation. Choosing a path finding algorithm is usually a trade off between performance cost and accuracy. For some users a 'good enough' solution will be preferable if it is faster, others will want the absolute best path every time no matter the cost of calculating it. Most users will fall somewhere between those two. Your article should prompt people to think about what they need from a path finding algorithm. You should give a sample implementation. You could write a pretty interesting program that would display a little map of tiles, let the user set the start and end points and cost properties of the tiles and thenstep through the path finding algorithm. Your language and presentation are quite poor and will turn a lot of people away. Compare how well written and illustrated the wikipedia article is
modified on Tuesday, March 2, 2010 9:28 PM
Josh Gray wrote:
what is it you think you *own*? Quote Selected Text
My text and pictures, my article.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
-
Josh Gray wrote:
what is it you think you *own*? Quote Selected Text
My text and pictures, my article.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
-
I disagree with you, however I don't intend to be a technical writing, I intend to be a software engineer.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
-
I disagree with you, however I don't intend to be a technical writing, I intend to be a software engineer.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
-
I disagree with you, however I don't intend to be a technical writing, I intend to be a software engineer.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
Well, it seems that you've written an article on a non complex subject, so at first glance, that seems reasonable. However, I'd attribute at least some of my success, and certainly the fact that I've done a lot better than workmates I counted as smarter than me, to my being willing to work hard, contribute to a team, and consider other people's needs rather than just complain about what I wanted. I don't see those qualities in you, at all.
Christian Graus Driven to the arms of OSX by Vista. Read my blog to find out how I've worked around bugs in Microsoft tools and frameworks.
-
-
CaptainSeeSharp wrote:
I finished it. Tell me what you think.
CaptainSeeSharp wrote:
1.) Add Point A to the Open List and make it the Current Node 2.) Scan for Nodes adjacent to the Current Node that qualify to be added to the Open List. 3.) Calculate their costs, set their Parents to the Current Node, and add them to the Open List. 4.) Pull the Node with the least Total Cost from the Open List and make it the Current Node. 35.) Repeat steps 2-34 until the Current Node is Point B (the end Node). 46.) Point A and Point B are now linked together by the Parent Nodes. Iterate through them from Point B to Point A.
FTFY Easy one first. Construct the wall to surround Point B. Does your algorithm still work?
Bob Emmett @ Ynys Thanatos
-
Christian Graus wrote:
Why not post it as a CP article ?
Because I own it.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
-
CaptainSeeSharp wrote:
I finished it. Tell me what you think.
CaptainSeeSharp wrote:
1.) Add Point A to the Open List and make it the Current Node 2.) Scan for Nodes adjacent to the Current Node that qualify to be added to the Open List. 3.) Calculate their costs, set their Parents to the Current Node, and add them to the Open List. 4.) Pull the Node with the least Total Cost from the Open List and make it the Current Node. 35.) Repeat steps 2-34 until the Current Node is Point B (the end Node). 46.) Point A and Point B are now linked together by the Parent Nodes. Iterate through them from Point B to Point A.
FTFY Easy one first. Construct the wall to surround Point B. Does your algorithm still work?
Bob Emmett @ Ynys Thanatos
Bob Emmett wrote:
Easy one first. Construct the wall to surround Point B. Does your algorithm still work?
Yes, it throws the
PathNotFoundException.Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
-
Bob Emmett wrote:
Easy one first. Construct the wall to surround Point B. Does your algorithm still work?
Yes, it throws the
PathNotFoundException.Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
CaptainSeeSharp wrote:
Yes, it throws the PathNotFoundException.
But your algorithm makes no mention of the possibility that a path may not be found, or the condition that indicates that no path exists. Thus your algorithm is incomplete.
Bob Emmett CSS: I don't intend to be a technical writing, I intend to be a software engineer.
-
CaptainSeeSharp wrote:
Yes, it throws the PathNotFoundException.
But your algorithm makes no mention of the possibility that a path may not be found, or the condition that indicates that no path exists. Thus your algorithm is incomplete.
Bob Emmett CSS: I don't intend to be a technical writing, I intend to be a software engineer.
It is a tutorial for beginners. My intention is to construct a tutorial website, mainly focusing on algorithms and small games that utilize those algorithms. That article is to get your foot in the door with the A* Path Finding Algorithm. I boil it down as simple as I can possibly make it so it is easy to understand. That is more important than listing the infinite details and possibilities. Such things belong is a comprehensive specification. My implementation is a bit more sophisticated, it is part of the GameFX library. It integrates with the TileMap components, and most functions automatically react to events in the TileMap so it is extremely easy to use as a library.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
-
It is a tutorial for beginners. My intention is to construct a tutorial website, mainly focusing on algorithms and small games that utilize those algorithms. That article is to get your foot in the door with the A* Path Finding Algorithm. I boil it down as simple as I can possibly make it so it is easy to understand. That is more important than listing the infinite details and possibilities. Such things belong is a comprehensive specification. My implementation is a bit more sophisticated, it is part of the GameFX library. It integrates with the TileMap components, and most functions automatically react to events in the TileMap so it is extremely easy to use as a library.
Watch the Fall of the Republic (High Quality 2:24:19)[^] Sons Of Liberty - Free Album (They sound very much like Metallica, great lyrics too)[^]
CaptainSeeSharp wrote:
It is a tutorial for beginners.
And, applied to a simple 2D world, A* is a non-complex algorithm and easy for a beginner to comprehend. To present a beginner with a non-functioning algorithm is unhelpful.
CaptainSeeSharp wrote:
That is more important than listing the infinite details and possibilities.
It is a pathfinding algorithm, it either finds a path or it doesn't, hardly infinite.
CaptainSeeSharp wrote:
My implementation is a bit more sophisticated
You mean that it includes the test to ensure that the path returned is actually the shortest?
Bob Emmett CSS: I don't intend to be a technical writing, I intend to be a software engineer.