11 replies to this topic

[IceMetalPunk]

I'm currently taking an Intermediate C++ class. Our second project is to generate a 22x22 maze, randomly deciding where the walls are with a 2:1 space-to-wall ratio (with a preset solid-wall border, the start at [1,1], and the goal at [20,20]). Then we need to write a function to solve the maze. The generation was simple enough, but I'm having trouble with the solving algorithm.

I figured it'd be easier to write the code first in GM, then once it works convert it to C++ (since I'm more familiar with GML than C++). But it's not working right.

I'm trying to use the Pledge algorithm (this one). That is, the computer should move in a random direction at first. When it hits a wall, it should follow that wall (i.e. keep it on the left or right) until it's turned back in the original direction it was moving, then continue on in a straight line again. It's basically a modification of the Wall Follower that allows for disjointed walls (which I'll have most of the time). It seems to work at first, but then gets stuck in places it shouldn't and goes into an infinite loop.

The code is below. We have a C++ structure to simulate stacks, so they behave exactly like GM's stacks; there's also a structure for points, which I'm simulating here with ds_lists, hence the _c suffix on my stack method calls (custom scripts to create the coordinate list and push it onto the stack). We're supposed to return a stack filled with the sequence of positions to follow to solve the maze--in other words, the resulting path. If there's no solution (which my algorithm can determine if it returns to the original start point), we are supposed to output that ("No solution") and nothing more.

In my implementation, I'm using the array values 0=wall, 1=free space, 2=free space that's been traversed already (I thought it might be useful information at some point). [i,j] is the current position being checked. xdir and ydir represent directions (+1 means right/down, -1 means left/up, and 0 means don't move on that axis). fx and fy are the offsets of the space to check for a wall when following a wall (i.e. where the "right side" is relative to the current direction). fxd and fyd store the original direction of motion before following begins (when this is the same as the current direction, stop following the walls). turns represents the number of turns we've made while following. If this is a multiple of 4, we've turned 360-degrees and are now facing our original direction. following is simply a flag to determine whether we should be following the wall or just moving straight.

moves=ds_stack_create();
  ds_stack_push_c(moves,1,1); /* Add the initial position, (1,1), to the stack. */

  maze[1,1]=2;

  xdir=0;
  ydir=1;
  i=1;
  j=1;
  fx=0;
  fy=0;
  fxd=0;
  fyd=0;
  turns=0;
  following=0;

  while (i!=20 && j!=20) {

    if (!following) {
      if (maze[i+xdir, j+ydir]!=0) {
        i+=xdir;
        j+=ydir;
      }
      else {
        following=1;
        fx=xdir;
        fy=ydir;

        fxd=xdir;
        fyd=ydir;
        turns+=1;

        if (xdir!=0) { xdir=0; }
        else { xdir=ydir; }
        if (ydir!=0) { ydir=0; }
        else { ydir=-fx; }

        if (maze[i+xdir, j+ydir]!=0) {
          i+=xdir;
          j+=ydir;
        }

      }
    }
    else {
      if (maze[i+xdir, j+ydir]==0) {

          fx=xdir;
          fy=ydir;

          if (xdir!=0) { xdir=0; }
          else { xdir=ydir; }
          if (ydir!=0) { ydir=0; }
          else { ydir=-fx; }

          if (maze[i+xdir, j+ydir]!=0) {
            i+=xdir;
            j+=ydir;
          }

          turns+=1;
      }

      else if (maze[i+xdir, j+ydir]!=0) {
          i+=xdir;
          j+=ydir;
      }
      else if (maze[i+fx, j+fy]!=0) {

          fx=-xdir;
          fy=-ydir;

          if (xdir!=0) { xdir=0; }
          else { xdir=-ydir; }
          if (ydir!=0) { ydir=0; }
          else { ydir=-fx; }

          if (maze[i+xdir][j+ydir]!=0) {
            i+=xdir;
            j+=ydir;
          }

          turns-=1;

      }
      }

      if (xdir==fxd && ydir==fyd) {
        following=0;
        turns=0;
      }

    if (i==1 && j==1 && (turns mod 4)==0) { show_message("ESCAPE IS IMPOSSIBLE"); ds_stack_destroy(moves); return -1; }
    
    ds_stack_push_c(moves,i,j);

    maze[i, j]=2;
  }

  return moves;

}

It seems like it should work to me, but it keeps going into an infinite loop. Upon debugging, I've found that it'll fall into loops in some paths, which shouldn't happen with this algorithm. Any help?

-IMP

Edited by IceMetalPunk, 10 February 2011 - 10:59 PM.

[janborg]

Hi...
I would like to help.
If you supply me with all the code (also the maze generation code), then I'd be happy to take a look at it.
Best regards
Jan

[Desert Dog]

Just quickly, was it required that you use pledge? I've done a depth first search on such a maze (only the player had a random position) and it's easy enough to implement.

Otherwise..

        i+=xdir;
        j+=ydir;

Over and over I see this. Why? Shouldn't you be moving in only one direction? (up/down/left/right)


I give a run down on the dfs search in this spoiler tag, if your interested in reading about it. It's pretty simple to implement, and works great.

Spoiler

000000000000
01111p1111#0
001000000000
000000000000

p=player, #=exit

The player checks for a direction to move in.. in this case, we'd say you've programmed it so he moves left first. So he checks if it's empty, as it is, he goes left (and each time he goes left, he pops that 'movement' onto his stack)

000000000000
0p22221111#0
001000000000
000000000000

Now he checks left again, finds nothing so he looks in the other directions and finds nothing! So he pops the last move off his stack

000000000000
02p2221111#0
001000000000
000000000000

And looks around again. Find he can go down so..

000000000000
0222221111#0
00p000000000
000000000000

He looks around, finds he can't move, so he pops the last move off his stack:

And of course, he can't move anywhere, either, that he hasn't already been, (i.e. a 2) or is a wall, so he pops a movement of his stack, all along and backtracks along the path, checking

000000000000
02222p1111#0
002000000000
000000000000

Until he finds he can go right. So he goes right. Until he finds the exit.

Because you've been popping off the moves as you back tracked, your path that is returned is simply the starting position, and move straight right. Perfect!

[Mnementh]

I don't think that your stop-following condition is complete. According to Wikipedia, following should stop when the current direction is identical to the original direction, and when the angular sum of the turns made is zero. I see the first part, but not the second.

if (xdir==fxy && ydir == fyd && (turns mod 4) == 0) {
  following = 0;
  turns = 0;
}

I'm also unsure about the right-turn portion of the following algorithm. If the navigator can move forward than it should - but it may also be required to turn right to keep its hand on the wall. Your code doesn't seem to allow the possibility of a forward move and a right turn, because once the navigator moves forward the iteration ends, and during the next iteration it will mistakenly make a left turn.

When you write this in C++, you'll use the point structure to represent the current position, and direction in the maze, right? If you do, it would be simple to write a function to rotate the direction vector left or right - you could use it not only in the turns, but to find the right-hand position. I probably would have written this in C++ to begin with, because the point structure would make this code much simpler.

I'm using the array values 0=wall, 1=free space, 2=free space that's been traversed already (I thought it might be useful information at some point).

The path produced is not efficient. You could easily use the fact that a space had been traversed multiple times to remove loops from the path.

[IceMetalPunk]

@JanBorg: That is all the code. The generation just chooses a random integer between 0 and 2, inclusive, for each array element. If the number is >0, it puts a space, otherwise it puts a wall. Then the outer border is fulled with walls.

@Desert Dog: No; we're allowed to use whatever maze-solving methods we want. I'll look into the depth-first search, thanks . And you are only moving one direction (when either xdir or ydir is non-zero, the other is always 0); I just didn't feel like checking which direction to move in and so setting one value to 0 and the other to non-zero seemed easier (read: lazier) .

@Mnementh: How is it possible to end up in the same direction without the angles summing to 0? If I make a left turn and a right turn, or if I make 4*n left or right turns, the angles still sum to 0, do they not?

But I think you're on to something with the wall-following issue (how it moves forward, then ends the iteration before deciding if it should turn or not, thus making it think it's in a free space instead of still following a wall). Unfortunately, I left my source files on my school computer, so I'll have to wait until tomorrow before I can even look at it...

Mind elaborating on how using a point structure would be any easier to rotate the direction vector? I suppose I could just do something like this, correct?:

x = cos(arccos(x) + directionToRotate);
y = -sin(arcsin(y) + directionToRotate);

Correct? Or were you thinking about something simpler?

-IMP

[Mnementh]

How is it possible to end up in the same direction without the angles summing to 0? If I make a left turn and a right turn, or if I make 4*n left or right turns, the angles still sum to 0, do they not?

Four right turns rotate the navigator back to its original direction, but do not sum to zero. Both you and I mistakenly thought that turns need only be a multiple of four, but the actual requirement is more stringent. The turns variable must be equal to zero - and you do not need the direction check, because if turns is zero, then the direction must be identical to the original direction.

Mind elaborating on how using a point structure would be any easier to rotate the direction vector? I suppose I could just do something like this, correct?:

x = cos(arccos(x) + directionToRotate);
y = -sin(arcsin(y) + directionToRotate);

Correct? Or were you thinking about something simpler?

My statement was ambiguous. What I meant was not that the rotate function itself would be simple - although it should be - but that your code would be simple overall, because the rotate function reduces repetition and increases clarity in your algorithm. You have three instances of essentially the same rotation code - two that are completely identical (right?) and one that is almost identical. Overall, the function with a point structure would look something like this code.

current = (1, 1)
end = (20, 20)
direction = (1, 0)

turns = 0

while current != end
    
    // if not wall following
    if turns == 0
        # move forward, if possible
        if place_free(current + direction)
            current += direction
        // otherwise rotate right
        else
            direction = rotate_left(direction)
            turns += 1
    // wall following
    else
        // turn right if possible
        if place_free(current + rotate_right(direction))
            direction = rotate_right(direction)
            turns -= 1
        // move forward, if possible
        else if place_free(current + direction)
            current += direction
        // otherwise, turn left
        else
            direction = rotate_left(direction)
            turns += 1

Notice that I've reversed the progression of the wall following code - right turn, straight, left turn is actually a much more natural way to express a right-handed wall follower, because it would, given a choice, always prefer to move right.

[Hrothgar]

Just as a quick tip, since you could not use any path finding algorithm you wanted this will only be a suggestion for further learning.
If you should know any pathfinding algorithm you should know the A*
For maps as small as the one you're using it is probably not the best choice,
but if you want an algorithm that works fast on any size of map it is the A*.
It's simply a dijkstra search algorithm with the addition of a heuristic function that in normal cases
will help the algorithm by pointing in the most likely direction to search for a shortest path.

The algorithm is widely used within the industry, and it's a handy thing to know how to program.

Good luck with your assignment!

[Khelder]

@Hrothgar: But, for that you need to be able to 'see' the whole maze at once, in which case you may as well just start with a dead-end filling algorithm, which will leave you with all valid paths, and then either apply A* or a loop-eliminating algorithm to pick one of the paths.

Since IMP started by using the Pledge algorithm, I'd assume he's supposed to use a 'self-mapping' algorithm - that is, one that doesn't know the whole maze, but builds up a 'mental map' as it explores - much like how a person stuck in a maze would have to.

[IceMetalPunk]

Well, that seems to be my professor's implication, but technically he said "you can use any method you want to solve the maze, as long as you use stacks somewhere". His suggestion was using stacks to keep track of your position so you can pop off dead ends, but as long as stacks are used, we can do this however we want.

I unfortunately didn't have a chance to try out any of these suggestions, since I had a test in my C++ class yesterday. And I don't have any class again until Tuesday... luckily, this is a project that's due at a later date . When I finally get a chance to test these, I'll post how it goes.

-IMP

[Hrothgar]

@Hrothgar: But, for that you need to be able to 'see' the whole maze at once, in which case you may as well just start with a dead-end filling algorithm, which will leave you with all valid paths, and then either apply A* or a loop-eliminating algorithm to pick one of the paths.

Since IMP started by using the Pledge algorithm, I'd assume he's supposed to use a 'self-mapping' algorithm - that is, one that doesn't know the whole maze, but builds up a 'mental map' as it explores - much like how a person stuck in a maze would have to.

Ah yes, I'm sorry for the misunderstanding.
I should've realised that :/

However, it no longer seems to be the case regarding the above post, so hopefully it might come in handy
never the less

Cheers!

[Khelder]

Here's a quick thing I threw together. You can tell it was quick, because:
* I used the mp_grid functions instead of writing out Dijkstra's algorithm myself
* It displays the result as a path, rather than a stack
* The map generation and/or dead-end filling algorithms need improving, because the dead-end filling doesn't support 'areas', just 1 wide 'corridors', and the map generated is simply random placement

It cycles through maps until it finds one that can be solved (using a stack-based flood-fill from the start to the exit) then eliminates dead-ends (badly) to make the next part easier, and finally generates the shortest route (by cheating)

Probably of no use at this stage, since you're likely further on, but I was bored XD
>>Linky<<
Oh, and it's been slowed down to look pretty

[janborg]

Hi
Made a visual implementation using a Depth First Search algorithm (DFS).
just to have some fun.
There is no backtracking or path recording btw, it only finds the goal.
Source .gmk here

Screenshot here

p.s. Anyone can use this code for anything and do anything with it. Credit if you will.

/br
Jan

Edited by janborg, 22 February 2011 - 09:29 AM.