Development adventures

The wrong way to A*

If you haven't had the pleasure of watching Daniel Shiffman struggle through an algorithm, you're in for a quite a treat. ( There is a certain satisfaction in watching other developers try to code and explain a problem at the same time. Sometimes with hilarious results. Personally, watching somebody code helps me understand his/her perspective and approach to solving the problem. Almost every time I run into a "huh" moment where I learned a new technique.  I figured this would be a good moment to give his approach a shot and see what I end up with. With that here is my attempt at doing his A* solution, but in c++. 

The solution:


Few examples of goofy code:

Leap of faith?    Magic Diagonal Jumps   Success

First two images made some magic leaps due to two pretty big bugs:

  • I incorrectly linked neighbors which lead it to wrong directions. I have a constant problem of mentally trying to map a grid by [x][y] but in reality its always [y][x] and that is the reason I need to stop mapping a 2D grid to x and y (GRRR).
  • Manhattan distance was no friend. Also typo in the math didn't help either.

Issues that I'll get to (shortly):

  • While it finds a path, the last one isn't rendered blue ....  :\
  • My stop can get rendered as a wall but it isn't.
  • Grid lines have a bit of overlap.
  • Clean up, optimize the search code for open and closed sets.

This was created in VS 2019. At some point in the future I'll work on setting up cmake and correctly link SDL2 library. If you want to build this, you can update your library folder or just copy your libs and includes to c:\src\sdl2\  (Windows folks)

Comments are closed

Copyright © 2020 - Design by Francis