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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
| #==============================================================================
# ** Pathfinder2
#------------------------------------------------------------------------------
# Path finder module. A* Algorithm
#==============================================================================
module Pathfinder
#--------------------------------------------------------------------------
# * Constants
#--------------------------------------------------------------------------
Goal = Struct.new(:x, :y)
ROUTE_MOVE_DOWN = 1
ROUTE_MOVE_LEFT = 2
ROUTE_MOVE_RIGHT = 3
ROUTE_MOVE_UP = 4
#--------------------------------------------------------------------------
# * Definition of a point
#--------------------------------------------------------------------------
class Point
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :x, :y, :g, :h, :f, :parent, :goal
#--------------------------------------------------------------------------
# * Object initialize
#--------------------------------------------------------------------------
def initialize(x, y, p, goal = Goal.new(0,0))
@goal = goal
@x, @y, @parent = x, y, p
self.score(@parent)
end
#--------------------------------------------------------------------------
# * get an Id from the X and Y coord
#--------------------------------------------------------------------------
def id; "#{@x}-#{@y}"; end
#--------------------------------------------------------------------------
# * Calculate score
#--------------------------------------------------------------------------
def score(parent)
if !parent
@g = 0
elsif !@g || @g > parent.g + 1
@g = parent.g + 1
@parent = parent
end
@h = (@x - @goal.x).abs + (@y - @goal.y).abs
@f = @g + @h
end
#--------------------------------------------------------------------------
# * Cast to move_command
#--------------------------------------------------------------------------
def to_move
return nil unless @parent
return RPG::MoveCommand.new(2) if @x < @parent.x
return RPG::MoveCommand.new(3) if @x > @parent.x
return RPG::MoveCommand.new(4) if @y < @parent.y
return RPG::MoveCommand.new(1) if @y > @parent.y
return nil
end
end
#--------------------------------------------------------------------------
# * singleton
#--------------------------------------------------------------------------
extend self
#--------------------------------------------------------------------------
# * Id Generation
#--------------------------------------------------------------------------
def id(x, y); "#{x}-#{y}"; end
#--------------------------------------------------------------------------
# * Check the passability
#--------------------------------------------------------------------------
def passable?(e, x, y, dir, s = false);
if s and e.through
return $game_map.passable?(x, y, dir)
end
e.passable?(x, y, dir)
end
#--------------------------------------------------------------------------
# * Check the terrain tag
#--------------------------------------------------------------------------
def terrain_tag_ok?(x, y, t);
if $game_map.terrain_tag(x, y) == t
return $game_map.terrain_tag(x, y)
end
end
#--------------------------------------------------------------------------
# * Check closed_list
#--------------------------------------------------------------------------
def has_key?(x, y, l)
l.has_key?(id(x, y))
end
#--------------------------------------------------------------------------
# * Create a path
#--------------------------------------------------------------------------
def create_path(goal, event, no_through = false,t)
open_list, closed_list = Hash.new, Hash.new
current = Point.new(event.x, event.y, nil, goal)
open_list[current.id] = current
while !has_key?(goal.x, goal.y, closed_list)&& !open_list.empty?
current = open_list.values.min{|point1, point2|point1.f <=> point2.f}
open_list.delete(current.id)
closed_list[current.id] = current
args = current.x, current.y+1
if terrain_tag_ok?(current.x, current.y, t) && !has_key?(*args, closed_list)
if !has_key?(*args, open_list)
open_list[id(*args)] = Point.new(*args, current, goal)
else
open_list[id(*args)].score(current)
end
end
args = current.x-1, current.y
if terrain_tag_ok?(current.x, current.y,t) && !has_key?(*args, closed_list)
if !has_key?(*args, open_list)
open_list[id(*args)] = Point.new(*args, current, goal)
else
open_list[id(*args)].score(current)
end
end
args = current.x+1, current.y
if terrain_tag_ok?(current.x, current.y, t) && !has_key?(*args, closed_list)
if !has_key?(*args, open_list)
open_list[id(*args)] = Point.new(*args, current, goal)
else
open_list[id(*args)].score(current)
end
end
args = current.x, current.y-1
if terrain_tag_ok?(current.x, current.y, t) && !has_key?(*args, closed_list)
if !has_key?(*args, open_list)
open_list[id(*args)] = Point.new(*args, current, goal)
else
open_list[id(*args)].score(current)
end
end
end
move_route = RPG::MoveRoute.new
if has_key?(goal.x, goal.y, closed_list)
current = closed_list[id(goal.x, goal.y)]
while current
move_command = current.to_move
move_route.list = [move_command] + move_route.list if move_command
current = current.parent
end
end
move_route.skippable = true
move_route.repeat = false
return move_route
end
end |
Chat
