¿Cómo encontrar todos los cuadrados de la cuadrícula en una línea?

Question

Estoy tratando de implementar un algoritmo de línea de visión en una cuadrícula bidimensional. Sé cómo debe funcionar conceptualmente, pero no puedo pensar cómo implementarlo como un algoritmo.

La idea básica es bastante simple. En pseudocódigo:

function LineOfSight(point1, point2): boolean 
    squares = GetListOfSquaresOnLine(point1, point2) 
    for each square in squares 
    if square.IsOpaque then return false 
    return true 

GetListOfSquaresOnLine sería (conceptualmente) dibujar una línea recta desde el centro de la cuadrícula en point1 al centro del cuadrado de la cuadrícula en punto2, y devolver una lista de todos los cuadrados que esta línea pasa a través de . Pero esa es la parte que no tengo idea de cómo implementarla. Alguien sabe cómo hacer esto? Delphi o C ejemplos preferidos, pero no requeridos.

Answer 1

Tanto las respuestas de punto hasta el momento a un artículo de Wikipedia en el algoritmo Bresenhams 's. Aquí está la ilustración que da el artículo, a tamaño completo. Observe que la línea pasa a través de cuadrículas que no están resaltadas, por lo que el algoritmo de Bresenham solo proporciona un subconjunto de lo que desea.

Dado que usted menciona "línea de visión", que suena como usted quiere un algoritmo que enumera todas las cuadrículas que la línea atraviesa. Este conjunto a veces se denomina supercubierta (de la línea) y one algorithm is described here.

También hay algunos otros enfoques, que figuran en las respuestas a this question.

Actualización:Here's another reference

Answer 2

¿No es Bresenham's Algorithm lo que estás buscando?

Answer 3

Ver http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Answer 4

Aquí está an implementation I wrote in C.