Infinite Mario AI. This is from a few years ago, but I never got around to linking to it. There’s a great set of videos of a Super Mario World-like game being controlled by AI. Here’s some of an interview with its creator, Robin Baumgarten:
The main part of the heuristic is a simple time-constraint: try to get to the right of the screen as fast as possible. Therefore, the path-cost function is the spent time since the start of planning, and the heuristic is “given maximum acceleration, how long does it take to reach the goal”. As the distance to the goal isn’t known, an arbitrary (large) constant is used. In that sense, I’d say that the heuristic is not quite admissible (i.e. does not overestimate the cost to reach the goal), but because the overestimation is the same for the entire search space, this isn’t a problem. To avoid running into enemies or falling into gaps, a high penalty is added to the heuristic so that it does not get chosen as the next node by the search algorithm.
It’s stuff like this that got me into Computer Science and it’s stuff like this that keeps me here.