diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/maze.rb | 63 | ||||
-rw-r--r-- | lib/path.rb | 134 |
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 |