How would I fix this backtracking algorithm?

Question

I'm trying to write a backtracking algorithm that can generate a pseudo-random path between a start and an end node in a 2D grid, represented by a 2D array. So the initial grid might look like this:

Where '2' is the start node and '3' is the end node, and '1's are the path between them. '0' nodes are empty. And I have a separate 2D array to keep track of what nodes have been visited.

And here is what I have for the algorithm:

  private get_next_valid_position(x: number, y: number) {
    // while not at END
    while (this.get_tile(x, y) != 3) {
      // we can move up, down, left or right - not diagonally!
      const options = [
        [x, y + 1],
        [x, y - 1],
        [x + 1, y],
        [x - 1, y],
      ];
      
      // a valid option is an unvisited, empty, non-start node position
      const valid_options = options.filter(
        ([x, y]) =>
          (this.get_tile(x, y) == 0 || this.get_tile(x, y) == 3) &&
          !this.get_visited(x, y)
      );

      // shuffle for randomness
      shuffleArray(valid_options);

      for (let option of valid_options) {

        // check_position uses A* to make sure there is a valid path from this point
        if (this.check_position(option[0], option[1])) {
          this.set_tile(option[0], option[1], 1);
          this.set_visited(option[0], option[1], true);

          this.get_next_valid_position(option[0], option[1]);

          this.set_tile(option[0], option[1], 0);
          this.set_visited(option[0], option[1], false);
        }
      }

      return;
    }
  }

I've so far based the logic for this algorithm off a Computerphile video on a sudoku solver that uses backtracking, but I can tell I'm doing something wrong here. I think I'm lacking a proper "success" condition that will stop the recursion since the array always ends up in its beginning state, but I can't really figure out how I would implement that.

EDIT So I think I may have improved my algorithm somewhat. I've removed the while loop and added and if condition instead, like so:

  private get_next_valid_position(x: number, y: number) {
    // while not at END
    const options = [
      [x, y + 1],
      [x, y - 1],
      [x + 1, y],
      [x - 1, y],
    ];

    const valid_options = options.filter(
      ([x, y]) =>
        (this.get_tile(x, y) == 0 || this.get_tile(x, y) == 3) &&
        !this.get_visited(x, y)
    );
    shuffleArray(valid_options);

    if (this.get_tile(x, y) != 3) {
      for (let option of valid_options) {
        if (this.check_position(option[0], option[1])) {

          // dont change the END node
          if (this.get_tile(option[0], option[1]) != 3) {
            this.set_tile(option[0], option[1], 1);
            this.set_visited(option[0], option[1], true);
          }

          this.get_next_valid_position(option[0], option[1]);

          this.set_tile(option[0], option[1], 0);
          this.set_visited(option[0], option[1], false);
        }
      }

      return;
    }

    // Grid is *nearly* correct at this stage
    console.table(this.map);
  }

Now when the program hits the console.table line, this.map does have a valid path, however it looks like there are extra paths its tried still in the grid that have not been backtrack-ed out. So I think I'm getting somewhere but there is still an issue with how I've implemented the backtracking.

user_12096922 · Answer

I would not use A* to solve this problem, since the backtrack itself can do the job of finding the path if properly coded.

This is because it's unnecessary to know if there is a path between the current tile and the goal as the backtrack guarantees to set a tile only in the places that are valid moves. So there's no need to rely on sophisticated path-finding algorithms.

So I'd put a full if-else and minor changes to the core of your backtracking algorithm in this way:

function can_move_to(x,y) is
    return if map[x][y].visited is false

algorithm get_next_valid_position(x,y) is 
{- Input: numbers x,y representing starting point
   Output: prints a valid path -}
for each option of valid_options
    if can_move_to(option) then
        if option value is endValue then
            print map
        else
            option.value := 1
            option.visited := true
            get_next_valid_position(option.x, option.y)
            option.value := 0
            option.visited := false

Notice that there are lots of ways to reach the end node from the start. So it may be useful to append direction signs to facilitate the visualization of how the path is outlined. For example:

Taken from the working algorithm in Typescript

How would I fix this backtracking algorithm?

1 Answers