There is a game called "Flow Free". I found it to be highly addictive, and thought it would be fun to remake it in 3D. To do so requires the ability to generate the levels automatically and check the generated levels to ensure that it is possible to solve. To start, I want to create a 2D solver. This poses quite a challenge. It appears simple, but the requirements of the game make this quite difficult. All cells must be visited and no two paths can cross.
Here is a 9x9 cell level and its solution:
The solution would break most path finding algorithms, and I'm not sure this really is a problem that a path finding algorithm would be best suited for anyway. While playing the game slowly and consciously thinking out the moves, I came to realize that I was actually solving for each different path while actively working on a single path. This leads me to think it is more of an AI issue than a simple path finding issue.
Take the magenta path as an example. The correct solution is not one that would be found via any path finding algorithm. A shorter path would be selected, but any other path would block out the red, brown and green paths. This means that while solving for the magenta, the algorithm must also be solving for the other paths. Even so, it is possibly to solve some levels without visiting all of the cells. This requires some rather highly serpentine routes that wouldn't be obvious from an algorithmic standpoint.
I haven't started coding, but I'm not sure how to begin. How would I go about this? The logic to code this escapes me at the moment.