Newsgroup: it.comp.lang.c++
Titolo: Rappresentazione mappa ad esagoni.

Devo rappresentare una mappa ad esagoni. Ho utilizzato un grafo
completamente dinamico, a puntatori. 
La struttura è la seguente: 
typedef struct node *nodeptr;
typedef struct list *listptr;
struct node {
	Elem_mp dati;
	int x;
	int y;
	nodeptr next;
	listptr adj;
};
struct list {
	listptr next;
	nodeptr node;
};
dove nodeptr è l'esagono, e listptr serve per trovare gli esagoni
adacenti ad un nodo senza cercarseli ogni volta.
Il problema sorge quando devo trovare il percorso migliore per andare da
un nodo all'altro. Ho utilizzato un algoritmo ricorsivo con
backtracking, di quelli che ci insegnano all'università :), e non
funziona molto bene. 
Cmq, sapete se:
1) Esiste un modo migliore del grafo per rappresentare mappe ad esagoni
2) Dove reperire algoritmi di questo tipo in rete (di siti ce ne sono a
migliaia, di doc e source da scaricare a miliardi, lo so, ma se qualcuno
sa esattamente dove posso trovare quello che cerco...)
3) Buoni libri di algoritmi. 
-- 
* Il Vero Programmatore non usa il  mouse e le icone, infatti il Vero
Programmatore non capisce perche' mai  per compilare un programma uno
debba staccare le mani dalla tastiera e cliccare su un menu quando  e'
tanto semplice battere 
CL pippo.c -k -iC:\all -q -w -e -r +t -y +cvb +f -g +g +p =l /f /a /s

 CL pippo.c -k -iC:\all -q -w -e -r +t -y +cvb +f -g +g +p =l /f /a /s
Il vero programmatore non scrive quello...al massimo "make" :)
(anche meglio: si e' aliasato un tasto in emacs che compila tutto e
prepare anche un caffe' a compilazione avvenuta.....)
Ciao,
Alberto
-- 
Alberto BARSELLA
PGP fingerprint = 13 3F 22 D2 0B 0A D3 25  F1 89 FE B5 82 AD 75 2A
** Beliefs are dangerous. Beliefs allow the mind to stop functioning.
A non-functioning mind is clinically dead.  Believe in nothing... **

abbia meno curve, che eviti gli esagoni "montagna", o altro?
Esatto. Quello che dovrebbe fare il nostro amico è costruirsi
un'euristica e implementare un algoritmo tipo A* e derivati.
Qualche mese fa è uscito un articolo su DEV o Computer Programming
(non ricordo quale dei due) che trattava di questi temi.
--
Roberto Lupi
Electronic Engineering Student - University of Ancona - Italy
Linux/NT System Administrator
Linux/Win32 Developer

 y, trovare gli esagoni adiacenti e' una banalita'.
Usare un array ? Ci ho provato all'inizio, ma dopo non riesco a fare un
algoritmo per trovare il percorso piů breve (il percorso col minor
numero di "passi" da un esagono all'altro).
Il problema sta nella numerazione degli esagoni. Essendo una matrice
quadrata, ogni esagono č identificato da 2 interi.
Ora, se le righe sono perfettamente orizzontali, le colonne possono
essere:
- parzialmente verticali (essendo esagonale e non quadrata). In questo
caso due esagoni adiacenti potrebbero avere lo stesso numero di colonna.
In effetti, percorrendo la mappa ad esampio dal basso-sinistra verso
alto-destra il numero di colonna cambia una volta sě e una no. Ciň mi
frega l'algrotimo ricorsivo di ricerca del percorso. 
- obliqui. In questo caso, per avere una mappa "rettangolare" 5*5 dovrei
allocare una mappa molto piů grossa, perlomeno il doppio, dato che
alloco un parallelogramma, e ne uso solo il rettangolo centrale.
Quindi ho optato per una struttura a puntatori. 
Magari i problemi che vi ho spiegato possono essere risolti...
-- 
FastWare: che programma vuoi oggi ?
http://www.terzomillennio.com/fastware

 - parzialmente verticali (essendo esagonale e non quadrata).
Ho capito dove e' il tuo problema. Cerco di farti un disegnino ASCII
per farti vedere come fare la corrispondenza esagoni->quadrati:
Gli esagoni:
 >---<     >---<     >---<    
/     \___/  1  \___/     \___
\     /   \     /   \     /   
 >---<  6  >---<  2  >---<    
/     \___/  A  \___/     \___
\     /   \     /   \     /   
 >---<  5  >---<  3  >---<    
/     \___/     \___/     \___
\     /   \  4  /   \     /   
 >---<     >---<     >---<    
/     \___/     \___/     \___
\     /   \     /   \     /   
Sono un po' deformati per colpa della grafica ASCII, ma sono sicuro
che si capisce in che modo sono collegati. Quello che e' importante e'
che l'esagono A e' contiguo a 6 esagoni, che ho numerato 1-6.
I quadrati:
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
|     |     |     |     |     |
|     |     |     |     |     |
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
|     |     |  A  |     |     |
|     |     |     |     |     |
+-----+-----+-----+-----+-----+
|     |     |     |     |     |
|     |     |     |     |     |
|     |     |     |     |     |
+-----+-----+-----+-----+-----+
Questa e' la tua matrice quadrata, ok? Chiaramente A *non* ha 6 vicini
come sopra. O sono 8 o sono 4 (a seconda di se usi le diagonali.
Ora faccio l'effetto speciale, ovvero shifto verso il basso di 1/2
quadrato le colonne dispari:
+-----+     +-----+     +-----+
|     |     |     |     |     |
+     +-----+  1  +-----+     +
|     |     |     |     |     |
+-----+  6  +-----+  2  +-----+
|     |     |     |     |     |
+     +-----+  A  +-----+     +
|     |     |     |     |     |
+-----+  5  +-----+  3  +-----+
|     |     |     |     |     |
+     +-----+  4  +-----+     +
|     |     |     |     |     |
+-----+     +-----+     +-----+
      |     |     |     |
      +-----+     +-----+
Come vedi adesso A ha 6 vicini, e la geometria della griglia e'
identica a quella esagonale. Sposta un po' i lati ed e' a tutti gli
effetti una griglia esagonale.
Quello che ti serve ora sono le funzioni che trovano i vicini. Nel
caso qui sopra (matrice quadrata 5x3) la cosa funziona cosi'
(assumo 0 <= X <= 4 e 0 <= Y <= 2).
A ha coordinate (2,1). Quali sono i suoi vicini 'esagonali'?
Sono quelli per cui: Y = Y_A +- 1, cioe' (2,0) e (2,2), che sono
quelli sopra e sotto.
Per quelli laterali invece ho che sono vicini SIA quelli con:
X = X_A +- 1, cioe' (1,1) e (3,1), ma anche quelli shiftati,
ovvero X = X_A +- 1, Y = YA - 1, cioe' (1,0) e (3,0).
La cosa e' asimmetrica fra colonne pari e dispari. Se volessi i vicini
di '5' dovrei usare Y = Y_5 + 1 nell'ultimo calcolo.
Una volta che hai la funzione che ti trova i vicini sei a posto, dato
che dal punto di vista della distanza il fatto di usare una mappa
esagonale ti dice che la distanza fra due esagoni e' costante.
Per calcolare la distanza "geometrica" oppure per disegnarli sullo
schermo l'idea e' analoga: semplicemente ti devi ricordare che le
colonne dispari sono "spostate" in una direzione di un mezzo passo
della griglia (questo ti risolve anche come passare da un eventuale
click sulla mappa all'elemento di matrice che ti serve).
Non ho nessuna implementazione da passarti, purtroppo, visto che avevo
iniziato a pormi il problema, ma poi sono passato ad altro....
