quello che vorrei fare si avvicina molto alla tua seconda ipotesi, è più o meno questo:
data la grandezza della mappa es 100x100 la divido in coordinate x e y, poi registro in un db tutte le coordinate degli altri giocatori, quando ti muovi vedi 10X10 spazi, se per esempio un giocatore ha la città alle coordinate 20-20 e tu sei a 19-20 vedi il suo villaggio e ci puo cliccare... inoltre puoi cliccare su qualsiasi quadratino per muoverti... mi sa che tanto che dovrò usare il famoso script "a manina" :-)) è un lavoraccio e mi preoccupano le prestazioni... speriamo che finisco prima di andare in pensione ...
A occhio farei questo:
Leggo da db tutte le coordinate coinvolte quindi al max 100 elementi se è tutta piena (10X10), doppio ciclo se trovo un elemento (città) visualizzo l'immaginetta sovrapposta alla mappa altrimenti visualizzo l'immagine di dafault (terreno), ad ogni quadratino associo una mappa cliccabile che invia le coordinate al server, registro coordinate di partenza, di arrivo e timestamp, parte un contatore javascript (tempo necessario a percorrere il qudratino) che alla fine lancia il refresh, ad ogni refresh faccio la fifferenza tra l'orario attuale ed il timestamp registrato per vedere se effettivamente è stato percorso il quadratino.. e così via... non mi viene in mente una soluzione migliore... ma la vedo abbastanza onerosa per il povero server...
se ti viene qualche genialata è ben accetta
ciao e grazie

per il server fai un ajaxcall e risolvi

quindi alla fine non è la mia seconda idea bensì la mia prima

cioè quella a matrice... magari possiamo realizzarla tutti assieme qui....
inizia a generare qualcosa... almeno la base della mappa così tutti abbiamo un punto di partenza

magari :-))
mi metto al lavoro

Una cosa tipo www.travian.it?

tipo.... a quanto ho capito

esatto:-), l'unica differenza che visualizzo il giocatore che "cammina" sulla mappa e possibilità di incontrarne altri che "camminano" a "sua volta"(come disse il mago di arcella).

edit:
diciamo travian con possibilità anche di battaglia in campo aperto :-))

per quello basta un if

ed una query ovviamente

per ora però andiamo sulla struttura

Ho lavorato duramente (faccina di pinocchio):
con questo ora riesco a visualizzare una mappa alla travian, manca soltanto una implementazione più accurata della funzione per visualizzare la mappa, dove metto i link ecc ecc
Prima di fare quella però credo si debba passare ad Ajax, bene da dove comincio (non sono esperto nel settore)...

function getMappa($x,$y,$celle){
	//$x,$y centro della mappa, $celle = spazi visibili oltre il centro per ogni lato, sopra e sotto
	//caselline da visualizzare = $mostra ^ 2
	//struttura array *[coordinata]-*[tipo]-*[user]....
	$x1=$x-$celle;//basso sx
	$y1=$y-$celle;//basso sx
	$x2=$x+$celle;//alto dx
	$y2= $y+$celle;//alto dx
	$mostra=$celle*2+1;
	//leggo da db le celle incriminate, se trovo sei valori li inserisco nell'array
    $result=getMappaDB($x1,$x2, $y1, $y2);
	$array [$mostra][$mostra];
	foreach ($result as $value){
		$array [$x2-$value[x]][$y2-$value[y]]=$value;	
	}
	visualizzaMappa($array, $mostra);
}
//funzione per leggere dal db
function getMappaDB ($x1, $x2, $y1, $y2) {
    // struttura array *[coordinata]-*[tipo]-*[user]
	$conn=connessione();
    $result = $conn->query ("SELECT * FROM mappa WHERE x >='$x1' AND  x <='$x2' AND  y >='$y1' AND  y <='$y2'");
	$i=0;
	while ($row=$result->fetch_row()){
		$array*[coordinata]=$row[0];
		$array*[x]=$row[1];
		$array*[y]=$row[2];
		$array*[tipo]=$row[3];
		$array*[user]=$row[4];
		$i++;
	}
	$result->free(); 
	$conn->close();
	return $array;
}
//Funzione per visualizzare la mappa 

function visualizzaMappa($array, $len ){
	for ($i=0;$i<$len;$i++){
		for ($j=$len-1;$j>-1;$j--){
		   	if (isset($array[$j]*)){ //nessun valore trovato nel db
				echo '<img src="img/2.gif" width="25" height="25" />';
			}else{ //ho trovato un valore nel db
				echo '<img src="img/1.gif" width="25" height="25" />';
			}
		}echo ("</br>");
	}
}

//chiamata di test
getMappa(4,3,5);

edit:
struttura del db
id chiave primaria (da capire più in là se realmente serve)
x int (indicizzato)
y int (indicizzato)
tipo int (mi indica l'immaginina da visualizzare)
altro (qualsiasi altra cosa che può servire)

già di per se non è pesante in quanto non visualizzi tutti gli indici

quando vado a casa o al max domani ti posto un po' di script e cosa và moddato per la chiamate javascript

grazie mille, io intanto perfeziono il template che visualizza la mappa.
Ho fatto anche uno scriptino che dai alcuni paramentri, altezza, larghezza rombo, numero di celle da visualizzare mi genera un foglio di style :-))
Questo è il risultato parziale (ho registrato nel db due città alle coordinate (1,3) e (4,4)... sta venendo figo :-)) Ancora troppo "travianesca" ma poi si aggiusta...

Ciao e grazie ancora

io la preferisco dall'alto
quell'impostazione romboidale la vedo troppo esagerata
comunque hai un mp