[ALGORITMO] Metodi per realizzare IA che agiscono su "mappe" 2D

[Luke31]

Ciao a tutti.

In realtà la mia domanda è da applicare in seguito su php, ma dato che il mio problema non è tanto di stilatura di codice quanto di logistica.. di algoritmi, ho pensato che questa sezione sia più adatta, visto che comunque è più comune usare linguaggi quali il c per questo genere di algoritmi piuttosto che farli con linguaggi quali il php.

Stò realizzando una specie di sistema di "combattimenti" che si svolgono su una mappa 2d MxN.. sono partito bene ma mi sono accorto che mi trovo in un campo più complicato del previsto.
Per realizzare tutte le operazioni di movimento e simili mi sono accorto che serve qualcosa di abbatanza elaborato.
Per il semplice problema del trovare il percorso minimo ho risolto usando l'algoritmo di Dijkstra, ma i problemi rimangono per altri tipi di funzioni necessarie.
Mi è quindi venuto il dubbio se sia effettivamente conveniente usare un grafo.. infatti ho pensato ad ogni gioco di azione, di guerra, d'avventura o di corse o di moltri altri generi. Tutti questi genere di giochi ormai sfruttano necessariamente queste tecnologie (comunque quasi sempre).
E non si basano su grafi MxN mi pare, perché ci si può spostare in un qualsiasi punto della mappa.. quindi ho immaginato che devono esserci altri metodi più convenienti.. ma non ne sono sicuro, quindi chiedo a qualcuno più esperto di me. Se si sfruttassero sempre gli algoritmi che si usano nei grafi, considerando che spesso le IA attive contemporaneamente sono molteplici non diventerebbe forse una cosa estremamente pesante?

Dopo questa premessa, l'effettiva domanda infine è: Come funzionano generalmente tutti questeo genere di giochi che sfruttano queste tecnologie? Che metodi usano?? Accetto molto volentieri link e chiunque sia disposto a darmi delucidazioni di sorta...
Grazie in anticipo

Ciaoo

[Visionario]

Io ho una piccola esperienza in merito usando irrlicht come motore 3d per un gioco (http://irrlicht.sourceforge.net).

Questo motore non fà altro che gestire le collisioni, se ad esempio la telecamera che rappresenta il tuo campo di vista è in collisione con un muro alla sua destra, lo rileva ed ai voglia di pigiare il tasto per andare a destra, lui non accetterà mai il tuo comando. Insomma si basa sulle collisioni per determinare gli spostamenti.

Se tu mi spiegassi meglio qual'è la tua esigenza forse posso aiutarti meglio.

Ciao

[Luke31]

Il funzionamento che mi hai spiegato mi sembra abbastanza elementare.. cioè non richiede molti calcoli.. infine deve solo rilevare se a destra si trova un ostacolo.
Nel mio caso forse la cosa è un pò più complessa. Deve servire a gestire un IA, quindi comunque fare tutto da sola.
Ma in pratica il concetto è che avendo una mappa 2d (io usavo un grafo, ma parte della domanda era proprio se non esistano modi migliori.. nei giochi immagino non si usino grafi, ma non possono esserne sicuro cosi chiedo), io devo poter trovare i percorsi più rapidi per avvicinarsi ad un altro punto (come l'avversario prestabilito), essendoci degli ostacoli in mezzo.
Ma non solo (questo problema l'ho risolto), devo poter per esempio trovare il punto più vicino al punto di partenza, che si trovi massimo ad una distanza x da un altro punto dato, e che abbia una visuale libera verso quest'ultimo.
Non sono sicuro di essermi spiegato bene, ma comunque sono queste le cose che mi servono.. cose usate in un qualsiasi gioco moderno praticamente. Ed io mi chiedo qual'è il metodo che in genere si usa!

[Luke31]

/up

[Luke31]

/up

[Dr_House]

Non è un discorso semplice...

Devi analizzare bene innanzitutto il tipo di agente, deduco che si possa inziiare a pensare ad un agente con riflessi...

Poi prima ancora di pensare al codice, ti servirebbe iniziare a pensare a:

Spazio degli stati;

Stato iniziale;

Stato Obiettivo;

Insieme di operazioni ammissibili;

Algoritmo di ricerca;

Io ti suggerisco un A* scegli la tue euristica e calcoli con quella i tuoi cammini.

Essenzialmente quindi, il tutto si basa su un Agente che, compie delle azioni nel mondo in cui si trova a seconda di percezioni che esso riceve.

Le strutture dati usate sono o Alberi (per algoritmi di ricerca in profondità, in ampiezza, limitata A*) o sono anche dei Grafi, dipende solo da quello che devi fare.

Per una mappa 2D appunto, un algoritmo A* è quello che potrebbe bastare

[scancode]

Originariamente inviato da Luke31
Il funzionamento che mi hai spiegato mi sembra abbastanza elementare.. cioè non richiede molti calcoli.. infine deve solo rilevare se a destra si trova un ostacolo.
Nel mio caso forse la cosa è un pò più complessa. Deve servire a gestire un IA, quindi comunque fare tutto da sola.
Ma in pratica il concetto è che avendo una mappa 2d (io usavo un grafo, ma parte della domanda era proprio se non esistano modi migliori.. nei giochi immagino non si usino grafi, ma non possono esserne sicuro cosi chiedo), io devo poter trovare i percorsi più rapidi per avvicinarsi ad un altro punto (come l'avversario prestabilito), essendoci degli ostacoli in mezzo.
Ma non solo (questo problema l'ho risolto), devo poter per esempio trovare il punto più vicino al punto di partenza, che si trovi massimo ad una distanza x da un altro punto dato, e che abbia una visuale libera verso quest'ultimo.
Non sono sicuro di essermi spiegato bene, ma comunque sono queste le cose che mi servono.. cose usate in un qualsiasi gioco moderno praticamente. Ed io mi chiedo qual'è il metodo che in genere si usa!

Se devi usare un algoritmo per certcare il percorso + breve certca con google "algoritmo del commesso viaggiatore" se mentre vai trovi ostacoli devi implementare un algoritmo per le collisioni: puoi cercare "collision detection e collision response" poi ti serve sempre per AI la funzione rand per randomizzare una situazione di scelta per il percorso o livello da fare...

ciao

[scancode]

Originariamente inviato da scancode
Se devi usare un algoritmo per cercare il percorso + breve cerca con google "algoritmo del commesso viaggiatore" se mentre vai trovi ostacoli devi implementare un algoritmo per le collisioni: puoi cercare "collision detection e collision response" poi ti serve sempre per AI la funzione rand per randomizzare una situazione di scelta per il percorso o livello da fare...

Un argomento in italiano da leggere si trova sul sito di robydx:
http://robydx.altervista.org/main.htm guarda nei menù a grandi linee ti può essere utile

ciao

Edit: mi sono quotato da solo... ): và bhè...!

[Luke31]

Innanzitutto, grazie a tutti per le risposte.
Il fatto è che io già conosco gli algoritmi di cammino minimo e simili. Almeno ne conoscevo uno: l'algoritmo di Dijkstra, comunque adesso dò un occhiata all'A*.
Il fatto è che a me praticamente serve una cosa, si laterale, ma forse leggermente diversa..

Il contesto in cui andrebbe usata, sarebbe durante l'esecuzione dell'IA di un personaggio, che, per attaccarne un altro a distanza, si trova la necessità di trovare:
Un punto a distanza in linea d'aria dall'avversario non maggiore della sua portata (sua di quello che agisce), il più lontano possibile dall'avversario sopracitato nei limiti dettati dalla portata. Inoltre il punto deve avere una visuale libera dall'avversario. E ora tra i vari punti possibili trovati con le condizioni sopracitate, bisognerà trovare il punto che dal punto di partenza del personaggio non sia maggiore di un certo valore movimento.

Ora, per fare questo, avevo pensato di fare cosi:
Inizialmente si mettono in una matrice tutti i punti ad un raggio massimo dal bersaglio pari alla portata del personaggio che agisce. E questo sò come farlo.
A questo punto però, dovrei, per ognuno di questi punti, calcolare dapprima la retta che li congiunge al bersaglio, per quindi scorrere questa retta e controllare che il percorso in linea d'aria sia libero (e sò come farlo, ho trovato un algoritmo apposta, anche se non ricordo come si chiama). Dopodiché, se il precedente controllo và a buon fine, dovrò controllare il percorso necessario per arrivarvi, con un algoritmo di Dijkstra o A* (l'ultimo ancora non l'ho guardato ma immagino che sia questo il suo scopo), per quindi escludere tutti i punti con un percorso per arrivarvi maggiore di quello possibile. Infine prenderò il punto più lontano dal bersaglio, ed avrò raggiunto il mio scopo.

Quello che mi preoccupa in tutto questo è proprio il fatto che per ogni punto dovrò far eseguire un algoritmo di cammino minimo, e temo che diventi molto pesante!.

Chiedevo come facevano i moderni giochi, tipo quelli di guerra, a fare queste cose, e se usino questi metodi. Semplicemente perché se usano anche loro grafi 2d (o 3d, peggio), considerando il numero gargantuesco di punti che ci starebbero da considerare, mi pare che diventerebbo assolutamente eccessivi questi calcoli, che vengono eseguiti ogni volta per ogni punto vicino..

[scancode]

Originariamente inviato da Luke31
Innanzitutto, grazie a tutti per le risposte.
Il fatto è che io già conosco gli algoritmi di cammino minimo e simili. Almeno ne conoscevo uno: l'algoritmo di Dijkstra, comunque adesso dò un occhiata all'A*.
Il fatto è che a me praticamente serve una cosa, si laterale, ma forse leggermente diversa..

Il contesto in cui andrebbe usata, sarebbe durante l'esecuzione dell'IA di un personaggio, che, per attaccarne un altro a distanza, si trova la necessità di trovare:
Un punto a distanza in linea d'aria dall'avversario non maggiore della sua portata (sua di quello che agisce), il più lontano possibile dall'avversario sopracitato nei limiti dettati dalla portata. Inoltre il punto deve avere una visuale libera dall'avversario. E ora tra i vari punti possibili trovati con le condizioni sopracitate, bisognerà trovare il punto che dal punto di partenza del personaggio non sia maggiore di un certo valore movimento.

Ora, per fare questo, avevo pensato di fare cosi:
Inizialmente si mettono in una matrice tutti i punti ad un raggio massimo dal bersaglio pari alla portata del personaggio che agisce. E questo sò come farlo.
A questo punto però, dovrei, per ognuno di questi punti, calcolare dapprima la retta che li congiunge al bersaglio, per quindi scorrere questa retta e controllare che il percorso in linea d'aria sia libero (e sò come farlo, ho trovato un algoritmo apposta, anche se non ricordo come si chiama). Dopodiché, se il precedente controllo và a buon fine, dovrò controllare il percorso necessario per arrivarvi, con un algoritmo di Dijkstra o A* (l'ultimo ancora non l'ho guardato ma immagino che sia questo il suo scopo), per quindi escludere tutti i punti con un percorso per arrivarvi maggiore di quello possibile. Infine prenderò il punto più lontano dal bersaglio, ed avrò raggiunto il mio scopo.

Quello che mi preoccupa in tutto questo è proprio il fatto che per ogni punto dovrò far eseguire un algoritmo di cammino minimo, e temo che diventi molto pesante!.

Chiedevo come facevano i moderni giochi, tipo quelli di guerra, a fare queste cose, e se usino questi metodi. Semplicemente perché se usano anche loro grafi 2d (o 3d, peggio), considerando il numero gargantuesco di punti che ci starebbero da considerare, mi pare che diventerebbo assolutamente eccessivi questi calcoli, che vengono eseguiti ogni volta per ogni punto vicino..

!. Ti conveniene "Presettare le matrici" se cmq i percorsi sono sempre gli stessi
quindi risparmiare sui calcoli
2. Dici i punti di una retta... Quì per velocizzare devi calcolare in 2 modi: Con i vettori loro sottrazione per trovare la distanza da un punto ad un'altro e sempre calcoli sui vettori per la direzione. Per farti un esempio io lavoro in 3d e dx quindi uso le funzioni dx D3D per il calcolo...

buon lavoro...


ciao