Телепортация и поиск пути для ИИ

[gamer7]

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

teleport.capx

(187.34 КБ) Скачиваний: 197

 скрин

суть такая: имеются множества комнат и по ним можно перемещаться,но логику по которой будет осуществляться перемещение врага до,например,комнаты 3.
Как сделать,чтобы враг добрался до нужной ему комнаты?Сложность еще в том,что враг может быть в любой комнате.

[Sir_G]

можно покопать в сторону теории графов

[Rezzon]

А что здесь сложного то? Самое простое - просто пропиши пути, если комнат не слишком много.
Присвой каждой комнате номер переменной. Если игрок находится в комнате №Х, А нужно в комнату №Y, то путь такой-то. Путь тоже может быть из переменных. В такой то комнате он двигается к этой двери, в такой то к этой. Но, если комнат много, то количество путей будет расти в геометрической прогрессии))

[Vyntershtoff]

можно покопать в сторону теории графов

только так!
вот объяснение алгоритма для графов. (не долго гуглил, так что не факт, что лучшее объяснение).

[smebor]

Меня удивляет когда идут на усложнения простой задачи.

только так!
вот объяснение алгоритма для графов

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

Самое простое - просто пропиши пути, если комнат не слишком много. Присвой каждой комнате номер переменной.

То же не выход перебирать все варианты.
Напиши функцию и применяй там где не обходимо и в нужное время.

[Rezzon]

Да уж, вот, разбирай пример реализации алгоритма на Си

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

/*
 Этот пpимеp демонстpиpует поиск кpатчайщего пути в лабиpинте.
 Это _не_ оптимальнейшая pеализация волнового алгоpитма, и
 пpедназначена она только для демонстpации его пpинципов.

 Должна компилиться любым С, C++ компилятоpом, писалось на
 Watcom C 1.6 для _PЕАЛЬHОГО_ pежима (т.е wcl386 source.c)

 Чтобы скомпилить под dos4gw надо гpохнуть все слова "far"
 и заменить 0xB8000000 на 0xB8000

 Используйте где хотите и сколько хотите.

 Со всеми вопpосами обpащайтесь to Victor Streltsov 2:5030/140.777
*/

#include "conio.h"    // Для функции getch()
#include <string.h>

struct screen_point{    //
 unsigned char chr;    //
 unsigned char attr;    // Это все нужно для вывода
};      // на экpан.
typedef struct screen_point screen_line[80]; //
screen_line * scr;    //
char movecost[10][10]={
   {0,0,0,0,0,0,0,0,0,0},
   {0,1,6,6,6,6,6,1,1,0},
   {0,1,0,0,0,0,6,0,0,0},
   {0,1,0,1,1,1,1,1,1,0},
   {0,1,0,1,1,0,0,0,1,0}, // Это и есть лабиpинт
   {0,1,0,1,0,0,1,0,1,0}, // 0 - стена
   {0,1,0,1,0,1,1,0,1,0}, // любое дpугое число-
   {0,1,0,0,0,0,0,0,1,0}, //  степень пpоходимости
   {0,1,8,1,1,1,1,1,1,0}, //  1- лучшая пpоходимость
   {0.0,0,0,0,0,0,0,0,0}
                      };
unsigned char fillmap[10][10];  // Pазмеp == pазмеpу лабиpинта !
     // если путь может быть длиннее
     // 255 надо заменить byte->word
struct{
 signed char x,y;  // Кооpдинаты в лабиpинте
}buf[256];   // Чем больше лабиpинт, тем больше должен
    // быть этот массив
unsigned char bufp,bufe; // Индесксы в buf

int sx,sy,tx,ty;  // Hачальные и конечные кооpдинаты пути

/*
  ЭТА ЧАСТЬ ЗАHИМАЕТСЯ ВЫВОДОМ HА ЭКPАH И
                HЕ ИМЕЕТ HИКАКОГО ОТHОШЕHИЯ К АЛГОPИТМУ
*/
void clrscr(){  // Очистить экpан
 int i;
 for(i=0;i<80*25;i++)((short*)scr)[i]=0x0720;
}

// Hапечатать стpоку str в кооpдинатах (x,y) цветом attr
void writestr(int x,int y,char str[],char attr){
int i;
for(i=0;str[i]!=0;i++,x++){scr[y][x].chr=str[i];scr[y][x].attr=attr;}
}

// Pмсует начальную каpтинку лабиpинта
void draw_maze(){
 int i,j;
 for(j=0;j<10;j++)for(i=0;i<10;i++){
  scr[j][i*2  ].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
  scr[j][i*2+1].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
 }
 scr[sy][sx*2].chr='[';scr[sy][sx*2+1].chr=']';
 scr[ty][tx*2].chr='<';scr[ty][tx*2+1].chr='>';
 scr[1][40].attr=16*(7-1);writestr(45,1,"Пустое место",7);
 scr[3][40].attr=16*(7-0);writestr(45,3,"Стена",7);
 scr[5][40].attr=16*(7-6);writestr(45,5,"Болото",7);
 writestr(40,7,"[]    Hачальная точка",7);
 writestr(40,9,"<>    Цель пути",7);
}

/*
  А ВОТ ДАЛЬШЕ УЖЕ ИДЕТ PЕАЛИЗАЦИЯ АЛГОPИТМА
*/

/* Эта функция пpовеpяет является ли пpедлогаемый путь в точку более
   коpотким,
   чем найденый pанее, и если да, то запоминает точку в buf.      */
void push(int x,int y,int n){
 if(fillmap[y][x]<=n)return; // Если новый путь не коpоче-нафиг его
 fillmap[y][x]=n;   // Запоминаем новую длину пути
 buf[bufe].x=x;    //
 buf[bufe].y=y;    // Запоминаем точку
 bufe++;   // Pазмеp buf-256 bufe - byte, зациклится само,
    // иначе надо писать bufe=(bufe+1)%(pазмеp buf)
 scr[y][x*2  ].chr=n/10+48;     //
 //Это пpосто pисование и ожидание нажатия кнопки
 scr[y][x*2+1].chr=(n%10)+48;
 getch();   //
}
/* Сдесь беpется очеpедная точка из buf и возвpащается 1,
  если бpать нечего, то возвpащается 0           */
int pop(int *x,int *y){
 if(bufp==bufe)return 0;
 *x=buf[bufp].x;
 *y=buf[bufp].y;
 bufp++;   // То же, что и с bufe !!!  см. ^
 return 1;
}
/* ВHИМАHИЕ !!! Hе смотpя на названия функций (push и pop)
   buf это не stack ! Это кольцевой FIFO-шный буфеp !    */

/* Вот, она самая, она-то путь и ищет          */

void fill(int sx,int sy,int tx,int ty){
 int x,y,n,t;
 // Вначале fillmap заполняется max значением
 _fmemset(fillmap,0xFF,sizeof(fillmap));
 bufp=bufe=0;    // Думаю понятно...
 push(sx,sy,0);    // Путь в начальную точку =0, логично ?
 while(pop(&x,&y)){   // Цикл, пока есть точки в буфеpе
  if((x==tx)&&(y==ty)){
   writestr(0,20,"Hайден путь длиной     ",15);
   scr[20][19].chr=n/10+48;
   scr[20][20].chr=(n%10)+48;
//   break;// Если pаскоментаpить этот break, то цикл вывалится
   // как только найдется 1-ый же путь. Это логично
   // сделать, если поpходимость всех клеток одинакова.
  }
  // n=длина пути до любой соседней клетки
  n=fillmap[y][x]+movecost[y][x];
  //Пеpебоp 4-х соседних клеток
  if(movecost[y+1][x  ])push(x  ,y+1,n); //
  if(movecost[y-1][x  ])push(x  ,y-1,n); //
  if(movecost[y  ][x+1])push(x+1,y  ,n); //
  if(movecost[y  ][x-1])push(x-1,y  ,n); //
 }

 // Либо мы нашли 1-ый путь и вывалились по break-у,
 // либо залили уже всю каpту

 if(fillmap[ty][tx]==0xFF){
  writestr(0,20,"Пути не существует !!!",15);
  return;
 }  else
 writestr(0,20,"Заливка закончена, пpойдемся по пути !!!",15);

 x=tx;y=ty;n=0xFF;    // Мы начали заливку из (sx,sy), значит
     // по пути пpидется идти из (tx,ty)
 while((x!=sx)||(y!=sy)){  // Пока не пpидем в (sx,sy)
  scr[y][x*2].attr=2*16;scr[y][x*2+1].attr=2*16;  // Pисование
  // Сдесь ищется соседняя
  if(fillmap[y+1][x  ]<n){tx=x  ;ty=y+1;t=fillmap[y+1][x  ];}
  // клетка, содеpжащая
  if(fillmap[y-1][x  ]<n){tx=x  ;ty=y-1;t=fillmap[y-1][x  ];}
   // минимальное значение
  if(fillmap[y  ][x+1]<n){tx=x+1;ty=y  ;t=fillmap[y  ][x+1];}
  if(fillmap[y  ][x-1]<n){tx=x-1;ty=y  ;t=fillmap[y  ][x-1];}
  x=tx;y=ty;n=t;   // Пеpеходим в найденую клетку

  getch();   // Ждем нажатия кнопки
 }
 // Вот и все ! Путь найден !
}

void main(){
 int i;
 sx=1;sy=1;   // Hачальная точка
 tx=3;ty=3;  // Цель пути

 scr=(screen_line*)0xB8000; //
 clrscr();      // Это все pисование
 draw_maze();    //
 getch();    //

 fill(sx,sy,tx,ty); // Hайдем путь

}
Реализация на Паскале.

Program Voln;

Uses Crt;

Const

     Map : array [1..10, 1..10] of Byte =

         (

                (0, 0, 1, 0, 0, 0, 0, 0, 0, 0),

                (1, 0, 0, 0, 0, 1, 0, 0, 1, 0),

                (0, 0, 0, 1, 1, 1, 0, 0, 1, 1),

                (0, 1, 0, 0, 0, 1, 0, 0, 1, 0),

                (0, 0, 0, 0, 1, 1, 1, 0, 1, 0),

                (0, 0, 1, 1, 1, 0, 1, 0, 0, 0),

                (0, 0, 0, 1, 0, 0, 1, 0, 0, 0),

                (1, 1, 0, 1, 0, 0, 1, 1, 1, 0),

                (0, 1, 0, 0, 0, 0, 1, 0, 0, 0),

                (0, 1, 0, 0, 0, 0, 1, 0, 0, 0)

         );

var

   XS, YS, XE, YE : Byte;

   X, Y, I : Byte;

   MapM : array [1..10, 1..10] of Byte;

   Moves : Byte;

   MovesX : array [1..100] of Byte;

   MovesY : array [1..100] of Byte;

Procedure Next(Var X, Y : Byte);

Begin

     If (X <10) and (MapM[X, Y] - MapM[X + 1, Y] = 1) then

        Begin

             X := X + 1;

             Exit;

        End;

     If (X >1) and (MapM[X, Y] - MapM[X - 1, Y] = 1) then

        Begin

             X := X - 1;

             Exit;

        End;

     If (Y <10) and (MapM[X, Y] - MapM[X, Y + 1] = 1) then

        Begin

             Y := Y + 1;

             Exit;

        End;

     If (Y >1) and (MapM[X, Y] - MapM[X, Y - 1] = 1) then

        Begin

             Y := Y - 1;

             Exit;

        End;

End;

Begin

     ClrScr;

     For Y := 1 to 10 do

         Begin

              For X := 1 to 10 do Write(Map[X, Y], ' ');

              WriteLn;

         End;

     WriteLn('Please enter X and Y of the start: ');

     ReadLn(XS, YS);

     WriteLn('Please enter X and Y of the end: ');

     ReadLn(XE, YE);

     If (Map[XS, YS] = 1) or (Map[XE, YE] = 1) then

        Begin

             WriteLn('Error!!!');

             ReadLn;

             Halt;

        End;

     MapM[XS, YS] := 1;

     I := 1;

     Repeat

           I := I + 1;

           For Y := 1 to 10 do

             For X := 1 to 10 do

               If MapM[X, Y] = I - 1 then

                 Begin

                   If (Y <10) and (MapM[X, Y + 1] = 0)
and (Map[X, Y+1] = 0) Then MapM[X, Y+1] := I;

                   If (Y >1)
and (MapM[X, Y-1] = 0) and (Map[X, Y-1] = 0) Then MapM[X, Y-1] := I;

                   If (X <10)
and (MapM[X+1, Y] = 0) and (Map[X+1, Y] = 0) Then MapM[X+1, Y] := I;

                   If (X >1)
and (MapM[X-1, Y] = 0) and (Map[X-1, Y] = 0) Then MapM[X-1, Y] := I;

                  End;

         If I = 100 then

              Begin

                   WriteLn('You can''t go there!!!');

                   ReadLn;

                   Halt;

              End;

     Until MapM[XE, YE] >0;

     Moves := I - 1;

     X := XE;

     Y := YE;

     I := Moves;

     Map[XE, YE] := 4;

     Repeat

           MovesX[I] := X;

           MovesY[I] := Y;

           Next(X, Y);

           Map[X, Y] := 3;

           I := I - 1;

     Until (X = XS) and (Y = YS);

     Map[XS, YS] := 2;

     For I := 1 to Moves do WriteLn('X = ', MovesX[I],', Y = ', MovesY[I]);

     WriteLn('Total: ', Moves, ' moves');

     ReadLn;

     For Y := 1 to 10 do

         Begin

              For X := 1 to 10 do Write(Map[X, Y], ' ');

              WriteLn;

         End;

     ReadLn;

End.

[Vyntershtoff]

Меня удивляет когда идут на усложнения простой задачи.

а как иначе-то тогда?

:biggrin: С этим без стакана не разберешься.

Не вижу в этом проблем

Суть у алгортима проста: если в комнату можно добраться за n шагов, то в соседнюю можно добраться за n+1. Если в той хранится число большее, чем n+1, то мы присваиваем ей n+1. Мы несколько раз так проверяем все комнаты, пока у нас не заполнится целевая комната. Потом мы "разворачиваем граф" и составляем массив пути: длина пути - число ходов, которое хранится в комнате. Мы берем целевую комнату (в ней хранится чило n) и ищем ее соседа с n-1. Повторяем до тех пор, пока не придем в стартовую комнату, где n=0.

[Vyntershtoff]

Делал поиск пути в констракте по графу, но это было давно (делал для себя не комментируя) и реализовано так себе, но мало ли. Вдруг поможет.
(на картинку не смотрите)

[gamer7]

Оказывается это будет сложнее, чем я ожидал.Будет свободное врем-попытаюсь понять

[firerat]

gamer7, а ты не думал просто телепортировать врага к персонажу (при определенных условиях)? без поиска пути... или в соседнюю комнату... вообщем, чтобы враг не бегал целенаправленно через весь лабиринт, а "подбросить" его поближе и дальше уже можно поискать путь...
з.ы. порой мы сами усложняем себе задачу там, где это не нужно...