Implementacja korytarza NetHack

Question

Właśnie bawiłem się z NetHack, ponieważ jestem w trakcie kodowania uproszczonej wersji dla siebie. Moje pytanie brzmi: w jaki sposób wdrażane są korytarze? Od kilku dni staram się myśleć o podejściu i nie mogę wymyślić niczego sensownego.

Answer 1

Generowanie map w Nethack występuje w mkmap.c. Metoda ta określa, które pokoje powinny być połączone. Metoda dig_corridor w sp_lev.c wykonuje faktyczne kopanie.

linie zainteresowania.

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

ten porównuje "Bieżący X i Y" z "target X i Y", aby określić kierunek, w którym będziemy początkowo kopanie w

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

Mamy Będziemy kontynuować, dopóki nie dojdziemy do celu, z kilkoma wyjątkami: jeśli "liczba korytarzy" cct wynosi 500, to wykopaliśmy długą drogę i chcemy się poddać. Jeśli nxcor jest prawdziwe, to korytarz może przejść w ślepy zaułek. rn2 to generator liczb losowych, więc jeśli ślepy zaułek jest możliwy, istnieje niewielka szansa podczas każdej pętli, którą poddamy.

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 to kafelek, na którym obecnie się znajdujemy. Przez większość czasu przekształcamy kafelek w zwykły korytarz. Czasami zamiast tego, tworzymy kafelek w SCORR, czyli Secret Corridor, który można przemierzać tylko po znalezieniu go przez przeszukanie. Umieszczamy również głazy, jeśli ścieżka może być ślepym zaułkiem.

/* 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; 
    } 
    } 

Jeśli „nachylenie” linii łączącej bieżącej pozycji i położenia docelowego jest znacznie daleko od 45 °, to próby zmiany kierunku; jeśli poruszamy się wzdłuż osi X, zamiast tego ruszamy wzdłuż osi Y; i wzajemnie. Powoduje to typowe faliste korytarze w kształcie schodów łączące dwie przekątne pomieszczenia. Jeśli zmiana kierunku spowoduje, że uderzymy w przeszkodę (inne pomieszczenia, lawę itp.), Po prostu pójdziemy dalej w kierunku, w którym zmierzamy.

Answer 2

Możesz sam sprawdzić źródło! Link

Pamiętam, jak dawno temu przeglądałem kod źródłowy. Pamięć jest trochę zardzewiała, ale uważam, że był to dość prosty proces sekwencyjny. Pudełka będą rysowane na pokoje do pewnej proporcji dostępnych płytek, a następnie będą generować korytarze i zamaskować pokoje przed nimi. Myślę, że mieli passę, w której szukali obszarów, które były niedostępne (za pomocą wypełnienia powodziowego?).

Następnie schody/drzwi/itp. Zostały zaludnione.

To, czego szukasz, to Maze generation algorithm. Jest mnóstwo.