Thread: Pathfinding

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    30

    Pathfinding

    Hi

    I need help coming up with an algorithm that that travels a predetermined path from point A to B. I'm not interested in the A* algorithm or anything with linked lists, I just need to use simple loops.

    It's a pretty complex program. I'm supposed to search through a 2d array, there are obstacles which I need to check for, I need to check all the adjacent cells from the focus cell and decide which path to travel according to costs i.e vertical and horizontal paths cost 10, while diagonal costs 14.

    Again, I'm not looking for a solution. Just tips where to begin or maybe even a pseudocode will be appreciated.

    Thanks

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    So basically you want the A* algorithm without calling it the A* algorithm? I mean, what you described pretty much matches exactly the definition of the A* algorithm. Can I ask why you're avoiding it?
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Assuming your algorithm knows the start and end points (versus only knowing when you've reached the end point -- having to "discover" it), you can work backwards from the goal, expanding recursively on all 8 neighbors, calculating the cheapest cost-to goal. I'll let you ponder the details.

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    30
    Quote Originally Posted by itsme86 View Post
    So basically you want the A* algorithm without calling it the A* algorithm? I mean, what you described pretty much matches exactly the definition of the A* algorithm. Can I ask why you're avoiding it?
    Sorry, I just read a few examples of the A* algorithm and they all used linked lists. I just thought that's the only way it's done.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by nasser View Post
    Sorry, I just read a few examples of the A* algorithm and they all used linked lists. I just thought that's the only way it's done.
    No, you don't have to use linked lists for A.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by nasser View Post
    Sorry, I just read a few examples of the A* algorithm and they all used linked lists. I just thought that's the only way it's done.
    No, you don't have to use linked lists for A.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fun with pathfinding
    By BobMcGee123 in forum Game Programming
    Replies: 11
    Last Post: 06-15-2006, 02:28 PM
  2. A* pathfinding: Has anyone here used it?
    By Stan100 in forum Game Programming
    Replies: 2
    Last Post: 10-11-2003, 01:46 PM
  3. AI (Pathfinding)
    By jdinger in forum Game Programming
    Replies: 7
    Last Post: 04-16-2003, 10:20 AM
  4. A* pathfinding
    By minesweeper in forum C++ Programming
    Replies: 3
    Last Post: 11-30-2002, 04:56 PM
  5. AI (pathfinding) tutorial
    By dirkduck in forum Game Programming
    Replies: 3
    Last Post: 02-09-2002, 12:04 PM