热烈庆祝，SRPG移动范围生成速度问题完美解决！！

寒冷魔王 · 发表于 2015-4-9 19:26:35

加入我们，或者，欢迎回来。

您需要登录才可以下载或查看，没有账号？注册会员

×

本帖最后由寒冷魔王于 2015-4-9 20:52 编辑

大家或许知道，我曾经在这里发布这个脚本的3.0版本：https://rpg.blue/thread-375993-1-1.html
3.0版本的Ruby版本性能虽然大大提升，但是速度方面仍不能满足普遍需要。不得不在某些方面借助C++等高效语言来解决。
今天，我怀着激动的心情，在这里告诉大家，SRPG地图范围生成+寻路在速度方面已经能够普遍地满足需要了！！

如图：
[fold] 捕获29.PNG

从32s到0.2s，

速度提升了100多倍。。。[/fold]
在地图大小500*500（RM中最大的地图大小），移动力为100的情况下，同样的地图，四周畅通（我的算法四周越通畅，计算耗时越长）时，获取可移点和路线所消耗时长如上。（左为4.0，右为3.0）
曾经跟某君做过对比，该君运行同段脚本消耗时长是我的计算机的2倍。也就是说，即使在这种极端条件（大地图，高移动）下，从计算机性能上来讲，计算的所耗时长也并不多。
因此我判断为这段脚本可以满足普遍地需要。（正常情况下，15移动力算是顶多的了。）
4.0与3.0改进的主要地方在于生成可否移动判断和放置判断的地图副本，而3.0版本使用的是线性表的遍历判断。V3与V2相比，改进就在于遍历判断的性能改进。可见遍历判断是影响性能的关键所在。4.0生成副本的想法来源于最近在研究的VA中的地图数据和我所建立的SRPG地图的转换中所考虑的生成副本的方法。通过实际的应用，我发现了3.0的许多功能并不会用到，因此在重写代码时全未加入。4.0和3.0有很多相似的地方，这是因为在重写时我copy了大量3.0的代码。但是因为涉及到了数据结构的变化，因此Map类我是重写了的。
这段代码只是地图处理最核心最关键的部分，如大家所见，我设计了0~6七个数字来表示，并在Data类增加了一个value的实例变量。这是为了以后增加新类型做准备。这段代码只是一个临时版本，我将会在之后对此进行后期的改进。
本人一直在VA上开发SRPG系统，目前这个系统已经有点SRPG的感觉了。我希望在不久的未来，我能亲眼见证这个系统的竣工。
诚邀嘉宾：@myownroc  @taroxd

代码如下：
[fold][pre lang="ruby"]#===================================================================================
# SMRC.rb
# Author    : Chill
# Version : 4.0.0.0  BETA
# Date    : 2015-04-09 to 2015-04-09
# Description: SRPG on Map of Ruby by Chill.
#===================================================================================

module Chill
  # Method
  def max(a,b); return (a>b) ? a : b; end
  def min(a,b); return (a<b) ? a : b; end
  def putError(str); puts(str); exit; end
  # Self Method
  def self.test(&block)
t = Time.new
block.call
return Time.new - t
  end
  def self.copy(cmap)
map = Array.new
cmap.each { |m| map.push(m.clone) }
return map
  end
end

module SRPG

  class Map
include Chill
# Reader
attr_reader :x, :y
# Initialize
def initialize(*args)
   arg = args.first
   if arg.class != Array
      # Create New Map
      @x, @y = args
      @map = Array.new(@x) { Array.new(@y,0) }
   else
      # Create Reference
      @x, @y = arg.size, arg[0].size
      @map = arg
   end
end
# Data
def judgeOut(x, y)
   return x>=@x || y>=@y || x<0 || y<0
end
def judgeError(x, y)
   putError("Error: Point in Map (#{x},#{y}) is Out.") if judgeOut(x,y)
end
def get(x, y)
   return if judgeOut(x,y); return @map[x][y]
end
def set(x, y, e)
   judgeError(x,y); @map[x][y] = e
end
# Method
def prints(maxSize = 20)
   x, y = min(maxSize,@x), min(maxSize,@y)
   y.times { |y| x.times { |x| print @map[x][y]," " }; print "\n" }
end
def clone
   map = Chill.copy(@map)
   return Map.new(map)
end
def create(sym)
   map = Chill.copy(@map)
   case sym
      when :pass
      map.each { |m| m.collect! { |m| Map.property(m).pass } }
      when :put
      map.each { |m| m.collect! { |m| Map.property(m).put } }
   end
end
  end

  class Map
class Data
   attr_reader :pass, :put, :value
   def initialize(pass = 0, put = 0, value = 0)
      @pass, @put, @value = pass, put, value
   end
   def pass?; return @pass!=1; end
   def put?;  return @put==0;  end
end
@@data = {
      0 => Data.new(0,0),  # 0: Bland
      1 => Data.new(0,0),  # 1: Self
      2 => Data.new(0,1),  # 2: Party
      3 => Data.new(1,1),  # 3: Enemy
      4 => Data.new(1,1),  # 4: Barrier
      5 => Data.new(2,0),  # 5: Hinder (Change Move : Up or Down)
      6 => Data.new(1,1) # 6: Move Range
}
def self.property(id)
   return ((0..5).include?(id)) ? @@data[id] : @@data[4]
end
  end

  class Route
include Chill
# Const Variable
MaxMoves = 500
# Reader
attr_reader :routes,:points
def initialize(map,position)
   # Set Reference of Map, To Clone this Map, Using 'clone' Method.
   @map = map
   # Set Position to save time, Each Actor with a single Instance.
   @position = position.clone
   @map.judgeError(*@position)
end
# Search
def search(moves)
   # Record Moves
   @moves = min(MaxMoves,moves)
   putError("We Don't Have a Right Value of Moves.") if @moves < 0
   # Create Arrays
   @routes = Array.new(@moves+1) { Array.new }
   @points = Array.new
   # Create Map
   @mapPass = @map.create(:pass)
   # Start Search
   fsearch
   nsearchs(@moves)
end
def fsearch
   # Create Refence
   routes = @routes[0]
   # Push Data
   routes.push [@position.clone,Array.new,put?(*@position)]
   @points.push @position.clone
   setPass(*@position)
end
def nsearch(move)
   # Create Refence
   routes = @routes[move]
   # Push Data
   @routes[move-1].each do |data|
      1.upto(4) do |d|
      point = dirMove(d,data[0])
      if (pass?(*point))
         routes.push [point,data[1]+[d],put?(*point)]
         @points.push point
         setPass(*point)
      end
      end
   end
end
def nsearchs(a, b = nil)
   a,b = 1,a if b.nil?
   a.upto(b) { |m| nsearch(m); break if @routes[m].empty? }
end
# Search Method
def dirMove(direction, point)
   x,y = point
   case direction
      when 0; [x, y]
      when 1; [x, y-1]
      when 2; [x, y+1]
      when 3; [x-1, y]
      when 4; [x+1, y]
   end
end
def setPass(x, y)
   @mapPass[x][y] = 1
end
def pass?(x, y)
   return false if @map.judgeOut(x,y)
   return @mapPass[x][y] != 1
end
def put?(x, y)
   return Map.property(@map.get(x,y)).put?
end
  end
end

module SRPG
  # TEST
  map = SRPG::Map.new(500,500)
  [[[4,5],3],[[3,7],3],[[5,6],3],[[4,7],4]].each { |data| map.set(*data[0],data[1]) }
  route = Route.new(map,[250,250])
  time = Chill.test{ route.search(100) }
  map.prints(10)
  p route.points.size
  p time
end[/pre][/fold]