Saber si entre dos puntos hay un obstáculo

Vamos a crear una función, para poder saber si dos puntos al azar dentro de un laberinto pueden verse o no (Es decir, entre los dos puntos y en linea recta no hay ningún obstaculo de por medio).

Hay un obstáculo entre dos puntos

 

Para ello, nos imaginaremos que tenemos en un array de dos dimensiones la estructura de un laberinto (En el ejemplo el array es map, donde 0 es un espacio libre y 1 es un muro), y queremos saber si desde un determinado punto (p1), podemos ver otro punto (p2) y solo podemos pasar por puntos libres.

map = [
[0,0,1,0,0,0,0,0],
[0,0,1,0,0,0,0,0],
[0,0,1,0,0,0,0,0],
[1,0,1,1,0,1,1,0],
[0,0,1,1,0,0,0,0],
[1,0,0,0,0,0,0,0],
[0,0,0,1,0,1,1,1],
[1,1,1,1,1,1,1,1]
];

function seePoints ( map, p1, p2, id ) {
  var dx = Math.abs( p2[ 1 ] - p1[ 1 ] );
  var dy = Math.abs( p2[ 0 ] - p1[ 0 ] );
  var sx = ( p1[ 1 ] < p2[ 1 ] ) ? 1 : -1;
  var sy = ( p1[ 0 ] < p2[ 0 ] ) ? 1 : -1;
  var err = dx - dy;
  while ( map[ p1[ 1 ] ][ p1[ 0 ] ] === id ) {
    var e2 = 2 * err;
    if ( e2 > -dy ) { err -= dy; p1[ 1 ]  += sx; }
    if ( e2 < dx ) { err += dx; p1[ 0 ]  += sy; }
    if ( p1[ 1 ] === p2[ 1 ] && p1[ 0 ] === p2[ 0 ] ) { return true; }
  }
  return false;
}

document.write (seePoints(map,[0,0],[5,2],0)); //FALSE

Si quieres hacer pruebas o cambios sobre esta función puedes hacerlo aquí.

 

Entradas relacionadas

Hoy inauguramos la nueva sección de trucos para programadores. En ella podremos encontrar todo tipo de trucos, aunque están principalmente orientados al desarrollo de videojuegos. En esta primera tanda, añadiremos algunos trucos relacionados...
Hace unos cuantos años, me dediqué durante una temporada a crear pequeños juegos en HTML5. El objetivo era aprender todo lo que pudiera de la tecnología emergente HTML5, y por el camino aprendí muchísimas cosas: (Node.js, CSS3, Javascript, Jq...