# Pathfinding

• 05-19-2011
nasser
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
• 05-19-2011
itsme86
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?
• 05-19-2011
anduril462
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.
• 05-19-2011
nasser
Quote:

Originally Posted by itsme86
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.
• 05-20-2011
iMalc
Quote:

Originally Posted by nasser
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.
• 05-20-2011
iMalc
Quote:

Originally Posted by nasser
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.