Алгоритм (путь через лабиринт)

[Sirik]

Люди, нужна помощь!!!
Может кто знает, как находить путь в лабиринте?
Например лабиринт задан матрицей:
11111
1A001
11101
10101
10B01
11111
Нужно пройти из А в В кротчайшем путём.
Я пробовал алгоритм с возвратом, он очень медленный. Может кто знает быстрый...
Очень надо

[GAGArin]

Методом волны. Создаешь функцию которая проходит из точки а и идет во все стороны, оттуда тоже во все кроме той откуда пришла. когда доходит до точки б смотрит путь и время и пишит их в результаты. потом выбираешь наименьший путь (и) и всё. Работает быстрее если пускать две функции. одну из а другую из б. пока не встретятся. но это труднее реализовать.

[Aqualung]

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

1. Каждой клетке присваивается свойство "Жизнь" (целое).
2. "Жизнь" всех клеток обнуляется.
3. Объявляется переменная "Текущая жизнь"=1.
4. Целевой клетке В также присваивается значение "Жизнь"=1.
5. Начало цикла.
6. Каждая свободная клетка, у которой "Жизнь"="Текущая жизнь", "оживляет" соседние клетки (в данном случае с общими сторонами), присваивая для них "Жизнь"="Текущая жизнь"+1.
7. "Текущая жизнь"="Текущая жизнь"+1.
8. Цикл завершается, если:
а) в данной итерации нет ни одной передачи "Жизни" - пути между А и В не существует;
б) "оживляется" исходная клетка А.
8. Перемещение начинается из А и идет из клетки со значением "Жизнь"=n в клетку со значением "Жизнь"=n-1.

[Sirik]

Да, про этот метод я слышал, но вот что про него говорят в инете:

Достоинствa - простотa, нaдёжность, 100% сaмый короткий путь (для клaссического методa). Hедостaтки - большой объём требуемой пaмяти и не сaмaя высокaя скорость нaхождения пути. В "HЛО-2", при перечисленных выше условиях, нaхождение пути может достигaть по времени до 1/10 секунды. Это, конечно, приемлимо для пошаговых стрaтегий и логических игрушек, но с трудом подойдёт для динaмических игр. A про попытку реaлизaции нa Бейсике я вообще молчу (рaзве в кaчестве примерa).

Так что врядли мне он подойдёт. Может что-то еще есть.

[Sirik]

Ладно, попробую через возврат.
Тогда кто-нибудь может мне посоветовать алгоритм (может и с примером) генерации случайного лабиринта.
У меня есть код, но он на С, может кто-то мне переыедёт:

Код: Выделить всё

//this demonstrates pseudo 2 dimentional array
//and labyrinth generation
//compiled with borlands C++ 5.5 command line compiler
/* The key point for this algorithm is to generate all initial points that will construct the walls of the labirinth
with even indexes like a[2][8] (see function getrandom(). All derived points (see explanation below in main())
must have at least one of the indexes even like a[5][4]. This is insured by always starting from initial point with
even coordinates.
Programm utilizes one-dimentional array for holding of labyrinth data that allows flexible memory allocation for different
labyrinth dimentions*/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>

//#define BCC                /*borland c++ compiler used*/
#ifdef BCC
#undef VCC
#else
#define VCC              /*microsoft c++ compiler for windows32 used */
#endif

#ifdef BCC
#define cls() clrscr();
#else
#include <windows.h>
#include <time.h>
#define cls() (printf("\n\n\n\n\n"))
HANDLE hdl = 0;
#endif

#define makeeven(_num)(_num & 0xFE)
#define myrand(_num)(_num?rand()%_num:0)
#define myevenrand(_num)(myrand(_num)& 0xFE) //obtain even number in the given range by clearing first bit
#define evenmax(_num)(_num & 0xFE)
#define evenaverage(_num)((evenmax(_num)/2)& 0xFE) 
#define myoddrand(_num)(myrand(_num)| 0x01)
#define randomize()(srand( (unsigned)time( NULL ) ))

void usage(void);
void display(int size,int w);                   //displays labirinth
void createborder(int size,int w,int h);        //creates lab border
void createdoors(int size, int width);
void consinit(void);
void cleanup(void);
int getrandom(int width,int height,int *x);
int getdirection(int width);
int evenbetween(int n1, int n2);
int oddbetween(int n1, int n2);

int *a;                                         //pointer to pseudo 2 dimentional array holding labirinth
int cycle;

int main(int argc, char *argv[])
{
  int *p,size,length,h,w;

  if(argc < 3){usage(); return 0;}
 
  /*if user put odd dimentions make them even*/
  h = makeeven(atoi(argv[2]));
  w = makeeven(atoi(argv[1]));

  //if(!(h & w)) {usage(); return 0;}  // to ensure they of the same size
  /*zero data check*/
  if(h == 0 || w == 0) {usage(); return 0;}
  if(argc > 3) length = atoi(argv[3]);

  length = length == 0?70:length;
  ++h; ++w; 
  size = h * w;
 
  /* allocate our array to hold lab. data*/
  a = (int *)calloc(size, sizeof(int));
       
  if(a != NULL)
    printf("\n\t%d bytes of memory allocated\n",size * sizeof(int));
  else{
    printf("Memory allocation failed\n");
    free(a);
    return 1;
  } 
   
  consinit();
  printf("\n\tprinting labyrinth, dimentions %d x %d...\n\n\t",w-1,h-1);
 
  createborder(size,w,h);
  createdoors(size,w);

  /*set random seed*/
  randomize();

  int x = 0,z = 0;
  cycle+= size + size/2;
  while(getrandom(w,h,&x) > 0) {
         
   if(a[x] == 1) continue;
   z = getdirection(w);
   //printf("%5d",x);

   /*here we're building the walls, creating derived points*/
   do{               
     if(a[x] == 0) a[x] = 1;
     x += z;
     if(myrand(100) > length) break;   
   }while(a[x] == 0 );
  }

  display(size,w);
  cleanup(); 
 
  return 0;
}

void createborder(int size,int w,int h){
  int *p = a;
   for(p;p - a < size;p++){
    if((p - a) < w ||          /* defines first row*/
    (p - a)%w == 0 ||          /* defines left side*/
    (p - a)%w == w - 1 ||      /* defines right side*/
    (p - a) > w * (h - 1))     /*   defines bottom*/
      *p = 1;
  }
}

void createdoors(int size, int width){
int t;
      do{ t = oddbetween(0,width); }while(t == 0 || t == width);
      a[t] = 0x2F;
      do{ t = oddbetween(size - width, size); }while(t == size || a[t] == 0);
      a[t] = 0x2F;
}

void display(int size,int w){
  int *p = a,row = 0;
  char ch = 32;
  printf("\n\n\t%05d",0x0);
  for(p;p - a < size;p++){
    if((p - a) > 0 && (p - a)%w == 0){     //print another row
       //printf("\n\t");
       if((p - a)%2 == 0) printf("\n\t%05d",row); else printf("\n\t%5c",32);
    } 
    //printf( " %c",(char)*p);
    ch = *p == 1? 120 : 32; printf ("%2c",ch);
    row++;
  }
  printf("\n");
}

/*this function defines in which direction we need to move while building the wall*/
inline int getdirection(int width){
  int z = myrand(4); 
  return (z == 0?-1: z == 1?1: z == 2? width: -width);
}

inline int oddbetween(int n1, int n2){
  int t;
  return (t = myoddrand(n2)) > n1?t:oddbetween(n1,n2);
}

inline int evenbetween(int n1, int n2){
  int t;
  return (t = myevenrand(n2)) > n1?t:evenbetween(n1,n2);
}

int getrandom(int width,int height,int *x){
int row,col;
row = evenbetween(0,height);
col = evenbetween(0,width);
*x = width * row + col;
/* here we prevent generation of number that would produce odd column value*/
if((*x%width)%2 != 0) {
    //printf("\n\tratio = %2d",(*x%width)%2); //getch();
    getrandom(width,height,x);
}
//  printf("\n\trow - %3d , col - %3d x = %3d width = %3d cycle = %4d", row,col,*x,width,cycle);
return cycle--;
}

void usage(void){
  printf("\nUsage: mylab <width> <height> <density>\n\n\twidth    - width of the labyrinth\n\theight   - height of the labyrinth"
         "\n\tdenstity - how long walls suppose to be\n\tall parameters are numbers\n\n");
}

void consinit(void){
  cls();
#ifdef VCC
   HANDLE hdl = GetStdHandle(STD_OUTPUT_HANDLE);
   if(hdl != INVALID_HANDLE_VALUE) SetConsoleTextAttribute(hdl, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
#endif
}

void cleanup(void){
#ifdef VCC
   if(hdl != INVALID_HANDLE_VALUE){
     SetConsoleTextAttribute(hdl, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
     FlushConsoleInputBuffer(hdl);
     CloseHandle(hdl);
   }
#endif
  free(a);
}



[Aqualung]

Нахождение пути или в определенных точек в матрице всегда будет пропорционально квадрату порядка матрицы, так что, никаких супералгоритмов здесь не предложишь. "Волна" или "Жизнь" - самый простой из них, на мой взгляд. Что касается динамики, графические редакторы используют и не парятся. А по поводу реализации на бейсике... Я, для развлечения, довольно быстро написал "Lines" и "Minesweeper" именно с этим алгоритмом.

[Sirik]

Я, для развлечения, довольно быстро написал "Lines" и "Minesweeper" именно с этим алгоритмом.

Правильно, для подобных игор время расчёта не имеет смысла. Я делаю игру где, как минимум, будет происходить 10 расчётов одновремённо. При этом матрица будет 30х60. Думаю тормоза будут крутейшие.

[alibek]

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

[mrs2000]

Попробуй A*
Он учитывает стоимость пути и направление к цели, тем самым осматривая меньше ячеек (в отличии от волны которая идет во всех направлениях одинаково)

Ну и конечно различные предвартельные расчеты, чтобы облегчть жизнь алгортму.

[Sirik]

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

Я так и попробовал (вчера) получилось нормально, т.е. поиск пути не провожу когда человечек не ходит. Как только пошёл, тогда и считаю.
Вобще-то тормоза у меня были когда я делал такую игру ещё на QBasic на 386... На VB всё ок.
Всем спасибо за помощь.

[GAGArin]

Кстати если это путь через лабиринт то не парься. Волна будет работать обалденно. Ей ведь будет надо идти одним и редко разветвляющемся путем.

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

[Mikle]

Вот генератор лабиринтов. Клик по форме - перерисовка:

[Sirik]

С обычным лабиринтом я разобрался (спасибо всем).
А кого есть мысли по поводу лабиринта игры Lode Runner?
Как там быть? Ведь, как я понимаю, там все эти методы не подойдут. Нельзя же человечку бегать по пустым местам, он просто упадёт. Тогда получается, что бегать можно везде лишь бы под ним было бы что-нибудь (стена, лестница, брусья и т.д. только не пустое место).
У кого будут идеи?