Yes, this exactly is what I was thinking when looking for a way to solve mazes by divide-and-conquer, and my own studies about AI.
This is your point. You assume that there is an optimal path between points A and B of a given game. Then, if there is a point in-between, C, in the optimal path, then the optimal path from A to C, and the optimal path from C to B appear in the optimal path from A to B.
This property work only if these segments are independent (or just slighty dependent, with some luck), but could be enough for some games.
But you must know that some optimal paths do sequence-breaking, so instead of a stream-lined game, you would have a graph (or a labyrinth), in which you could reach the same point from different places. You can't assume beforehand that your optimal path to B will pass from a given point C (just like mazes). You just know that it has to pass from one of the paths that reach B.
A. To solve this maze:
############
...##....#.#
#.#...##.#.#
#.#.#.#....#
#.#.#.#.####
#...###..#..
#.##...#...#
#....#..####
#.#####....#
############
These two maze must be solvable
A
############
...##....#.#
#.#...##.#.#
#.#.#.#....#
#.#.#.#.####
B
#...###..#..
#.##...#...#
#....#..####
#.#####....#
############
And their solutions must be connected.
Of course, you can keep partitioning the labyrinths until they are trivial problems, and then interconnect them. But this wastes a lot of time solving parts that won't be part of the main solution. On the other side, many computers may work at the same time on different parts of the main problem.
Those sub-labyrinths show that there can be multiple solutions to a single segment, but there is maybe only one that can be connected to the next sub-labyrinth.
There can be many starts to a single segment, too. In games, this will be starting the segment with different values of: lives left, ammo, starting position, items equipped, etc...
So, the same segment must be solven min-maxing those variables until they are no longer solvable: that way, you get the min time needed to pass the segment (wasting any number of resources), and to know the min values required to pass the segment, (though maybe losing time).
Some segments are highly dependent of others. For example, there is a trigger in Prince of Persia 2 (PC Game) that creates a skeleton on the bridge that triggers another event which makes you lose your sword. There's a way to pass without activating the trigger, and thus the skeleton is never created. The path to solve that segment changes drastically. If you don't know beforehand about that trigger/glitch, you could end with a sub-optimal path.
Note: If you pass the bridge without losing your sword, the next level is a lot more easy. Though, you need to move very quickly in order to pass.
