CODEWITHSUNDEEP
calgorithmflood-fill
Stefan Bossbaly
Stefan Bossbaly

Reputation: 6794

Flood Fill Algorithm - Maze Navigation

I am trying to implement a version of the flood fill algorithm to help solve the shortest distance path of a maze for a micro mouse. It works the same way as the regular flood fill except that each adjacent non-filled place will be assigned a number representing the distance of that place to the start place. Each time the algorithm moves to a different cell the number is incremented by one. Here is an example of a maze with no wall starting in the bottom left hand corner.

2 3 4
1 2 3
0 1 2

Here is the current code I have ...

void nav_flood_rec(struct nav_array *array, int row, int column, int flood_num)
{
    //Check the base case (not shown here)
    if (base_case)
        return;

    //Assign the flood number
    arrray->cells[row][column]->flood_number = flood_num;

    //North
    nav_flood_rec(array, row + 1, column, flood_num + 1);

    //East
    nav_flood_rec(array, row, column + 1, flood_num + 1);

    //South
    nav_flood_rec(array, row - 1, column, flood_num + 1);

    //West
    nav_flood_rec(array, row, column - 1, flood_num + 1);
}

The problem that I am having is that the recursion is not going one step at a time (kind of vague but let me explain). Instead of checking all directions and then moving on the algorithm will keep moving north and not check the other directions. It seems that I want to make the other recursive calls somehow yield until the other directions are checked. Does anyone have any suggestions?

Upvotes: 2

Views: 7489

Answers (3)

Pubby
Pubby

Reputation: 53047

You've implemented something analogous to a depth-first-search, when what you're describing sounds like you want a breadth-first-search.

Use a queue instead of a stack. You're not using a stack explicitly here, but recursion is essentially an implicit stack. A queue will also will solve the problem of stack overflows, which seems likely with that much recursion.

Also, as G.Bach says, you'll need to mark cells as visited so your algorithm terminates.

Upvotes: 4

d0rmLife
d0rmLife

Reputation: 4250

You call north() without testing any conditionals. Therefore, your recursion will, in order:

  • 1) Test for base case
  • 2) Set new flood number
  • 3) Encounter //north and call nav_flood_rec()
  • 4) REPEAT.

As you can see, you will never reach your other calls. You need to implement a test conditional, branch it, or something like that.

Not really sure what you're trying to do, but you could pass another struct as a parameter and have a value for each direction and then test them for equality... like...

struct decision_maker {
  int north;
  int south;
  int west;
  int east;
};

Then in your code:

/* assume dm is passed as a pointer to a decision_maker struct */

if (dm->north > dm->south) {
  if (dm->south > dm->east) {
    dm->east++; // increment first
    // call east
  } else if (dm->south > dm->west) {
    dm->west++; // increment first
    // call west
  } else {
    dm->south++;
    // call south
} else {
    dm->north++;
    // call north
}
/* 
*  needs another check or two, like altering the base case a bit
*  the point should be clear, though.
*/

It will get a little messy but it will do the job.

Upvotes: 1

Alexey Frunze
Alexey Frunze

Reputation: 62068

Wikipedia's article on the subject:

An explicitly queue-based implementation is shown in pseudo-code below. It is similar to the simple recursive solution, except that instead of making recursive calls, it pushes the nodes into a LIFO queue — acting as a stack — for consumption:

 Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. Add node to the end of Q.
 4. While Q is not empty: 
 5.     Set n equal to the last element of Q.
 7.     Remove last element from Q.
 8.     If the color of n is equal to target-color:
 9.         Set the color of n to replacement-color.
 10.        Add west node to end of Q.
 11.        Add east node to end of Q.
 12.        Add north node to end of Q.
 13.        Add south node to end of Q.
 14. Return.

Upvotes: 1

Related Questions