u/richardathomein r/compsci • Recommends
On “A* vs BFS in snake game”
It's pretty much the gold star in gaming for finding the shortest path between two points in a graph:
https://en.wikipedia.org/wiki/A\*\_search\_algorithm
[video
0:00 / 0:00
#a-starsearch#dijkstra#pathfinding
A* (A Star) Search Algorithm - Computerphile
Computerphile
2.6M subscribers • 87 videos on Hallway
- Recommended by 2 people: 2 in engineering communities.
- Presented by Dr. Mike Pound, University of Nottingham
- May be out of date. Uploaded 9 years ago, in an area where tools change fast.
Beginner. No background in the topic needed.
1.3M views9 years ago2 recommendations
Computer scienceGame developmentAlgorithmsGame programming
Dr. Mike Pound explains the A* search algorithm, showing how it improves on Dijkstra's algorithm by using heuristics to find the shortest path.
Improving on Dijkstra, A* takes into account the direction of your goal. Dr Mike Pound explains. Correction: At 8min 38secs 'D' should, of course, be 14 not 12. This does not change the result. Dijkstra's Algorithm: youtu.be/GazC3A4OQTE How GPS Works: youtu.be/EUrU1y5is3Y facebook.com/computerphile twitter.com/computer_phile This video was filmed and edited by Sean Riley. Computer Science at the University of Nottingham: bit.ly/nottscomputer Computerphile is a sister project to Brady Haran's Numberphile. More at bradyharan.comWhy it's here
2 people recommend thisWhat people say. Recommended as a gold standard explanation of pathfinding and graph traversal algorithms.
Moments people linked to
u/AsyncDopaminein r/swift • Recommends
On “How do I Create a Loop in Swift?”
This sounds like a graph traversal problem. Where the intersections of walk-able paths are the vertexes and the paths are edges. You could traverse from the starting location, avoid previous vertexes, then maybe use something like A\* to return back to the starting location.
You could look at https://en.wikipedia.org/wiki/Graph\_traversal and https://en.wikipedia.org/wiki/A\*\_search\_algorithm to start. Then maybe watch this video to understand route finding [video Maybe there is a library which can help with this.
u/bart2019in r/programming • Mentions
On “Factorio's new pathfinding algorithm-- how a video game studio upgraded their heuristic for A* pathfinding”
introduction to A* (14 minute video)
u/AlfredoTheHamsterin r/programming • Mentions
On “Best explanation & visualisation of A* Path Finding”
For me, the you tube video A* (A Star) Search Algorithm - Computerphile is what made it finally 'click'