Sunday, November 13, 2011

A* Path Finding in C++

So, I got curious this weekend and decided to code up an implementation of the A* Pathfinding Algorithm.

A nice ZIP file can be found here with the source code.

I followed the description found at Policy Almanac and it seemed to work perfectly. The main problems I had implementing the code were mostly race conditions (pain. in. the. rear. >.>) and making sure I didn't go over the bounds for my 2d array (segfaults! boo!).

Here's some example runs:
000/0000
00/1\000
0S010E00
00010000
00000000

S00/--00
0\-111\0
0001E1|0
0011\1|0
00000/00

S000000000
0\01110000
00\1010000
0/11010000
00\00/--00
000\-110E0




S00/--00000

|0/111\1100
0\0101|1100
111101|0000
000100|0010
0001111\110
00--\01|000
0/111\11\00
E00010-/000
^^ Does not seem so optimal - at the start it should go directly to the right, instead of going down.

S---0011000000000000000010000000000000000
1111\011000000001111110010000001111100000
00000\11110000001000000010000000000100000
00000|000100000010000000100000/---0100000
0000/111110000001000111110000/1111\011000
0000|10000000001100000000000/00001|000000
0000|1001111100110000/------000001|000000
0000|100000110000000/1111111110001|001100
0000|100000/00/-----0100\000010001|000000
0000|10000/1\-111111110/1\00010001|000000
00000\----010010000001/011\0010001|000000
0001111111110010E00111|0110\010001|000000
00000000000000100-\111|01000\11111|000000
0000000000000010000--/0010000----/0000000

Heh, that was fun.

EDIT: It seems like I did not maintain a priorityQ for the lowest cost F for open nodes, darn.....
EDIT 2: Which doesn't make a difference since I'm only picking the lowest F for iterating on. The only issue is, efficiency. Or lack of, thereof :)

No comments: