Calcolo delle tessere illuminate in un gioco basato su tessere (& # 8220; raytracing & # 8221;)

StackOverflow https://stackoverflow.com/questions/174659

  •  05-07-2019
  •  | 
  •  

Domanda

Sto scrivendo un piccolo gioco basato su tessere, per il quale mi piacerebbe supportare le fonti luminose. Ma il mio algoritmo-fu è troppo debole, quindi vengo da te per un aiuto.

La situazione è questa: esiste una mappa basata su riquadri (mantenuta come un array 2D), contenente una singola fonte di luce e diversi oggetti in piedi intorno. Voglio calcolare quali tessere sono illuminate dalla sorgente luminosa e quali sono in ombra.

Un aiuto visivo di come sarebbe, approssimativamente. L è la fonte di luce, le X sono elementi che bloccano la luce, gli 0 sono tessere illuminate e le -s sono tessere in ombra. 

0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -

Un sistema frazionario sarebbe ancora meglio, ovviamente, dove una tessera può essere in penombra a causa dell'oscuramento parziale. L'algoritmo non dovrebbe essere perfetto - semplicemente non ovviamente sbagliato e ragionevolmente veloce.

(Certo, ci sarebbero più sorgenti luminose, ma questo è solo un anello.)

Qualche acquirente?

È stato utile?

Soluzione

La comunità di sviluppo roguelike ha un po 'di ossessione per gli algoritmi line-of-sight, field-of-view.

Ecco un link a un articolo wiki roguelike sull'argomento: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Per il mio gioco roguelike, ho implementato un algoritmo di casting ombra ( http: // roguebasin. roguelikedevelopment.org/index.php?title=Shadow_casting ) in Python. È stato un po 'complicato da mettere insieme, ma ha funzionato ragionevolmente in modo efficiente (anche in puro Python) e ha generato buoni risultati.

Il campo visivo "consentito" " sembra anche guadagnare popolarità: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

Altri suggerimenti

Puoi entrare in ogni sorta di complessità calcolando l'occlusione ecc. oppure puoi optare per il semplice metodo della forza bruta: per ogni cella, usa un algoritmo di disegno come Bresenham Line Algorithm per esaminare ogni cella tra quella corrente e la sorgente luminosa. Se ci sono celle riempite o (se hai solo una fonte di luce) celle che sono già state testate e sono state trovate in ombra, la tua cella è in ombra. Se incontri una cella nota per essere accesa, anche la tua cella si accenderà. Una facile ottimizzazione a questo è di impostare lo stato di tutte le celle che incontri lungo la linea a qualunque sia il risultato finale.

Questo è più o meno quello che ho usato nella mia iscrizione vincente IOCCC 2004 . Ovviamente, ciò non costituisce un buon esempio di codice. ;)

Modifica: come sottolinea Loren, con queste ottimizzazioni, devi solo selezionare i pixel lungo il bordo della mappa da cui tracciare.

Gli algoritmi qui presentati mi sembrano fare più calcoli di quanto ritenga necessario. Non l'ho provato ma penso che funzionerebbe:

Inizialmente, contrassegnare tutti i pixel come illuminati.

Per ogni pixel sul bordo della mappa: come suggerito da Arachnid, usa Bresenham per tracciare una linea dal pixel alla luce. Se quella linea colpisce un ostacolo, segna tutti i pixel dal bordo appena oltre l'ostruzione come in ombra.

Veloce e sporco:

(A seconda della dimensione dell'array)

  • Passa attraverso ogni riquadro
  • traccia una linea verso la Luce
  • Se una parata della linea colpisce una X, allora è in ombra
  • (Opzionale): calcola la quantità di X che attraversa la linea ed esegui elaborati calcoli per determinare la proporzione della piastrella in ombra. NB: Questo potrebbe essere fatto anti-aliasing della linea tra la piastrella e la Luce (quindi guardando altre tessere lungo il percorso di ritorno alla sorgente luminosa) durante la procedura di soglia, queste appariranno come piccole anomalie. A seconda della logica utilizzata, potresti potenzialmente determinare quanto (se non del tutto) il riquadro è in ombra.

Potresti anche tenere traccia di quali pixel sono stati testati, quindi ottimizzare leggermente la soluzione e non ripetere il test due volte.

Questo potrebbe essere piuttosto discreto usando la manipolazione delle immagini e disegnando linee rette tra pixel (tessere) Se le linee sono semi trasparenti e i blocchi X sono di nuovo semi-trasparenti. Puoi impostare il limite dell'immagine per determinare se la linea ha intersecato una "X"

Se hai un'opzione per usare uno strumento di terze parti, probabilmente lo prenderò. A lungo termine potrebbe rivelarsi più veloce, ma capiresti meno del tuo gioco.

Questo è solo per divertimento:

Puoi replicare l'approccio Doom 3 in 2D se prima fai un passo per convertire le tue tessere in linee. Ad esempio, 

- - - - -
- X X X -
- X X - -
- X - - -
- - - - L

... verrebbe ridotto in tre linee che collegano gli angoli dell'oggetto solido in un triangolo.

Quindi, fai quello che fa il motore Doom 3: Dal punto di vista della sorgente luminosa, considera ogni "muro" che affronta la luce. (In questa scena, verrebbe presa in considerazione solo la linea diagonale.) Per ciascuna di queste linee, proiettala in un trapezio il cui bordo anteriore è la linea originale, i cui lati giacciono su linee dalla sorgente luminosa attraverso ciascun punto finale e la cui parte posteriore è lontano, oltre l'intera scena. Quindi, è un trapezio che "punta a" la luce. Contiene tutto lo spazio su cui il muro getta la sua ombra. Riempi tutte le tessere di questo trapezio con l'oscurità.

Procedi attraverso tutte queste linee e finirai con uno "stencil". che include tutte le tessere visibili dalla sorgente luminosa. Riempi queste tessere con il colore chiaro. Potresti voler illuminare la tessera un po 'meno mentre ti allontani dalla fonte ("attenuazione") o fare altre cose fantasiose.

Ripeti per ogni fonte di luce nella tua scena.

Per verificare se una piastrella è in ombra è necessario tracciare una linea retta sulla sorgente luminosa. Se la linea interseca un'altra tessera occupata, la tessera che stavi testando è in ombra. Gli algoritmi di Raytracing eseguono questa operazione per ogni oggetto (nel riquadro del caso) nella vista.

L'articolo di Raytracing su Wikipedia ha pseudocodice.

Ecco un approccio molto semplice ma abbastanza efficace che utilizza un tempo lineare nel numero di tessere sullo schermo. Ogni riquadro è opaco o trasparente (che ci viene fornito) e ognuno può essere visibile o ombreggiato (è quello che stiamo cercando di calcolare).

Iniziamo contrassegnando l'avatar stesso come " visibile " ;.

Quindi applichiamo questa regola ricorsiva per determinare la visibilità delle tessere rimanenti.

  1. Se il riquadro si trova sulla stessa riga o colonna dell'avatar, è visibile solo se il riquadro adiacente più vicino all'avatar è visibile e trasparente.
  2. Se la tessera si trova su una diagonale di 45 gradi rispetto all'avatar, è visibile solo se la tessera diagonale adiacente (verso l'avatar) è visibile e trasparente.
  3. In tutti gli altri casi, considera le tre tessere vicine più vicine all'avatar rispetto alla tessera in questione. Ad esempio, se questa tessera è in (x, y) ed è sopra ea destra dell'avatar, le tre tessere da considerare sono (x-1, y), (x, y-1) e (x- 1, y-1). La tessera in questione è visibile se qualsiasi di queste tre tessere è visibile e trasparente.

Per far funzionare questo, le tessere devono essere ispezionate in un ordine specifico per assicurarsi che i casi ricorsivi siano già calcolati. Ecco un esempio di un ordinamento funzionante, a partire da 0 (che è l'avatar stesso) e contando: 

9876789
8543458
7421247
6310136
7421247
8543458
9876789

Le piastrelle con lo stesso numero possono essere ispezionate in qualsiasi ordine tra loro.

Il risultato non è una bella proiezione d'ombra, ma calcola la credibile visibilità delle tessere.

La soluzione di TK è quella che generalmente useresti per questo genere di cose.

Per lo scenario di illuminazione parziale, potresti averlo in modo tale che se una tessera risulta in ombra, quella tessera viene quindi suddivisa in 4 tessere e ognuna di esse viene testata. Potresti quindi dividerlo quanto volevi?

Modifica:

Puoi anche ottimizzarlo un po 'non testando nessuna delle tessere adiacenti a una luce - questo sarebbe più importante da fare quando hai più fonti di luce, immagino ...

In realtà ho appena scritto questa funzionalità in uno dei miei progetti. 

void Battle::CheckSensorRange(Unit* unit,bool fog){
    int sensorRange = 0;
    for(int i=0; i < unit->GetSensorSlots(); i++){
        if(unit->GetSensorSlot(i)->GetSlotEmpty() == false){
            sensorRange += unit->GetSensorSlot(i)->GetSensor()->GetRange()+1;
        }
    }
    int originX = unit->GetUnitX();
    int originY = unit->GetUnitY();

    float lineLength;
    vector <Place> maxCircle;

    //get a circle around the unit
    for(int i = originX - sensorRange; i < originX + sensorRange; i++){
        if(i < 0){
            continue;
        }
        for(int j = originY - sensorRange; j < originY + sensorRange; j++){
            if(j < 0){
                continue;
            }
            lineLength = sqrt( (float)((originX - i)*(originX - i)) + (float)((originY - j)*(originY - j)));
            if(lineLength < (float)sensorRange){
                Place tmp;
                tmp.x = i;
                tmp.y = j;
                maxCircle.push_back(tmp);
            }
        }
    }

    //if we're supposed to fog everything we don't have to do any fancy calculations
    if(fog){
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
        }
    }else{

        bool LOSCheck = true;
        vector <bool> placeCheck;

        //have to check all of the tiles to begin with 
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            placeCheck.push_back(true);
        }

        //for all tiles in the circle, check LOS
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            vector<Place> lineTiles;
            lineTiles = line(originX, originY, maxCircle[circleI].x, maxCircle[circleI].y);

            //check each tile in the line for LOS
            for(int lineI = 0; lineI < (int) lineTiles.size(); lineI++){
                if(false == CheckPlaceLOS(lineTiles[lineI], unit)){
                    LOSCheck = false;

                    //mark this tile not to be checked again
                    placeCheck[circleI] = false;
                }
                if(false == LOSCheck){
                    break;
                }
            }

            if(LOSCheck){
                Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
            }else{
                LOSCheck = true;
            }
        }
    }

}

Ci sono alcune cose extra che non ti serviranno se le stai adattando per il tuo uso personale. Il tipo Luogo è appena definito come una posizione xey per motivi di convenienza.

La funzione di linea è presa da Wikipedia con modifiche molto piccole. Invece di stampare coordinate x y l'ho modificato per restituire un vettore di luogo con tutti i punti nella linea. La funzione CheckPlaceLOS restituisce solo vero o falso in base al fatto che il riquadro contenga un oggetto. Ci sono alcune ulteriori ottimizzazioni che potrebbero essere fatte con questo, ma questo va bene per le mie esigenze.

So che questa è una domanda vecchia di anni, ma per chiunque cerchi questo stile di cose vorrei offrire una soluzione che ho usato una volta per un mio roguelike; manualmente "precalcolato" FOV. Se il campo visivo della sorgente luminosa ha una distanza esterna massima, non è davvero molto difficile disegnare a mano le ombre create bloccando gli oggetti. Devi solo disegnare 1/8 del cerchio (più le direzioni dritte e diagonali); puoi usare la simmetria per gli altri otto. Avrai tante mappe d'ombra quanti quadrati hai in quell'ottavo di un cerchio. Quindi basta OR insieme insieme in base agli oggetti.

I tre principali pro per questo sono: 1. È molto veloce se implementato correttamente 2. Puoi decidere come proiettare l'ombra, senza confrontare quale algoritmo gestisce quale situazione sia la migliore 3. Nessuno strano caso indotto da algoritmi che è necessario correggere in qualche modo

L'aspetto negativo è che non riesci a implementare un algoritmo divertente.

Ho implementato il campo visivo basato su piastrelle in una singola funzione C. Ecco qui: https://gist.github.com/zloedi/9551625

Se non vuoi spendere il tempo per reinventare / reimplementarlo, ci sono molti motori di gioco là fuori. Ogre3D è un motore di gioco open source che supporta completamente l'illuminazione, nonché i controlli audio e di gioco.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top