OutOfMemoryException For Maze Solver of Large Dimensions

Question

The Program Works for arrays upto 20x20 But for anything larger it throws an OutOfMemoryException.

Below is the code:

public static Point GetFinalPath(int x, int y) {

        queue.Enqueue(new Point(x,y, null));

        while(queue.Count>0) {
            Point p = queue.Dequeue();

            if (arr[p.x,p.y] == 9) {
                Console.WriteLine("Found Destination");
                return p;
            }

            if(IsOpen(p.x+1,p.y)) {
                arr[p.x,p.y] = 1;
                queue.Enqueue(new Point(p.x+1,p.y, p));
            }

            //similarly for the other directions


        }
        return null;
    }

public int[,] SolutionMaze()
            {
                Point p = GetFinalPath(0, 0);

                while (p.getParent() != null)
                {
                    solvedarray[p.x, p.y] = 9;
                    p = p.getParent();
                }
                return solvedarray;
            }

ok people here is the rest of the code

public static Queue<Point> queue=new Queue<Point>();

  public static bool IsOpen(int x, int y)
        {
            //BOUND CHECKING
            if ((x >= 0 && x < XMAX) && (y >= 0 && y < YMAX) && (arr[x,y] == 0 || arr[x,y] == 9))
            {
                return true;
            }
            return false;
        }
 public class Point
        {
           public int x;
           public int y;
            Point parent;

            public Point(int x, int y, Point parent)
            {
                this.x = x;
                this.y = y;
                this.parent = parent;
            }

            public Point getParent()
            {
                return this.parent;
            }

        }

Assumes start to be 0,0 and final destination is set as 9 at the constructor.

Help me implement this for an array of size 500x500

Answer 1

Okay i found an answer to the OutOfMemory. Now the code works even for 500x500 matrix As it turns out i just implemented a node list which keeps track of added nodes in queue using y*MAX_X_LENGTH + x formula

public static Queue<Point> queue=new Queue<Point>();

        public SolveMaze(int[,] array,int staX,int staY,int finX,int finY)
        {
            //sets Destination as 9
            arr = array;
            XMAX = array.GetLength(0);
            YMAX = array.GetLength(1);
            finishY = finX; finishX = finY; startY = staX; startX = staY;
            solvedarray = new int[XMAX, YMAX];
        }

        public static List<int> nodelist=new List<int>();

        public void AddPointToQueueIfOpenAndNotAlreadyPresent(Point p,int direction)
        {
            if (nodelist.Contains(XMAX * p.y + p.x))
                return;
            else
            {
                switch(direction){
                case 1:
                    //north
                    if (IsOpen(p.x, p.y - 1))
                    {
                        arr[p.x, p.y] = 1;
                        queue.Enqueue(new Point(p.x, p.y - 1, p));
                        nodelist.Add(XMAX * (p.y - 1) + p.x);
                    }
                    break;
                case 0:
                    //east
                    if (IsOpen(p.x + 1, p.y))
                    {
                        arr[p.x, p.y] = 1;
                        queue.Enqueue(new Point(p.x + 1, p.y, p));
                        nodelist.Add(XMAX * (p.y) + p.x + 1);
                    }
                    break;
                case 3:
                    //south
                    if (IsOpen(p.x, p.y + 1))
                    {
                        arr[p.x, p.y] = 1;
                        queue.Enqueue(new Point(p.x, p.y +1, p));
                        nodelist.Add(XMAX * (p.y + 1) + p.x);
                    }
                    break;
                case 2:
                    //west
                    if (IsOpen(p.x - 1, p.y))
                    {
                        arr[p.x, p.y] = 1;
                        queue.Enqueue(new Point(p.x - 1, p.y, p));
                        nodelist.Add(XMAX * (p.y) + p.x-1);
                    }
                    break;                    }
            }
        }

        public Point GetFinalPath(int x, int y) {
            if (arr[finishX, finishY] == 0)
                arr[finishX, finishY] = 9;
            else
                return null;

                queue.Enqueue(new Point(x, y, null));
                nodelist.Add(XMAX * y + x);

        while(queue.Count>0) {
            Point p = queue.Dequeue();
            nodelist.Remove(p.y * XMAX + p.x);

            if (arr[p.x,p.y] == 9) {
                Console.WriteLine("Exit is reached!");
                return p;
            }

            for (int i = 0; i < 4; i++)
            {
                AddPointToQueueIfOpenAndNotAlreadyPresent(p, i);
            }
        }
        return null;
    }


        public static bool IsOpen(int x, int y)
        {
            //BOUND CHECKING
            if ((x >= 0 && x < XMAX) && (y >= 0 && y < YMAX) && (arr[x,y] == 0 || arr[x,y] == 9))
            {
                return true;
            }
            return false;
        }


            public int[,] SolutionMaze()
            {
                Point p = GetFinalPath(startX, startY);
                if(p!=null)
                while (p.getParent() != null)
                {
                    solvedarray[p.x, p.y] = 9;
                    p = p.getParent();
                }
                return solvedarray;
            }
    }

         public class Point
        {
           public int x;
           public int y;
            Point parent;

            public Point(int x, int y, Point parent)
            {
                this.x = x;
                this.y = y;
                this.parent = parent;
            }

            public Point getParent()
            {
                return this.parent;
            }

        }