Προς το περιεχόμενο

Τεχνιτή νοημοσύνη που μαθαίνει...

desolatorXT

Από τον desolatorXT
στο Προγραμματισμός

Προτεινόμενες αναρτήσεις

desolatorXT Mentor

desolatorXT

Δημοσ.
Δημοσ.

Γεία.. φτιάχνουμε ένα game με 2 φίλους και έχουμε μερικά προβλήματα στο AI...

 

Έχουμε λοιπόν ένα 2D shooter, σκεφτήτε κάτι σε στύλ CS για να το καταλάβετε ποιο εύκολα. Θέλουμε λοιπόν, το bot να μην διαλέγει τυχαία ένα path στον χάρτη και να πηγαίνει από εκεί. Αλλα κρίνοντας απο διάφορα στοιχεία να επιλέγει το σωστό path, αλλά επίσης να θυμάται ότι ακολουθώντας το τάδε path ή όντας "καβατζωμένο" σε εκείνο το σημείο, το σκότωσε ο παίκτης, οπότε να μην το επιλέξει στον επόμενο γύρο. Σιγά σιγά λοιπόν να αναπτύσει τακτικες ενάντια στον παικτη και να βελτιωνεται, μαθαίνοντας απο τα λάθη του...

 

Σκεφτήκαμε αρκετές ιδέες, ένα σενάριο ήταν, να κάνουμε το παιχνίδι gird-based, δηλαδή να είνα η πίστα χωρισμένη σε τετράγωνα, ανάλογα με το πόσες φορές σκοτώθηκε στο κάθε τετράγωνο, ή έμεινε με λίγο HP, ή σκότωσε τον παίκτη, να αναβαίνει/κατεβαίνει η προτήμησή του γ αυτό(την προτήμιση την δείχει μια μεταβλητή). Έτσι το bot κινείται κάθε φορα στο κοντινό τετράγωνο που έχει την μεγαλύτερη προτίμηση.

 

Το πρόβλημα μ αυτό όμως είναι, ότι πολλές φορές κάνει κύκλους, ή μένει στα τετράγωνα που κάνει spawn... Επίσης δεν ξέρουμε πως να αποθηκεύσουμε τέτιου είδους πληροφορίες, ώστε να μην χρειάζετε κάθε φορά που κλείνει το πρόγραμμα να ξαναμαθαίνει. Και τέλος, όταν το πρόγραμμα ξεκινάει για πρώτη φορά, το bot Μερικές φορές δεν κινείτε γιατί δεν ξέρει σε πιο τετράγωνο να πάει εφόσον όλα έχουν τιμή προτίμησης 0...

Το μεγαλύτερο δε πρόβλημα όλων είναι ότι πολλές φορές, το τετράγωνο στο οποιο βρίσκετε έχει μεγαλύτερη προτίμηση απο τα γύρω, οπότε όταν πάει στο επόμενο τετράγωνο, κατόπιν θα διαλέξει να ξαναπάει στο προηγούμενο... Δλδ μένει στάσιμο στο ίδιο σημείο... Το πρόβλημα αυτό μεν λύθηκε απαγορευοντας στο bot να πηγαίνει στο προηγούμενο τετράγωνο, πολλές φορές όμως κατά την διάρκει της μάχης με τον παίκτη, πρέπει να πάει πίσω, αλλα δεν μπορεί γιατί δεν τον αφήνουμε, οπότε ένας κώδικας του λέει να πάει πίσω και ένας όχι, ώς αποτέλεσμα το Bot Κολάει εκεί χωρίς να κάνει τίποτα, και το σκοτώνει ο παίκτης...

 

Έχει κανείς καμιά ιδέα για την βελτίωση αυτού του συστήματος, ή και κάποιον άλλον τρόπο για να γίνει μια τεχνητή νοημοσύνη που να μαθαίνει?

 

thnx προκαταβολικά :)

  • 2 εβδομάδες αργότερα...
eirinikp Proficient

eirinikp

Δημοσ.
Δημοσ.

Prepei na diabasete papers sxetika me robot motion planning in 2D kai eidikotera texnikes euresis road map

 

Auto den einai lusi sto pws 8a "8umatai", alla einai lusi sto pws 8a briskei kainouria monopatia, upo tin proupo8esi oti 8umatai pou einai ta empodia. Etsi isws na min peftei se periptwseis pou de 8a 3erei pou na paei.

 

Ki egw den exw diabasei polla pragmata. Omws exontas ena oso to dunaton plirestero road map, toso pio eukolo 8a einai na briskei kapoio path to opoio 8a apofeugei ta empodia. (Empodia = palies diadromes opou skotw8ike)

http://igitur-archive.library.uu.nl/math/2006-1220-202051/UUindex.html

http://www.give.nl/movie/viewPublicPublications.php

eirinikp Proficient

eirinikp

Δημοσ.
Δημοσ.
Na proteinw ton A* algorithmo gia arxi gia 2D pathfinding.

Epeidi den ton 3erw, psaxnwntas brika auto to link. An exeis upopsin sou kai alla pou kukloforoun gia auton ton algori8mo (px ta pio advanced pou egrapses) steile na ta xoume upopsin!!

Fukushuusha Proficient

Fukushuusha

Δημοσ.
Δημοσ.

Eirinikp , to gamedev.net einai ena site me APEIRA tutorials kai poli enimerwtika forums mesa pou tha sas voithisoune se oti thelete.

 

Pate ekei kai psaxteite.

 

P.S. : NAi ayto to tutorial gia ton A* algorithm einai poli gnwsto kai poli kalo. Ama pas kai rwtiseis sto gamedev gia allous pio advanced algorithmous tha sou poune ... alla tha sou protathei prwta na kaneis implement ayton sto programma sou, dioti oloi oi alloi basizontai ligo i poli panw se ayton.

 

Genikotera siga siga pante to. Afou katanoisete ton A* kai niwsete oti den sas ikanopoiei psakste "Evolving pathfinding algotithms". Ayto asxoleitai me generic programming.

 

Elpizw na voithisa

FarCry Crazy Insomniac

FarCry

Δημοσ.
Δημοσ.

8. Dijkstra's Algorithm: While A* is generally considered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstra's usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.

 

 

So why use it? Sometimes we don't know where our target destination is. Say you have a resource-gathering unit that needs to go get some resources of some kind. It may know where several resource areas are, but it wants to go to the closest one. Here, Dijkstra's is better than A* because we don't know which one is closest. Our only alternative is to repeatedly use A* to find the distance to each one, and then choose that path. There are probably countless similar situations where we know the kind of location we might be searching for, want to find the closest one, but not know where it is or which one might be closest

 

The time complexity of A* depends on the heuristic. In the worst case, the number of nodes expanded is exponential in the length of the solution (the shortest path)

 

More problematic than its time complexity is A*'s memory usage. In the worst case, it must also remember an exponential number of nodes

 

Several variants of A* have been developed to cope with this, including iterative deepening A*, memory-bounded A* (MA*) and simplified memory bounded A* (SMA*) and recursive best-first search (RBFS).

unre@l Mentor

unre@l

Δημοσ.
Δημοσ.

Oriste mia upoloihsh tou dijkstra se C pou eixa kanei koitodas ena paper kai kati paradeigmata se java. Htan gia ena panellinio diagonismo gia sxoleia. san input exeiena arxeio keimenou.Stin proti grammi einai o ari8mos ton komvon kai ton diadromon. Stin deuteri i apostasi olon ton diadromon apo kovmo se komvo.Kai sto telos i diadromh pou prepei na kanoume:

 

>

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

#define UNDEFINED       -1
#define INF       5000000

enum dlabel {final,temp};

struct edge_vector
{
int src;
int dst;
int len;
};

struct node
{
      int prev;
      int len;
      enum dlabel label;
};

struct edge_vector *sdlVectors;
struct node *Steps;
int** weight;

int nNodes = 0;
int nEdges = 0;
int Source = 0;
int Destination = 0;
int nSteps = 0;

int path[100];

int readFile(void)
{
   ///////////// Variable Declaration
FILE *fp;
int i=0;
int j=0;

///////////// Open File For Reading
if(!(fp = fopen("apollon.txt","r")))
{
	printf("\nError While Opening Input File!");
	/* Error */
	return -1;
}
fscanf(fp, "%d %d", &nNodes, &nEdges);
printf("\n-------------------------------------------------");
printf("\nFile Info:\nNumber Of Nodes: %d\nNumber Of Edges: %d", nNodes, nEdges);

/////////////  Memory Allocation
sdlVectors = (struct edge_vector*) malloc(sizeof(struct edge_vector)*nEdges);
weight = (int**) malloc (sizeof(int) * nNodes);
for(i=0;i<nNodes;i++){  weight[i] = (int*) malloc (sizeof(int)*nNodes); }
Steps = (struct node*) malloc (sizeof(struct node) * nNodes);

///////////// Initialize sdlVectors and weight array
for(i=0;i<nNodes;i++){  for(j=0;j<nNodes;j++) { weight[i][j] = INF; } }
   for(i = 0; i < nEdges; i++)
{
         fscanf(fp,"%d %d %d", &sdlVectors[i].src, &sdlVectors[i].dst, &sdlVectors[i].len);
         printf("\n%d %d %d",sdlVectors[i].src, sdlVectors[i].dst, sdlVectors[i].len);
         weight[sdlVectors[i].src][sdlVectors[i].dst] = sdlVectors[i].len;
         weight[sdlVectors[i].dst][sdlVectors[i].src] = sdlVectors[i].len;
   }
   ///////////// Read Source And Destination Nodes
   fscanf(fp,"%d %d", &Source, &Destination);
   printf("\nSource: %d\tDestination: %d", Source, Destination);
   printf("\n------------------------------------------------- End Of File Info.");
   
   ///////////// Print Weight Array
//  for(i=0;i<nNodes;i++){  printf("\n"); for(j=0;j<nNodes;j++) { printf("\nweight[%d][%d] = %d", i, j, weight[i][j]); } }
   
fclose(fp);
fp = NULL;
return 1;
}

void dijkstra(void)
{
    int i,j,k,min;
    
    for(i = 0;i < nNodes;i++)
    {   
         Steps[i].prev = UNDEFINED;
         Steps[i].len = INF;
         Steps[i].label = temp;
    }
    Steps[source].len = 0;
    Steps[source].label = final;
    k = Source;
    
    do
    {
        for(i = 0;i < nNodes;i++)
        {
            if(weight[k][i] != 0 && Steps[i].label == temp)
            {
                if(Steps[i].len > (Steps[k].len + weight[k][i]))
                {
                    Steps[i].len = Steps[k].len + weight[k][i];
                    Steps[i].prev = k;
                }
            }
        }
        k = 0;
        min = INF;
        for(i = 0;i < nNodes;i++)
        {
            if(Steps[i].len < min && Steps[i].label == temp)
            {
                 k = i;
                 min = Steps[i].len;
            }
        }
        Steps[k].label = final;
        nSteps++;
    }while(k != Destination);
    
    i = 0;
    k = Destination;
    
    do
    {
        path[i++]=k;
        k = Steps[k].prev;
    }while(k >= 0);
    path[i] = k;
    
    printf("\n\n\nThe Shortest Path Is:");
    for(i=nSteps-1;i>0;i--) printf(" %d ->",path[i]);
    printf(" %d\n",path[i]);
    printf("\nPath Length is: %d", Steps[path[0]].len);
}

int main (void)
{
if(!readFile())
{
	printf("\nFailed To Read Input File!");
}

printf("\n\nStarting Shortest Path Calculation...");
dijkstra();
printf("\n\nCalculation Finished!");

printf("\n\n\nPress Any Key To Terminate Program...");
getch();

return 0;
}

Αρχειοθετημένο

Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.

Προς την λίστα θεμάτων
  • Δημιουργία νέου...