Алгоритм Прима для генерации лабиринта

[anete.anetes]

Delphi, однако можно и на C# если так же просто описано будет.

Алгоритм:
3 атрибута локации:
значения Inside (внутри)
Outside (снаружи)
Border (на границе).

1.Изначально атрибут каждой локации == Outside.
2.Выберем случайную локацию в лабиринте и присвоим значение Inside.
3.Присвоим также атрибутам соседних с ней локаций значение Border.
4.ПОКА атрибут хотя бы одной локации равен Border.
5.Выберем случайную лок., атрибут которой == Border, присвоим Inside.
6.Атрибут ВСЕХ соседних лок := Border ЕСЛИ он == Outside.
7.Из ВСЕХ соседних лок атрибут которых == Inside, выберем
случайную и разрушим стену между ней и текущей локацией.

На бумаге получается, по факту нет.
Краткий листинг:

Type TAtr=(Inside, Outside, Border);

Type
  Maze = object
    l,t: Boolean; //стена слева или сверху
    at: TAtr; //атрибут локации
  end;

var
  Lab: array [1..5,1..5] of Maze;
  EndLab: Boolean;

{Процедура генерации}
begin
CleanLab();
Randomize;
l:=RandomRange(1,6);
m:=RandomRange(1,6);
Lab[l,m].at:=InSide;
Lab[l,m+1].at:=Border;
Lab[l,m-1].at:=Border;
lab[l-1,m].at:=Border;
lab[l+1,m].at:=Border;
EndLab:=False;
repeat
begin
MyScdRec();
  //2 step
end;
//check
begin
en:=0;
for i := 1 to 5 do
  begin
    for q := 1 to 5 do
    begin
      if lab[i,q].at=Border then
        en:=en+1;
    end;
  end;
end;
if en=0 then
EndLab:=True;
until EndLab=True;
end;

{Рекурсия на выбор Border локации} //MyScdRec
begin
Randomize;
l:=RandomRange(1,6);
m:=RandomRange(1,6);
if Lab[l,m].at=Border then
  begin
    lab[l,m].at:=Inside;
    if lab[l,m+1].at=Outside then
    lab[l,m+1].at:=Border;
    if lab[l,m-1].at=Outside then
    lab[l,m-1].at:=Border;
    if lab[l-1,m].at=Outside then
    lab[l-1,m].at:=Border;
    if lab[l+1,m].at=Outside then
    lab[l+1,m].at:=Border;
    MyFstRec(l,m);
    Button5Click(Form1);  //ОТРИСОВКА, см ниже
  end
  else
  begin
    MyScdRec();
  end;
end;

{Рекурсия на выбор случайной Inside локации рядом} //MyFstRec
begin
Randomize;
id:=RandomRange(1,5);
  case id of
  1:begin
      if lab[x,y+1].at=InSide then
      begin
      lab[x,y+1].l:=False;
      end
      else
      MyFstRec(x,y);
    end;
  2:begin
      if lab[x,y-1].at=InSide then
      begin
      lab[x,y].l:=False;
      end
      else
      MyFstRec(x,y);
    end;
  3:begin
      if lab[x+1,y].at=InSide then
      begin
      lab[x+1,y].t:=False;
      end
      else
      MyFstRec(x,y);
    end;
  4:begin
      if lab[x-1,y].at=InSide then
      begin
      lab[x,y].t:=False;
      end
      else
      MyFstRec(x,y);
    end;
  end;//Case end;
end;

{Отрисовка}
begin
z:=0;
for i := 1 to 5 do
  begin
    for a := 1 to 5 do
      begin
        z:=z+1;
        v:=FindComponent('lab'+IntTOStr(z));
        if (lab[i,a].l=True) and (Lab[i,a].t=True) then
        begin
          TImage(v).Picture.LoadFromFile('C:\lab\lt.bmp');
          GoTo Lamo;
        end;
        if lab[i,a].l=True then
        begin
          TImage(v).Picture.LoadFromFile('C:\lab\l.bmp');
          GoTo Lamo;
        end;
        if lab[i,a].t=True then
        begin
          TImage(v).Picture.LoadFromFile('C:\lab\t.bmp');
          GoTo Lamo;
        end;
        if (lab[i,a].l=False) and (Lab[i,a].t=False) then
        begin
          TImage(v).Picture.LoadFromFile('C:\lab\nn.bmp');
          GoTo Lamo;
        end;
        Lamo:
        //
      end;
  end;
end;

Здесь уйма недочётов итд, однако это прототип.
В итоге получается:

Подскажите пожалуйста где ошибка.

[evg_m]

id:=RandomRange(1,5);
  case id of
  1: ...
  2: ...
  3: ...
  4: ...
  else MyFst(x,y);  
  end;

вопрос почему отсылаю к справке по RandomRange.

[anete.anetes]

id:=RandomRange(1,5);
  case id of
  1: ...
  2: ...
  3: ...
  4: ...
  else MyFst(x,y);  
  end;

RandomRange(1,5);

Случайно выбирает int из 1,2,3,4.

Проверка:
for i := 1 to 99 do
begin
a:=RandomRange(1,5);
Memo1.Lines.Add(IntTOStr(a));
end;

Или я совсем тупой в другом месте а это только индекс того места?
Delphi изучаю сам всего лишь два месяца, так что прошу не ругать сильно.

UPD: Возможно Вы не внимательно прочитали код и не заметили что else ВНУТРИ begin/end вариации кейса?

id:=RandomRange(1,5);
  case id of
  1:begin
      //вошли в кейс
      if lab[x,y+1].at=InSide then
      //если локация InSide тогда:
      begin
      lab[x,y+1].l:=False;
      end
      //мы в кейсе, если локация НЕ Inside, тогда:
      else
      MyFstRec(x,y);
    end;

[anete.anetes]

В чём проблема? Никто не может разобраться в коде? Задавайте хотя бы вопросы.

[phomm]

Весь проект архивом скиньте, можно будет покопаться, а так - в лом собирать _только из одного кода_ что-то рабочее.
Проверил сейчас, кстати, рендомрейндж не выдаёт числа на конце диапазона, хотя даже в офсправке указано inclusive
код из Math:

function RandomRange(const AFrom, ATo: Integer): Integer;
begin
  if AFrom > ATo then
    Result := Random(AFrom - ATo) + ATo
  else
    Result := Random(ATo - AFrom) + AFrom;
end;

[WorldMaster]

Вот полностью готовый метод. Только на С++. Переписать на Делфи не должно быть сложно. Я тут комментировал код.

 Переменные 
struct MapCell
 { bool PeakAttr; // показатель вершины
   int Attribute; // показатель посещаемости клетки
   bool Left, Up, Right, Down; // направления выхода из вершины
   int NumPeak; // индекс в массиве вершин

   int LeftEdgeOut, UpEdgeOut, RightEdgeOut, DownEdgeOut; // отметки выхода ребер
   int LeftEdgeIn, UpEdgeIn, RightEdgeIn, DownEdgeIn; // отметки вхождения ребер
 };

// массив вершин
struct Peak
 { TPoint Coordinates;
 } *PeakMass;

// массив вершин найденного пути
struct TracePeak
 { TPoint  Coords;
   int Dest; // направления для визуализации
 } *GTrace;

int Size = 35;  // размер лабиринта
int Cell = 15;   // размер ячейки
int delay; // задержка для анимации
MapCell **Map;  // массив карты лабиринта
int MaxPeaks; // максимальное количество вершин

void GeneratePrim(MapCell **Massive) // создает лабиринт методом Прима
{
int x,y;

// очищаем карты
for (int c=0; c<Size; c++)
 for (int v=0; v<Size; v++)
  { Massive[c][v].Attribute = Outside;
    Massive[c][v].Left = false;
    Massive[c][v].Up = false;
    Massive[c][v].Right = false;
    Massive[c][v].Down = false;
  };

randomize();
x = random(Size);
y = random(Size);
Massive[x][y].Attribute = Inside;
if ((x-1)>=0) Massive[x-1][y].Attribute = Border;
if ((x+1)<Size) Massive[x+1][y].Attribute = Border;
if ((y-1)>=0) Massive[x][y-1].Attribute = Border;
if ((y+1)<Size) Massive[x][y+1].Attribute = Border;
// список ячеек с параметром Border
TPoint *mas;
mas = new TPoint[Size*Size];
int Bordcount; // курсор в массиве
do {   // повторяем пока есть хотя бы одна клетка Border
Bordcount = 0; // очистка счетчика
// просматриваем массив ищем все клетки с атрибутом Border
for (int c=0; c<Size; c++)
 for (int v=0; v<Size; v++)
  if (Massive[c][v].Attribute == Border)
    {mas[Bordcount].x = c;
     mas[Bordcount].y = v;
     Bordcount++;
    };
// список соседей с атрибутом Inside
TPoint Ins[4];
int count = 0; // счетчик
// Выберем случайную клетку, атрибут которой равен Border, и присвоим ей Inside
int buf = random(Bordcount);
x = mas[buf].x;
y = mas[buf].y;
Massive[x][y].Attribute = Inside;
// Изменим на Border атрибут всех соседних с текущей клеток, атрибут которых                        
// равен Outside
if ((x-1)>=0)
 if (Massive[x-1][y].Attribute == Outside) Massive[x-1][y].Attribute = Border; else
 if (Massive[x-1][y].Attribute == Inside)
      {Ins[count].x = x-1;
       Ins[count].y = y;
       count++;
      };

if ((x+1)<Size)
 if (Massive[x+1][y].Attribute == Outside) Massive[x+1][y].Attribute = Border; else
 if (Massive[x+1][y].Attribute == Inside)
      {Ins[count].x = x+1;
       Ins[count].y = y;
       count++;
      };

if ((y-1)>=0)
 if (Massive[x][y-1].Attribute == Outside) Massive[x][y-1].Attribute = Border; else
 if (Massive[x][y-1].Attribute == Inside)
      {Ins[count].x = x;
       Ins[count].y = y-1;
       count++;
      };

if ((y+1)<Size)
 if (Massive[x][y+1].Attribute == Outside) Massive[x][y+1].Attribute = Border; else
 if (Massive[x][y+1].Attribute == Inside)
      {Ins[count].x = x;
       Ins[count].y = y+1;
       count++;
      };
// теперь из полученного массива выберем случайную и сломаем стену
// между текущей и ей
// X и Y до сих пор содержат текущие координаты
buf = random(count);

if ((Ins[buf].x > x) & (Ins[buf].y == y))
    { Massive[Ins[buf].x][Ins[buf].y].Left = true;
      Massive[x][y].Right = true;
    } else
if ((Ins[buf].x < x) && (Ins[buf].y == y))
    { Massive[Ins[buf].x][Ins[buf].y].Right = true;
      Massive[x][y].Left = true;
    }else
if ((Ins[buf].x == x) && (Ins[buf].y > y))
    { Massive[Ins[buf].x][Ins[buf].y].Up = true;
      Massive[x][y].Down = true;
    }else
if ((Ins[buf].x == x) && (Ins[buf].y < y))
    { Massive[Ins[buf].x][Ins[buf].y].Down = true;
      Massive[x][y].Up = true;
    };
} while (Bordcount > 0);
delete [] mas;
};

[WorldMaster]

А вот результат.

[anete.anetes]

Сообщение от phomm

Весь проект архивом скиньте, можно будет покопаться, а так - в лом собирать _только из одного кода_ что-то рабочее.
Проверил сейчас, кстати, рендомрейндж не выдаёт числа на конце диапазона, хотя даже в офсправке указано inclusive
код из Math:

function RandomRange(const AFrom, ATo: Integer): Integer;
begin
  if AFrom > ATo then
    Result := Random(AFrom - ATo) + ATo
  else
    Result := Random(ATo - AFrom) + AFrom;
end;

У меня XE4, посмотреть Math не могу, т.к. в офисе нет IDE, однако у меня RandomRange однозначно не выдаёт число на конце диапазона. Но судя по вашему Math, мистика какая-то.
Опять же, весь проект скинуть не могу, на G-Drive забыл скинуть, в офисе IDE нет, однако это весь код, что бы скомпилить достаточно добавить локальные переменные (а они там явно Integer), 1 button и 25 image, ну или отрисовывать по другому, я использую 25 img только на прототипе. А так это весь код, и поэтому вариант который предложили на С++ (спасибо) не подходит, мне всё таки хочется попробовать реализовать это упрощённо.

Спасибо за ответы, на сайбере предложили похожий вариант, но я думаю что можно исправить этот переписав под такие нужды:

Сообщение от FIL

Из логических ошибок:
- следующая ячейка для обработки (Border) выбирается не случайно из всех ячеек, пальцем в небо, а относительно общего кол-ва ячеек типа Border, гарантировано выбирается. А у тебя MyScdRec запускается неопределенное кол-во раз вхолостую.
- примерно тоже самое и с MyFstRec - запускается неопределенное кол-во раз. Спасает только малый размер лабиринта, при большом - вообще зависать должно.
- нет проверок на край лабиринта.

[phomm]

что бы скомпилить достаточно добавить локальные переменные (а они там явно Integer), 1 button и 25 image, ну или отрисовывать по другому, я использую 25 img только на прототипе

Ну, кто кроме Вас это сделает? Постарайтесь помочь помогающим Вам людям, или каждому надо всё это проделать? Как программист Вы должны стремиться к оптимизации, подумайте, что лучше - Вы один раз быстренько провернёте это с макс. скоростью, ибо Вам всё тут известно, или же несколько человек сядут разбирать что куда сунуть и привязать? Затраты явно больше во втором случае.
Вы не подумайте, что лень там или что-то подобное - просто я, например, гораздо быстрее смогу выделить время, если буду знать, что мне достаточно только запустить и смотреть, а не возиться полчаса (возможно даже безрезультатно, ибо Ваш проект может подвязан на какую-то мелочь, которую я не задействую, и получится что мы работаем над разными вещами, а потом ещё тратить время, чтобы понять, а где же расхождения и т.д.)

[anete.anetes]

Ну, кто кроме Вас это сделает? Постарайтесь помочь помогающим Вам людям, или каждому надо всё это проделать? Как программист Вы должны стремиться к оптимизации, подумайте, что лучше - Вы один раз быстренько провернёте это с макс. скоростью, ибо Вам всё тут известно, или же несколько человек сядут разбирать что куда сунуть и привязать? Затраты явно больше во втором случае.
Вы не подумайте, что лень там или что-то подобное - просто я, например, гораздо быстрее смогу выделить время, если буду знать, что мне достаточно только запустить и смотреть, а не возиться полчаса (возможно даже безрезультатно, ибо Ваш проект может подвязан на какую-то мелочь, которую я не задействую, и получится что мы работаем над разными вещами, а потом ещё тратить время, чтобы понять, а где же расхождения и т.д.)

в офисе IDE нет

Часов через 5 скину, мне не сложно) была бы онлайн IDE скинул бы и сейчас.