Maze Solver

UPDATE: Years ago, when I wrote this, I don't know why it didn't occur to me to link to the code. Here it is.

My mind, for whatever it's worth, was being under-used, so I applied it to solving mazes. Check this action out. First, here is the original maze which inspired this project (yeah, it's kind of big).

Beautiful, huh?

Okay, so, here is the result. The blue area represents the places that the algorithm searched (notice that some areas are still white); the green plus ("+") is the start point; the red plus is the end point; and the red line is the (rather spastic) path from one to the other.

And here's a pseudo code form of the search algorithm. It works like this: initialize a path associated with the begin point containing just the begin point. Then find all of the adjacent points (1) whose color is the same as the begin point and (2) that we haven't visited yet. If there is only one adjacent point, give it a reference to the referring point's path; otherwise create a new path with a reference back to the referring point's path and current size (ie, the number of items in the path). Add each point to it's respective path. Mark each point as being visited. Add each point to our set of points that we'll use on the next iteration. And repeat this until one of the points is the end point. To find the solution we look at its path and follow the chain of references back to the start.

When a particular path hits a dead end, there are no adjacent points that we're interested in and the memory is re-claimed. The only memory that is actively used is associated with the leading-edge points and their paths back to the start.

Said another way: it searches like water flowing into a level room from a drain on the floor. That was my inspiration anyway.

POINT begPoint = { x1, y1 }
POINT endPoint = { x2, y2 }
SET tmpset, newset = [], s1 = [ begPoint ]

WHILE (1) {
  foreach POINT point1 IN s1 {
    if point1 == endPoint
      done

    INT count = 0
    SET s2 = adjacentUnvisitedPoints(point1)

    foreach POINT point2 IN s2 {
      if begPixel != pixelAtPoint(point2)
        continue
      if count++ == 0
        point2.path = point1.path
      else {
        point2.path = new PATH
        point2.path.prevPath = point.path
        point2.path.prevIndex = point.path.count
      }
      addPointToPath(point2.path, point2)
      markAsVisited(point2)
      addPointToSet(newset, point2)
    }

    tmpset = set1
    set1 = newset
    newset = tmpset
    clearSet(newset)
  }
}

I've got some more mazes that aren't exactly pixel-perfect. And I'm not sure how to approach that, but I'll think of something. If I continue to be bored, that is.

Update: Here's one more example, this time with a much less precise maze, but still one of a very high quality. I had to draw lines across the "entrance" and "exit" to prevent the search from escaping the maze. The original and the solution.