Implementazione del corridoio NetHack

Question

Stavo solo giocando con NetHack mentre sto programmando una versione semplificata per me stesso. La mia domanda è, come vengono implementati i corridoi? Ho cercato di pensare a un approccio per alcuni giorni e non riesco a trovare nulla di ragionevole.

Answer 1

La generazione della mappa in Nethack si verifica in mkmap.c. Il metodo join_map determina quali stanze devono essere connesse. Il metodo dig_corridor in sp_lev.c esegue la ricerca vera e propria.

linee di interesse:.

if (tx > xx)  dx = 1; 
else if (ty > yy) dy = 1; 
else if (tx < xx) dx = -1; 
else   dy = -1; 

questo confronto "X corrente e Y" con "target X e Y" per determinare la direzione che saranno inizialmente scavando in

while(xx != tx || yy != ty) { 
    /* loop: dig corridor at [xx,yy] and find new [xx,yy] */ 
    if(cct++ > 500 || (nxcor && !rn2(35))) 
    return FALSE; 

Noi Continueremo finché raggiungiamo l'obiettivo, con alcune eccezioni: se "il conteggio del corridoio" cct è 500, allora abbiamo scavato una lunga strada e vogliamo rinunciare. Se nxcor è vero, allora il corridoio è consentito a vicolo cieco. rn2 è un generatore di numeri casuali, quindi se un vicolo cieco è possibile, allora c'è una piccola possibilità durante ogni ciclo che ci arrendiamo.

crm = &levl[xx][yy]; 
    if(crm->typ == btyp) { 
    if(ftyp != CORR || rn2(100)) { 
     crm->typ = ftyp; 
     if(nxcor && !rn2(50)) 
      (void) mksobj_at(BOULDER, xx, yy, TRUE, FALSE); 
    } else { 
     crm->typ = SCORR; 
    } 

crm è la piastrella in cui ci troviamo attualmente. La maggior parte delle volte, trasformiamo la tessera in un normale corridoio. A volte invece, facciamo la tessera in uno SCORR, o Corridoio segreto, che può essere attraversato solo dopo averlo trovato cercando. Mettiamo anche dei massi se il percorso potrebbe essere un vicolo cieco.

/* do we have to change direction ? */ 
    if(dy && dix > diy) { 
    register int ddx = (xx > tx) ? -1 : 1; 

    crm = &levl[xx+ddx][yy]; 
    if(crm->typ == btyp || crm->typ == ftyp || crm->typ == SCORR) { 
     dx = ddx; 
     dy = 0; 
     continue; 
    } 
    } else if(dx && diy > dix) { 
    register int ddy = (yy > ty) ? -1 : 1; 

    crm = &levl[xx][yy+ddy]; 
    if(crm->typ == btyp || crm->typ == ftyp || crm->typ == SCORR) { 
     dy = ddy; 
     dx = 0; 
     continue; 
    } 
    } 

Se la "pista" della linea tracciata tra la posizione attuale e la posizione finale è sensibilmente lontano da 45 gradi, si cerca di cambiare direzione; se ci muoviamo lungo l'asse X, invece, iniziamo a spostarci lungo l'asse Y; e viceversa. Ciò causa i tipici corridoi sagomati a forma di scala che collegano due stanze diagonali. Se cambiando direzione dovremmo farci sbattere contro un ostacolo (altre stanze, lava, ecc.), Continueremo nella direzione in cui stavamo andando.

Answer 2

È possibile controllare la fonte per te! Link

Mi ricordo di aver passato il codice sorgente una volta tanto tempo fa. La memoria è un po 'arrugginita, ma penso che sia stato un processo sequenziale piuttosto semplice. Le scatole verrebbero disegnate per le stanze con un determinato rapporto di tessere disponibili, quindi genererebbero i corridoi e maschererebbero le stanze contro di loro. Penso che abbiano avuto un passaggio dove hanno cercato aree inaccessibili (usando un riempimento di piena?).

Quindi scale/porte/ecc. Erano popolate.

Quello che stai cercando è un Maze generation algorithm. Ci sono tonnellate