# coding: utf-8


# Graph-Klasse zur Generierung von Labyrinthen
# Die Labyrinthe sind Recktecke mit x Spalten und
# y Zeilen
# Von einer Zelle kann potenziell in die vier
# Nachbarszellen gegangen werden.

class Graph
  attr_reader :x,:y,:dirs

  # Grösse des Rechecks (Anzahl Zellen)
  def initialize(x,y)
    @x=x
    @y=y
    
    # Richtungen, trigonometrisch in 90-Grad Schritten
    @dirs = [[1,0], [0,1],[-1,0],[0,-1]]

    # @right[x][y] ist true, wenn von x,y nach x+1,y
    # gegangen werden kann (und umgekehrt).
    @right=Array.new(@x-1) { Array.new(@y, false) }

    # @down[x][y] ist true, wenn von x,y, nach x,y+1
    # gegangen werden kann.
    @down=Array.new(@x) { Array.new(@y-1,false) }

    # Markierungen auf Knoten initialisieren und auf false setzen
    clearMarks

  end
  
  def clearMarks
    @marks = Array.new(@x) { Array.new(@y, false) }
  end

  # True, wenn die Koordinaten im Rechteck sind
  def onBoard(pos)
    return pos[0]>=0 && pos[0]<@x && pos[1]>=0 && pos[1]<@y
  end

  # pos ist ein Array [x,y] mit den Koordinaten
  # dir ist 0,1,2,3, die Richtung in 90-Grad schritten
  # Liefert die verschobene Position zurück
  def move(pos,dir)
    return [pos[0]+@dirs[dir][0],pos[1]+@dirs[dir][1]]
  end

  # Setzt die Knotenmarkierung bei pos=[x,y] auf what
  def setMark(pos, what)
    @marks[pos[0]][pos[1]] = what
  end

  # Lieftert die Knotenmarkierung zurück
  def getMark(pos)
    return @marks[pos[0]][pos[1]]
  end

  # Setzt eine Kante auf what (default true), jene von pos in Richtung dir
  def setEdge(pos, dir, what=true)
    if (dir>1)
      pos = move(pos,dir)
      dir = dir-2
    end
    if dir==0
      @right[pos[0]][pos[1]]=what
    else
      @down[pos[0]][pos[1]]=what
    end
  end

  # Erfragt, ob eine Kante von pos in Richtung dir existiert
  def getEdge(pos,dir)
    if (dir>1)
      pos = move(pos,dir)
      return false unless onBoard(pos)
      dir = dir-2
    end
    return @right[pos[0]][pos[1]] if dir==0
    return @down[pos[0]][pos[1]]
  end

  # Liefert das Labyrinth als ASCII-Art
  def to_s(thick=false)
    unless thick
      res = "+"+"---+"*@x+"\n"
      @y.times{|y|
        res += "| " + (@marks[0][y] ? "X" : " ") + " "
        (@x-1).times{|x|
          res += (@right[x][y] ? " " : "|") + " " + (@marks[x+1][y] ? "X" : " ") + " "
        }
        res += "|\n"
        res += "+"
        if (y<@y-1)
          @x.times{|x|
            res += @down[x][y] ? "   +" : "---+"
          }
          res += "\n"
        else
          res += "---+"*@x+"\n"
        end
      }
      return res
    end
    
    # block="##"
    # ANSI-Terminal Codes
    block=27.chr+"[30;47m  "+(27.chr)+"[0m"
    res = block*(@x*2+1)+"\n"
    @y.times{|y|
      res += block
      (@x-1).times{|x|
        res += "  "+(@right[x][y] ? "  " : block)
      }
      res += "  #{block}\n#{block}"
      if (y<@y-1)
        @x.times{|x|
          res += @down[x][y] ? "  #{block}" : "#{block*2}"
        }
        res += "\n"
      else
        res += block*(@x*2)+"\n"
      end
    }
    return res
  end

  # Generiert das Labyrinth
  # Von einem Startpunkt werden Wege zu allen anderen Punkten bestimmt
  # Die Kanten auf den Wegen werden gesetzt.
  def generate(start=[0,0])
    todo = [start]
    clearMarks
    setMark(start,true)
    counter = 0
    limit = 5+rand(20)
    while todo.size>0
      aktuell = todo.pop  # Entfernt letztes Element
      [0,1,2,3].shuffle.each.with_index{|dir,i|
        nachbar=move(aktuell, dir)
        if onBoard(nachbar) && getMark(nachbar)==false
           setEdge(aktuell, dir)
           setMark(nachbar,true)
           todo.push(nachbar)  # hinten anhängen
           #puts to_s()
           #sleep(0.1)
           counter+=1
           if (counter>limit)
              limit = 5+rand(20)
              todo.shuffle!
              counter=0
           end
           if (i<3)
             todo.unshift(aktuell)  # vorne anhängen
             break  # Aus each-block ausbrechen
           end
        end
      } 
    end
  end
  
  def setVerboten(pos, verboten, what)
      verboten[pos[0]][pos[1]] = what
  end
  
  def getVerboten(pos, verboten)
      return verboten[pos[0]][pos[1]]
  end
  
  def iniVerboten
     return Array.new(@x){Array.new(@y,false)} 
  end
  
  def hasPath?(start, goal, verboten=iniVerboten)
     if start==goal
         setMark(goal,true)
         return true
     end
     setVerboten(start, verboten, true)
     
     4.times{|dir|
        n = move(start, dir)
        if onBoard(n) && getEdge(start, dir) && getVerboten(n,verboten)==false
            if hasPath?(n,goal,verboten)
               setMark(start, true)
               return true
            end   
        end
     }
     setVerboten(start, verboten, false)
     return false
  end
  
end
g = Graph.new(15,11)
g.generate()
g.clearMarks
puts g.to_s(false)
g.hasPath?([0,0], [g.x-1,g.y-1])
puts g.to_s(false)