Looking for some clarification as I cannot seem to get an answer. When writing an astar algorirthm for grids, I was wondering if it was meant to work with any size rectangle or just perfectly square grids? If there is a specific method for handling the heuristic for rectangles, what is it?
If people need to know I’m writing it in C++ for use in UE4.
Thanks everyone!
No, A* doesn't need a grid at all. You can use any placement of nodes, and as long as your heuristic is admissible, A* should work.
In fact, if you can guarantee your heuristic is admissible (i.e., it is guaranteed to never overestimate the distance), your nodes don't actually need a position at all. Of course, many actual applications do have nodes with particular locations, and Euclidean distance is a convenient admissible heuristic.
The only thing you need to do to make a rectangular grid work is to make sure your metrics are correct. That is: your node-to-node distances and your Euclidean distance calculation must correctly reflect the horizontal and vertical spacing of your grid.
