Wavefront Algorithm

Question

I am creating a maze program, where the maze is randomly generated, and the user has to find a randomly place cube. Now, I want to be able to allow the game to solve itself, using a wavefront algorithm, Dijkstra's algorithm, or an A* algorithm?

Here is the code for the generation of the maze walls.

    public void GenerateMaze()
    {
        for (int x = 0; x < mazeWidth; x++)
            for (int z = 0; z < mazeHeight; z++)
            {
                MazeCells[x, z].Walls[0] = true;
                MazeCells[x, z].Walls[1] = true;
                MazeCells[x, z].Walls[2] = true;
                MazeCells[x, z].Walls[3] = true;
                MazeCells[x, z].Visited = false;
            }
        MazeCells[0, 0].Visited = true;
        EvaluateCell(new Vector2(0, 0));
    }

    public void resetMaze()
    {
        for (int x = 0; x < mazeWidth; x++)
            for (int z = 0; z < mazeHeight; z++)
            {
                MazeCells[x, z].Visited = false;
            }

        RandomWalls(new Vector2(0, 0));
    }

    private void EvaluateCell(Vector2 cell)
    {
        List<int> neighborCells = new List<int>();
        neighborCells.Add(0);
        neighborCells.Add(1);
        neighborCells.Add(2);
        neighborCells.Add(3);

        while (neighborCells.Count > 0)
        {
            int pick = rand.Next(0, neighborCells.Count);
            int selectedNeighbor = neighborCells[pick];
            neighborCells.RemoveAt(pick);

            Vector2 neighbor = cell;

            switch (selectedNeighbor)
            {
                case 0: neighbor += new Vector2(0, -1);
                    break;
                case 1: neighbor += new Vector2(1, 0);
                    break;
                case 2: neighbor += new Vector2(0, 1);
                    break;
                case 3: neighbor += new Vector2(-1, 0);
                    break;
            }

            if (
                (neighbor.X >= 0) &&
                (neighbor.X < mazeWidth) &&
                (neighbor.Y >= 0) &&
                (neighbor.Y < mazeHeight)
                )
            {
                if (!MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited)
                {
                    MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited = true;
                    MazeCells[(int)cell.X, (int)cell.Y].Walls[selectedNeighbor] = false;
                    MazeCells[(int)neighbor.X, (int)neighbor.Y].Walls[(selectedNeighbor + 2) % 4] = false;
                    EvaluateCell(neighbor);
                }
            }
        }
    }

    //Removes random walls
    private void RandomWalls(Vector2 cell)
    {
        List<int> neighborCells = new List<int>();
        neighborCells.Add(0);
        neighborCells.Add(1);
        neighborCells.Add(2);
        neighborCells.Add(3);

        while (neighborCells.Count > 0)
        {
            int pick = rand.Next(0, neighborCells.Count);
            int selectedNeighbor = neighborCells[pick];
            neighborCells.RemoveAt(pick);

            Vector2 neighbor = cell;

            switch (selectedNeighbor)
            {
                case 0: neighbor += new Vector2(0, -1);
                    break;
                case 1: neighbor += new Vector2(1, 0);
                    break;
                case 2: neighbor += new Vector2(0, 1);
                    break;
                case 3: neighbor += new Vector2(-1, 0);
                    break;
            }

            //Ensures that end piece is not deleted
            if (
                (neighbor.X >= 0) &&
                (neighbor.X < mazeWidth) &&
                (neighbor.Y >= 0) &&
                (neighbor.Y < mazeHeight)
                )
            {

                //if cell was not visited
                if (!MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited)
                {
                    Random random = new Random();

                    MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited = true;

                    //if random number is >= a certain number, removes the walls on both ends
                    if (random.Next(20) >= 15 && removed <= 100)
                    {
                        //MazeCells[(int)neighbor.X, (int)neighbor.Y].Visited = true;
                        MazeCells[(int)cell.X, (int)cell.Y].Walls[selectedNeighbor] = false;
                        MazeCells[(int)neighbor.X, (int)neighbor.Y].Walls[(selectedNeighbor + 2) % 4] = false;
                        removed++;
                    }

                    RandomWalls(neighbor);
                }
            }
        }
    }

I apologize for the lack of notes, but in essence it puts all of the cells into a box, and then tears down the walls so that you can reach any cell in the maze. Then I just remove a few extra cells, so that the maze doesn't feel as claustrophobic.

here is a picture of the maze from above:

There are walls around the maze to keep the player inside, in case they are hard to see. Normally, you see this more as a 1st person point of view.

So, the goal: Now, I want the camera to find the location of the cube, and the location of camera, and then find the shortest route between the two. Then, I want the camera to slowly follow the rout to get there, until it hits the cube. Now, which algorithm should I use, and how.

In case it helps, this code is almost entirely from the XNA 4 3D Game Developement by Example book. The only real edit I made was the RandomWalls() method.

Answer 1

I think that the wavefront algorithm might be a little bit too complicated to use for this problem, thus in my answer I'll be looking at the other two graph searching algorithms.

The first step you would need to take is to yield a graph representation of the maze. I think that the easiest way would be to:

1. Have each square (tile) in your map represented as a node in a graph.
2. If there is no edge between any two given adjacent squares, then, there is an edge between the two nodes representing those squares.

Once that you will have that done, you would need to assign weights. Since in your case you do not seem to have any preference over one edge or another, giving each edge a cost of 1 should be fine.

After that the weighted graph will be generated, you will need to search through it. I think that the two most popular algorithms are Dijkstra's Shortest Path Algorithm and the A* algorithm.

From what I am understanding, you have no information on where the cube will be placed, this, in my opinion means that you can't use A* since A* bases itself upon heuristics, which in this case could be the distance between the current node and the target node which is something you do not know.

Thus, the only option left is the Shortest Path Algorithm. To do this however, you would need to slightly modify the stopping condition of the search since you will need to check the square each node represents for its contents. If you find what you are looking for, you stop.

If on the other hand, for some reason you will have to use negative weights, then the Shortest Path will no longer work. For that, you will need to use the same approach however, use a Label Correcting Algorithm or the Bellman-Ford Algorithm.

Once that you will have the shortest path from the source node to the destination node, you could extract a series of vectors which will move you from one square to the next. After that you obtain these vectors, you should then be able to move the camera as explained in this MSDN tutorial.

EDIT: This line in your question: So, the goal: Now, I want the camera to find the location of the cube made me understand that you do not know where the cube is before hand. If this is not the case, then, as per @Gene's comment the A* algorithm will be more suitable since (assuming you know where your goal it) it will be more efficient.

Manhattan distance (see image below) should serve well as your heuristic section of your algorithm since it seems you can't traverse square blocks diagonally and thus, the most common way of calculating distances (Euclidean) will be less effective.