AI z siatką waypointów

[Exigo]

Orientuje się ktoś w tym temacie? W jakiej formie należy przygotować taką siatkę i połączyć z jakąś zewnętrzną biblioteką wyszukiwania ścieżek, aby to miało ręce i nogi? Szukałem po sieci, ale większość przykładów obsługuje ruch 4 lub 8-kierunkowy.

Mi jednak chodzi o coś innego - na wzór grafu, gdzie to ja definiuje połączenia, a kod generuje listę id waypointów.

Tu jest to dokładnie pokazane (ba!, zrobione w gm'ie) ; )

http://www.youtube.com/watch?v=0LK_TB9IY9Q

Jakieś pomysły? ; )

[Roki]

It basicly loops through every waypoint, checking if it's close enough to another waypoint, and if nothing is blocking it's way.

 

W sumie wystarczy zrobić obiekt "objPoint" i potem pętlą po każdym jechać i sprawdzać mozliwe połączenia. Co do połączeń, użyłbym tablicy i tam zapisywał ID/numer innych punktów :>

[gnysek]

Coś takiego chyba mój brat robił teraz na zaliczenie na polibudę w C... wystarczyła do tego macierz, wyliczało się krawędzie i wierzchołki i potem w sumie prostą pętlą od razu najkrótszą drogę wskazywało.

 

#include<stdio.h>
#include<stdlib.h>
#define ROZMIAR 5

struct skraw {
   int i;
   int j;
};

int silnia(int n) {
   return (n < 1) ? 1 : n * silnia(n-1);
}

int liczbaKraw(int x) {
   return silnia(x)/( 2 * silnia(x-2));
}

int main() {
   int i,j;
   int m[ROZMIAR][ROZMIAR] = {
        {0,1,1,0,0},
        {0,0,0,7,0},
        {0,5,0,0,0},
        {2,0,3,0,1},
        {0,3,0,0,0}
       };
   struct skraw* krawedzie = (struct skraw*) malloc(liczbaKraw(ROZMIAR)*sizeof(struct skraw));

   printf("%i\n", liczbaKraw(ROZMIAR));

   for (i=0; i<ROZMIAR; i++) {
       for (j=0; j<ROZMIAR; j++) {
           printf("%i ", m[i][j]);
       }
       printf("\n");
   }

   int liczbaKrawedzi = 0;
   //sprawdzamy macierz
   for (i=0; i<ROZMIAR; i++) {
       for (j=0; j<ROZMIAR; j++) {
           if (m[i][j] * m[j][i] != 0) {
               printf("bledna macierz\n");
           } else if (m[i][j] > 0) {
               //printf("%i %i\n",i,j);
               //dodajemy krawedz
               krawedzie[liczbaKrawedzi].i = i;
               krawedzie[liczbaKrawedzi].j = j;
               //printf("dodana krawedz %i, i = %i, j = %i\n", liczbaKrawedzi + 1, krawedzie[liczbaKrawedzi].i, krawedzie[liczbaKrawedzi].j);
               liczbaKrawedzi++;
           }
       }
   }

   // liczba wierzcholkow
   int liczbaWierzcholkow = 0;

   for (i=0; i<ROZMIAR; i++) {
       int suma = 0;
       for (j=0; j<ROZMIAR; j++) {
           //printf("%i %i\n",m[i][j],m[j][i]);
           suma+= m[i][j];
           suma+= m[j][i];
       }
       //printf("\n");
       if (suma > 0) liczbaWierzcholkow++;
   }

   int d[ROZMIAR], *p;
   p = (int*) malloc(liczbaWierzcholkow*sizeof(int));

   for (i=0; i< liczbaWierzcholkow; i++) {
       d[i] = 30000;
       p[i] = -1;
   }

   int pyt;

   printf("skad startowac: ");
   scanf("%i", &pyt);
   //printf("z: %i\n", pyt);
   //printf("liczba wierzcholkow: %i\n", liczbaWierzcholkow);

   d[ pyt ] = 0;

   for (i=liczbaWierzcholkow-1; i>=0; i--) {
       for (j=0; j<liczbaKrawedzi; j++) {
           //printf("if ( d[%i] > d[%i] + m[ %i, %i ] )\n", krawedzie[j].j, krawedzie[j].i, krawedzie[j].i, krawedzie[j].j);
           //printf("if ( %i > %i + %i )\n\n", d[krawedzie[j].j], d[krawedzie[j].i], m[ krawedzie[j].i ][ krawedzie[j].j ]);

           if ( d[ krawedzie[j].j ] > d[ krawedzie[j].i ] + m[ krawedzie[j].i][ krawedzie[j].j ] ) {
               d[ krawedzie[j].j ] = d[ krawedzie[j].i ] + m[ krawedzie[j].i][ krawedzie[j].j ];
               p[ krawedzie[j].j ] = krawedzie[j].i;
           }
       }
   }

   /*for (i=0; i< liczbaWierzcholkow; i++) {
       printf("d[%i] = %i, p[%i] = %i\n", i, d[i], i, p[i]);
   }*/

   int koniec;

   printf("gdzie konczyc: ");
   scanf("%i", &koniec);
   //printf("do: %i\n", koniec);

   if (d[ koniec ] < 1 || d[ koniec ] >= 30000) {
       printf("nie ma drogi\n");
       return 1;
   }

   int k;
   k = koniec;

   int droga[ ROZMIAR ];
   j = ROZMIAR - 1;

   for (i=0; i< ROZMIAR; i++) {
       droga[ i ] = -1;
   }

   while (k > -1) {
       droga[ j ] = k;
       k = p[ k ];
       j--;
   }

   if (NULL == 0)
   for (i=0; i< ROZMIAR; i++) {
       if (droga[i]>=0) {
           printf("krok: %i\n", droga[ i ]);
       }
   }
   printf("koszt: %i\n", d[ koniec ]);

return 0;
}

 

Nie wiem jak to dokładnie działa, podajesz tam punkty grafu chyba z ktorego do którego idziesz i on podaje przez co przechodzisz.

 

Edit: ah, to jest jednokierunkowe i jeszcze tam jakieś wagi są podawane, zeby iść drogą z najmniejszym kosztem, a nie tylko najkrótszą.

[Will]

Poszukaj: Navigation Graph

 

Generalnie w takim prostym przypadku całość nie jest zbytnio skomplikowana: budujesz sobie strukturę przechowującą sąsiadów+opcje według, których wybierasz najkrótszą ścieżkę a potem rzucasz na to A*.