Поиск пути от TheoAllen

#============================================================================== # TheoAllen - A* Pathfinding # Версия : 1.0 # Автор : TheoAllen # Модификация: DeadElf79 # Язык комментариев : русский # Перевод : DeadElf79 # --По ходу скрипта могут встречаться такие комментарии переводчика --эльф #++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ # Контакты : #------------------------------------------------------------------------------ # *> http://www.rpgmakerid.com # *> http://www.rpgmakervxace.net # *> http://www.theolized.com #============================================================================== ($imported ||= {})[:Theo_Pathfinding] = true #=============================================================================== # Список изменений: # ------------------------------------------------------------------------------ # 2015.01.07 - Добавлен поиск пути по правилам A* # - Цикл на карте поддерживает работу скрипта # 2015.01.06 - Релиз # 2014.05.08 - Выпуск прототипа #=============================================================================== =begin ================================= *) Описание : --------------------------------- Данный скрипт позволяет автоматически проложить путь движения для события к игроку или другому событию. ================================= *) Установка : --------------------------------- Просто скопируйте и вставьте скрипт над Main. ---------------------- *) ВЫЗОВ СКРИПТА ---------------------- - find_path(x,y) Ищет путь к координатам, заданным в x и у. Координаты задаются статически (один раз при загрузке карты), для динамического использования... придумайте что-нибудь, автор это не предусмотрел --эльф - goto_event(idORname) Ищет путь к ивенту, имеющему id, равное idORname или имя, равное idORname Примеры: goto_event(12) goto_event("Пётр") - goto_player Ищет путь к игроку, используется для преследования его. ---------------------- *) КОММЕНТАРИЙ В СОБЫТИИ ---------------------- <chase player>. Ищет путь к игроку, используется для преследования его. <stop chase> скрипт </stop chase> Между этими тегами вы можете записать условия, по которым преследование может быть прервано. Не нужно писать конструкции вида if ... then ... end, просто ставьте условия. Смотрите пример, в котором преследования будет прекращено, если игрок вошел в регион карты, помеченный единицей. <stop chase> $game_player.region_id == 1 </stop chase> ================================= *) Предупреждения и ограничения : --------------------------------- Преследования игрока - экспериментальное и может иметь недостатки. Основные недостатки, кстати - невозможность диагонального передвижения (скрипт ищет путь только в четырех направлениях), а также возможные неполадки со скриптами типа Pixel Movement. ================================= *) Правила использования : --------------------------------- Вы можете свободно использовать этот скрипт, переводить его и модифицировать, но, прошу Вас, укажите меня, TheoAllen, и моих соучатсников: gw, ngedit2, ngeklaim а также bebasin, в титрах, пожалуйста. --насчет правильности перевода этого абзаца у меня большие сомнения, --но я совсем не знаю индонезийский, так что это останется тайной --эльф =end #=============================================================================== # На этом описание закончено, переходим к скрипту #=============================================================================== #=============================================================================== # ** Pathfinding Queue #=============================================================================== class Pathfinding_Queue #---------------------------------------------------------------------------- # * Initialize #---------------------------------------------------------------------------- def initialize(tx, ty, first_node) @astar = !$game_map.any_loop? @tx = tx @ty = ty clear @front_queue.push(first_node) @range_cache = {} end #---------------------------------------------------------------------------- # * Range #---------------------------------------------------------------------------- def range(node) unless @range_cache[node] range_x = node.x - @tx range_y = node.y - @ty @range_cache[node] = Math.sqrt((range_x**2) + (range_y**2)) end return @range_cache[node] end #---------------------------------------------------------------------------- # * Push #---------------------------------------------------------------------------- def push(new_node, parent_node) if @astar && range(new_node) < range(parent_node) @front_queue.push(new_node) @front_queue.sort! {|a,b| range(a) <=> range(b)} else @back_queue.push(new_node) end end #---------------------------------------------------------------------------- # * Shift #---------------------------------------------------------------------------- def shift result = @front_queue.shift return result if result return @back_queue.shift end #---------------------------------------------------------------------------- # * Empty #---------------------------------------------------------------------------- def empty? @front_queue.empty? && @back_queue.empty? end #---------------------------------------------------------------------------- # * Clear #---------------------------------------------------------------------------- def clear @front_queue = [] @back_queue = [] end end #=============================================================================== # ** MapNode #=============================================================================== class MapNode #---------------------------------------------------------------------------- # * Public attributes #---------------------------------------------------------------------------- attr_accessor :parent attr_accessor :visited attr_reader :expanded attr_reader :nodes attr_reader :x attr_reader :y #---------------------------------------------------------------------------- # * Initialize #---------------------------------------------------------------------------- def initialize(x,y) @x, @y = x, y @nodes = {} @visited = false @expanded = false end #---------------------------------------------------------------------------- # * Expand node #---------------------------------------------------------------------------- def expand_node(mapnodes, char) dir = [2,4,6,8] dir.each do |d| next unless char.pathfinding_passable?(@x, @y, d) xpos = $game_map.round_x_with_direction(@x, d) ypos = $game_map.round_y_with_direction(@y, d) key = [xpos, ypos] next_node = mapnodes[key] if next_node.nil? next_node = MapNode.new(xpos, ypos) mapnodes[key] = next_node elsif next_node.visited next end next_node.parent = self self.nodes[d] = next_node end @expanded = true end #---------------------------------------------------------------------------- # * Get Parent Direction #---------------------------------------------------------------------------- def get_parent_dir parent.nodes.index(self) end end #=============================================================================== # ** Game_Map #=============================================================================== class Game_Map def any_loop? loop_horizontal? || loop_vertical? end end #=============================================================================== # ** Game_Event # --я добавил это дополнение для писка ивента по имени #=============================================================================== class Game_Event < Game_Character #-------------------------------------------------------------------------- # * Public Instance Variables #-------------------------------------------------------------------------- attr_reader :name #-------------------------------------------------------------------------- # * Object Initialization # event: RPG::Event # --Я не смог сделать алиас для этого метода --эльф #-------------------------------------------------------------------------- def initialize(map_id, event) super() @map_id = map_id @event = event @id = @event.id @name = @event.name moveto(@event.x, @event.y) refresh end end #=============================================================================== # ** Game_Character #=============================================================================== class Game_Character #---------------------------------------------------------------------------- # * Find path (x, y) # Никогда не ставьте clear равным true при использовании # через команду "Задать маршрут" в событии! #---------------------------------------------------------------------------- def find_path(tx, ty, clear = false) return if x == tx && y == ty return unless [2,4,6,8].any? {|dir| passable?(tx, ty, dir)} # Initialize @move_code = nil @mapnodes = {} @target_findx = tx @target_findy = ty # Make first node to check first_node = MapNode.new(self.x, self.y) first_node.expand_node(@mapnodes, self) first_node.visited = true @mapnodes[[self.x, self.y]] = first_node @queue = Pathfinding_Queue.new(tx, ty, first_node) # breadth first seach iteration until @queue.empty? bfsearch(@queue.shift) end # Execute move code if clear unless @move_code process_route_end return end route = RPG::MoveRoute.new route.repeat = false route.list = @move_code force_move_route(route) elsif @move_code mv_list = @move_route.list.clone insert_index = @move_route_index @move_code.each do |li| mv_list.insert(insert_index, li) insert_index += 1 end @move_route.list = mv_list @move_route_index -= 1 end @target_findx = @target_findy = nil end #---------------------------------------------------------------------------- # * Breadth First Search #---------------------------------------------------------------------------- def bfsearch(node) dir = [2,4,6,8] dir.shuffle.each do |d| next_node = node.nodes[d] next unless next_node next if next_node.visited if next_node.x == @target_findx && next_node.y == @target_findy @move_code = generate_route(next_node) @queue.clear return end next_node.expand_node(@mapnodes, self) unless next_node.expanded next_node.visited = true @queue.push(next_node, node) end end #---------------------------------------------------------------------------- # * Generate move command list based on node #---------------------------------------------------------------------------- def generate_route(node) list = [] while node.parent command = RPG::MoveCommand.new command.code = node.get_parent_dir/2 list.unshift(command) node = node.parent end return list end #---------------------------------------------------------------------------- # * Chase character #---------------------------------------------------------------------------- def goto_character(char, clear = false) return unless char find_path(char.x, char.y, clear) end #---------------------------------------------------------------------------- # * Chase player #---------------------------------------------------------------------------- def goto_player(clear = false) goto_character($game_player, clear) end #---------------------------------------------------------------------------- # * Chase event #---------------------------------------------------------------------------- def goto_event(idORname, clear = false) if idORname.is_a? Integer goto_character($game_map.events[idORname], clear) elsif idORname.is_a? String $game_map.events.each_value{|event| puts event.class if event.name==idORname goto_character($game_map.events[event.id], clear) break end } end end #---------------------------------------------------------------------------- # * Target point? #---------------------------------------------------------------------------- def target_point?(x, y) @target_findx == x && @target_findy == y end #---------------------------------------------------------------------------- # * Pathfinding Passable? #---------------------------------------------------------------------------- def pathfinding_passable?(x, y, d) x2 = $game_map.round_x_with_direction(x, d) y2 = $game_map.round_y_with_direction(y, d) if target_point?(x2, y2) return true if @through return map_passable?(x, y, d) && map_passable?(x2, y2, reverse_dir(d)) end passable?(x, y, d) end end #=============================================================================== # ** Game_Event #=============================================================================== class Game_Event #---------------------------------------------------------------------------- # * Regular expression for chase player #---------------------------------------------------------------------------- REGX_ChasePlayer = /<chase[\s_]player>/i REGX_ChaseCondS = /<stop[\s_]chase>/i REGX_ChaseCondE = /<\/stop[\s_]chase>/i #---------------------------------------------------------------------------- # * Alias : Setup page settings #---------------------------------------------------------------------------- alias theo_pathfind_setup_page_settings setup_page_settings def setup_page_settings theo_pathfind_setup_page_settings init_chase_variables return unless @list load = false @list.each do |cmd| next unless [108, 408].include?(cmd.code) case cmd.parameters[0] when REGX_ChasePlayer setup_chase($game_player, 45) when REGX_ChaseCondS load = true @chase_condition = "" next when REGX_ChaseCondE load = false else if load @chase_condition += cmd.parameters[0] end end end end #---------------------------------------------------------------------------- # * Init chase variables #---------------------------------------------------------------------------- def init_chase_variables @target_object = nil @path_refresh_rate = 0 @path_refresh_count = 0 @chase_condition = "false" @player_lastpost = [] end #---------------------------------------------------------------------------- # * Setup chase #---------------------------------------------------------------------------- def setup_chase(char, rate) @target_object = char @path_refresh_rate = rate end #---------------------------------------------------------------------------- # * Alias : Update #---------------------------------------------------------------------------- alias theo_pathfind_update update def update theo_pathfind_update return unless @target_object return if $game_map.interpreter.running? @path_refresh_count -= 1 return if @path_refresh_count > 0 || moving? || playerpos_not_changed? update_pathfinding end #---------------------------------------------------------------------------- # * Update pathfinding #---------------------------------------------------------------------------- def update_pathfinding @path_refresh_count = @path_refresh_rate @player_lastpost = [$game_player.x, $game_player.y] unless eval(@chase_condition) goto_character(@target_object, true) else process_route_end end end #---------------------------------------------------------------------------- # * Player position not changed? #---------------------------------------------------------------------------- def playerpos_not_changed? @player_lastpost == [$game_player.x, $game_player.y] end end