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

Tricks
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...
IOTA Nodes
Vamos a usar la libreria iota.lib.js para mostrar la información en tiempo real de nuestro nodo IOTA. Como podéis ver en el siguiente ejemplo, esta librería nos facilita mucho las cosas: var iota = new IOTA({ 'provider' : 'http://timemox...