Initial CommitHEADmaster

2 files changed, 197 insertions, 0 deletions

diff --git a/lib/maze.rb b/lib/maze.rb
new file mode 100644
index 0000000..4001bea
--- /dev/null
+++ b/lib/maze.rb
@@ -0,0 +1,63 @@
+class Maze
+  def initialize(w, h, sx = 0, sy = 0, tx = 0, ty = 0)
+    @width = w
+    @height = h
+    @start = [sx, sy]
+    @target = [tx, ty]
+    @blocks = []
+  end
+
+  attr_reader :width, :height, :start, :target
+
+  def generate_random(t = -1)
+    @start = [rand(@width), rand(@height)]
+    @target = [rand(@width), rand(@height)]
+
+    t = rand(100) if t == -1
+    t.times do
+      x = rand(@width)
+      y = rand(@height)
+      w = [rand(5), @width - x].min
+      h = [rand(5), @height - y].min
+      @blocks << [x, y, w, h]
+    end
+
+    @blocks.reject! do |blk|
+      sx = @start[0]
+      sy = @start[1]
+      tx = @target[0]
+      ty = @target[1]
+      bx1 = blk[0]
+      by1 = blk[1]
+      bx2 = blk[0] + blk[2]
+      by2 = blk[1] + blk[3]
+
+      sx >= bx1 && sx < bx2 && sy >= by1 && sy < by2 ||
+      tx >= bx1 && tx < bx2 && ty >= by1 && ty < by2
+    end
+
+    self
+  end
+
+  def blocked(x, y)
+    @blocks.any? do |blk|
+      bx1 = blk[0]
+      by1 = blk[1]
+      bx2 = blk[0] + blk[2]
+      by2 = blk[1] + blk[3]
+
+      x >= bx1 && x < bx2 && y >= by1 && y < by2
+    end
+  end
+
+  def walkable(x,y)
+    !blocked(x,y)
+  end
+
+  def mml
+    "#{@width} #{@height}\n" +
+      "#{@start[0]} #{@start[1]}\n" +
+      "#{@target[0]} #{@target[1]}\n" +
+      @blocks.map{|b| b.join(" ")}.join("\n")
+  end
+end
diff --git a/lib/path.rb b/lib/path.rb
new file mode 100644
index 0000000..365df9c
--- /dev/null
+++ b/lib/path.rb
@@ -0,0 +1,134 @@
+class Node
+  O_cost = 1000
+  D_cost = 1414
+
+  def initialize(x, y, sx, sy, tx, ty, w, h, g = 0, parent = nil)
+    @x = x
+    @y = y
+    @sx = sx
+    @sy = sy
+    @tx = tx
+    @ty = ty
+    @w = w
+    @h = h
+    @g = g
+    @parent = parent
+  end
+
+  attr_reader :x, :y
+  attr_accessor :g, :parent
+
+  def h
+    dx = (@x - @tx).abs
+    dy = (@y - @ty).abs
+
+    if dy > dx then
+      D_cost * dx + (O_cost * (dy - dx))
+    else
+      D_cost * dy + (O_cost * (dx - dy))
+    end
+  end
+
+  def f
+    g + h
+  end
+
+  def start?
+    @x == @sx && @y == @sy
+  end
+
+  def target?
+    @x == @tx && @y == @ty
+  end
+
+  def ==(oth)
+    @x == oth.x && @y == oth.y
+  end
+
+  def neighbours
+    ns = []
+    ns << neighbour(@x-1, @y-1, true ) if @x > 0      && @y > 0
+    ns << neighbour(@x-1, @y  , false) if @x > 0
+    ns << neighbour(@x-1, @y+1, true ) if @x > 0      && @y < (@h-1)
+    ns << neighbour(@x  , @y+1, false) if                @y < (@h-1)
+    ns << neighbour(@x+1, @y+1, true ) if @x < (@w-1) && @y < (@h-1)
+    ns << neighbour(@x+1, @y  , false) if @x < (@w-1)
+    ns << neighbour(@x+1, @y-1, true ) if @x < (@w-1) && @y > 0
+    ns << neighbour(@x  , @y-1, false) if                @y > 0
+    ns
+  end
+
+  private
+  def neighbour(x, y, d)
+    Node.new(x, y, @sx, @sy, @tx, @ty, @w, @h, @g + (d ? D_cost : O_cost), self)
+  end
+end
+
+class Path
+  def initialize(maze)
+    @maze = maze
+    @path = []
+    @pathvalid = false
+  end
+
+  def valid?
+    @pathvalid
+  end
+
+  def generate_astar
+    open = []
+    closed = []
+
+    open << Node.new(@maze.start[0], @maze.start[1],
+                     @maze.start[0], @maze.start[1],
+                     @maze.target[0], @maze.target[1],
+                     @maze.width, @maze.height)
+    loop do
+      break if open.empty?
+
+      open.sort! { |a, b| a.f <=> b.f }
+      current = open.shift
+      closed << current
+
+      if current.target? then
+        n = current.parent
+        until n.start?
+          @path.unshift([n.x, n.y])
+          n = n.parent
+        end
+        @pathvalid = true
+        break
+      end
+
+      current.neighbours.each do |n|
+        next if !traversable(current.x, current.y, n.x, n.y) || closed.include?(n)
+
+        if open.include?(n) then
+          ni = open.index(n)
+          m = open[ni]
+          if n.f < m.f then
+            m.g = n.g
+            m.parent = current
+          end
+        else
+          open << n unless open.include?(n)
+        end
+      end
+    end
+
+    self
+  end
+
+  def traversable(sx, sy, tx, ty)
+    if sx == tx || sy == ty then
+      @maze.walkable(tx, ty)
+    else
+      @maze.walkable(tx, ty) &&
+      (@maze.walkable(sx, ty) || @maze.walkable(tx, sy))
+    end
+  end
+
+  def pml
+    @path.map{|p|p.join(" ")}.join("\n")
+  end
+end