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!
Quote this message in a reply
Moderator
Posts: 771
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... Rasp
Quote this message in a reply
Moderator
Posts: 3,572
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.
Blink 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.
Quote this message in a reply
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!
Quote this message in a reply
DoG
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... Rasp

You're trying to trick everyone with bad wording Smile
Quote this message in a reply
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.

http://studentpages.scad.edu/~bwalte21/Firefight.dmg

Thanks again, to everyone here at iDevGames.
Quote this message in a reply
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
Quote this message in a reply
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.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  finding a training center - Heeeelp Glauter 1 2,895 Dec 26, 2011 12:30 PM
Last Post: zenkimoto
  Finding an object by name markhula 2 4,495 Mar 29, 2011 08:08 AM
Last Post: markhula
  Drawing a path in-game GregX999 3 3,420 Dec 1, 2010 07:16 AM
Last Post: GregX999
  Kind of a noob question - finding artwork within my .app?? Nethfel 2 2,761 Mar 8, 2010 08:00 AM
Last Post: AndyKorth
  Finding the height of a point on a given list of vertexes? mikey 10 5,221 Jan 4, 2010 05:36 AM
Last Post: mikey