Artificial Intelligence for Computer Games

Pathfiding: search algorithms.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2023/PA217/um/4.pdf
Questions

  1. Why should we combine movement and pathfinding?
  2. What is a search problem? What types of search problems do you know?
  3. Define the base terminology related to pathfinding graphs.
  4. Describe graph representation using adjacency lists.
  5. Describe graph representation using the adjacency matrix.
  6. How would you represent a tile-based map? What is the waypoint graph?
  7. How is the graph explored by the breadth-first search algorithm? Describe the implementation of the breadth-first search algorithm. 
  8. How is the graph explored by the depth-first search algorithm? Describe the implementation of the depth-first search algorithm.
  9. Compare the breadth-first search algorithm and depth-first search algorithm.
  10. Describe the implementation of the Dijkstra algorithm.
  11. How would you implement the Dijkstra algorithm to compute the shortest path for all nodes?
  12. Discuss the exploration of the graph on slide 23 using the Dijkstra algorithm.
  13. Compare the differences between BFS, Dijkstra, greedy, and A* algorithms.
  14. Describe the implementation of the A* algorithm.
  15. What is admissible heuristics? Why is it important? What would happen if the heuristic overestimated the length of the path to the goal?
  16. What data structures are needed by the A* algorithm?
  17. What is the priority heap? Discuss the complexity of operations.
  18. What are the bucketed priority queues?

Předchozí
Následující