0
\$\begingroup\$

I have created a procedural level generator in unity. However, occasionally the algorithm creates a level that is impossible to solve. Therefore, I tried to implement a navmesh agent to check if it is possible to get from the start to the end. However, it seems the agent really doesn't work with procedurally generated levels. I used the github repository to try and bake the navmesh during runtime, but it didn't work as intended. Half the levels that were actually solvable the agent said weren't and vis versa. (I've double checked everything).

The levels consist of a flat cube for the floor, and multiple un-climbable cubes placed throughout to be walls. The end result mimics a maze.

Does anyone know of any other algorithms that can be used to check if it is possible to get from a to b on a flat 3d plane? Thanks in advance.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ What can you tell us about the content of your levels and how you generate them? The more we know about the kinds of obstacles to expect, the more efficiently we can determine whether they block the desired path. \$\endgroup\$
    – DMGregory
    Oct 21 '21 at 3:05
  • \$\begingroup\$ Ok. I've edited it to provide more detail \$\endgroup\$ Oct 21 '21 at 3:08
  • \$\begingroup\$ Are you building these cubes on a grid? If so, this is a trivial graph search. \$\endgroup\$
    – DMGregory
    Oct 21 '21 at 3:09
  • \$\begingroup\$ I can build then into a grid if it makes it easier. What should I research to achieve a graph search? \$\endgroup\$ Oct 21 '21 at 3:11
  • \$\begingroup\$ An alternative approach to this problem could be to use a different procedural generation algorithm which is guaranteed to only generate solvable mazes. Many maze generation algorithms have this property. \$\endgroup\$
    – Philipp
    Oct 21 '21 at 7:04
0
\$\begingroup\$

This is just a connected component search - depth-first search is probably the easiest to get up & running.

Create a 2D array to keep track of which cells contain obstacles: bool[,] isObstacle. Each time you place an obstacle cube, set its corresponding entry in the array to true.

Then you can check whether the starting cell can reach the goal cell with something like:

// List the valid moves we can take from a particular cell coordinate.
static readonly Vector2Int[] neighbours = new Vector2Int[] {
    new Vector2Int(1, 0), new Vector2Int(0, 1), new Vector2Int(-1, 0), new Vector2Int(0, -1)
};

public bool IsReachable(Vector2Int start, Vector2Int end, bool[,] isObstacle) {
    int width = isObstacle.GetLength(0);
    int height = isObstacle.GetLength(1);
    var hasBeenVisited = new bool[width, height];

    // Keep a set of reachable cells to explore.
    var openSet = new Stack<Vector2Int>();

    // Initialize that set with our starting position.
    hasBeenVisited[start.x, start.y] = true;
    openSet.Add(start);

    // As long as we have reachable cells to check, 
    // recursively search them and their reachable neighbours.
    while (openSet.Count > 0) {

       // Remove a reachable cell from our open set, and check if it's the goal.
       var parent = openSet.Pop();
       // If so, we're done.
       if (parent == end) return true;
       
       // Otherwise, check what cells we can reach from here.
       foreach (var neighbour in neighbours) {
           var child = parent + neighbour;

           // Skip cells that are out of bounds.
           if (child.x < 0 || child.y < 0 || child.x >= width || child.y >= height)
               continue;

           // Skip cells we've already visited, or that are unnavigable.
           if (hasBeenVisited[child.x, child.y] || isObstacle[child.x, child.y])
               continue;

           // Mark this cell as visited and add it to our open set to investigate
           // more deeply when we get around to it.
           hasBeenVisited[child.x, child.y] = true;
           openSet.Push(child);
       }
    }

    return false;
}

You can optionally speed this up using A* to bias the search in the direction of the goal, but for small maps the basic depth first approach is good enough.

This is extremely basic, 1st year computer science material. So if this is unfamiliar to you then you may want to take some online classes to get ramped up on the fundamentals.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks! I'll give it a try \$\endgroup\$ Oct 21 '21 at 3:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .