O ponto chave nesse desafio é conseguir testar as rotas possíveis de forma que dê para saber o caminho mais curto e o que foi percorrido. Um jeito de conseguir isso é através de grafos. Grafos são uma estrutura de dados que representam nós ligados entre si. Em um grafo existe um algoritmo de pesquisa que serve bem ao propósito de encontrar a menor distância entre dois nós, portanto se transformarmos nosso labirinto de uma matriz para um grafo poderemos utilizá-lo para resolver o desafio.
Podemos começar criando uma classe para representar uma posição no labirinto. O labirinto será uma matriz de tamanho qualquer onde é possível se mover horizontal ou verticalmente, ou seja, cada posição pode ser representada como um nó de um grafo interligado às posições imediatamente a cima, a baixo, a esquerda e a direita. Um nó de um grafo precisa possuir um método para conectar-se a um outro nó, ou seja, adicionar esse nó a lista de "vizinhos" do nó atual e vice-versa. Também vamos armazenar a coluna e linha da posição, seu valor e uma label que servirá para identificá-la de forma legível mais a frente. Vejamos como fica a implementação:
class Position { constructor(row, col, value) {
this.label = `(${row}, ${col})`
this.row = row
this.col = col
this.value = value
this.neighbors = []
}
connect(position) {
if (!this.isNeighbor(position)) {
this.neighbors.push(position)
position.neighbors.push(this)
}
}
getNeighbors() {
return this.neighbors
}
isNeighbor(position) {
return !!this.neighbors.find(neighbor => neighbor.row === position.row && neighbor.col === position.col)
}
}
Agora podemos passar para a criação de uma classe para o nosso labirinto. Seu construtor deve receber a matriz e a partir dela iremos armazenar alguns valores que podem ser úteis ao longo da resolução. Iremos tratar o array externo como sendo as linhas e o array interno como sendo as colunas da nossa matriz, assim podemos guardar o tamanho máximo de linhas e colunas para garantir que não iremos ultrapassar os limites do nosso labirinto. Vamos também criar um atributo para guardar os objetos Position de toda as posições inicialmente vazio e chamar um método para transformar nossa matriz em vários nós. Outra informação que pode ser útil é o nó de entrada e o de saída. Ficará assim:
class Position {
constructor(row, col, value) {
this.label = `(${row}, ${col})`
this.row = row
this.col = col
this.value = value
this.neighbors = []
}
connect(position) {
if (!this.isNeighbor(position)) {
this.neighbors.push(position)
position.neighbors.push(this)
}
}
getNeighbors() {
return this.neighbors
}
isNeighbor(position) {
return !!this.neighbors.find(neighbor => neighbor.row === position.row && neighbor.col === position.col)
}
}
class Maze {
constructor(grid = [[]]) {
this.grid = grid
this.rows = grid.length
this.cols = grid.reduce((highestLength, row) => highestLength < row.length ? row.length : highestLength, 0)
this.positions = []
this.transformIntoGraph()
this.start = this.positions.find(pos => pos.value === 'S')
this.end = this.positions.find(pos => pos.value === 'E')
}
}
Agora vamos implementar o método de transformar a matriz em grafo que chamamos no construtor. Primeiramente ele precisará criar um objeto Position para cada posição da matriz, então podemos usar duas repetições for para iterar sobre a matriz toda criando objetos para cada posição. Depois disso podemos chamar um outro método, que já vamos implementar, para encontrar os vizinhos de cada posição. Ficará assim:
class Position {
constructor(row, col, value) {
this.label = `(${row}, ${col})`
this.row = row
this.col = col
this.value = value
this.neighbors = []
}
connect(position) {
if (!this.isNeighbor(position)) {
this.neighbors.push(position)
position.neighbors.push(this)
}
}
getNeighbors() {
return this.neighbors
}
isNeighbor(position) {
return !!this.neighbors.find(neighbor => neighbor.row === position.row && neighbor.col === position.col)
}
}
class Maze {
constructor(grid = [[]]) {
this.grid = grid
this.rows = grid.length
this.cols = grid.reduce((highestLength, row) => highestLength < row.length ? row.length : highestLength, 0)
this.positions = []
this.transformIntoGraph()
this.start = this.positions.find(pos => pos.value === 'S')
this.end = this.positions.find(pos => pos.value === 'E')
}
transformIntoGraph() {
for (let i = 0; i < this.grid.length; i++) {
for (let j = 0; j < this.grid[i].length; j++) {
this.positions.push(new Position(i, j, this.grid[i][j]))
}
}
this.findNeighbors()
}
}
Para encontrarmos os "vizinhos" de cada posição podemos simplesmente testar cada uma das posições possíveis de movimento, verificando se elas não estão fora do alcance da matriz. Como ainda estamos lidando com a matriz, pois é ela quem possui os vizinhos, precisamos simular como seriam os possíveis movimentos nela. Com as 4 direções possíveis preparadas podemos iterar sobre todas as Positions e depois sobre as quatro direções verificando se elas estão fora dos limites da matriz. Para cada posição vizinha válida vamos conectá-la à posição atual.
class Position {
constructor(row, col, value) {
this.label = `(${row}, ${col})`
this.row = row
this.col = col
this.value = value
this.neighbors = []
}
connect(position) {
if (!this.isNeighbor(position)) {
this.neighbors.push(position)
position.neighbors.push(this)
}
}
getNeighbors() {
return this.neighbors
}
isNeighbor(position) {
return !!this.neighbors.find(neighbor => neighbor.row === position.row && neighbor.col === position.col)
}
}
class Maze {
constructor(grid = [[]]) {
this.grid = grid
this.rows = grid.length
this.cols = grid.reduce((highestLength, row) => highestLength < row.length ? row.length : highestLength, 0)
this.positions = []
this.transformIntoGraph()
this.start = this.positions.find(pos => pos.value === 'S')
this.end = this.positions.find(pos => pos.value === 'E')
}
transformIntoGraph() {
for (let i = 0; i < this.grid.length; i++) {
for (let j = 0; j < this.grid[i].length; j++) {
this.positions.push(new Position(i, j, this.grid[i][j]))
}
}
this.findNeighbors()
}
findNeighbors() {
const rowDirections = [-1, 1, 0, 0]
const colDirections = [0, 0, 1, -1]
this.positions.forEach(position => {
for (let i = 0; i < 4; i++) {
const rowIndexToMove = position.row + rowDirections[i]
const colIndexToMove = position.col + colDirections[i]
const isOutOfBounds = rowIndexToMove < 0 || colIndexToMove < 0 || rowIndexToMove >= this.rows || colIndexToMove >= this.cols
if (!isOutOfBounds) {
const neighbor = this.positions.find(pos => pos.row === rowIndexToMove && pos.col === colIndexToMove)
position.connect(neighbor)
}
}
})
}
}
Agora vamos começar a implementar a nossa busca pelo caminho mais curto utilizando um algoritmo conhecido como BFS, ou Breadth First Search (busca priorizando amplitude, numa tradução livre).
Ele funciona pesquisando, a partir do nó inicial, em cada um dos vizinhos imediatos. Cada nó vizinho que vai sendo encontrado é então adicionado em uma pilha (ou queue), e então para cada item da pilha vamos verificando se já chegamos na saída. Vale destacar que em uma pilha o primeiro a entrar é o primeiro a sair, portanto podemos utilizar um array e os métodos .psuh() para adicionar ao final e .shift() para remover do começo.
Com isso, ao adicionar o vizinho, eventualmente iremos buscar nele para adicionar os seus vizinhos, até percorrermos todo o grafo. Também temos que lembrar que só vamos adicionar um vizinho se ele não for uma parede ('#'), afinal não podemos andar através delas. Ficará parcialmente assim:
class Position {
constructor(row, col, value) {
this.label = `(${row}, ${col})`
this.row = row
this.col = col
this.value = value
this.neighbors = []
}
connect(position) {
if (!this.isNeighbor(position)) {
this.neighbors.push(position)
position.neighbors.push(this)
}
}
getNeighbors() {
return this.neighbors
}
isNeighbor(position) {
return !!this.neighbors.find(neighbor => neighbor.row === position.row && neighbor.col === position.col)
}
}
class Maze {
constructor(grid = [[]]) {
this.grid = grid
this.rows = grid.length
this.cols = grid.reduce((highestLength, row) => highestLength < row.length ? row.length : highestLength, 0)
this.positions = []
this.transformIntoGraph()
this.start = this.positions.find(pos => pos.value === 'S')
this.end = this.positions.find(pos => pos.value === 'E')
}
transformIntoGraph() {
for (let i = 0; i < this.grid.length; i++) {
for (let j = 0; j < this.grid[i].length; j++) {
this.positions.push(new Position(i, j, this.grid[i][j]))
}
}
this.findNeighbors()
}
findNeighbors() {
const rowDirections = [-1, 1, 0, 0]
const colDirections = [0, 0, 1, -1]
this.positions.forEach(position => {
for (let i = 0; i < 4; i++) {
const rowIndexToMove = position.row + rowDirections[i]
const colIndexToMove = position.col + colDirections[i]
const isOutOfBounds = rowIndexToMove < 0 || colIndexToMove < 0 || rowIndexToMove >= this.rows || colIndexToMove >= this.cols
if (!isOutOfBounds) {
const neighbor = this.positions.find(pos => pos.row === rowIndexToMove && pos.col === colIndexToMove)
position.connect(neighbor)
}
}
})
}
breadthFirstSearch() {
const queue = [this.start]
while (queue.length > 0) {
const position = queue.shift()
if (position.value === 'E') {
console.log('Found the exit!')
return
}
for (const neighbor of position.getNeighbors()) {
if (neighbor.value !== '#') {
queue.push(neighbor)
}
}
}
}
}
Porém temos um problema aqui. Se executarmos nosso código atual ele irá entrar em um loop infinito. Isso acontece porque cada nó tem vizinhos, que vão ser adicionados à pilha, mas os vizinhos do nó atual tem ele próprio como vizinho também. Para resolver isso, e também para nos ajudar a reconstruir o caminho percorrido uma vez que cheguemos à saída do labirinto, podemos utilizar um objeto para memorizar as posições que nós já passamos.
A primeira propriedade desse objeto será a do início, mas que terá o valor nulo para diferenciá-la das demais. Dentro do nosso loop iremos verificar se já passamos pela posição antes de colocá-la na pilha, se o objeto tiver uma propriedade com a label (que criamos lá no começo) da posição atual é porque ela já foi percorrida.
Além disso, temos que então adicionar uma propriedade com a label da posição a ser colocada na pilha, e seu valor pode ser a posição anterior, ou seja a que levou até ela. Por fim, quando encontrarmos a saída precisaremos reconstruir todos os passos que demos a partir desse objeto, pois cada propriedade com a label da posição irá ter a posição anterior que levou a ela. Vamos deixar esse método de reconstruir o caminho separado, mas já vamos implementá-lo.
Também podemos colocar um console.log() antes de encerrar nosso while apenas para sinalizar que nenhuma saída foi encontrada, porque nesse momento teremos percorrido todo o grafo sem achar a saída. Nosso código ficará assim:
class Position {
constructor(row, col, value) {
this.label = `(${row}, ${col})`
this.row = row
this.col = col
this.value = value
this.neighbors = []
}
connect(position) {
if (!this.isNeighbor(position)) {
this.neighbors.push(position)
position.neighbors.push(this)
}
}
getNeighbors() {
return this.neighbors
}
isNeighbor(position) {
return !!this.neighbors.find(neighbor => neighbor.row === position.row && neighbor.col === position.col)
}
}
class Maze {
constructor(grid = [[]]) {
this.grid = grid
this.rows = grid.length
this.cols = grid.reduce((highestLength, row) => highestLength < row.length ? row.length : highestLength, 0)
this.positions = []
this.transformIntoGraph()
this.start = this.positions.find(pos => pos.value === 'S')
this.end = this.positions.find(pos => pos.value === 'E')
}
transformIntoGraph() {
for (let i = 0; i < this.grid.length; i++) {
for (let j = 0; j < this.grid[i].length; j++) {
this.positions.push(new Position(i, j, this.grid[i][j]))
}
}
this.findNeighbors()
}
findNeighbors() {
const rowDirections = [-1, 1, 0, 0]
const colDirections = [0, 0, 1, -1]
this.positions.forEach(position => {
for (let i = 0; i < 4; i++) {
const rowIndexToMove = position.row + rowDirections[i]
const colIndexToMove = position.col + colDirections[i]
const isOutOfBounds = rowIndexToMove < 0 || colIndexToMove < 0 || rowIndexToMove >= this.rows || colIndexToMove >= this.cols
if (!isOutOfBounds) {
const neighbor = this.positions.find(pos => pos.row === rowIndexToMove && pos.col === colIndexToMove)
position.connect(neighbor)
}
}
})
}
breadthFirstSearch() {
const queue = [this.start]
const walkedPositions = {}
walkedPositions[this.start.label] = null
while (queue.length > 0) {
const position = queue.shift()
if (position.value === 'E') {
console.log('Found the exit!')
return this.reconstructPath(walkedPositions, position)
}
for (const neighbor of position.getNeighbors()) {
if (!walkedPositions.hasOwnProperty(neighbor.label) && neighbor.value !== '#') {
walkedPositions[neighbor.label] = position
queue.push(neighbor)
}
}
console.log('No way out!')
}
}
}
A última etapa agora será reconstruir o caminho que percorremos. Sabemos que ele será o mais curto porque, apesar de o processo ser quase simultâneo, nós fomos avançando um nível de vizinhos por vez até chegar na saída. Com isso, ao chegar na saída iremos reconstruir o caminho que levou menos "nível", ou menos passos, para encontrá-la.
Para reconstruir o caminho percorrido começaremos pela última posição, ou seja, a saída, que pode ser obtida pelo atributo que criamos na classe ou mesmo passada como argumento quando chamamos o método de reconstrução. A partir da última posição iremos adicionar a anterior no começo de um array com o método .unshift() até chegar na primeira posição, que será a inicial (com valor null). Esse array então conterá, em ordem, todos os passos que percorremos para chegar ao fim. Vejamos como ficará a código finalizado:
class Position {
constructor(row, col, value) {
this.label = `(${row}, ${col})`
this.row = row
this.col = col
this.value = value
this.neighbors = []
}
connect(position) {
if (!this.isNeighbor(position)) {
this.neighbors.push(position)
position.neighbors.push(this)
}
}
getNeighbors() {
return this.neighbors
}
isNeighbor(position) {
return !!this.neighbors.find(neighbor => neighbor.row === position.row && neighbor.col === position.col)
}
}
class Maze {
constructor(grid = [[]]) {
this.grid = grid
this.rows = grid.length
this.cols = grid.reduce((highestLength, row) => highestLength < row.length ? row.length : highestLength, 0)
this.positions = []
this.generateGraph()
this.start = this.positions.find(pos => pos.value === 'S')
this.end = this.positions.find(pos => pos.value === 'E')
}
generateGraph() {
for (let i = 0; i < this.grid.length; i++) {
for (let j = 0; j < this.grid[i].length; j++) {
this.positions.push(new Position(i, j, this.grid[i][j]))
}
}
this.connectNeighbors()
}
connectNeighbors() {
const rowDirections = [-1, 1, 0, 0]
const colDirections = [0, 0, 1, -1]
this.positions.forEach(position => {
for (let i = 0; i < 4; i++) {
const rowIndexToMove = position.row + rowDirections[i]
const colIndexToMove = position.col + colDirections[i]
const isOutOfBounds = rowIndexToMove < 0 || colIndexToMove < 0 || rowIndexToMove >= this.rows || colIndexToMove >= this.cols
if (!isOutOfBounds) {
const neighbor = this.positions.find(pos => pos.row === rowIndexToMove && pos.col === colIndexToMove)
position.connect(neighbor)
}
}
})
}
breadthFirstSearch() {
const queue = [this.start]
const walkedPositions = {}
walkedPositions[this.start.label] = null
while (queue.length > 0) {
const position = queue.shift()
if (position.value === 'E') {
console.log('Found the exit!')
return this.reconstructPath(walkedPositions, position)
}
position.getNeighbors().forEach(neighbor => {
if (!walkedPositions.hasOwnProperty(neighbor.label) && neighbor.value !== '#') {
walkedPositions[neighbor.label] = position
queue.push(neighbor)
}
})
}
return 'No way out!'
}
reconstructPath(walkedPositions, endPosition) {
let currentPosition = endPosition
const shortestPath = []
while (currentPosition !== null) {
shortestPath.unshift(currentPosition.label)
currentPosition = walkedPositions[currentPosition.label]
}
return shortestPath
}
}