pathfinding conditions def

Question

Ok so I had to crack a Heineken for this one. Trying to solve a shortest path problem with a text file.

My research took me to: link text link text pretty good information for my algorithm

Basically, I'm trying to start out at 'S' for start and quit at 'F' for finish or return no solution message

the two self styled tests or text files being considered

      ##########
      #S       #
      ######   # 
      #F       #
      ##########

      and non-solvable

      ##########
      #S       #
      ########## 
      #F       #
      ##########

My problem is I'm having trouble writing a pathfinding def for this and returning it to the custom print def. Below is the code for the whole darn thing. As well as my first attempt at it. Spaces are free to be a path. Walls are defined as any other key but the space bar. Also be warned my while loop for quiting will return an error, I'm working that out right now.

  puts "enter a file name (example maze1.mz) PRESS ENTER" 
  filename = gets.chomp.to_s
  while filename != 'quit' do


  def read_maze( filename )
  local_maze = []
  mz_file = File.open(filename,"r")

  while ! mz_file.eof? do
  line = mz_file.gets.chomp
  local_maze << line.scan(/./)
  end

  mz_file.close
  return local_maze
  end

  def solve_maze(row, column, blank_spot, blank_spot_not ) #parse throug args
  #from http://en.wikipedia.org/wiki/Maze
  #from http://en.wikipedia.org/wiki/Pathfinding


  return unless self[column][row]   #condition for its full
  return if self[column][row] != space #condition for printable spot
  return if self[column][row] == blank_spot_not #can't use this spot
  return if self[column][row]== full or f encountered
  #maze is full can't solve or finished
  self[column][row] = blank_spot_not

  #direction up down left right
  solve_maze(column+1, row, space, blank_spot_not) #right
  solve_maze(column-1, row, space, blank_spot_not) #left
  solve_maze(column, row+1, space, blank_spot_not) #up
  solve_maze(column, row-1, space, blank_spot_not) #down



 end

 def print_maze( maze )
 maze.each {|row|
 puts row.join('')
  }
 end


 maze = read_maze(filename)
 print_maze(maze)
 solve_maze(maze)
 print_maze(maze)

 puts "would you like to further drive yourself nuts with this maze solver"

 filename = gets.chomp.to_s
 maze = read_maze(filename)
 print_maze(maze)

 end

 puts "you have quit"

Answer 1

Here's a couple of hints regarding your code:

• solve_maze takes four parameters, but you are only passing one in the initial invocation (solve_maze(maze))
• All your objects are either strings or arrays of strings, but you are constantly doing integer math with them
• You are constantly using self to refer to the current object, but you don't even have a current object, since you are writing in a procedural style, not an object-oriented one. [Note: I know that in Ruby, you always have a current object, which in this case is the anonymous top-level object.]

Here's a couple of more hints regarding your workflow:

• Forget about the while loop. Why would you want the possibility of solving multiple mazes when you cannot even solve one at the momen? You can always add that in later.
• Forget about reading the maze from a file, just hardcode it in a string. You can always add that in later.
• In fact, forget about parsing the string altogether, just hardcode the maze in a datastructure that is convenient for you to deal with. I'd suggest a two-dimensional array of Booleans. You can always ... well, you get the drift.
• Start with a simple maze. Like, really simple. Like, one tile where you already start up at the destination. Then move on to a maze with two tiles where the destination is right next to the start.

Examples:

solvable = [
  [false, false, false, false, false, false, false, false, false, false],
  [false,  true,  true,  true,  true,  true,  true,  true,  true, false],
  [false, false, false, false, false, false,  true,  true,  true, false],
  [false,  true,  true,  true,  true,  true,  true,  true,  true, false],
  [false, false, false, false, false, false, false, false, false, false]
]

unsolvable = [
  [false, false, false, false, false, false, false, false, false, false],
  [false,  true,  true,  true,  true,  true,  true,  true,  true, false],
  [false, false, false, false, false, false, false, false, false, false],
  [false,  true,  true,  true,  true,  true,  true,  true,  true, false],
  [false, false, false, false, false, false, false, false, false, false]
]

start  = [1, 1]
finish = [3, 1]

This way, you can simply use if to check whether the path is free or not, since empty tiles are true and walls are false

Here's a neat trick: in Ruby, everything which is not either false or nil is true. This means, you can put everything you want (except false or nil, of course) in there instead of true and the if trick will still work. For example, you can encode the distance information that the algorithm needs directly in the maze itself. Just put some really big number instead of true in there, and 0 into the finish:

infin = 1.0/0.0

solvable = [
  [false, false, false, false, false, false, false, false, false, false],
  [false, infin, infin, infin, infin, infin, infin, infin, infin, false],
  [false, false, false, false, false, false, infin, infin, infin, false],
  [false,   0  , infin, infin, infin, infin, infin, infin, infin, false],
  [false, false, false, false, false, false, false, false, false, false]
]

unsolvable = [
  [false, false, false, false, false, false, false, false, false, false],
  [false, infin, infin, infin, infin, infin, infin, infin, infin, false],
  [false, false, false, false, false, false, false, false, false, false],
  [false,   0  , infin, infin, infin, infin, infin, infin, infin, false],
  [false, false, false, false, false, false, false, false, false, false]
]

start  = [1, 1]
finish = [3, 1]

However, start simple:

maze   = [[0]]
start  = [0, 0]
finish = [0, 0]

maze   = [[0, infin]]
start  = [0, 1]
finish = [0, 0]

maze = [
  [false, false, false],
  [false, infin, false],
  [false,   0  , false],
  [false, false, false]
]
start  = [1, 1]
finish = [2, 1]

maze = [
  [false, false, false],
  [false, infin, false],
  [false, infin, false],
  [false,   0  , false],
  [false, false, false]
]
start  = [1, 1]
finish = [3, 1]