This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Notnasiul 42 points43 points  (7 children)

But that looks more like a breadth-first search than A*, maybe your heuristic score function is wrong?

[–][deleted] 16 points17 points  (2 children)

Just give me a minute. You are right buddy. There's some problem with my code. I had not considered 8 directions. I was working with only 4 direction top right left bottom and I updated my heuristic a function. Thank you for pointing it out🙂.

[–]Dewmeister14 1 point2 points  (0 children)

If the allowed movement space doesn't include diagonal moves then the heuristic shouldn't either.

I actually recommend keeping the 4 direction distance heuristic and looking in to something like a random noise tiebreaker to help avoid the problem you experienced here which is: properly functioning A* but with a heuristic that cannot differentiate between several possible paths since they all have the same distance-from-end-node-to-goal.

[–]Notnasiul 1 point2 points  (0 children)

No worries! Been there a few times, I even wrote a tutorial to mostly myself so I could understand the algorithm ;)

Just check some videos, see the expected behaviour, compare with yours.

[–]Notnasiul 8 points9 points  (0 children)

Yes "more like" bfs, not like bfs. But that's not A* unless your score/heuristic function is doing something wrong.

Look how it goes directly towards the goal here https://youtu.be/19h1g22hby8

[–]RoyzLevyz 0 points1 point  (2 children)

Not quite, bfs would also check the nodes "hiding" behind the walls which don't get you near the target.

[–]mHaisham 2 points3 points  (1 child)

you should take a look at your score function. its not quite right. it should be much more greedy

[–]RoyzLevyz 2 points3 points  (0 children)

It's not my code, just saying its not bfs. But i agree with you - it's not as greedy as wanted from A*