How to check for the previous path searched on a maze C#

Question

I am trying to code an algorithm that solves a maze problem but I am facing some difficulty to apply it correctly.

The algorithm runs over the walls instead of changing the direction after finding the valid point.

I do not understand clearly how to check for the previousPoint and then from that point check for the next valid move.

Could someone help me giving me some tips on which direction I could go?

class MapPathFinder
{
    public bool[,] correctPath = new bool[12,12];
    public int[,] previousPoint = new int[12, 12];
    public bool startPointFound = false;
    public bool nextValidMove(MapFile map, int y, int x)
    {
        if ((y == map.width) && (x == map.height)) { 

            return false; //Checks if at the edge and terminates the method
        }

        if ((map.Matrix[y, x]) == 1 ) {
            return true; // check if at a wall and terminate the method
        }

        if (y != 0)
        {
            if (nextValidMove(map, y-1,x))
            {
                map.Matrix[y, x] = 9; //changes the color of the position
                correctPath[y, x] = true;
                return correctPath[y, x];
            }

            if (y != map.width - 1) //check if at the limit of the map
            {
                if (nextValidMove(map,y + 1, x))
                {
                    map.Matrix[y, x] = 9;
                    correctPath[y, x] = true;
                    return correctPath[y, x];
                }       
            }

            if (x != 0)
            {
                if (nextValidMove(map, y, x - 1))
                {
                    map.Matrix[y, x] = 9;
                    correctPath[y, x] = true;
                    return correctPath[y, x];
                }
            }

            if (x != map.height - 1)
            {
                if (nextValidMove(map, y, x + 1))
                {
                    map.Matrix[y, x] = 9;
                    correctPath[y, x] = true;

                    return correctPath[y, x];
                }
            }
        }
        return false;
    }

    public bool PathFinder(MapFile map)
    {
        for (int y = 1; y < map.width; y++)
        {
            for (int x = 1; x < map.height; x++)
            {
               var status = MapDisplay.DisplayMap(map);
                 if (status)
               {
                   nextValidMove(map, x, y);
               }
            }           
        }
        return true;
    }

I tried to implement the answer given by Paul but could not really get anywhere from it and I am completely lost.

That is what I got from your answer:

public bool nextValidMove(MapFile map, int y, int x)
{
    if ((y == map.width) || (x == map.height)) return false; 

    if(y<0 || x<0) return false;

    if ((map.Matrix[y, x]) == 1) return true; // check if at a wall and terminate the method

    if (map.Matrix[y, x] == 5) return map.end;

    if (y - 1 >= 0 && map.Matrix[y-1, x] == 2 && !nextValidMove(map, y-1, x))
    {
        map.Matrix[y, x] = 9;
        previousPoint[y, x] = map.Matrix[y, x];
        return false;
    }
    //  Test the East wall...
    if (x + 1 <= map.width - 1 && map.Matrix[y + 1, x] == 2 && !nextValidMove(map, y, x+1))
    {
        map.Matrix[y, x] = 9;
        previousPoint[y, x] = map.Matrix[y, x];
        return false;
    }
    //  Test the South wall...
    if (y + 1 <= map.height - 1 && map.Matrix[y, x + 1] == 2 && !nextValidMove(map, y+1,x))
    {
        map.Matrix[y, x] = 9;
        previousPoint[y, x] = map.Matrix[y, x];
        return false;
    }
    //  Test the West wall...
    if (x - 1 >= 0 && map.Matrix[y, x - 1] == 2 && !nextValidMove(map, y, x-1))
    {
        map.Matrix[y, x] = 9;
        previousPoint[y, x] = map.Matrix[y, x];
        return false;
    }

    return false;
}

When I run it I get a stack overflow error.

When I am checking the possible points and calling the function recursively with

!nextValidMove(map, y-1, x)

I don't really understand why I am checking the nextValidMove(y-1,x) since it was already true at the begining of my if statement:

if(map.Matrix[y-1, x] == 2 && !nextValidMove(y-1,x))

I thought of checking the previousPoint together, like this:

if(nextValidMove(map, y - 1, x)&&!previousPoint[y-1,x])

But I am getting a stackoverflow error. I have no clue how to get out of there anymore.

surely you just keep a note of each time theres a choice, you make note of you options and if its tested, untested choices can then be found and gone back to try — BugFinder, Aug 23 '17 at 08:10
a few comments in your code that describe the thought behind it would be really helpful. Please make the thought process not unnecessarily hard for the people who can help you. — Mong Zhu, Aug 23 '17 at 08:11
I take it that you're pushing your moves onto a LIFO stack? ... and that your maze is a simple cuboid maze (i.e. each cell of the maze only has four or six possible directions - cube walls)? — Paul, Aug 23 '17 at 08:20
Shouldn't `if ((y == map.width) && (x == map.height))` actually be `if ((y == map.width) || (x == map.height))`, if you're checking for the extremes of the map? Why do you actually need to do this? Each cell should have the walls set-up to prevent travel in particular directions. — Paul, Aug 23 '17 at 08:24
@Paul When x and y are the same value as the size of the map, it just doesn't fall on the other ifs anymore and finishes the method. The way I saw it, seemed to be right. I don't know if this is the best approach — EAzevedo, Aug 23 '17 at 08:30
I suppose it does prevent execution of the rest of the code in the routine and makes it milliseconds faster...... — Paul, Aug 23 '17 at 08:32
@Paul following the comments development here one can get the feeling of beeing the rat in the maze ;) — Mong Zhu, Aug 23 '17 at 08:35
I've actually had to do some simple pathfinding myself, in order to solve this issue I made a distinction between walls and path by either setting the square OPEN or CLOSED. Any tile considered closed I would ignore when checking around me. I used this in combination with the Dijkstra algorithm, in which I evaluated all possible branches and once I hit a full closed round (a dead end) i would just "close" that branch. so in the case I was able to reuse the OPEN/CLOSED variables not just for walls, but for any tile considered "not the right direction". — Bart de Ruijter, Aug 23 '17 at 09:15
(Just to expand on @BartdeRuijter 's comment): https://stackoverflow.com/questions/10674468/finding-the-shortest-route-using-dijkstra-algorithm and https://code.msdn.microsoft.com/windowsdesktop/Dijkstras-Single-Soruce-69faddb3 — Paul, Aug 23 '17 at 09:32
You're on the right path (no pun intended!). The idea behind returning true and false was to say that a particular move was valid or not. Returning `map.end` will also cause an error as it's not a bool. I'll update my answer, but it won't be now - off home! — Paul, Aug 24 '17 at 15:52
Are you trying to implement something like the A* algorithm? https://www.codeproject.com/Articles/15307/A-algorithm-implementation-in-C (also https://stackoverflow.com/questions/2138642/how-to-implement-an-a-algorithm) — Jay, Aug 25 '17 at 11:48
Fix3r, I'd really appreciate it if you'd stop messing with my reputation. I **REALLY** don't appreciate it. — Paul, Sep 04 '17 at 08:10

Lamelas84 · Accepted Answer · 2017-08-29T09:55:35.087

I have rewriten your MapPathFinder class to make it work.

class MapPathFinder
{
    public const byte WALL = 1;
    public const byte ROAD = 2;
    public const byte START = 3;
    public const byte FINISH = 5;
    public const byte ALREADY_THERE = 9;

    public bool NextValidMove(MapFile map, int x, int y)
    {
        // Check edges
        if (x < 0 || x > map.width || y < 0 || y > map.height)
            return false;

        byte currentPosition = map.Matrix[x, y];

        // Check walls or already there
        if (currentPosition == WALL || currentPosition == ALREADY_THERE)
            return false;

        // Print
        var status = MapDisplay.DisplayMap(map);

        if (status)
        {
            // Check finish
            if (currentPosition == FINISH)
            {
                return true; // We've arrived!
            }

            // Road
            //
            // Set ALREADY THERE
            map.Matrix[x, y] = ALREADY_THERE;

            // Left
            if (NextValidMove(map, x - 1, y))
                return true;

            // Right
            if (NextValidMove(map, x + 1, y))
                return true;

            // Up
            if (NextValidMove(map, x, y - 1))
                return true;

            // Down
            if (NextValidMove(map, x, y + 1))
                return true;

            // Not the correct path.. 
            map.Matrix[x, y] = ROAD;
        }

        return false;
    }

    public bool PathFinder(MapFile map)
    {
        // Looking for start point
        for (int x = 0; x < map.width; x++)
        {
            for (int y = 0; y < map.width; y++)
            {
                if (map.Matrix[x, y] == START)
                    return NextValidMove(map, x, y);
            }
        }

        return false;
    }
}

However I left some work for you:

No storing of the correct path.
If there are two correct paths, this algorithm won't take always the shorter one, but the first found.

score 8 · Answer 2 · answered Aug 23 '17 at 09:06

Your walls are determined by there being a # in any of the adjacent cells or a . for the floor, S start and F finish.

In that case, you want to simply check on a rotational basis, starting at, say, North, then move onto the next position round, until you arrive back at North. Each check should be pushed on the stack and popped off when it gets nowhere. That way, at least, you'll be able to trace your way backward each time.

//  Test to see if we've found Utopia...
if(map.Matrix[x, y] == 'F') return true;
//  Test the North wall...
if(y-1>=0 &&          map.Matrix[x, y-1]=='.' && !nextValidMove(map, x, y-1)) return false;
//  Test the East wall...
if(x+1<=map.width  && map.Matrix[x+1, y]=='.' && !nextValidMove(map, x+1, y)) return false;
//  Test the South wall...
if(y+1<=map.height && map.Matrix[x, y+1]=='.' && !nextValidMove(map, x, y+1)) return false;
//  Test the West wall...
if(x-1>=0 &&          map.Matrix[x-1, y]=='.' && !nextValidMove(map, x-1, y)) return false;

The recursive calls should then unwind naturally.

Note that you'll need to look at the success criteria a little better than I have there, and you may need to play with how the routine unwinds. The code here gives a demonstration, though, of how to check your adjoining walls.

Notice that && only performs the next check if the prior one was successful in the first place.

Just like being really honest... I am feeling quite stupid at the moment since I could not make this work until now. I posted an edit of the question to try explain. Thanks for helping me though. — EAzevedo, Aug 24 '17 at 14:39
Sorry? I didn't understand what you said there - did you mean that my answer did help or it has confused you? — Paul, Aug 24 '17 at 14:43
The answer helped me to get further with my problem. I am just feeling stupid because It seems that I do not understand how to solve this from there. — EAzevedo, Aug 24 '17 at 14:45
Okay. Update your question with what you have learned so we can all see what you mean. — Paul, Aug 24 '17 at 14:46

How to check for the previous path searched on a maze C#

2 Answers2