1. Pascal / Говнокод #12564

    +86

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    Function TMainForm.PrimGenerateMaze(Width, Height: Integer): Maze;

Type Point = record
  x, y: Integer;
end;

Var
  TehMaze: Maze;
  Todo: array of Point;
  todonum: integer;
  x,y,n,d: integer;

Const
  dx: array [0..3] of Integer = (0, 0, -1, 1);
  dy: array [0..3] of Integer = (-1, 1, 0, 0);

BEGIN
  SetLength(TehMaze, Width, Height);
  SetLength(Todo, (Width * Height) - 1);

  For x:=0 to Width-1 do
    For y:=0 to Height-1 do
      If (x = 0) or (x = Width-1) or (y = 0) or (y = Height-1) then
        TehMaze[x][y]:=32
      Else TehMaze[x][y]:=63;

  Randomize;
  x := Random(Width-2)+1;
  y := Random(Height-2)+1;
  todonum := 0;

  TehMaze[x][y]:= TehMaze[x][y] and not 48; // Пометить клетку как принадлежащую лабиринту

   // Пока не обработаны все клетки
   Repeat
    Begin
       // Занести в список todo все ближайшие необработанные клетки
       For d:=0 to 3 do
           if (TehMaze[x + dx[d]][y + dy[d]] and 16) <> 0 then
           Begin
             todo[todonum].x := x + dx[d];
             todo[todonum].y := y + dy[d];
             Inc(todonum);
             TehMaze[x + dx[d]][y + dy[d]] := TehMaze[x + dx[d]][y + dy[d]] and not 16;
           End;

       // Выбрать из списка todo произвольную клетку
       n:= Random(todoNum);
       x:= ToDo[n].x;
       y:= ToDo[n].y;

       // Удалить из списка обработанную клетку
       Dec(todonum);
       ToDo[n]:= todo[todonum];

       // Выбрать направление, которое ведет к лабиринту
       Repeat
           d:=Random(4);
       Until ((TehMaze[x + dx[d]][y + dy[d]] and 32) = 0);

       // Присоединить выбранную клетку к лабиринту
       TehMaze[x][y] := TehMaze[x][y] and not ((1 shl d) or 32);
       TehMaze[x + dx[d]][y + dy[d]] := TehMaze[x + dx[d]][y + dy[d]] and not (1 shl (d xor 1));
    End;
   Until (todonum = 0);

   TehMaze[1][1] := TehMaze[1][1] and -2;                 // начало лабиринта - в левом верхнем углу
   TehMaze[Width-2][Height-2] := TehMaze[Width-2][Height-2] and not 2; // конец лабиринта - в правом нижнем углу

   Result := TehMaze;
END;

    Генерация лабиринтов по алгоритму Прима.

    Запостил: Govnocoder#0xFF, 10 Февраля 2013

    Комментарии (24) RSS

    • ava Govnocoder#0xFF 10.02.2013 17:26 # 0

      Забыл добавить: 
      Type Maze = array of array of Integer;
      Ответить

    • ava TarasB 10.02.2013 17:49 # +4 

      repeat
begin

end
until

      лол
      Ответить

    • ava TarasB 10.02.2013 17:50 # +2 

      repeat
  a := random(...);
until foo(a);

      убивать
      Ответить

      • ava Govnocoder#0xFF 10.02.2013 19:16 # 0

        Смешно, но у меня никак не получается переписать этот кусок. Похоже я понимаю, почему автор прибегнул именно к этому способу, потому что другие отказываются корректно работать.
        Ответить

        • ava TarasB 10.02.2013 20:16 # 0

          Я делаю так, например:
          a := 0;
c := 1;
for i := 1 to 3 do if random(c+1)=0 then begin
  a := c;
  c := c+1;
end;
          Ответить

          • ava Govnocoder#0xFF 10.02.2013 20:29 # 0

            Я не понимаю, зачем там вообще нужен рандом? Можно же просто пройтись циклом от 0 до 3.
            Ответить

            • ava TarasB 10.02.2013 20:35 # 0

              Надо выбрать случайное направление из допустимых.
              Я в предыдущем посте херню написал.
              Правка:
              a := 0;
c := 0;
for i := 0 to 3 do if IsOK(i) then begin
  if random(c+1)=0 then a := c;
  c := c+1;
end;
              Ответить

              • ava Govnocoder#0xFF 10.02.2013 20:53 # 0

                Мне вообще надо этот код на Яву переписать, только у меня реализация на яве работает не так как на делфи, хотя код идентичный. Поможете? http://pastebin.com/FTvqHrSg
                Ответить

                • ava TarasB 10.02.2013 20:59 # 0

                  Понятия не имею, что там не так.
                  Ответить

                  • ava Lure Of Chaos 10.02.2013 22:18 # 0

                    нет желания особо вглядываться, но подозреваю, что дело в битовой логике, т.к. целое там 4-байтовое. да и new Random(width*height) - весьма странная конструкция.
                    Ответить

                • ava bormand 10.02.2013 22:54 # +1

                  Лениво сегодня разбираться. На глаз вроде правильно переписано. Так что возникают сомнения в работоспособности оригинального кода... Он работает?

                  P.S. Для todo применил бы очередь а не этот массив, код бы чуть понятней стал.

                  > Random(width*height) - весьма странная конструкция.
                  Действительно, каждый раз лабиринт будет одинаковый, при одном размере.

                  P.P.S. Загугли алгоритм Прима (построение остовного дерева?), попробуй понять, как его тут реализовали через эти битоебства. Может багу заметишь какую-то.
                  Ответить

                  • ava bormand 11.02.2013 05:44 # 0

                    > P.S. Для todo применил бы очередь а не этот массив, код бы чуть понятней стал.
                    А, тут выборка случайного элемента. Тогда очередь не прокатит. Разве что PriorityQueue с рандомным приоритетом.
                    Ответить

                  • ava Govnocoder#0xFF 11.02.2013 12:00 # 0

                    > Он работает?
                    Да, вполне.
                    Ответить

                • ava bormand 11.02.2013 06:12 # 0

                  Посмотри внимательно на строку 86 в твоем коде, кстати. И сравни ее с 65 в оригинале.
                  Ответить

                  • ava Govnocoder#0xFF 11.02.2013 11:50 # 0

                    Repeat ... Until в Паскале работает наоборот, Пока ... Условие (ложь), а в Жаве Пока ... Условие (истина), поэтому я там поменял условие.
                    Ответить

                    • ava TarasB 11.02.2013 11:53 # +2

                      Но в том, что ты выложил, условие не поменяно.
                      Ответить

                • ava bormand 11.02.2013 06:22 # +3

                  И второй серьезный баг в строке 74. Ты делаешь
                  todo[n] = todo[todonum];
                  В паскале это копировало структурку, в яве же ты скопировал ссылку, и после этого два элемента массива начнут ссылаться на одну и ту же точку, со всеми вытекающими последствиями.
                  Ответить

                  • ava Govnocoder#0xFF 11.02.2013 11:57 # 0

                    Точно, спасибо, исправлю на arraycopy и протестирую.
                    Ответить

                    • ava bormand 11.02.2013 12:34 # +1

                      > исправлю на arraycopy
                      Какой нахуй arraycopy()?! arraycopy() точно так же скопирует ссылки. Надо как-то так:
                      todo[n].x = todo[todonum].x;
todo[n].y = todo[todonum].y;
                      Ответить

    • ava anonimb84a2f6fd141 11.02.2013 17:24 # −12

      показать все, что скрытоЛаба
      Ответить

    Добавить комментарий