Pages: [1]   Go Down

Author Topic: Path Finder  (Read 3945 times)

Offline Spikerocks101

  • Hero Member
  • *****
  • Posts: 711
Path Finder
« on: June 11, 2009, 07:15:45 PM »
I am making a strategy game in my own time (first real task i am been taking on in C++, hint, i am using C++), and am stuck on the path finder. My path finder is a very crappy one that really only does simple path finds. All it does is see if current x = target x, cy = ty, if not, if x + 1 is clear, x = x + 1 and so on, and it gets stuck at corners easily. How then should i do a path finder? I am pretty sure this is a deep topic, and theres 100 ways of doing it, but I just need one way so my units get there, it doesn't need to be the easiest way (I could always add a better way as a Robot Command Center type upgrade). Thanks.
Logged
I AM YOUR PET ROCK!!!!!!

Offline Kayedon

  • Sr. Member
  • ****
  • Posts: 378
Path Finder
« Reply #1 on: June 11, 2009, 11:42:28 PM »
Logged
"Trust me, I'm crazy."

Offline Spikerocks101

  • Hero Member
  • *****
  • Posts: 711
Path Finder
« Reply #2 on: June 12, 2009, 06:17:50 PM »
I guess i should look into them, but not this week, got exams :P
Logged
I AM YOUR PET ROCK!!!!!!

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Path Finder
« Reply #3 on: June 12, 2009, 11:51:27 PM »
You're going to want to learn about A* as a starting point. Maybe some of the more general ones too like breadth first search, or depth first search. The breadth first and depth first searches are general and will work on any "graph". The A* algorithm is basically a modified breadth first search that is optimized to work on more specific data sets with an easily defined metric function, such as on a grid. (The metric on a grid is usually the euclidean metric, but can be something different such as the manhattan metric).


That first link is garbage. The algoritm posted there is basically wonder around aimlessly until you just happen to randomly bump into the end point. Note exactly a great algorithm. The other two seem to be based on A*.
 
Logged

Offline Spikerocks101

  • Hero Member
  • *****
  • Posts: 711
Path Finder
« Reply #4 on: June 13, 2009, 07:30:28 PM »
I really don't know what you typed Hooman :( I understand something about planning your way with a grid, but I didn't understand what you typed, except the last pary. Is "A*" something, or are you listing things like "A*", "B*", "C*"? I remember hearing something about something called pointers (I know you know what pointers are, I just have a rough idea about what they are) where you type things like "A*" for the pointer location. I would thing path finding has something to do with collision detection, so if you have something to teach me, or have a book to recomend (mind you, my game lacks collision detection but instead uses a massive grid, and 1 means that spot has an object there, 0 means it doesn't, kinda collision dection). Sorry if I ask to much/hard to understand.
Logged
I AM YOUR PET ROCK!!!!!!

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Path Finder
« Reply #5 on: June 13, 2009, 07:59:34 PM »
A* (A Star), is a path finding algorithm. (It has nothing to do with pointers).  If you google for it, you will find tons of references. If you grab any book on Game AI, you will probably find A* in it. (Well, particularly if the book is for RTS games, but many other games make use of it too).

If that is hard to understand, you can also try reading about Breadth first search. That is another path finding algorithm, but it was designed to work on a graph (a set of edges (lines) and verticies (points), not a 2D plot). A grid, is a special case of a graph. In a grid, each vertex has 4 edges (or 8 edges if diagonal links are allowed), which connect it to it's neighboring vertexes.

Algorithms like A* make use of this extra information about the regularness of the grid to direct the search towards the goal, rather than expanding out in all directions until it hits the goal. Breadth first search just expands in all directions at once, where the next node to process is the current closest to the start of the search. A* gets the information about where to expand from the metric function. This is basically just using the fact that a grid is regular, and you know where a vertex's possible neighbors are without having to ask it. The breadth first search doesn't make any such assumptions.
 
Logged

Offline Spikerocks101

  • Hero Member
  • *****
  • Posts: 711
Path Finder
« Reply #6 on: June 14, 2009, 05:47:06 AM »
Okay, thank you. Your are programming god. ALL HAIL THE C++ MESSIAH!!! :P
Logged
I AM YOUR PET ROCK!!!!!!

Offline Hidiot

  • Hero Member
  • *****
  • Posts: 1018
Path Finder
« Reply #7 on: June 14, 2009, 06:29:24 AM »
He's not the only one who knows about A* and other path finding algorithms. Because those are pretty common knowledge, the way I know it.
Logged
"Nothing from nowhere, I'm no one at all"

Offline Spikerocks101

  • Hero Member
  • *****
  • Posts: 711
Path Finder
« Reply #8 on: June 14, 2009, 09:50:52 AM »
I know, but I call him that becuase he almost always responds when some one has a programming question... if you awnsered first, you would be the Idiot God :P
Logged
I AM YOUR PET ROCK!!!!!!

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Path Finder
« Reply #9 on: June 14, 2009, 01:48:23 PM »
How motivating.

But just for the record, I find being called things like that rather offensive.
 
Logged

Offline Fenrisul

  • Full Member
  • ***
  • Posts: 153
Path Finder
« Reply #10 on: June 14, 2009, 04:28:22 PM »
Quote
How motivating.

But just for the record, I find being called things like that rather offensive.
Good man :)


Anyway

http://www.policyalmanac.org/games/aStarTutorial.htm

here is probably the best A* tutorial on the net.  Very simple to read - and it has pictures.
Logged

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4955
Path Finder
« Reply #11 on: June 14, 2009, 05:53:36 PM »
That article looks fairly good. I didn't read all of it, but he does seem to know what he is talking about, and did bring up some very good points.

Plus, the pictures are nice. They seem to show the direction from which the nodes were expanded to.
Logged
Pages: [1]   Go Up