1 Востаннє редагувалося FakiNyan (05.01.2017 18:42:53)

Тема: порадьте алгоритм генерації лабиринту

Прів. Мені тре згенерувати алгоритм, котрий має вказану кількість входів, від 1 до 4, і в середині алгоритму має бути кімнатка з вказаною кількістю дірок. І ще було б файно, аби мінімальна кількість унікальних шляхів до цієї кімнати дорівнювала заданому числу, і при цьому шоб була можливість переходити з однієї дороги на іншу

Post's attachments

maze.jpg 191.07 kb, 234 downloads since 2017-01-05 

2 Востаннє редагувалося P.Y. (05.01.2017 20:39:27)

Re: порадьте алгоритм генерації лабиринту

Не впевнений, наскільки це ефективно, але перше, що спадає на думку — заповнити лабіринт кімнатками з рандомними входами та виходами й випадково міняти їх, доки лабіринт не стане відповідати умові. Можливо, змінювати не всі, а лише ті, що лежать на краю доступної області, щоб забезпечити проходжуваність.

Р.Ѕ. не бачу лабіринту на картинці — там білий аркуш.

3

Re: порадьте алгоритм генерації лабиринту

P.Y. написав:

Не впевнений, наскільки це ефективно, але перше, що спадає на думку — заповнити лабіринт кімнатками з рандомними входами та виходами й випадково міняти їх, доки лабіринт не стане відповідати умові. Можливо, змінювати не всі, а лише ті, що лежать на краю доступної області, щоб забезпечити проходжуваність.

Р.Ѕ. не бачу лабіринту на картинці — там білий аркуш.

озьдо картинка
http://не-дійсний-домен/tcaRe/782facd13a.png

в мене була ідея - спочатку з'ясувати точку, з котрої починається шлях, а потім рандомно прибирати стіни, доки не дійдемо до середини, але така рандомність до добра не доведе

4

Re: порадьте алгоритм генерації лабиринту

почав з простого, просто обирати рандомний напрямок і йти туди (це вже після того, як побудована сітка)
Озьдо результати з різною кількістю спроб. Починаємо з верхнього лівого кута

10 кроків

Прихований текст

http://не-дійсний-домен/tdb9v/3d95f38b74.png

50 кроків

Прихований текст

http://не-дійсний-домен/tdbbJ/198aa77c19.png

100 кроків

Прихований текст

http://не-дійсний-домен/tdbcQ/d9e26c47da.png

200 кроків

Прихований текст

http://не-дійсний-домен/tdbdT/424f3ab728.png

Як бачите, є дві основні проблеми:

1. Кількість кроків не забезпечує розгалуженості лабиринту, адже воно може 100 разів ходити вперед-назад
2. Створюються пустоти, а потрібні заплутані коридори.

Подякували: 221VOLT1

5

Re: порадьте алгоритм генерації лабиринту

https://m.habrahabr.ru/post/262345/
З поясненням/кодом.

Подякували: 221VOLT1

6

Re: порадьте алгоритм генерації лабиринту

Я відхилив вашускаргу про москальські ресурси. Хех, як я міг..
Що далі будете робити? Візьмете алгоритм, написаний розумними дядьками чи спробуєте написати костиль? (результат якого можна сказати вже)

Подякували: 221VOLT1

7

Re: порадьте алгоритм генерації лабиринту

намагаюся реалізувати перший алгоритм, котрий в статті на вікіпедії, поки шо якась чортівня виходе

Прихований текст

http://не-дійсний-домен/togT6/36aa3b508a.png

а ще воно тупо застигає в одному місці, хоча має повертатись до самого початку, якщо більше нікуди йти не може

8

Re: порадьте алгоритм генерації лабиринту

опа

Прихований текст

http://не-дійсний-домен/tokMu/2fcb25130f.gif

це воно так ходе дивно, бо в мене зара не рандомно обирається напрямок руху

9 Востаннє редагувалося FakiNyan (16.01.2017 23:10:25)

Re: порадьте алгоритм генерації лабиринту

ну от

Прихований текст

http://не-дійсний-домен/toAC4/783756a98b.gif

але ви ж бачите, яка тут проблема, ага?

10

Re: порадьте алгоритм генерації лабиринту

шось я мудрив-мудрив з тою оптимізацією, але нічо путнього не намудрив. Може й мудрити не треба було. Проблема було в тому, що при ході назад, воно, бува, скакає на якісь далекі точки, і йде далі вже з них.
Озьдо приклад згенереного мейзу, 40 x 40

Прихований текст

http://не-дійсний-домен/tplWx/59a1525737.png

11

Re: порадьте алгоритм генерації лабиринту

ги, поки грав в гру, то в голову прийшла думка, як ту штуку оптимізувати.

Що ми робимо:
стаємо в якусь рандомну клітинку. Додаємо цю клітинку в "стек". Потім шукаємо по сторонам (діагональ не включається) такі клітинки, в котрих ми ще не були. Тобто, такі клітинки, котрих немає в "стеку".
Коли знайшли таку клітинку, то відкриваємо дверцята, що між поточною і знайденою клітинками, після чого позначаємо знайдену клітинку як поточну і додаємо її в "стек".
Якщо ми зайшли в куток, в котрому немає сусідніх клітинок, котрі, також, не знаходяться в "стеку", то ми витягуємо з стеку клітинки, починаючи з самої останньої, котру додали, і робимо її поточною, після чого знову шукаємо потрібну нам клітинку, якщо не знаходимо, то знову витягаємо зі "стеку" клітинку. Тобто, рухаємося назад.

Проблема:
якщо ми спочатку зайдемо в кут, в котрому не буде потрібних клітинок, то остання клітинка, котру ми додали, залишається в "стеку". Далі ми рухаємось назад, знаходимо потрібні клітинки, котрі також додаємо в "стек", після чого можемо знову зайти в глухий кут, і почати хід назад. Але коли ми проходимо ту кількість кроків, котра дорівнює кількості доданих клітинок, після того, як ми пішли назад, з попереднього глухого кута, то ми автоматом перецибуємо в ту клітинку, котру ми додали в "останньою", перед тим, як піти назад.

Озьдо я схематично намалював
http://не-дійсний-домен/tpr7x/1a91653f29.png
Коли голівка повертається після 20 кроку, вона робить 4 кроки назад. Воно проходить 4 клітинки, котрі ми щойно додали в стек, після чого воно бере наступну клітинку зі стеку, індекс котрої на одиницю менший, і потрапляє в не ту, що треба, клітинку, на 25 кроці.  А мало б зайти в клітинку, що позначена кроком 13 та 16.

Спочатку я намутив хтозна-що з усілякими індексами і т.д. А потім просто зрозумів, що після "руху назад", нові клітинки треба додавати в стек не на самий верх, чи низ, а запихувати її на той індекс, котрий ми отримаємо, якщо відняти від максимального індексу кількість кроків, котрі ми пройшли "назад". Тоді індекси клітинок, котрі ми додали перед тим, як зайти в глухий кут, залишаться ”зверху” стека, і ми не зайдемо в ті клітинки, коли будемо рухатись назад.

Коротше кажучи, треба було просто створити змінну для поточного індексу, і при додаванні нової клітинки інкрементувати той індекс, а при "русі назад" зменшувати на 1.


хоча я помітив, що воно знову якось трохи не так робе

Озьдо лайнокід, включно з закоментованим ще більшим лайнокодом.

Мова - Java, середовище розробки - Processing, можете запустити та погратись

class Stack<T>
{
  private ArrayList<T> items;
  private int back=0;
  public int addInARow=0;
  public int backStart=0;
  public int currentIndex=0;
  
  public Stack()
  {
    items = new ArrayList<T>();
  }
  
  public void Push(T item)
  {
    items.add(currentIndex, item);
    currentIndex++;
    
   /* if(back>0){
      backStart=items.size()-back-1;
      back=0;
      addInARow=0;
      
     // println("remembered index: "+backStart+"  "+((int[])items.get(backStart))[0]+" "+((int[])items.get(backStart))[1]);
    }
    addInARow++;*/
    
  }
  
  public T Pop()
  {
    /*if(items.size()>0)
    {
      T result;
      int index = items.size()-1-back;
      back++;
      if(back-1==addInARow)
      {
       // println("oh yah! popping: "+backStart+"  back: "+back+" addInARow: "+addInARow);
        result = items.get(backStart);
        back = items.size()-backStart;
      }
      else
      {
       // println("popping: "+index+"  "+((int[])items.get(index))[0]+" "+((int[])items.get(index))[1]);
        result = items.get(index);
      }
      //items.remove(items.size()-1);
      return result;
    }
    return null;*/
    currentIndex--;
    if(currentIndex<0)
      currentIndex=0;
    return items.get(currentIndex);
  }
  
  public boolean Exists(int[] item)
  {
    for(int i =0; i<items.size(); i++)
    {
      int[] it = (int[])items.get(i);
      if(it[0]==item[0] && it[1] == item[1])
      {
        return true;
      }
    }
    return false;
  }
}

class Maze
{
  
  public int ww, wl, w, h, xOffset, yOffset; //ww - wall width, wl - wall length, w  - width, h - height
  
  class Room
  {
    class Wall
    {
      public boolean state;
    }
    
    public String visited=" ";
    
    public Room ()
    {
      top=new Wall();
      right=new Wall();
      bottom = new Wall();
      left = new Wall();
    }
    
    public Wall top, right, bottom, left;
  }
  
  private Room[][] rooms;
  
  public Maze(int roomX, int roomY, int wallWidth, int wallLength, int xOffset, int yOffset)
  {
    w=roomX;
    h=roomY;
    ww = wallWidth;
    wl = wallLength;
    this.xOffset = xOffset;
    this.yOffset = yOffset;
    
    rooms = new Room[roomX][roomY];
        
    for(int i =0; i<roomX; i++)
    {
      for(int j = 0; j<roomY; j++)
      {
        rooms[i][j]=new Room();
        if(i>0)
        {
          rooms[i][j].left = rooms[i-1][j].right;
        }
        if(j>0)
        {
          rooms[i][j].top = rooms[i][j-1].bottom;
        }
      }
    }
    
   /* rooms[roomX/2-1][roomY/2-1].right.state=true;
    rooms[roomX/2][roomY/2-1].bottom.state=true;
    rooms[roomX/2][roomY/2].left.state=true;
    rooms[roomX/2-1][roomY/2].top.state=true;*/
  }
  
  public void OpenRoom(int fromX, int fromY, int toX, int toY)
  {
    int x = toX-fromX;
    int y = toY-fromY;
    
    if(x==1)
    {
      rooms[fromX][fromY].right.state = true;
    } else
    if(x==-1)
    {
      rooms[fromX][fromY].left.state = true;
    } else
    if(y==1)
    {
      rooms[fromX][fromY].bottom.state = true;
    } else
    if(y==-1)
    {
      rooms[fromX][fromY].top.state = true;
    }
  }
  
  public void Draw()
  {    
    int i=0, j=0;
    
    int xstep = (wl+ww);
    int ystep =(wl+ww); //<>//
    
    for(i = 0; i<w; i++)
    {
      for(j = 0; j<h; j++)
      {
        stroke(100);
        strokeWeight(ww);
        
       // println("i: "+i+" j: "+j +"  rooms[0].length: "+rooms[0].length+"  rooms[1].length: "+rooms[1].length);
        
        Room room = rooms[i][j];
        
        textSize(15);
        String text = room.visited;
        fill(0, 0, 0, 250);
        text(text, xOffset+i*xstep+6/max(text.length(),1), yOffset+j*ystep+12); 
        
        if(room.top.state==false)
        {
          line(xOffset+i*xstep, yOffset+j*ystep, xOffset+i*xstep+wl, yOffset+j*ystep);
        }
        if(room.right.state==false)
        {
          line(xOffset+i*xstep+wl+ww, yOffset+j*ystep, xOffset+i*xstep+wl+ww, yOffset+j*ystep+wl);
        }
        if(room.bottom.state==false)
        {
          line(xOffset+i*xstep, yOffset+j*ystep+wl+ww, xOffset+i*xstep+wl, yOffset+j*ystep+wl+ww);
        }
        if(room.left.state==false)
        {
          line(xOffset+i*xstep, yOffset+j*ystep, xOffset+i*xstep, yOffset+j*ystep+wl);
        }
      }
    }
  }
}

Maze maze;


void setup()
{
  size(800, 800);
  background(233,216,185);
  
  maze= new Maze(10, 10, 5, 30, 50, 50);
  stack = new Stack<int[]>();
  initX = (int)random(0,maze.w);
  initY = (int)random(0,maze.h);
  currX=initX; currY=initY;
  numVisit=1;
  
  oldCx=0; oldCy=0;
  stack.Push(new int[]{initX, initY});
  
  //MakePath();
  
  maze.Draw();
  
}

boolean wait=true, canGo=false;
int value=-1;

void draw()
{   
 /* fill(value);
  if(wait)
  {
   // delay(5000);
    wait=false;
  }*/
  
  //if(canGo)
  {
    //canGo=false;
    clear();
    background(233,216,185);
    MakePath();

    maze.Draw();
  }
  delay(200);
}

void keyPressed() {
 canGo=true;
}

Stack<int[]> stack;
int initX;
int initY;
int currX, currY;
int numVisit;

int oldCx, oldCy;

void MakePath()
{
 // for(int i =0; i<200; i++){
  
   // println("curr X: "+currX+"  curr Y: "+currY);
    
   // while(true){    
    int tempX = 0;
    int tempY = 0;
  
    boolean found=false;
  
    ArrayList<int[]> ways = new ArrayList<int[]>();
    
    if(currX>0 && !stack.Exists(new int[]{currX-1, currY}))
    {
      ways.add(new int[]{-1,0});
    }
    if(currX<maze.w-1 && !stack.Exists(new int[]{currX+1, currY}))
    {
      ways.add(new int[]{1,0});
    }
    if(currY>0 && !stack.Exists(new int[]{currX, currY-1}))
    {
      ways.add(new int[]{0,-1});
    }
    if(currY<maze.h-1 && !stack.Exists(new int[]{currX, currY+1}))
    {
      ways.add(new int[]{0,1});
    }
    
    int index = -1;
    index = (int)random(0, ways.size());
    if(ways.size()>0)
    {
      tempX = currX + ways.get(index)[0];
      tempY = currY + ways.get(index)[1];
      
      found=true;
    }
    
   
   /* for(int x =-1; x<2; x++)
    {
      for(int y = -1; y<2; y++)
      {
        if(x!=0 && y!=0){
          continue;
        }
          
        tempX = x+currX;
        tempY = y+currY;
        
        if(tempX>=0 && tempX<maze.w && 
          tempY>=0 && tempY<maze.h &&
          !stack.Exists(new int[]{tempX, tempY}))
        {
          found=true;
          println("found: "+tempX+"  "+tempY);
          break;
        }
      }
      if(found)
        break;
    }*/
    
    if(!found)
    {
      if(currX==initX && currY ==initY){
       // println("end");
        return;
      }
      else
      {
        int[] back = stack.Pop();
        if(back==null)
        {
         // println("end #2");
          return;
        }
        else
        {
         // println("back: "+back[0]+" "+back[1]);
        }
        currX = back[0];
        currY = back[1];
        
       // println("\t\t\tpop: "+currX+"  "+currY+" add in a row: "+stack.addInARow+"  back: "+stack.back);
        maze.rooms[oldCx][oldCy].visited = "";
        maze.rooms[currX][currY].visited = "+";
        oldCx = currX;
        oldCy = currY;
        
        if(currX==initX && currY ==initY){
         // println("end");
          return;
        }
      }
    }
    else
    {
      maze.OpenRoom(currX, currY, tempX, tempY);
      currX = tempX;
      currY = tempY;
      
      maze.rooms[oldCx][oldCy].visited = "";
      maze.rooms[currX][currY].visited = "+";
      oldCx = currX;
      oldCy = currY;
      
      //println("\t\t\tpush: "+currX+"  "+currY+" add in a row: "+stack.addInARow+"  back: "+stack.back);
      stack.Push(new int[]{currX, currY});
    }
    //}
 // } 
}
Подякували: 0xDADA11C71

12 Востаннє редагувалося FakiNyan (19.01.2017 17:12:09)

Re: порадьте алгоритм генерації лабиринту

зацініть, це алгоритм крускала з рандомним вибором стінки, 20x20

Прихований текст

http://не-дійсний-домен/trII5/8a4d7ea405.gif

100x100

Прихований текст

http://не-дійсний-домен/trLeu/a12c1cfef0.png

пів дня генерувалося

Подякували: 0x9111A, quez2

13 Востаннє редагувалося FakiNyan (21.01.2017 14:07:35)

Re: порадьте алгоритм генерації лабиринту

а оце алгоритм Прима 20 x 20

Прихований текст

http://не-дійсний-домен/tud6D/2dad22dd25.gif

14 Востаннє редагувалося FakiNyan (21.01.2017 14:14:51)

Re: порадьте алгоритм генерації лабиринту

капець, я й не думав, що відмалювання кожної зміни забирає так багацько часу. Якщо малювати лабиринт 100х100 покроково, то на це йде купа часу, а якщо відразу все зробити, і відмалювати лише результат, то воно виконується миттєво.
То, походу, через те, що відмальовка виконується 30, чи 60 разів в секунду, через то й так довго.
аах, ну да. Воно ж, при відмальовці, проходить по кожній клітинці і перевіряє, чи треба малювати кожну стінку, це теж багацько часу займає, і чим більший лабиринт, тим більше часу