Raytracing (LoS) su mappe di tessere 3D esagonali

Question

Saluti,

Sto lavorando a un progetto di gioco che utilizza una variante 3D di mappe a tessere esagonali.Le tessere sono in realtà cubi, non esagoni, ma sono disposte proprio come esagoni (perché un quadrato può essere trasformato in un cubo per estrapolare da 2D a 3D, ma non esiste una versione 3D di un esagono).Invece di una descrizione dettagliata, ecco un esempio di una mappa 4x4x4:

(Ho evidenziato una tessera arbitraria (verde) e le sue tessere adiacenti (gialle) per aiutare a descrivere come dovrebbe funzionare il tutto;ma le funzioni di adiacenza lo sono non il problema è già risolto.)

Ho un tipo di struttura per rappresentare le tessere e le mappe sono rappresentate come una serie 3D di tessere (avvolte in un Map class per aggiungere alcuni metodi di utilità, ma non è molto rilevante).Ogni tessera dovrebbe rappresentare a perfettamente spazio cubico, e sono tutti esattamente Le stesse dimensioni.Inoltre, l'offset tra "righe" adiacenti è esattamente metà delle dimensioni di una piastrella.

Questo è abbastanza contesto;la mia domanda è:
Date le coordinate di due punti A E B, come posso generare un elenco delle tessere (o, piuttosto, le loro coordinate) che una linea retta separa A E B attraverserebbe?

Ciò verrebbe successivamente utilizzato per una varietà di scopi, come determinare la linea di vista, la legalità del percorso di carica e così via.

A proposito, questo può essere utile:le mie mappe usano (0,0,0) come posizione di riferimento.La "frastagliatura" della mappa può essere definita come lo spostamento di ciascuna tessera ((y+z) mod 2) * tileSize/2.0 a destra rispetto alla posizione che avrebbe su un sistema cartesiano "sano".Per le righe non frastagliate, il risultato è 0;per righe dove (y+z) mod 2 è 1, produce 0,5 tessere.

Sto lavorando su C#4 destinato a .Net Framework 4.0;ma non ho davvero bisogno di un codice specifico, solo dell'algoritmo per risolvere lo strano problema geometrico/matematico.Sono diversi giorni che provo a risolvere questo problema senza alcun risultato;e provare a disegnare il tutto su carta per "visualizzarlo" non è servito a niente :( .

Grazie in anticipo per qualsiasi risposta

Answer 1

Finché non salta fuori uno degli astuti SOer, ecco la mia stupida soluzione.Lo spiegherò in 2D perché è più semplice da spiegare, ma si generalizzerà abbastanza facilmente al 3D.Penso che qualsiasi tentativo di provare a farlo funzionare interamente nello spazio dell'indice delle celle sia destinato al fallimento (anche se ammetto che è proprio quello che penso e non vedo l'ora di essere smentito).

Quindi è necessario definire una funzione per mappare dalle coordinate cartesiane agli indici di cella.Questo è semplice, anche se un po' complicato.Per prima cosa, decidi se point(0,0) è l'angolo inferiore sinistro di cell(0,0) o il centro, o qualche altro punto.Poiché semplifica le spiegazioni, sceglierò l'angolo in basso a sinistra.Osserva che qualsiasi point(x,floor(y)==0) mappe a cell(floor(x),0).Anzi, qualsiasi point(x,even(floor(y))) mappe a cell(floor(x),floor(y)).

Qui invento la funzione booleana even che restituisce True se il suo argomento è un numero intero pari.Lo userò odd Prossimo:qualsiasi punto point(x,odd(floor(y)) mappe a cell(floor(x-0.5),floor(y)).

Ora conosci le basi della ricetta per determinare le linee di vista.

Avrai anche bisogno di una funzione da cui mappare cell(m,n) tornare ad un punto dello spazio cartesiano.Dovrebbe essere semplice una volta che hai deciso dove si trova l'origine.

Ora, a meno che non abbia smarrito alcune parentesi, penso che tu sia sulla buona strada.Dovrai:

• decidere dove cell(0,0) la tua posizione point(0,0);e regolare la funzione di conseguenza;
• decidere dove cadono i punti lungo i confini della cella;E
• generalizzarlo in 3 dimensioni.

A seconda delle dimensioni del campo di gioco, potresti memorizzare le coordinate cartesiane dei confini della cella in una tabella di ricerca (o altra struttura dati), il che probabilmente accelererebbe le cose.

Answer 2

Forse puoi evitare tutti i calcoli complessi se guardi il tuo problema in un altro modo:

Vedo che sposti i tuoi blocchi (alternati) lungo il primo asse solo della metà della dimensione del blocco.Se dividi i tuoi blocchi lungo questo asse, l'esempio sopra diventerà (con spostamenti) un semplice sistema di coordinate cartesiane (9x4x4) con blocchi impilati regolari.Ora eseguire il raytracing diventa molto più semplice e meno soggetto a errori.