Tutorial - L铆nea de Visi贸n (Line of Sight)
Este documento explica como implementar el algoritmo de l铆nea de visi贸n haciendo uso de un mapa de bloques accesible v铆a filas y columnas y con dos tipos de bloques (colisionables y no colisionables).
El mapa
El mapa lo representaremos por medio de array de enteros de dos dimensiones, donde la primer componente ser谩 la columna y la segunda componente ser谩 la fila.
En lenguaje C esta estructura de datos podr铆a ser declarada del siguiente modo:
| int map[COL][ROW];
Donde COL es la cantidad total de columnas y ROW es la cantidad total de filas.
Luego, existir谩n dos posiciones dentro del mapa que representar谩 la posici贸n del objeto A y el objeto B. La idea ser谩 verificar si el camino de A a B est谩 libre de obst谩culos, es decir, libre de bloques colisionables.
El algoritmo
La funci贸n que implementa el algoritmo requerido para determinar si el objeto A “ve” al objeto B est谩 determinado por la siguiente funci贸n, codificada en lenguaje C++:
| bool LineOfSight(int x1, int x2, int y1, int y2)
| {
| float col = x1;
| float row = y1;
| float slopeRow = GetSlopeRow(x1, x2, y1, y2);
| float slopeCol = GetSlopeCol(x1, x2, y1, y2);
|
| // Voy desde (x1, y1) a (x2, y2)
| if (fabs(slopeRow) == 1)
| {
| while (row != y2)
| {
|
| // Si alg煤n bloque que est茅 en camino es colisi贸n
| // los objetos no se ven
| if (map[floor(col)][floor(row)] == BLOCK_COLLISION)
| return false;
|
| // Incremento la fila y la columna
| row += slopeRow;
| col += slopeCol;
| }
| }
| else
| {
| while (col != x2)
| {
| // Si alg煤n bloque que est茅 en camino es colisi贸n
| // los objetos no se ven
| if (map[floor(col)][floor(row)] == BLOCK_COLLISION)
| return false;
|
| // Incremento la fila y la columna
| row += slopeRow;
| col += slopeCol;
| }
| }
|
| return true;
| }
La idea es partir de (x1, y1) y moverse por la estructura de datos hasta (x2, y2). Por lo tanto es necesario utilizar una sentencia de iteraci贸n condicional hasta llegar al punto B. Luego en cada iteraci贸n se deber谩 verificar si la pocisi贸n calculada de fila y columna dentro del mapa es un bloque de colisi贸n; de ser as铆 se retorna inmediatamente con un false.
Pages: 1 2
