Newsgroup: it.comp.programmare
Titolo: Algoritmo di decisione pe la scelta di un percorso

Salve a tutti, e intanto auguri!
Qualche tempo fa', per diletto, scrissi delle routine di AI per giocare a
Cluedo; nella fattispecie analizzava le richieste di carte e le risposte tra
i vari giocatori e di conseguenza costruiva le sue congetture. Si trattava,
insomma, di un "aiuto" per giocare a Cluedo. Il sistema indica anche quali
sono la stanza, l'arma e l'assassion da "chiamare", ma non dice nulla sul
percorso.
Volevo ora completarlo per farne un gioco completo, e mi serve dunque un
algoritmo che "calcoli" ad ogni mossa, in base alla situazione attuale, un
percorso per arrivare ad una certa stanza.
Per chi on ha familiarità con il gioco specifico, si tratta di trovare un
percorso percorribile in una "scacchiera" irregolare. Infatti a volte alcuni
"personaggi" potrebbero sbarrare la strada e costringere a scegliere
un'altra strada oppure un'altra destinazione (alternativa).
Se qualcuno ha qualche consiglio, perché non so da dove partire (al di là
del calcolo della direzione da seguire)
Grazie
Piero

Si tratta del classico problema dei cammini minimi, ti consiglio di cercare
qualcosa a riguardo all'algoritmo di Dijkstra, oppure l'algoritmo di
Dellman-Ford o ancora Floyd-Warshall, ma probabilmente (non so come funziona
il cluedo)  dovresti aggiungere anche un algoritmo che calcoli la mossa
migliore come ad esempio il minmax, per scegliere la mossa migliore
--
{G}eppo
Panther Power 3D Studio - Coder of GBA Team
www.panther3d.com
L'uomo utilizza solo il 10% del suo cervello
il restante 90% è file di swap del sistema operativo

 (alternativa).
e' un problema ampiamente studiato ed esiste una soluzione abbastanza 
semplice. Prima di tutto occorre considerare il tabellone di gioco come 
un grafo (se non sai cos'e` ti consiglio un bel libro di algoritmi). In 
questo caso credo che la scelta migliore sia di rappresentare il grafo 
in maniera implicita (se non sai cos'e` ti consiglio un bel libro di 
algoritmi). Dopodiche` fai una visita in ampiezza sino a quando non 
raggiungi il punto desiderato (se non sai cos'e` una visita in ampiezza 
ti consiglio un bel libro di algoritmi).
Se non hai voglia/tempo di leggerti questo benedetto libro ;-) prova a 
cercare su google "visita in ampiezza grafo" o "breadth-first visit": 
dovresti ottenere diversi link utili.
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 l'algoritmo di Dellman-Ford o ancora Floyd-Warshall, ma probabilmente
Cosa e' il Dellman-Ford?
Cmq gli altri algoritmi non sono i migliori in questo caso: il grafo 
del tabellone del cluedo e' non pesato, quindi basta una semplice 
visita in ampiezza. Il Floyd-Warshall calcola i cammini minini tra 
*tutte* le coppie di caselle e non e' quello che ci interessa (a meno 
di non utilizzare una tabella precalcolata), mentre Dijkstra richiede 
l'impego di uno coda con priorita`, quindi l'implementazione e` 
senz'altro piu` compless.


 wrote in message
l6sh0a...@localhost.localdomain...