Using the flood fill algorithm in a multidimensional maze.

[pucksnow]

I am very new to C++, and I recently made a maze generator by using 2D arrays. However, I need to create a "mouse" of sorts to travel through the maze. It should start at the starting cell and finish once it reaches the end cell. It needs to run through the maze and should be represented by an asterisk.

I really don't know how to code this, I learned about the flood fill algorithm and think it could work, but I don't know how to code it.

If anyone would look at my code and help me determine how to program this I would really appreciate it. Sorry if this is the wrong place, I just started C++ a little under two weeks ago.

The code is a bit long so I'll link to it:

https://pastebin.com/0aC2vGkR

[jonnin]

can't access external links.

I almost always recommend a 1-d solution (you can treat 1d as any dimension). Then you can flood fill it with a simple loop.

but that aside...


for(i = 0; i < rows; i++)
for(j = 0; j < cols; j++)
thing[i][j] = fillvalue;

if you insist on 2-d, you can collapse the inner loop in some cases:
for(i = 0; i < rows; i++)
memset( &thing[i][0], value, cols*sizeof(type));

but that only works if you are filling zeros or single bytes.

if its 1-d the memset will do the whole thing if it applies.

most likely, you should stick to the first version for now, memset is not a good plan for a beginner.

Memset is sort of a flood-fill approach. The loop isnt technically a flood fill. Not 100% sure what you need here... ?

[lastchance]

jonnin wrote:

Memset is sort of a flood-fill approach.

Only if everyone drowns.

https://en.wikipedia.org/wiki/Flood_fill

[jonnin]

I see. Sorry about that, I was not thinking about image algorithms :)

I think that algorithm could be made to work, yes. But you don't want to 'fill' here, you want one path. That is, if your flood fill stepped on every square in a big open room, then found that the north exit leads out, you wouldn't post a solution that stepped on all those extra squares before hitting the exit, you would just walk directly to the exit. You need some modification to the algorithm so the output it generates is sensible. I think if you carefully select how you choose what square to visit next each iteration combined with a way to 'backtrack' when you get stuck, it will produce the results you want -- just remember as you choose your next square that you are not coloring an image but seeking a route. I am thinking recursion is easier than iteration, have you seen recursion yet?

[pucksnow]

Yeah, that's when a function calls itself right? I haven't really used it for anything though. I only brought up this algorithm because someone told me about it, but I have no idea how to implement it in my code. The maze also has to be 2-d. The code I linked cannot be changed, the only thing I am allowed to do is add the "mouse" , but I am a bit stuck on how to do that

[jonnin]

ok. adding the mouse... play with it, see if you can figure it out. That should be simple (just assign a location in the maze to a symbol that means mouse).

most people do factorial as a first recursive program.

int fact(int x)
{
if(x == 1)
return 1;
else
return x*fact(x-1);
}

if you call that with 5, 5 is not 1, so it returns 5*(fact(4)). it can't do that, it does not know what fact(4) is yet, so it suspects the current iteration and fires up a new copy of the code on fact(4). 4 discovers that it is 4 * fact(3), which is 3*fact(2), which is 2*fact(1) ... which is 1 because of the if statement. Then it backtracks out: returns 1, 2*1 is 2, 2*3 is 6, 6*4 is 24, and 24*5 is 120, and then its done. This backtracking is what you want to know where you have been..

so you have something like
mark current square (color it in flood fill, mark as visited for you) (this is the color/mark for the true solution, all others are not correct)
is current square the maze exit? If so, solution found, stop and show.
else
{
can go left (not marked already, not a wall)? if so, recursive call on left square
can go up? if so recursive call up
can go right? If so, recursive call right
can go down?
else return stuck ... which pops the recursion (mark this square as totally checked out and dead end, not the same mark as above)
}

how that would work is it goes left, goes left, goes left, can't go left goes up, tries to go left again, lets say it gets stuck here and can't do anything new. It then pops back one... last thing it did was the up, so now it is on the 'right' step for that square, does that, can it go left (no, already visited, important, it could go if you had not marked this square first)... and so on.

Does this make sense? (Operating on understand it first, code it later here). The order of the squares I gave may not be optimal, need to look at that on paper a bit.