Pathfinding Peril

Pathfinding Robot Session from SC2012

Transcript

1. Pathfinding Peril Software Craftsmanship 2012 Chris Parsons and Steve Tooke Thursday, 14 June 12
2. Huh? What is it all good for... Absolutely nothing? Thursday, 14 June 12
3. Games Thursday, 14 June 12
4. Workshop Plan Introduction Graph Theory Pathfinding Algorithms The Maze Contest Thursday, 14 June 12
5. Graph Theory A B D C E F G Thursday, 14 June 12
6. 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. Thursday, 14 June 12
7. Shortest route from B to C A B D C E F G Thursday, 14 June 12
8. “Brute force” A B D C E F G Thursday, 14 June 12
9. “Brute force” A B D C E F G Thursday, 14 June 12
10. “Brute force” A B D C E F G Thursday, 14 June 12
11. Weighted graphs A B D E F G 3 3 17 2 2 3 22 1 C Thursday, 14 June 12
12. B - E - C will cost 19 A B D E F G 3 3 17 2 2 3 22 1 C Thursday, 14 June 12
13. ...but B-A-G-D-C is only 9 A B D E F G 3 3 17 2 2 3 22 1 C Thursday, 14 June 12
14. Dijkstra's Algorithm Published 1959 Uses an ordered set of open nodes, tracking minimum cost to each Thursday, 14 June 12
15. Shortest route from B to C A B D E F G 3 3 17 2 2 3 22 1 C Thursday, 14 June 12
16. 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 Thursday, 14 June 12
17. 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 Thursday, 14 June 12
18. 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 Thursday, 14 June 12
19. 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 Thursday, 14 June 12
20. 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 Thursday, 14 June 12
21. 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 Thursday, 14 June 12
22. Updated weights A B D E F G 3 3 17 2 2 3 3 1 C Thursday, 14 June 12
23. 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 Thursday, 14 June 12
24. 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 Thursday, 14 June 12
25. 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 Thursday, 14 June 12
26. 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 Thursday, 14 June 12
27. 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 Thursday, 14 June 12
28. 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 Thursday, 14 June 12
29. A* algorithm Published 1968 Variation on Dijkstra, using a heuristic to cut down on nodes to visit Thursday, 14 June 12
30. Distance Heuristic A 23 B 10 D 12 E 13 F 18 G 20 3 3 17 2 2 3 22 1 C 0 Thursday, 14 June 12
31. 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 Thursday, 14 June 12
32. 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 Thursday, 14 June 12
33. 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 Thursday, 14 June 12
34. 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 Thursday, 14 June 12
35. 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 Thursday, 14 June 12
36. 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 Thursday, 14 June 12
37. 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 Thursday, 14 June 12
38. 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) Thursday, 14 June 12
39. Summary Thursday, 14 June 12
40. Summary Brute force approach: O(n²) (ouch!) Thursday, 14 June 12
41. Summary Brute force approach: O(n²) (ouch!) Dijkstra: guarantees best path but still can be slow Thursday, 14 June 12
42. 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 Thursday, 14 June 12
43. 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* Thursday, 14 June 12
44. Your turn Visit http://172.31.31.25:3000 for the tournament We’ll run an overflow server if we need to The rules for the game are shown Rest of this session for practice (1m rounds) Proper contest will be 5m rounds after the break Thursday, 14 June 12
45. BDD Kickstart Matt Wynne + myself running our BBC courses publicly Central London, 16th - 19th July £450/day, use code SC2012 for 20% off http://bddkickstart.com Thursday, 14 June 12
46. Thanks! Chris Parsons @chrismdp - http://pa.rsons.org Steve Tooke @tooky - http://heavi.es Thursday, 14 June 12