Волновой алгоритм!

[flaminger]

Здравствуйте! Делаю лабиринт со стенка которые закодированы как 0,1,2,3
Числа 0,1,2,3 нужно рассматривать как битовые маски, т.е. рассматривать их двоичное представление. Это числа 00, 01, 10 и 11. Каждый бит здесь указывает на наличие или отсутствие перегородки вправо или вниз. Допустим 01 – есть перегородка вниз, а 10 –есть перегородка вправо. Тогда 11 – есть перегородка и вниз и вправо.

Возникла проблема с волновым алгоритмом, а именно с условиями. Те, что я надумал обозначены в методах, но они не работают.

Помогите, пожалуйста, с реализацей волнового алгоритма в этом случае!
Заранее спасибо! хотя бы просто какие условия должны быть.

Вот прога:

bool NeedToGoUp(int i,int  j)
        {
            if ((i != 0) && (laber[i - 1, j] == 1) && (po[i - 1, j] == -1) || (i != 0) && (laber[i, j] == 3) && (po[i - 1, j] == -1))
            {
                return true;
            }
            return false;
        }
        bool NeedToGoLeft(int i, int j)
        {
            if ((j != 0) && (laber[i, j - 1] == 2) && (po[i, j - 1] == -1) || (laber[i, j] == 3)&&(j != 0)&& (po[i, j - 1] == -1))
            {
                return true;
            }
            return false;
        }
        bool NeedToGoRight(int i, int j)
        {
            if (((laber[i, j] == 2) || (laber[i, j] == 0)) && (po[i, j + 1] == -1) && (j != 19))
            {
                return true;
            }
            return false;
        }
        bool NeedToGoDown(int i, int j)
        {
            if ((laber[i, j] == 1) && (po[i + 1, j] == -1) && (i != n - 1))
            {
                return true;
            }
            return false;
        }
        private void button1_Click(object sender, EventArgs e)
        {
            laber = new int[n, n];
            int i, j;
            po = new int[n, n];
            Random r = new Random();
            for (i = 0; i < n; i++)
                for (j = 0; j < n; j++)
                {
                    laber[i, j] = r.Next(0, 4);
                    po[i, j] = -1;
                }
            for (i = 0; i < n-1; i++)
                laber[i, n - 1] = 1;
            for (j = 0; j < n; j++)
                laber[n - 1, j] = 2;
            
            List<Point> curfront = new List<Point>();
            curfront.Add(new Point { X = 0, Y = 0 });
            List<Point> newFront = new List<Point>();
            while (curfront.Count >0)
            {
                
                int nStep = 0;
                po[0, 0] = nStep;
                i = 0; j = 0;
                foreach (Point p in curfront)
                {
                    i = p.X;
                    j = p.Y;
                    if  (po[n - 1, n - 1] != -1)
                        break;
                    else if(NeedToGoRight(i,j)==true)
                    {
                        
                        po[i, j + 1] = nStep + 1;                                                
                        newFront.Add(new Point { X = i, Y = j+1 });
                    }
                    else if (NeedToGoDown(i,j)==true)
                    {
                        po[i + 1, j] = nStep + 1;                                          
                        newFront.Add(new Point { X = i+1, Y = j });
                    }
                    else if (NeedToGoUp(i,j)==true)
                    {
                        po[i - 1, j] = nStep + 1;     
                        newFront.Add(new Point { X = i-1, Y = j });
                    }
                    else if (NeedToGoLeft(i, j) == true)
                    {
                        po[i, j - 1] = nStep + 1;                  
                        newFront.Add(new Point { X = i, Y = j-1 });
                    }
                    else { break; }
                    nStep++;
                    
                }
                
                curfront = newFront;
                newFront = new List<Point>();
            }
            if(po[n-1, n-1] != -1)
            pictureBox1.Invalidate();
        }

[WorldMaster]

Как мне объясняли суть волнового алгоритма это просмотр путей с определенным расстоянием. Постепенно увеличивая расстояние от центра со временем находится выход. Есть реализация данного алгоритма однако структура данных лабиринта немного другая.

[s-andriano]

Так автора как раз и интересует именно такая "измененная" схема лабиринта.

Честно говоря, не вижу принципиальной разницы между стандартным и приведенным вариантами - просто чуть изменяется код проверки возможности перемещения в выбранном направлении, все остальное - полностью идентично.

По поводу реализации, в С не силен, но мне кажется, вместо конструкций типа

(laber[i, j] == 2) || (laber[i, j] == 0)

следует применять битовые операции.

Разобраться в том, что пытается сделать ТС в программе без единого комментария и с совершенно неговорящим названием массива po я лично не сумел.
Хоть бы уж словесное описание имелось - чтобы сравнить то, что пытался сделать, с тем, что на самом деле получилось.

[WorldMaster]

И правда .. скриншотов бы работы существующего алгоритма ... чтобы посмотреть что вообще получается.
И вообще не понятно как происходит перемещение по лабиринту и закрытие тупиковых вершин?

[BDA]

Попробуйте так:

        private void button1_Click(object sender, EventArgs e)
        {
            laber = new int[n, n];
            int i, j;
            po = new int[n, n];
            Random r = new Random();
            for (i = 0; i < n; i++)
                for (j = 0; j < n; j++)
                {
                    laber[i, j] = r.Next(0, 4);
                    po[i, j] = -1;
                }
            for (i = 0; i < n-1; i++)
                laber[i, n - 1] = 1;
            for (j = 0; j < n; j++)
                laber[n - 1, j] = 2;
            
            List<Point> curfront = new List<Point>();
            curfront.Add(new Point { X = 0, Y = 0 });
            int nStep = 0;
            po[0, 0] = nStep;
            i = 0; j = 0;
            while (po[n - 1, n - 1] == -1 && curfront.Count > 0)
            {
                nStep++;
                List<Point> newFront = new List<Point>();
                foreach (Point p in curfront)
                {
                    i = p.X;
                    j = p.Y;
                    if  (po[n - 1, n - 1] != -1)
                        break;
                    if (i > n - 1 || i < 0 || j > n - 1 || j < 0)
                        continue;
                    po[i, j] = nStep;
                    if (laber[i, j] & 1 == 0)                                          
                        newFront.Add(new Point { X = i+1, Y = j });
                    if (laber[i, j] & 2 == 0)                                           
                        newFront.Add(new Point { X = i, Y = j+1 });                                       
                    newFront.Add(new Point { X = i-1, Y = j });
                    newFront.Add(new Point { X = i, Y = j-1 });
                }
                curfront = newFront;
            }
            if(po[n-1, n-1] != -1)
                pictureBox1.Invalidate();
        }

Правда, не знаю, что за язык. Возможны утечки памяти (проверьте этот момент).