Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Pathfinding Peril - BCS 2014

chrismdp
January 07, 2015

Pathfinding Peril - BCS 2014

Finding the shortest path through a connected graph is a complex problem, and one which has a number of very useful applications. Thankfully there are some efficient algorithms out there which solve it well. The first part of the session will take you through some basic theory and how the A-Star algorithm works.
In the second part, you will then put your newly-found pathfinding skills to the test! We'll run a tournament for the remaining hour and a bit, using a robot tournament engine. You'll be able to write a robot in any language, which will be one of two characters in a maze, and the idea is to find the exit as soon as possible without being eaten by the minotaur that roams randomly around it.

chrismdp

January 07, 2015
Tweet

More Decks by chrismdp

Other Decks in Programming

Transcript

  1. What is it all good for... Graphs can model internet

    networks, data organisation, computation flow, neural networks, the web, wikis, molecular structures, linguistics, social networks, biological habitats, transport networks, etc.
  2. B - E - C will cost 19 A B

    D E F G 3 3 17 2 2 3 22 1 C
  3. ...but B-A-G-D-C is only 9 A B D E F

    G 3 3 17 2 2 3 22 1 C
  4. Shortest route from B to C A B D E

    F G 3 3 17 2 2 3 22 1 C
  5. Visit B Node Cost B 0 A (from B) 3

    F (from B) 3 E (from B) 17 A B D E F G 3 3 17 2 2 3 22 1 C
  6. Visit A Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 E (from B) 17 A B D E F G 3 3 17 2 2 3 22 1 C
  7. Visit F Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 E (from B) 17 (25 is bigger) A B D E F G 3 3 17 2 2 3 22 1 C
  8. Visit G Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 D (from G) 8 E (from B) 17 A B D E F G 3 3 17 2 2 3 22 1 C
  9. Visit D Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 D (from G) 8 C (from D) 9 E (from B) 17 A B D E F G 3 3 17 2 2 3 22 1 C
  10. Visit C - we’re done! Node Cost B 0 A

    (from B) 3 F (from B) 3 G (from A) 6 D (from G) 8 C (from D) 9 E (from B) 17 A B D E F G 3 3 17 2 2 3 22 1 C
  11. Visit B Node Cost B 0 A (from B) 3

    F (from B) 3 E (from B) 17 A B D E F G 3 3 17 2 2 3 3 1 C
  12. Visit A Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 E (from B) 17 A B D E F G 3 3 17 2 2 3 3 1 C
  13. Visit F Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 E (from F) 6 A B D E F G 3 3 17 2 2 3 3 1 C
  14. Visit G Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 E (from F) 6 D (from G) 8 A B D E F G 3 3 17 2 2 3 3 1 C
  15. Visit E Node Cost B 0 A (from B) 3

    F (from B) 3 G (from A) 6 E (from F) 6 C (from E) 8 D (from G) 8 A B D E F G 3 3 17 2 2 3 3 1 C
  16. Visit C - we’re done! Node Cost B 0 A

    (from B) 3 F (from B) 3 G (from A) 6 E (from F) 6 C (from E) 8 D (from G) 8 A B D E F G 3 3 17 2 2 3 3 1 C
  17. Distance Heuristic A 23 B 10 D 12 E 13

    F 18 G 20 3 3 17 2 2 3 22 1 C 0
  18. Visit B Node Cost Order B 0 10 (0+10) F

    3 21 (3+18) A 3 26 (3+23) E 17 40 (17+13) A 23 B 10 D 12 E 13 F 18 G 20 3 3 17 2 2 3 22 1 C 0
  19. Visit F Node Cost Order B 0 10 (0+10) F

    3 21 (3+18) A 3 26 (3+23) E 17 30 (17+13) A 23 B 10 D 12 E 13 F 18 G 20 3 3 17 2 2 3 22 1 C 0
  20. Visit A Node Cost Order B 0 10 (0+10) F

    3 21 (3+18) A 3 26 (3+23) G 6 26 (6+20) E 17 30 (17+13) A 23 B 10 D 12 E 13 F 18 G 20 3 3 17 2 2 3 22 1 C 0
  21. Visit G Node Cost Order B 0 10 (0+10) F

    3 21 (3+18) A 3 26 (3+23) G 6 26 (6+20) D 8 20 (8+12) E 17 30 (17+13) A 23 B 10 D 12 E 13 F 18 G 20 3 3 17 2 2 3 22 1 C 0
  22. Visit D Node Cost Order B 0 10 (0+10) F

    3 21 (3+18) A 3 26 (3+23) G 6 26 (6+20) D 8 20 (8+12) C 9 9 (9 +0) E 17 30 (17+13) A 23 B 10 D 12 E 13 F 18 G 20 3 3 17 2 2 3 22 1 C 0
  23. Visit C - we’re done! Node Cost Order B 0

    10 (0+10) F 3 21 (3+18) A 3 26 (3+23) G 6 26 (6+20) D 8 20 (8+12) C 9 9 (9 +0) E 17 30 (17+13) A 23 B 10 D 12 E 13 F 18 G 20 3 3 17 2 2 3 22 1 C 0
  24. Non-admissible Heuristic A 23 B 10 D 12 E 13

    F 18 G 20 3 3 17 2 2 3 22 1 C 0
  25. Different Heuristics Dijkstra no heuristic A* exact distance (admissible) http://en.wikipedia.org/wiki/A*_search_algorithm

    http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm A* over-egging distance (non-admissible)
  26. Summary Brute force approach: O(n²) (ouch!) Dijkstra: guarantees best path

    but still can be slow A*: depending on Heuristic can trade speed for best path Admissible Heuristics (never overestimating cost) is the sweet spot for A*
  27. Your turn Wifi: BCS Guest Password: *** Visit http://10.30.22.75:3000 for

    the tournament The rules for the game are shown Rest of this session for practice (1m rounds) Proper contest will be 5m rounds after the break
  28. Sol Trader I’m a web programmer moved back into Games

    Running a Sol Trader Kickstarter this month http://soltrader.net