question about results

[PcChip]

Hi,

Thanks for the awesome code!

I have a question, this is the first A-Star I have ever implemented, and I'm getting these winding results
instead of a straight line - is this normal for A-Star?

https://i.imgur.com/g113sCK.png

note: entire map is initialized to a cost of 1

thanks again for any suggestions you might have

edit: with the entire map initialized to a cost of 0, I get this even stranger result : https://i.imgur.com/3UuJWLk.png

looking for it to be a straight line unless there are obstacles, any ideas?

[justinhj]

Setting the cost to zero is not great because it prevents any objective measure of how good each node is. Every node effectively is just as near to the goal as any other.

Setting the cost to 1 is fine, and your algorithm is probably working fine despite the weird L shape. So why is it an L shape? Well assuming you can only move horizontally and vertically on the grid, one of the optimal routes is to simply move left the number of times you need to, then up the number of times you need to and you arrive at the goal. There's no difference between going:

UP RIGHT UP RIGHT UP RIGHT

vs

UP UP UP RIGHT RIGHT RIGHT

So what's the solution? Either allow your path to move diagonally, in which case you should get a straight line from the start to the goal, or when expanding nodes you can choose to investigate the ones that are more 'towards' the goal first (using trigonometry for example), or you can actually bias the cost of nodes as they move further from the direct path to the goal.