Prevent the continuous looping of tree generation using Breadth-First Search (

Question

Prevent the continuous looping of tree generation using Breadth-First Search (

My current assignment involves writing a program to determine the shortest path between a knight and a target tile on a chessboard. The task requires me to represent the knight's possible moves in a tree structure and utilize recursion to find paths to the target location. I've encountered challenges with the recursive call in the `getMoves` function, particularly regarding avoiding repeating visited tiles to prevent an infinite loop.

While browsing solutions on StackOverflow, I noticed various methods involving graphs and simpler implementations. However, I have opted to use trees and Breadth-First Search (BFS) as the primary approach due to my ongoing study focus and the specific requirement of this exercise. The code consists of three classes: `Board`, `Knight`, and `TreeMoves` where the available moves are stored. The BFS algorithm resides within the `TreeMoves`, iterating through each tree level recursively to check for a node matching the target position. Essentially, the process entails generating all possible knight moves, running BFS to identify the target location, and recursively expanding the tree to explore further positions, excluding previously visited ones.

Although I considered creating a more concise version for the community, I'm concerned it might cause confusion at this point. The existing code performs well when the target is within immediate reach of the knight's available moves. However, if the target is slightly moved away from these initial positions, it leads to the infinite loop issue mentioned earlier.

I would appreciate any guidance or hints on identifying potential mistakes in my implementation.

Cheers!


        <!-- JavaScript code snippets omitted for conciseness -->

javascript tree breadth-first-search

Answer 1

Answer №1

After persistent efforts, I successfully resolved the structural issues in my code by relocating the getMoves method to the MovesTree class and making some necessary corrections. Utilizing the BFS algorithm played a crucial role in managing move generation effectively, preventing infinite loops. Surprisingly, implementing this method not only prevented unexpected behavior but also unveiled that the shortest path consists of a series of moves elucidated wonderfully in this question: Knight's Shortest Path on Chessboard, if my memory serves me right. Without further ado, here is the finalized code.

  static size = 8;

  targetPos = [];
  targetToken = 't';
  moveToken = 'a';

  static isOutOfBoundaries(x,y){
    if(x>Board.size-1||x<0)
      return true;
    else if(y>Board.size-1||y<0)
      return true;
    else
      return false;
  }

  constructor(){
    this.tiles = Array.from(Array(Board.size), ()=>Array.from(Array(Board.size), tile=>'·')); 
  }

  visualize(){
    this.tiles.forEach(row=>console.log(row.join(' ')));
  }

  placeItem(position, token){
    if(Board.isOutOfBoundaries(position[0],position[1]))
      throw new Error(`Piece/Target is out board boundaries`);
    else
      this.tiles[position[1]][position[0]] = token;
  }
  
  markPieceMoves(piece){
    for(let i = 0; i<piece.moves.length; ++i)
      this.tiles[piece.moves[i][1]][piece.moves[i][0]] = this.moveToken;
  }

}

class MovesTree{
  constructor(position){
    
    this.pos = position;


    // Initialization of move directions


  }

  static getMoves(node){
    const twoSteps = 2;
    const oneStep = 1;
    // Move generation logic

    
  }    

  BFS(func,target){
    let queue = [this];
    while(queue.length>0){
      if(target.toString()!==queue[0].pos.toString()){
        MovesTree.getMoves(queue[0])
        queue.push(...func(queue[0]));
      }
      else
        return; 
      queue.shift();
    }
  }

  DFS(node, target, path){

    let visited; 
    path === undefined ? visited = [node.pos]: visited = this.mergePath(path, node.pos);
    if(node.pos.toString()===target.toString()){
      visited.reverse();
      console.log(visited);
      return;
    }
    else{
      // Depth First Search traversal

    }
  }

  toArray(node){

    // Convert tree nodes to array
    
  }

  mergePath(path, current){
    let merged = [];
    merged.push(current);
    path.forEach(step=>{
      merged.push(step)
    });
    return merged;
  }
}
class Knight{
  token = 'k';
  constructor(row,col){
    this.position = [row,col];
    this.moves = new MovesTree(this.position,this);
  }
}
const board = new Board();
board.targetPos = [6,0];
const knight = new Knight(0,7);
board.placeItem(knight.position, knight.token);
board.placeItem(board.targetPos, board.targetToken)

knight.moves.BFS(knight.moves.toArray, board.targetPos);
knight.moves.DFS(knight.moves, board.targetPos)
board.visualize();

Answer 2

After persistent efforts, I successfully resolved the structural issues in my code by relocating the getMoves method to the MovesTree class and making some necessary corrections. Utilizing the BFS algorithm played a crucial role in managing move generation effectively, preventing infinite loops. Surprisingly, implementing this method not only prevented unexpected behavior but also unveiled that the shortest path consists of a series of moves elucidated wonderfully in this question: Knight's Shortest Path on Chessboard, if my memory serves me right. Without further ado, here is the finalized code.

  static size = 8;

  targetPos = [];
  targetToken = 't';
  moveToken = 'a';

  static isOutOfBoundaries(x,y){
    if(x>Board.size-1||x<0)
      return true;
    else if(y>Board.size-1||y<0)
      return true;
    else
      return false;
  }

  constructor(){
    this.tiles = Array.from(Array(Board.size), ()=>Array.from(Array(Board.size), tile=>'·')); 
  }

  visualize(){
    this.tiles.forEach(row=>console.log(row.join(' ')));
  }

  placeItem(position, token){
    if(Board.isOutOfBoundaries(position[0],position[1]))
      throw new Error(`Piece/Target is out board boundaries`);
    else
      this.tiles[position[1]][position[0]] = token;
  }
  
  markPieceMoves(piece){
    for(let i = 0; i<piece.moves.length; ++i)
      this.tiles[piece.moves[i][1]][piece.moves[i][0]] = this.moveToken;
  }

}

class MovesTree{
  constructor(position){
    
    this.pos = position;


    // Initialization of move directions


  }

  static getMoves(node){
    const twoSteps = 2;
    const oneStep = 1;
    // Move generation logic

    
  }    

  BFS(func,target){
    let queue = [this];
    while(queue.length>0){
      if(target.toString()!==queue[0].pos.toString()){
        MovesTree.getMoves(queue[0])
        queue.push(...func(queue[0]));
      }
      else
        return; 
      queue.shift();
    }
  }

  DFS(node, target, path){

    let visited; 
    path === undefined ? visited = [node.pos]: visited = this.mergePath(path, node.pos);
    if(node.pos.toString()===target.toString()){
      visited.reverse();
      console.log(visited);
      return;
    }
    else{
      // Depth First Search traversal

    }
  }

  toArray(node){

    // Convert tree nodes to array
    
  }

  mergePath(path, current){
    let merged = [];
    merged.push(current);
    path.forEach(step=>{
      merged.push(step)
    });
    return merged;
  }
}
class Knight{
  token = 'k';
  constructor(row,col){
    this.position = [row,col];
    this.moves = new MovesTree(this.position,this);
  }
}
const board = new Board();
board.targetPos = [6,0];
const knight = new Knight(0,7);
board.placeItem(knight.position, knight.token);
board.placeItem(board.targetPos, board.targetToken)

knight.moves.BFS(knight.moves.toArray, board.targetPos);
knight.moves.DFS(knight.moves, board.targetPos)
board.visualize();

Prevent the continuous looping of tree generation using Breadth-First Search (

Answer №1

Similar questions

Display HTML components as JSON data using AngularJS

Having trouble with my basic AJAX request; it's not functioning as expected

The type 'Pagination<UserEntity>' is lacking the following attributes from type 'UserEntity':

Troubleshooting a Laravel method invoked in JavaScript using PhpStorm

Kudos to the information provided in the table!

Error: Unable to locate module: Issue discovering 'crypto' and 'fs' modules

problem encountered while attempting to transmit data to multer in React

In main.js within the Google Maps API, an error is triggered when trying to setDraggable(false) on a

Error: Unable to submit form with jQuery due to timeout issue - e[h] function not recognized

Error Encountered: Angular JS Throwing Unhandled Injection Error

What is the best way to cycle through sprite positions within an array?

Changing a string into a JavaScript date object

Displaying a dynamic flag icon in a span element based on the selection from a mat-select

aviary usage resulted in a file_get_contents error

After clicking on the checkbox, req.body.task becomes undefined

Combining Option Value and Name Selection Using React Hooks

Comparison between using jQuery to append and execute a <script> tag versus using vanilla JavaScript

encountering a typeError upon attempting deployment on Heroku

Is it better to deploy a JS app to the browser, or should I consider using nw.js

Tips for updating a specific portion of a component in react.js