Artificial Intelligence for Computer Games

Homework 1 tutorial.

Pathfiding: search algorithms.

Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2024/PA217/um/4.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2024/PA217/um/4_Pathfinding_Dijkstra.pdf
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/jaro2024/PA217/um/hw/Assignment_1_tutorial.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 additional slides 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 path length to the goal?

Předchozí
Následující