1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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
|
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
|
