The Algorithm Design Manual Second Edition

Stop and Think: The Pink Panther’s Passport to Peril

Problem: “I’m looking for an algorithm to design natural routes for video-game

characters to follow through an obstacle-filled room. How should I do it?”

Solution: Presumably the desired route should look like a path that an intelligent

being would choose. Since intelligent beings are either lazy or efficient, this should

be modeled as a shortest path problem.

any pair of nearby vertices, weighted proportionally to the distance between them.

Although direct geometric methods are known for shortest paths (see Section

15.4

(page

489

)), it is easier to model this discretely as a graph.