Creating a algorithm for a game field

Question

I am currently searching for a way to check if every field is reachable and if so if there is a way to reach every field without using a field twice. My current thought is to just try to start in every direction and use used fields as new walls. If the roboter gets stuck, he restarts and goes into another direction. But I am not sure if this is going to work. What about the performance? Does this even work?

The world/walls and the roboter's position are random. The roboter mustn't use a field, which he used before.

Here is an example image.

Answer 1

Depending on your input you could maybe use a breadth first search algorithm that searches through the world having the robots starting position as the root of the tree. Typically with BFS you remember which 'nodes' or tiles in this particular situation you have already seen. When the algorithm terminates you can check if the list of visited nodes is equal to the list of nodes you want to reach.

I think you could do this if for every tile you know which are the adjacent nodes (by reference for instance).

Answer 2

The reachability of all cells is easy, just a boolean matrix "reachable" for every cell, propagate connexity information starting from robot starting position, make sure all cells end up marked. This is linear to the world size so no issue there.

For the non redundant path, basically you need a heuristic, since as already mentioned in other answers the Hamiltonian path problem is NP. Then you write a BFS or DFS traversal of the search space looking for winning paths.

I used the following heuristic that scales pretty well on the "chessboard horse" where with a chess "knight" you have to cover all positions on the chess board. If you look at it in a topological light, it is really the same problem as yours.

So, the heuristic :

• in each cell count the number of ways you can get out of it. Store this info in a matrix. So a middle cell gets 4, a cell next to a wall only 3 etc...
• at each decision point in your DFS, select the next cell as the one with the least number of exits (This is the core of the heuristic)
• if two adjacent cells are at 1 outgoing exit, backtrack, the problem is dead along this branch
• when you enter a cell decrement exits of adjacent cells

rinse and repeat

This is just guiding the exploration, which remains in high overall complexity if you are unlucky.

Intuitively, it's good to go to areas with less exits right now, since it will be more difficult to come back to them later. The 2 cells with 1 exit rule is just an optimization, but it can prune large subtrees which is good. You can also backtrack if you detect unvisited cells with 0 exits depending on where you place the test.

I had this heuristic easily spitting lots of solutions even on larger chessboards than the classic 8x8.