Introduzione
A* (A star) è un algoritmo per trovare un percorso tra due punti, anche
in presenza di ostacoli
http://en.wikipedia.org/wiki/A*.
Massimo (un amico del poli) ha scritto un programma simile;
così mi sono interessato all'algoritmo, e ho voluto provare anch'io.
Installazione: Linux
Basta scaricare il file
A_star.tar.gz
e installare le relative dipendenze (su Ubuntu
"sudo apt-get
install libwxbase2.8 libwxgtk2.8 wx-common" L'archivio
compresso contiene una versione precompilata nella cartella
bin/release oltre
ai sorgenti e al file di progetto per Code::Blocks (rilasciati sotto
licenza GPL). L'implementazione è ancora in versione "beta", in quanto,
sebbene l'algoritmo trovi sempre un percorso quando è possiblie,
talvolta il percorso non è ottimale.
Installazione: Windows
Basta scaricare il file
A_star.tar.gz.
L'archivio
compresso contiene una versione precompilata nella cartella
A_star (windows)\bin\release
oltre
ai sorgenti e al file di progetto per Code::Blocks (rilasciati sotto
licenza GPL). Se non avete installato Code::Blocks con la versione
precompilata delle wxWidgets occorre anche scaricare questo file:
wx_runtime.tar.gz che
contiene due dll da copiare in C:\WINDOWS\system32
Usare il programma
Per disegnare i muri basta fare clic col mouse sulla griglia, per
cancellare dei muri basta fare Shift+clic, mentre per cancellare tutti
i muri c'è il pulsante "clear walls". Con il pulsante "start" si avvia
l'algoritmo (esegue 10 passi al secondo), mentre il pulsante "step"
serve a far avanzare l'algoritmo un passo alla volta. Il pulsante
"reset" cancella il percorso. Le caselle azzurre sono quelle che fanno
parte della "closed list", mentre quelle grigie fanno parte della "open
list" (vedere la spiegazione su wikipedia).
