0
ASharp::ASharp(Maze *NMZ){
    MZ = NMZ;

    //Set all closedList items to false
    std::memset(closedList, false, sizeof(closedList));

    //Uses A* algorithm to find the fastest solution through the maze
    sf::Vector2i curPos = MZ->greenPos;
    sf::Vector2i centerPos = MZ->centerPos;
    std::vector<std::vector<block>> maze = MZ->maze;

    maze[curPos.x][curPos.y].fCost = 0.0;
    maze[curPos.x][curPos.y].gCost = 0.0;
    maze[curPos.x][curPos.y].hCost = 0.0;
    maze[curPos.x][curPos.y].parentPos = curPos;
    openList.emplace_back(maze[curPos.x][curPos.y]);

    while (!openList.empty() && openList.size() < (globals::WIDTH/globals::BLOCK_SIZE) * (globals::HEIGHT/globals::BLOCK_SIZE)){
        block route = *openList.begin();

        openList.erase(openList.begin());

        curPos = route.pos;
        closedList[curPos.x][curPos.y] = true;

        double fNew, gNew, hNew;
        for (int i = 0; i < 4; i++){
            int curNeighbourX = curPos.x, curNeighbourY = curPos.y;
            bool shouldProcess = false; //If a block should not be processed, this prevents it from being processed
                                        //i.e. block does not exist

            switch(i){
            case 0:
                if (curPos.y != 0){
                    curNeighbourY -= 1;
                    shouldProcess = true;
                }
            case 1:
                if (curPos.x != globals::BLOCK_WIDTH_NUM){
                    curNeighbourX += 1;
                    shouldProcess = true;
                }
            case 2:
                if (curPos.y != globals::BLOCK_HEIGHT_NUM){
                    curNeighbourY += 1;
                    shouldProcess = true;
                }
            case 3:
                if (curPos.x != 0){
                    curNeighbourX -= 1;
                    shouldProcess = true;
                }
            }

            if (shouldProcess){
                if (MZ->SquareIsValid(maze[curNeighbourX][curNeighbourY].shape.getFillColor())){
                    if (MZ->PartOfCenter(curNeighbourX, curNeighbourY)){
                        //A route is found, path is now made
                        MZ->maze[curNeighbourX][curNeighbourY].parentPos = curPos;
                        path = makePath();
                    }else if(!closedList[curNeighbourX][curNeighbourY]){
                        gNew = route.gCost + 1.0;
                        hNew = CalculateHeuristic(curNeighbourX, curNeighbourY, centerPos);
                        std::cout << hNew;
                        fNew = gNew + hNew;

                        //Checks if this path is better than the one previous
                        if (MZ->maze[curNeighbourX][curNeighbourY].fCost == FLT_MAX ||
                            MZ->maze[curNeighbourX][curNeighbourY].fCost > fNew){
                            MZ->maze[curNeighbourX][curNeighbourY].fCost = fNew;
                            MZ->maze[curNeighbourX][curNeighbourY].gCost = gNew;
                            MZ->maze[curNeighbourX][curNeighbourY].hCost = hNew;
                            MZ->maze[curNeighbourX][curNeighbourY].parentPos = curPos;
                            openList.emplace_back(MZ->maze[curNeighbourX][curNeighbourY]);
                        }
                    }
                }
            }
            shouldProcess = false;
        }
    }

    if (path.empty()){
        std::cout << "Maze has no solution" << std::endl;
    }
}

I'm trying to implement a simple maze solver for practice. There is a random point along the edge that is the starting point, the solution is in the center.

MZ is a pointer to a maze class that contains the maze <std::vector<std::vector<block>>

block is a struct containing relevant info of each block (pos, parentpos, color of block f,g,h cost)

Console prints "Maze has no solution" every time, without fail. I can physically trace the solution (there is currently only one possible path) but it should still work. I have applied the algorithm, step by step, but still to no avail.

Riverreed Ward
  • 13
  • 4
  • 2
    You forgot a small but important detail in your `case`s. – molbdnilo Sep 17 '20 at 16:04
  • Tip: adding `auto& current = maze[curNeighbourX][curNeighbourY];` inside the conditional and using `current` instead of `maze[curNeighbourX][curNeighbourY]` would save you a lot of both typing and reading. – molbdnilo Sep 17 '20 at 16:07
  • @moldbnilo Oh bugger. You have no idea how often I've done that and beaten my head against the wall for hours for that little detail. However, that has still not solved it. – Riverreed Ward Sep 17 '20 at 19:01
  • Please provide a [mre] with a function `main` and a minimal hard-coded sample maze. – Andreas Wenzel Sep 17 '20 at 22:26
  • Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine at which point your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). – Andreas Wenzel Sep 17 '20 at 22:30

0 Answers0