In platform videogames, players are frequently tasked with solving medium-term navigation problems in order to gather items or powerups. Artificial agents must generally obtain some form of direct experience before they can solve such tasks. Experience is gained either through training runs, or by exploiting knowledge of the game's physics to generate detailed simulations. Human players, on the other hand, seem to look ahead in high-level, abstract steps. Motivated by human play, we introduce an approach that leverages not only abstract "skills", but also knowledge of what those skills can and cannot achieve. We apply this approach to Infinite Mario, where despite facing randomly generated, maze-like levels, our agent is capable of deriving complex plans in real-time, without relying on perfect knowledge of the game's physics.