Pagina 1 di 1

movimento intelligente di un personaggio

Inviato: 06/10/2009, 20:59
da nightwish88
sono fermo a questo punto da giorni... per questo chiedo a voi

immaginiamo di avere una scacchiera e dei pedoni che si muovono su di essa come vogliono, però fissando due limiti
1) numero massimo di caselle su cui si può spostare
2) non può oltrepassare caselle già occupate

vorrei creare un algoritmo che, fissata la casella di arrivo effettua il percorso evitando tutti gli ostacoli possibili

in sintesi vorrei creare un sistema del genere
Spoiler
il sistema che ho creato funziona ma ha un bug e non riesce a aggirare ostacoli formati da file voluminose di caselle occupanti (quindi non un altro pedone per esempio ma l'equivalente di un muro )

non voglio script o codici già fatti... vorrei semplicemente ricevere un aiuto a parole, perché sicuramente il mio sistema è giusto ma limitato e non riesco a superare la mia fantasia più di quanto ho già fatto

ecco il mio algoritmo, per i più curiosi
Spoiler
fissato il numero massimo di spostamenti che la pedina può effettuare, calcolo l'angolo che forma dal punto di partenza a quello di arrivo, e con una funzione appositamente creata approssima l'angolo ottenuto con uno di queste 4 possibilità: 0,90,180,270

a questo punto a seconda dell'angolo approssimato setto dei opportuni pesi i,j, ovvero il seno e coseno dell'angolo ottenuto. Così ho valori unitari positivi e negativi e capisco come devo effettuare lo spostamento e controllo se quella casella è libera oppure no. SE è libera proseguo con la ricorsione, altrimenti sfaso l'angolo ottenuto di 90 gradi e proseguo con il nuovo percorso. IL bug principale è che in certe situazioni lo sfasamento oscilla da 1 a -1 quindi si sposta sempre nelle stesse due caselle fino a quando esaurisce gli spostamenti

Re: movimento intelligente di un personaggio

Inviato: 06/10/2009, 21:54
da maz85
Dato che non ti interessa raggiungere una determinatata posizione:

0) vecchiacasella=casella attuale; vecchiadirezione=0;
1) scelta angolazione (0,90,180,270) e inserimento in variabile vecchiadirezione (da scartare se nel passo successivo è stata usata trovandola occupata)
2) controllo angolazione se occupata ritorno punto 1, se libera vado al punto 3, inoltre controllo se è una vecchiacasella ritornando al punto 1 nel caso fosse così
3) se libera > spostamento > caselleusate+=1
4) ritorna al punto 0

L'ho scritto così di getto, ma dovrebbe funzionare come ragionamento.

Re: movimento intelligente di un personaggio

Inviato: 06/10/2009, 23:03
da BaronVsCorsar
che interessante questione!

non ci ho riflettuto quanto merita...

per ora mi limito a proporre un suggerimento per modificare il tuo algoritmo:
altrimenti sfaso l'angolo ottenuto di 90 gradi e proseguo con il nuovo percorso
questo non può andare bene, perchè facendo questa scelta perdi memoria del "da dove vieni", quindi di fronte ad un ostacolo lungo orizzontale frapposto lungo un percorso verticale puoi davvero arrivare a loopare all'infinito.

nel caso il percorso più breve trovato con il tuo algoritmo sia interrotto da un ostacolo ti propongo
- determinare la direzione per aggirare l'ostacolo (dettaglio dopo), e memorizzare direzione_di_provenienza
- matenere tale direzione fino a quando la direzione_di_provenienza è libera e muoverti in quella direzione riprendendo l'algoritmo originale
- se anche nella nuova direzione trovi un ostacolo (ostacoli a elle) è un casino... per ora suggerisco di applicare la stessa strategia creandoti direzione_prv[0] [1] [3] [4] (gli ostacoli concavi tipo spirale con pg all'interno non sarebbero gesititi: gli ostacoli devono essere convessi!)
- di sicuro si deve prevedere anche la possibilità di invertire il moto... ma questo prendilo in considerazione in uno step successivo

per determinare la direzione per aggirare l'ostacolo:
versione 0: tira a caso tra +90° e -90° rispett odirezione originale
versione 1: eslpora le caselle adiacenti per valutare in quale delle due direzioni troverai per primo il passo successivo

ovvio che questa proposta non sta assolutamente ottimizzando il percorso, ostacoli successivi potrebbero scombussolare il percorso migliore.

Hai preso in considerazione l'A*? Hai già la matrice per determinare i collegamenti poco costosi e quelli a costo infinito...

Re: movimento intelligente di un personaggio

Inviato: 07/10/2009, 7:02
da nightwish88
maz85 ha scritto:Dato che non ti interessa raggiungere una determinatata posizione:

0) vecchiacasella=casella attuale; vecchiadirezione=0;
1) scelta angolazione (0,90,180,270) e inserimento in variabile vecchiadirezione (da scartare se nel passo successivo è stata usata trovandola occupata)
2) controllo angolazione se occupata ritorno punto 1, se libera vado al punto 3, inoltre controllo se è una vecchiacasella ritornando al punto 1 nel caso fosse così
3) se libera > spostamento > caselleusate+=1
4) ritorna al punto 0

L'ho scritto così di getto, ma dovrebbe funzionare come ragionamento.
il ragionamento è buono, il punto è che io ho una determinata posizione da raggiungere.... e infatti non riesco a capire come scegliere l'angolazione del punto 1 senza dover casualmente provarle tutte

BaronVsCorsar ha scritto:che interessante questione!

non ci ho riflettuto quanto merita...

per ora mi limito a proporre un suggerimento per modificare il tuo algoritmo:
altrimenti sfaso l'angolo ottenuto di 90 gradi e proseguo con il nuovo percorso
questo non può andare bene, perchè facendo questa scelta perdi memoria del "da dove vieni", quindi di fronte ad un ostacolo lungo orizzontale frapposto lungo un percorso verticale puoi davvero arrivare a loopare all'infinito.

nel caso il percorso più breve trovato con il tuo algoritmo sia interrotto da un ostacolo ti propongo
- determinare la direzione per aggirare l'ostacolo (dettaglio dopo), e memorizzare direzione_di_provenienza
- matenere tale direzione fino a quando la direzione_di_provenienza è libera e muoverti in quella direzione riprendendo l'algoritmo originale
- se anche nella nuova direzione trovi un ostacolo (ostacoli a elle) è un casino... per ora suggerisco di applicare la stessa strategia creandoti direzione_prv[0] [1] [3] [4] (gli ostacoli concavi tipo spirale con pg all'interno non sarebbero gesititi: gli ostacoli devono essere convessi!)
- di sicuro si deve prevedere anche la possibilità di invertire il moto... ma questo prendilo in considerazione in uno step successivo

per determinare la direzione per aggirare l'ostacolo:
versione 0: tira a caso tra +90° e -90° rispett odirezione originale
versione 1: eslpora le caselle adiacenti per valutare in quale delle due direzioni troverai per primo il passo successivo

ovvio che questa proposta non sta assolutamente ottimizzando il percorso, ostacoli successivi potrebbero scombussolare il percorso migliore.

Hai preso in considerazione l'A*? Hai già la matrice per determinare i collegamenti poco costosi e quelli a costo infinito...
penso di aver capito... in effetti avevo un pò intuito che l'errore principale è determinare "lo sfasamento" e come lo impostavo io dava un bel pò di problemi. Infatti come dici tu si vengono a creare proprio cicli infiniti di spostamenti, limitati dal numero massimo delle caselle di cui tu puoi spostare

oggi sul tardi proverò a dare una sorta di memoria all'algoritmo e vediamo cosa succede

se per A* intendi AI ho solo vaghe idee su come farla.... in ogni caso il calcolo principale sarà di individuare coordinate intelligenti per i pedoni.... scritto l'algoritmo in modo corretto basta inserire tali coordinate in esso e il gioco è fatto

per la matrice.... sinceramente non ce l'ho perchè tengo in considerazione prima lo spostamento diretto, graficamente quello più breve e poi eventuali aggiunte per evitare ostacoli. In più il massimo numero di caselle di spostamento è un vincolo discretamente breve ( per la giocabilità non più di 10 ) quindi per ora è un problema che "si risolve da solo"

Re: movimento intelligente di un personaggio

Inviato: 07/10/2009, 19:10
da civic71
:fapensare: Io utilizzerei dei bullet ( sparati nelle varie direzioni ) dall' oggetto che si deve muovere nella scacchiera ( non devono essere visibile all' utente ) .
Questi bullet selezionano la migliore posizione ed una volta trovata si distruggono.
A questo punto dico all' oggetto di muoversi verso la posizione indicata dal bullet predefinito.

Re: movimento intelligente di un personaggio

Inviato: 08/10/2009, 9:23
da Freeflip
Prova a dare un'occhiata a questa semplice formula sulla diffusione:

http://gm6guide.altervista.org/php5/tut ... nzati&id=1

Re: movimento intelligente di un personaggio

Inviato: 08/10/2009, 18:48
da Homunculus
freeflip ha scritto:Prova a dare un'occhiata a questa semplice formula sulla diffusione:

http://gm6guide.altervista.org/php5/tut ... nzati&id=1
Tra l'altro é roba mia, se hai domande ci sono :P

Re: movimento intelligente di un personaggio

Inviato: 08/10/2009, 20:15
da nightwish88
lol homunculus è roba tua? bhè ho letto il sistema oltre ad essere molto intelligente mi stuzzica parecchio.... sto convertendo tutto il discorso letto in gml XD

Re: movimento intelligente di un personaggio

Inviato: 08/10/2009, 21:58
da Homunculus
So che non ti piace andare a vedere il codice altrui, ma nel tutorial sono rimasto volutamente vago riguardo all'implementazione proprio perché é molto piu semplice capire vedendo un esempio, quello allegato al tutorial

Re: movimento intelligente di un personaggio

Inviato: 09/10/2009, 6:33
da nightwish88
guarda.... sono rimasto un pò sbigottito al passaggio in cui utilizzi un doppio ciclo for per la distribuzione del gas... per me ha più senso una via risorsiva partendo dal centro per poi espandersi verso il fuori.... poi ho capito che servono più passaggi per arrivare alla zona di stallo.... questo per me è un problema perchè l'estensione del gas dovrebbe essere calcolata in un singolo step e mettere il tutto in un altro ciclo for rende tutto un pò pesantuccio... sto valutando una via di mezzo anche perchè vorrei poter far girare il programma anche su pc meno potenti

Re: movimento intelligente di un personaggio

Inviato: 09/10/2009, 9:01
da Homunculus
Night il fatto che uso due ciclo for é perché abbiamo una griglia, non una lista. Uno determina la riga e uno la colonna, il risultato é che i passaggi totali sono esattamente quanto il numero totale delle celle. Se usi l'A* ottieni molti piu passaggi (in media)