movimento intelligente di un personaggio

Hai una curiosità o un problema con Game Maker? Domanda e ti sarà risposto!
Rispondi
Avatar utente
nightwish88
GMI Advanced
Messaggi: 1739
Iscritto il: 18/01/2009, 13:41
Contatta:

movimento intelligente di un personaggio

Messaggio 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
Immagine

Web Site: AFGames

Avatar utente
maz85
Admin
Messaggi: 8287
Iscritto il: 07/02/2004, 15:57
Specialità: Nientologo
Località: Oblio
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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.

Avatar utente
BaronVsCorsar
GMI VIP
Messaggi: 4699
Iscritto il: 14/02/2004, 12:05
Specialità: Saccenza
Uso: GameMaker 8.1
Località: Ferrara
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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...
ImmagineSchiva questo - http:\\baronvscorsar.altervista.org
by Lego: Vado in un bar e faccio "votiamo che quel tizio la in fondo venga buttato fuori", ma perché?

Avatar utente
nightwish88
GMI Advanced
Messaggi: 1739
Iscritto il: 18/01/2009, 13:41
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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"
Immagine

Web Site: AFGames

Avatar utente
civic71
GMI Advanced
Messaggi: 2210
Iscritto il: 23/10/2003, 17:31
Specialità: Risotto con zucchine
Uso: GM:Studio 1.4 Pro
Località: Jesolo (venezia)
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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.

Avatar utente
Freeflip
Newbie
Messaggi: 33
Iscritto il: 06/01/2008, 18:18
Specialità: GML
Uso: GM:Studio 2
Località: Bologna
Contatta:

Re: movimento intelligente di un personaggio

Messaggio da Freeflip »

Prova a dare un'occhiata a questa semplice formula sulla diffusione:

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

Avatar utente
Homunculus
Admin
Messaggi: 6840
Iscritto il: 25/11/2007, 20:36
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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

Avatar utente
nightwish88
GMI Advanced
Messaggi: 1739
Iscritto il: 18/01/2009, 13:41
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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
Immagine

Web Site: AFGames

Avatar utente
Homunculus
Admin
Messaggi: 6840
Iscritto il: 25/11/2007, 20:36
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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

Avatar utente
nightwish88
GMI Advanced
Messaggi: 1739
Iscritto il: 18/01/2009, 13:41
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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
Immagine

Web Site: AFGames

Avatar utente
Homunculus
Admin
Messaggi: 6840
Iscritto il: 25/11/2007, 20:36
Contatta:

Re: movimento intelligente di un personaggio

Messaggio 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)

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 37 ospiti