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

I've implemented something like this here to solve a puzzle known as the "Knight's Tour". I believe the problem should pretty much involve the same logic with a few minor modifications.

Rather than talking about traversals, I will try to make this more generally accessible - From any given point, to answer the question "what is the next best move?" you want to think a step further and ask: "what is the most limiting factor?" In this case, the most limiting factor, based on your next available moves, is how many moves are available from each of those moves. Each of your next available moves will have its own set of next available moves. The next available move(s) with the least number of their own next available moves are your most limiting factor(s).

So, for instance, let's say I have moves x, y and z available. Both x and z have 2 next available moves and y has 3 next available moves - you want to move to either x or z (it shouldn't matter which you decide on so you can just randomize it as I did in my code).

Why does this make sense? Think about it another way - the next available moves (x, y and z in our example) are all spots you have to get to at some point! The next available moves for x, y and z could also be considered ways you will get BACK to x, y or z. Since there are fewer ways to get back to x and z, you might as well go to one of them now. If x, for instance, only had 1 next available move (all other conditions unchanged) then x would be your only valid option (and as an optimization you could immediately go to x's next available move because you know there is only 1).

The code I provided has a lot of stuff you don't need to be concerned with, but it should be self contained so you should be able to pop it into a JSFiddle or html page and it should just work. The functions related to your question are getPossibleMoves, getAvailableMoves and getBestNextMove (and whatever functions these functions call). The interpolation point stuff in the getPossibleMoves function is D3 related and not something you need to worry about. The function simply calculates all the possible moves, based on the rules of how a knight is allowed to move, from a point (with x and y properties) and then simply evaluates each of these points to see if they're in bounds. It shouldn't be too hard to modify this function to fit your roboter's allowed moves and you will also need to update the function that checks if the point is in bounds to also disallow points where there are walls.

Disclaimer: I threw this code together for fun so it's not optimized or by any means an excellent sample of coding practices in JavaScript

Also note this is just one way to solve this problem. There are certainly other ways to solve it, but this is the most straightforward way I know of doing it.

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.

Answer 3

This problem can be modeled as a question of connectivity in a graph where we can run Depth First Search once on your maze and find every position reachable from the starting position where if any position that is not a wall/block and not visited after running DFS then you cannot reach this position from the starting position following any path in your maze.

Essentially you would need to represent every position in the game as a node in a graph where each node has flags for it's north, east, south and west walls. When you want to visit an adjacent position via an edge you can only do so if the adjacent positions wall is not up in the direction you are trying to come from. So all you need to do is make a modification to the DFS algorithm such that you can only visit/call dfs on an adjacent node if there is no wall.

void explore(Node position)
{
    position.visited = true

    while(position.hasUnvisitedDirection())
    {
        //random unvisited direction
        int direction   =   position.getDirection();

        if(direction == WEST && !west(node).visited && !position.westWall)
            explore(west(node));

        if(direction == EAST && !east(node).visited && !position.eastWall)
            explore(east(node));

        if(direction == SOUTH && !south(node).visited && !position.southWall)
            explore(south(node));

        if(direction == NORTH && !north(node).visited && !position.northWall)
            explore(north(node));

    }
}

Here we make a modification to DFS in that we select a random unvisited position at each position we visit. The east(Node), north(Node) etc. calls would return the position east, north respectively of the passed Node - be careful of edge cases in the grid (It's quite intuitive if you model the graph as a 2D array).

Next we want to check if the graph has only one strongly connected component and this will be the case if there is only one jump in our DFS, that is we will have a single tree in the depth first search forest and every position will be reachable from our starting position which is what you want. Otherwise those nodes not visited after running DFS will be unreachable and you can check for those positions after if the algorithm returns false. So the following should achieve this:

boolean isConnected(Graph g, Node startPosition)
{
    int jumps   =   0;
    for (Node node : g.nodes())
    {
        if(!node.visited)
        {
            jumps++;
            if(jumps > 1) return false;
            else explore(position);
        }
    }

    return true;
}

Depth first search can be used to generate and solve mazes as shown above.

Answer 4

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).