- Unity 2017 Game AI Programming(Third Edition)
- Ray Barrera Aung Sithu Kyaw Thet Naing Swe
- 323字
- 2021-07-02 19:14:12
Dijkstra's algorithm
While perhaps not quite as popular as A* Pathfinding (which we will cover next), it's crucial to understand Dijkstra's algorithm, as it lays the foundation for other similar approaches to finding the shortest path between two nodes in a graph. The algorithm was published by Edsger W. Dijkstra in 1959. Dijkstra was a computer scientist, and though he may be best known for his namesake algorithm, he also had a hand in developing other important computing concepts, such as the semaphore. It might be fair to say Dijkstra probably didn't have StarCraft in mind when developing his algorithm, but the concepts translate beautifully to game AI programming and remain relevant to this day.
So what does the algorithm actually do? In a nutshell, it computes the shortest path between two nodes along a graph by assigning a value to each connected node based on distance. The starting node is given a value of zero. As the algorithm traverses through a list of connected nodes that have not been visited, it calculates the distance to it and assigns the value to that node. If the node had already been assigned a value in a prior iteration of the loop, it keeps the smallest value. The algorithm then selects the connected node with the smallest distance value, and marks the previously selected node as visited, so it will no longer be considered. The process repeats until all nodes have been visited. With this information, you can then calculate the shortest path.
Need help wrapping your head around Dijkstra's algorithm? The University of San Francisco has created a handy visualization tool: ;https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html.
While Dijkstra's algorithm is perfectly capable, variants of it have been developed that can solve the problem more efficiently. A* is one such algorithm, and it's one of the most widely used pathfinding algorithms in games, due to its speed advantage over Dijkstra's original version.
- Vue.js 3.x快速入門
- Computer Vision for the Web
- Visual Basic程序開發(學習筆記)
- Python Game Programming By Example
- jQuery從入門到精通 (軟件開發視頻大講堂)
- Scratch 3.0少兒編程與邏輯思維訓練
- EPLAN實戰設計
- Mathematica Data Analysis
- Mastering Android Development with Kotlin
- Creating Mobile Apps with jQuery Mobile(Second Edition)
- Clojure for Machine Learning
- SignalR:Real-time Application Development(Second Edition)
- 交互設計師成長手冊:從零開始學交互
- Java EE輕量級解決方案:S2SH
- Android開發進階實戰:拓展與提升