## Path Finding

Sage
Posts: 1,403
Joined: 2005.07
Post: #16
codemattic hit the nail on the head.

http://upe.acm.jhu.edu/websites/Benny_Ts....htm#Test3 Wrote:Section 3: The Heuristic Function
The success of A-Star rests heavily on the heuristic function chosen. For any given problem that we may wish to apply A-Star to, there are good heuristics and bad heuristics. A good one will allow the algorithm to run quickly and find the optimal solution. A bad one may just increase the running time. Or it may be so bad that it misleads the algorithm into returning sub-optimal solutions or not find solutions at all.

as the article sais that's only possible if the heuristic is not admissible, if your going to say A* always finds the shortest (or lowest cost) path then you must also state the conditions of the heuristic.

I think the reason for this misunderstanding is because of the way A* is generally taught as pathfinding on a square grid.
When I first learned it I thought for about a year doing an outwards fill from the ending node numbering all the grid squares increasingly until reaching the start, then going from the start toward the end following the smallest adjacent number.. was A*. Which is isn't its a step that gives you a heuristic for every square you will encounter.
There is a lack of sensible material about A* on the net and most of it is either highly theoretical or pathfinding on a square based grid.

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Moderator
Posts: 776
Joined: 2003.04
Post: #17
unknown Wrote:as the article sais that's only possible if the heuristic is not admissible, if your going to say A* always finds the shortest (or lowest cost) path then you must also state the conditions of the heuristic.

You mean the fact that the heuristic has to be less than or equal to the true cost of the path? I think I mentioned that on every post so far...
Moderator
Posts: 3,591
Joined: 2003.06
Post: #18
unknown Wrote:There is a lack of sensible material about A* on the net and most of it is either highly theoretical or pathfinding on a square based grid.
Look, I know I'm all mister bad-guy-of-the-week for you unkown, but seriously... `There is a lack of sensible material about A* on the net'...??? This sudden surge of invincibility you have been displaying lately is a little over the top.
Sage
Posts: 1,403
Joined: 2005.07
Post: #19
PowerMacX,
Yeah, the heuristic only has to be less than or equal to the true cost of the path to get the shortest/lowest cost path, A* is used a lot with non-admissible heuristics mostly too speed it up.

AnotherJake, what I mean is there's probably 50 decent pages about A* for every 3000 ones written by someone who just found out how to do pathfinding and though they could help people by explaining something they dont understand fully, leading other people to beleive A* is something else than what it really is.
At least this is my experience from learning it a couple of years ago, it was a couple of months later I discovered what it really is and what I thought was wrong.
As for a surge of invincibility, I really don't know what your talking about. I checked recent posts by you to see what 'bad-guy-of-the-week' stuff i'd been replying too, all I see is a post about crayon colors.

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Moderator
Posts: 869
Joined: 2003.01
Post: #20
PowerMacX Wrote:You mean the fact that the heuristic has to be less than or equal to the true cost of the path? I think I mentioned that on every post so far...

You're trying to trick everyone with bad wording
Apprentice
Posts: 19
Joined: 2005.11
Post: #21
Hey everyone... thanks for all the advice.. I've made many posts/threads in this forum, OpenGL, C++, getting advice on my game. And, well, today my project is due. No, it's not complete, but I figured I'd go ahead and share with all of you what I plan on turning in today.

Thanks again, to everyone here at iDevGames.
Apprentice
Posts: 19
Joined: 2005.11
Post: #22
Well that quickly killed off all discussions...

Well, anybody who downloaded it and played around with my game (see link above) have any suggestions on pathfinding with multiple units / collisions between units (when 1+ is moving?) That seems to be the biggest flaw in my game so far.

And for anybody else whose interested in seeing the game, you can download it above, or see this movie clip of it: http://studentpages.scad.edu/~bwalte21/my_rts_game.mov
Member
Posts: 254
Joined: 2005.10
Post: #23
You might try ignoring the positions of other units if it isn't important to your game, just deal with obstacles(trees or whatever) and buildings. It might make for some weird things sometimes, but if its just for a class that may not really matter.