Creating a algorithm for a game field

 

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. 在这里输入图像描述

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

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.

    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.

    链接地址: http://www.djcxy.com/p/29060.html

    上一篇: elasticsearch匹配搜索查询中来自文档的所有单词

    下一篇: 为游戏领域创建一个算法