5

Ho bisogno di aiuto nella creazione di un algoritmo di collisione di linea specializzato che consente "angoli di taglio" a determinati angoli.Algoritmo di Tricky Line per un gioco (indipendente dalla lingua)

Nelle seguenti immagini, lasciare che il quadrato blu rappresenti il ​​giocatore e il quadrato nero rappresenti un muro. I quadratini bianchi, poi, rappresentano piazze di "linea di vista" di un giocatore (piazze valide), e le piazze grigi sono quadrati al di fuori "linea di vista" di un giocatore (quadrati non validi):

img1

Il seconda immagine è dove le cose si fanno più interessanti, come si comincia angoli taglienti:

img2

Diamo uno sguardo più da vicino questa linea che è consentito, nonostante passando sopra l'angolo del muro:

img3

La linea è consentito perché:

  • dx < = 0.5 (con un essere 1x1 quadrato)
  • dx/dy è sopra un certo rapporto (per esempio, 2 - I' m non sicuro del valore esatto rappresentato in queste immagini)

la linea inverso non è consentito perché il rapporto (di dy/dx in questo caso) è troppo bassa.

img4

O forse dovrei parlare l'angolo di entrata vs uscita dalla piazza ....

Il problema principale che sto avendo è che non riesco a capire come generalizzare una soluzione per i vettori che viaggiano con qualsiasi angolazione tra due punti sulla griglia. Non riesco a decidere se usare la trigonometria o cosa. La mia soluzione più vicina finora è stata quella di utilizzare le parti decimali delle intercettazioni di linea per ogni quadrato come dx e dy e verificare se è consentito in base alla pendenza della linea e in quale quadrante si trova.

Qualcuno può aiutare?

Ho anche preso in prestito o partendo da altri algoritmi di linea, ma non ho trovato nulla di troppo utile. Molti di quelli che ho visto vogliono una linea da (x1, y1) a (x2, y2) per essere uguale a da (x2, y2) a (x1, y1) che rende questo problema abbastanza diverso.

+0

Suppongo che tu possa avere molti muri e che non siano sempre adiacenti alla posizione del giocatore? Puoi pubblicare il tuo attuale algoritmo (pseudocodice almeno)? – Groo

+5

Il mio primo pensiero è guardare quanto vicino la linea arriva al centro del quadrato. Ma nel tuo secondo esempio, non ha senso per me che questo processo non sia simmetrico: posso vederti, ma non puoi vedermi? – Teepeemm

+0

Esatto, Teepeemm: Una linea dal punto A al punto B non è solitamente la stessa del punto B in A, quando dx! = Dy! = 0. Vedrò se riesco ad ottenere un esempio di pseudocodice. –

risposta

1

Suggerisco di utilizzare cerchi, sono abbastanza ottimali in senso angolare.

Suppongo che le coordinate siano prese al centro di ciascun pixel.

L'algoritmo per sapere se (xo, yo) si nasconde la vista da (xa, ya) a (xb, YB) sarebbe allora:

  • calcolo (XC, YC) il punto più vicino al (xo, yo) sulla linea da (xa, ya) a (xb, yb)
  • calcolare distanza d da (xo, yo) a (xc, yc)
  • se d < mezzo pixel, allora la La vista è nascosta

È possibile semplificare le prime due fasi calcolando direttamente la distanza tra il punto e la linea http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line ed eventualmente calcolare la distanza al quadrato se si desidera evitare sqrt

+0

Ciò consente di tagliare gli angoli, ma non tiene conto del fatto che (xa, ya) a (xb, yb) può essere consentito, ma (xb, yb) a (xa, ya) non consentito, gli angoli possono essere tagliati solo se entrano sotto una certa angolazione. –