Having a lot trouble implementing A*

[benbalach]

Hi guys. I'm applying for an internship and they asked me to create a maze solver program that uses recursive backtracking to solve the maze. I did that, sent it, and now they want me to have the program solve the maze using the shortest path. I've been stuck on this for about 2 weeks now. It took me 1 week to understand how the A* algorithm works (I read so many articles and watched so many videos on YouTube and I can't say I understand it fully), and another week to try and implement it. I made the necessary adjustments to my code and rewrote the algorithm pseudocode from

http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode

I have no idea if my code works at all and I don't know how to reconstruct the path found by algorithm. I have never been stuck on a project for this long and I have never felt this lost ever. Here's the code:

MinGW on Code::Blocks

https://www.dropbox.com/s/bjpxqzx5nwojp4n/Maze%20GCC.rar

or

MSVS 2013

https://www.dropbox.com/s/kljheyllccve7xj/Maze%20MSVS.zip

After I got the hang of A* I realized how widely used it is (Google Maps, game AIs, etc..) and how important it is and that's why I really want to understand it.

Could you guys tell me if you on the right track and if my code works at all and how to reconstruct the path?

Thanks in advance!

[Smac89]

What directions are valid in the maze? In the documentation you say 8 -> N, S, E, W, NE, NW, SE, SW. But in your code you have an enum declared directions with only 4 available:

enum class Direction { up, down, left, right };

[benbalach]

I had them before, but then I removed them because it didn't make sense for a maze. I forgot to update the documentation.

[Smac89]

Please enter the name of the maze file to load:
sample3.txt
Please enter an output file name for the solution:
Out.txt

Is maze solveable:
P X P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P
P X X X P X X X X X X X X X X X X X X X X X X X X X X X X X X X P
P T P X P X P P P P P P P P P P P P P P P P P P P P P P P P P X P
P T P X X X P T P T T T T T T T T T T T T T T T T T T T T T T X P
P T T P P P P T P P P P P T T T T T T T T T T T T T T T T T T X P
P P T P T T T T P T T T T T T T T T T T P T T T T P T T T T T X P
P T T P P P T T P T T T P P P P P P P P P T T T T P T T T T T X P
P T P P P P T P P P P P P P P P P P P P P P P P P P T T T T T X P
P T P P P P T P P P P T T T T T T P T T T T T T T P T T T T T X P
P T P P P P P P P P P T T T T T T P P P P P P P T T T T T T T X P
P T T T T T T T T T T T P P P P P P P P P P P P P P T T T T T X P
P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P X P
true

Please enter the name of the maze file to load:
sample2.txt
Please enter an output file name for the solution:
Out.txt

Is maze solveable:
T T T T T P P P P P
P P P P P X X X X X
X X X X X X P T P P
P P P P P T P T T T
T T T T T T P T T T
P P P P P P P P T T
true

Please enter the name of the maze file to load:
sample1.txt
Please enter an output file name for the solution:
Out.txt

Is maze solveable:
P P P P P P P P P P P P P P P P P P P P P P P P X P P P P P P P P P P P P P P P P P P P
T T T T T T T T T T T T T T T T T T T T T T T P X X X X X X X X X X X X X X X X X X X P
P P P P P P P P T P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P X P
P T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T X P
P T P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P X P
P T X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X P
P P X P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P
true

X's mark the path from start to finish

Most of the code has been changed, but you will still recognize some of your work in there. If you have a hard time following the logic, I can explain some things to you.

https://dl.dropboxusercontent.com/u/69324346/Maze%20MSVS.zip

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

[benbalach]

@Smac89

THANK YOU SO MUCH! You have no idea how much this helped me! My attempt was so wrong, I didn't know what I was doing. Your code is very readable and I understand you logic fully (and most of the time I don't understand other peoples code at all). Now I'm starting to understand A* a bit more. Thanks again for taking the time and explaining everything to me!