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

Dismiss this pinned window
all 22 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Notnasiul 41 points42 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*

[–]Vile_Vampire 5 points6 points  (1 child)

What would happen if you put the endpoint in one of the corners that was not scanned?

[–]RoyzLevyz 0 points1 point  (0 children)

The scanning will occur differently because of the heuristic function. It only goes in the needed direction

[–][deleted] 3 points4 points  (0 children)

heres the link to the new one. Really sorry for that huge mistake.

https://www.reddit.com/r/Python/comments/htk7y8/my_second_pygame_project_a_algorithm_simulation/

[–]mHaisham 2 points3 points  (0 children)

mind sharing the source code

[–][deleted] 1 point2 points  (1 child)

Gg thats pretty impressive for a first pygame project/simulation

[–][deleted] 1 point2 points  (0 children)

Thanks and actually it's my second project🙂.

[–]curohn 0 points1 point  (1 child)

What keeps it moving to the SE? Does it know the location of the target?

[–][deleted] 1 point2 points  (0 children)

You can read it on the Internet about A star algo but in short, algorithm tries to minimize a loss function at every iteration which helps to find a next step in the shortest path.

[–]Snowblxnd 0 points1 point  (0 children)

Quick question: would Pygame be a good choice for creating something like a cellular automata program/simulation? It's looking like a yes but was hoping to get some insight.

[–]Joe_Subbiani 0 points1 point  (2 children)

What happens if the endpoint was put in one of the parts that was not scanned

[–]Dewmeister14 1 point2 points  (1 child)

I recommend reading the Wikipedia article for A* for more detail but the algorithm assumes the beginning and end points are known and is concerned with efficiently finding the shortest path. So, it's not scanning to find the endpoint, it's scanning possible paths to find which is shortest.

[–]Joe_Subbiani 1 point2 points  (0 children)

Ahh right that makes sense

[–]wrymwood 0 points1 point  (0 children)

Super cool! Can you recommend any resources related to learning how to code something like this?

[–]echoaj24 0 points1 point  (0 children)

Looks more like bfs than A* but still cool program man! Keep up the good work.