Come posso modificare questo algoritmo di linea di vista per accettare i raggi che passano attraverso gli angoli?

Question

Sto lavorando ad un algoritmo di pathfinder basato su Theta *, una variante di A * che fornisce un buon sistema per il path-finding che non è vincolato a una griglia, anche se il terreno/le ostruzioni sono basati su un modello di griglia. Questo sistema richiede un algoritmo di linea di vista per determinare se un particolare percorso è ostruito o meno.

Ho trovato this algoritmo di linea di mira estremamente utile e l'ho implementato con successo nel mio codice. Purtroppo, considera il seguente per essere un percorso non valido:

Tuttavia, per i miei scopi, mi vogliono un tale percorso può essere considerata valida. Ho provato a modificare l'algoritmo rilevando se un punto si trova sulla linea stessa utilizzando la formula di base y = mx + b, ma le incoerenze dell'algoritmo mi impediscono di fare affidamento su tale sistema.

Esiste un modo efficace per modificare questo algoritmo per consentire tale percorso? Esiste un altro algoritmo che potrebbe funzionare meglio? Tieni presente che i punti iniziale e finale del percorso saranno non necessariamente confinati in una griglia, quindi tutti i punti utilizzano la precisione double.

Answer 1

il codice di riferimento in realtà omette di gestire esplicitamente il caso in cui la linea passa attraverso un punto della griglia (dove si toccano quattro quadrati). È necessario verificare per error == 0.

In questo caso, al massimo uno dei quattro riquadri che toccano il punto della griglia potrebbe essere bloccato per avere ancora un percorso valido.

saluti, Erich