Class: AStar

Inherits:
Object
  • Object
show all
Defined in:
lib/A_Star.rb

Instance Method Summary collapse

Constructor Details

#initialize(maze, start, dest) ⇒ AStar

Returns a new instance of AStar.



40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/A_Star.rb', line 40

def initialize maze, start, dest
  raise "Either start, end or both locations not found!" if start.empty? || dest.empty?
  @maze = maze
  @start = start
  @dest = dest
  @solvedMaze = @maze
  mazeName = ARGV[ARGV.length - 1]
  @mazeLabel = mazeName.split( /()\s|\./)[0]
  @mazeFileType = "." + mazeName.split(/\s|\./)[1]

  @firstNode = node start[0], start[1], -1, -1, -1, -1 # [x, y, index, cost, heuristic, totalCost]
  @destNode  = node dest[0], dest[1],   -1, -1, -1, -1

  @height       = maze.dimension.height
  @width        = maze.dimension.width
  @perimiter    = (2 * @width) + (2 * @height)
  @area = @width * @height
  @visited = []
  @unvisited  = []
  @visited << @firstNode
end

Instance Method Details

#cost(here, destination) ⇒ Object 



149
150
151
152
153
154
155
 
# File 'lib/A_Star.rb', line 149

def cost here, destination
  direction = direction here, destination
  if [2, 4, 6, 8].include? direction
    return 10
  end
  return 14
end

#direction(here, destination) ⇒ Object 



170
171
172
173
174
175
176
177
178
179
180
181
182
 
# File 'lib/A_Star.rb', line 170

def direction here, destination
  direction = [ destination[1] - here[1], destination[0] - here[0] ]
  return case
    when direction[0] > 0 && direction[1] == 0
      2 # y-negative, down
    when direction[1] < 0 && direction[0] == 0
      4 # x-negative, left
    when direction[0] < 0 && direction[1] == 0
      8 # y-positive, up
    when direction[1] > 0 && direction[0] == 0
      6 # x-positive, right
  end
end

#draw ⇒ Object 



193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/A_Star.rb', line 193

def draw
  puts "Solving..."

  go = Time.new # Start the time
  path = solve # Here we go!
  finish = Time.new # Take the finish time

  unless path.empty?
    puts "\n\nTime taken to solve: " + (finish - go).to_s + " seconds!"
    minutes = ((finish - go) / 60.0).round
    if minutes > 0
      if minutes > 1
        puts "Circa " + minutes.to_s + " Minutes."
      else
        puts "Circa " + minutes.to_s + " Minute."
      end
    end
  else
    puts "No solution found, solve function returned empty array for path!\nPlease make sure your maze is solvable!"
  end

  @solvedMaze.save(@mazeLabel + "-solved" + @mazeFileType)
end

#heuristic(here, destination) ⇒ Object 



145
146
147
 
# File 'lib/A_Star.rb', line 145

def heuristic here, destination
  return ( Math.sqrt( ((here[0] - destination[0]) ** 2) + ((here[1] - destination[1]) ** 2) ) ).floor
end

#lookAround(here) ⇒ Object 



184
185
186
187
188
189
190
191
 
# File 'lib/A_Star.rb', line 184

def lookAround here
  return [
    [here[0], (here[1] + 1)], # y-positive, up
    [here[0], (here[1] - 1)], # y-negative, down
    [(here[0] + 1), here[1]], # x-positive, right
    [(here[0] - 1), here[1]]  # x-negative, left
  ]
end

#passable?(x, y) ⇒ Boolean

Returns:

  • (Boolean) 


157
158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/A_Star.rb', line 157

def passable? x, y
  if (x < 0 || y < 0) || (x > @width - 1 || y > @height - 1)
    return false
  end
  red = ChunkyPNG::Color.r(@maze[x, y])
  green = ChunkyPNG::Color.g(@maze[x, y])
  blue = ChunkyPNG::Color.b(@maze[x, y])
  if red > 255/2 && green > 255/2 && blue > 255/2
    return true
  end
  return false
end

#solve ⇒ Object 



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/A_Star.rb', line 62

def solve

  until @visited.empty? do
    minIndex = 0
    0.upto @visited.length - 1 do |i|
      if @visited[i][5] < @visited[minIndex][5]
        minIndex = i
      end
    end
    chosenNode = minIndex

    here = @visited[chosenNode]

    if here[0] == @destNode[0] && here[1] == @destNode[1]
      path = [@destNode]
      puts "We're here! Final node at: (x: #{here[0]}, y: #{here[1]})"
      until here[2] == -1 do
        here = @unvisited[here[2]]
        path.unshift here
      end
      puts "The entire path from node #{@start} to node #{@dest} are the nodes: \n#{path}"

      hue = 0
      hueCoeff = 360.0 / path.length # when * by path.length (the end of the arr) it would be 360, so one complete rainbow

      (1..path.length).each do |n|
        @solvedMaze[ path[n - 1][0], path[n - 1][1] ] = ChunkyPNG::Color.from_hsl(hue, 1, 0.6)
        hue = (hueCoeff * n).floor # Rainbow!
      end

      return path
    end

    @visited.delete_at chosenNode
    @unvisited << here

    friendNodes = lookAround here
    0.upto friendNodes.length - 1 do |j|
      horizontalFriend = friendNodes[j][0]
      verticalFriend   = friendNodes[j][1]

      if passable? horizontalFriend, verticalFriend || (horizontalFriend == @destNode[0] && verticalFriend == @destNode[1])
        onUnvisited = false
        0.upto @unvisited.length - 1 do |k|
          unvisitedNode = @unvisited[k]
          if horizontalFriend == unvisitedNode[0] && verticalFriend == unvisitedNode[1]
            onUnvisited = true
            break
          end
        end
        next if onUnvisited

        onVisited = false
        0.upto @visited.length - 1 do |k|
          visitedNode = @visited[k]
          if horizontalFriend == visitedNode[0] && verticalFriend == visitedNode[1]
            onVisited = true
            break
          end
        end
        friendHeuristics = Array.new
        for k in 0..friendNodes.length - 1 do
          friendHeuristics << heuristic(friendNodes[k], @dest)
        end
        lowestHeuristic = friendHeuristics.min
        unless onVisited && heuristic(friendNodes[j], @dest) != lowestHeuristic # If you're somwhere new and is fastest
          newNode = node horizontalFriend, verticalFriend, @unvisited.length - 1, -1, -1, -1
          newNode[3] = here[3] + cost(here, newNode)
          newNode[4] = heuristic newNode, @destNode
          newNode[5] = newNode[3] + newNode[4]

          @visited << newNode
          #puts "!! New Node at\n(x: " + horizontalFriend.to_s + ", y: " + verticalFriend.to_s + ")"
          #puts "Destination = " + @destNode[0].to_s + ", " + @destNode[1].to_s
          # Uncoment below to see unvisited nodes!
          #@solvedMaze[horizontalFriend, verticalFriend] = ChunkyPNG::Color.from_hex "#999"
        end
      end
    end
  end
  return []
end