dijkstra.rb

class MazeSolver

  def initialize(maze)
    @maze_str = maze
    @table = Array.new
    @table_reversed = Array.new
    @nodes = Array.new
    @step = 1
    @start_node = 999
    @table_x = 0
    @table_y = 0
    @unvisited_set = Array.new
    @current_node = 999
    @table_merged = Array.new
    @node_list = Array.new
    parse_maze
    init_nodes
    dijkstra
  end

  # converts the maze string to an array of arrays
  def parse_maze
    node = 0
    @maze_str.strip.split(/[\l|\n\/]/).each do |line|
      puts line
      @row = Array.new
      line.split(/ /).each do |item|
        @row << item
        @nodes << node #append an incremental number for each node
        node = node + 1
      end
      @table << @row
    end
    @table_reversed = @table.reverse #flip table values horizontally

    # search for start node
    x = 0
    y = 0
    z = 0 # will be used as a node number
    @table_reversed.each do |row|
      row.each do |item|
        node = @nodes[z]
        if item == "S"
          @start_node = z
          @current_node = @start_node
        end
        @table_merged << item
        y = y + 1
        z = z + 1
      end
      x = x + 1
      y = 0
    end

    # set table size
    @table_x = @table_reversed[0].size
    @table_y = @table_reversed.size

    # create the unvisited set of nodes but remove walls
    @unvisited_set = @nodes.map { |r| if @table_merged[r] != "X" then r end }
    @unvisited_set.delete(nil)
    # @unvisited_set.delete(@start_node)

    return @table_reversed
  end

  # initializes nodes structure
  def init_nodes

    nodes = []
    previous_node = nil

    # set the current node as the start one
    @current_node = @start_node
    unvisited_set = @unvisited_set.dup

    while unvisited_set.size > 0 do
      @current_node = unvisited_set.shift
      # set values for neighbours
      neighbours = []
      left_node = @current_node - @step
      top_node = @current_node + @table_x
      right_node = @current_node + @step
      bottom_node = @current_node - @table_x

      # check If we are not in the edges
      if left_node > 0 && left_node % 8 != 0 && @table_merged[left_node] != "X"
        neighbours << left_node
      end
      if top_node + 8 < (@table_x * @table_y) && @table_merged[top_node] != "X"
        neighbours << top_node
      end
      if bottom_node - 8 >= 0 && @table_merged[bottom_node] != "X"
        neighbours << bottom_node
      end
      if (right_node + 1) % 8 != 0 && @table_merged[right_node] != "X"
        neighbours << right_node
      end

      # Assign to every node a tentative distance value: set it to zero for
      # our initial node and to infinity for all other nodes
      if @current_node == @start_node
        @distance = 0
      else
        @distance = 1
      end

      # create a hash for current node and append node to a table
      # For the current node, consider all of its unvisited neighbors and
      # calculate their tentative distances. In our current solver
      # all distances of the neighbour nodes are 1
      @node_list << {
        :id => @current_node,
        :neighs => neighbours,
        :dist => @distance,
        :prev => previous_node
      }
    end

    puts "~" * 40
    return @node_list
  end

  def dijkstra

    puts @node_list
    unvisited_set = @unvisited_set.dup

    while unvisited_set.size > 0 do
      # mark the current node as visited and remove it from the unvisited set
      current_node = unvisited_set.shift
      puts current_node

    end

  end

  # prints the reversed table
  def print_table_reverse

    z = 0 # will be used as a node number
    @table_merged.each do |item|
      node = @nodes[z]
      print "#{item} (#{node}) \t"
      z = z + 1
      if z % 8 == 0
        puts
      end
    end

  end


end