【SRPG地图移动范围生成】 SMRC Ver5.1 | 附 XP VX控制台输出方法

寒冷魔王

经过一个多月的书写、测试，SMRC V5终于可以发布。
SMRC是处理SRPG地图移动范围生成的代码，是SRPG地图的核心代码。使用纯Ruby构建。
V5版本是V4的进化版本。经过重构，性能、功能和质量全面提升。
高性能、精简
经过V4的性能提升后，V4相对V3提升了100倍，而V5又在此基础上提升3-4倍。同时，V5遵循着最小代码的准则，其核心代码只有几十行。
功能升级、使用方便
V5的Map类传入一个一维数组，而不是以往的只能通过直接构造；
Route类传入移动力消耗地图，因此V5的具有很大的灵活性，使用者可以方便的修改以达到使用目的。
V5原生支持阻碍（移动力-1）和ZOC（只能放置不能通过），如下的测试代码中显示了这一点。
稳定、能够满足基本需要
自第一版于2014年10月构建以来，SMRC经历了许多次变革，性能和质量不断提升。无数次的测试，SMRC质量有着可靠的保证。
SMRC在V4版本就已经能够满足基本需要。500*500的地图，空地图（最坏情况），移动力100时，在RMVA下的运行结果V4需要0.25s，而V5仅需0.08s。
而同时附加的两种新形态，使得SMRC能够普遍地满足大多数人的需要。SMRC的时代即将来临。
兼容RGSS1-3
由于是Ruby书写的代码，故其具有很强的兼容性。
目前已在XP、VX、VA下测试通过。测试如图【RGSS1-3三版速度比较（移动力100）】。
由于Ruby1.8与1.9的区别，所以部分Ruby方法无法调用，但本代码本身是兼容的。
定制自由
本代码不仅仅适用于默认的4方向，还可以通过定制轻松实现6方向、8方向。
可以自由变更所想要的形状，只需变更79-82行judgeSet即可。默认形状见3L，变更形状见9L。

P.S.关于具体的原理如果大家有兴趣日后本人会写出来。
下面贴代码：

[fold=SMRC主体 （基本代码）][pre lang="ruby"]#==============================================================================
# SMRC.rb
# Author     : Chill
# Version    : 5.1.7.0  BETA
# Date(V5)   : 2015-06-20 to 2015-07-30
# Description: SRPG on Map of Ruby by Chill.
#==============================================================================

#=================================================
# Basic Method
#=================================================

module SRPG
  #----------------------------------------------------------------------------
  # Class Map
  #----------------------------------------------------------------------------
  class Map
    # Reader
    attr_reader :x, :y
    # Initialize
    def initialize(x, y, data = nil)
      @x, @y = x, y
      # There is Setting Reference.
      @data = data.is_a?(Array) ? data : Array.new(x*y,data)
    end

    # Data Method
    # Unsafe
    def get(x, y)
      @data[y*@x+x]
    end
    def set(x, y, inc)
      @data[y*@x+x] = inc
    end
    # Check
    def out?(x, y)
      x>=@x || y>=@y || x<0 || y<0
    end
  end

  #----------------------------------------------------------------------------
  # Class Route
  #----------------------------------------------------------------------------
  class Route
    # Const Variable
    MaxMoves = 500
    # Data Struct
    Route_Way  = Struct.new(:x, :y, :way)
    Route_Data = Struct.new(:x, :y, :move)
    # Reader
    attr_reader :movmap, :waymap
    # Initialize
    def initialize(map, x, y)
      # Set Reference of Map, To Clone this Map, Using 'clone' Method.
      @map = map
      # Set Position to save time, Each Actor with a single Instance.
      putError("Error: Position(#{x},#{y}) was Out.") if (@map.out?(x,y))
      @position = [x, y]
      # Set Route Map.
      @movmap = Map.new(map.x,map.y,MaxMoves + 1)
      @waymap = Map.new(map.x,map.y)
    end

    # Search
    def search(moves)
      # Record Moves
      @moves = (moves < MaxMoves) ? moves : MaxMoves
      putError("We Don't Have a Right Value of Moves.") if (@moves < 0)
      # Create Arrays
      @record = Array.new
      # Set Data
      x, y = *@position
      setData(x,y,x,y,0,0)
      # Start Search
      @record.each do |route|
        x, y = route.x, route.y
        move = route.move + @map.get(x,y)  # Current Point
        next if (move > @moves)
        # judgeSet
        judgeSet(x, y-1, x, y, move, 1)  # Up
        judgeSet(x, y+1, x, y, move, 2)  # Down
        judgeSet(x-1, y, x, y, move, 3)  # Left
        judgeSet(x+1, y, x, y, move, 4)  # Right
      end
    end

    private
    # Private Method
    def judgeSet(x, y, rx, ry, move, dir)
      return if (@map.out?(x,y) || move >= @movmap.get(x,y) || @map.get(x,y).zero?)
      setData(x,y,rx,ry,move,dir)
    end
    def setData(x, y, rx, ry, move, way)
      @movmap.set(x,y,move)
      @waymap.set(x,y,Route_Way.new(rx,ry,way))
      @record.push(Route_Data.new(x,y,move))
    end
  end
end

[/pre][/fold]
[fold=功能代码][pre lang="ruby"]#=================================================
# Function Method
#=================================================

class SRPG::Map
  include Enumerable
  # Const Variable
  MaxShowSize = 20
  # Data Method
  # Safe
  def [](x, y)
    judgeOut(x,y) ? nil : get(x,y)
  end
  def []=(x, y, inc)
    judgeError(x,y); set(x,y,inc)
  end
  # Create & Copy
  def clone
    SRPG::Map.new(@x,@y,@data.clone)
  end
  def new
    SRPG::Map.new(@x,@y,@data.collect{|a|yield(a)})
  end
  # Enumerable Basic
  def each
    @data.each { |a| yield(a) }; self
  end
  def each_index
    @y.times { |y| @x.times { |x| yield(x,y) } }; self
  end
  private
  # Judge Method
  def judgeOut(x, y)
    out?(x,y)
  end
  def judgeError(x, y)
    putError("Error: Point in Map (#{x},#{y}) is Out.") if judgeOut(x,y)
  end
end

class SRPG::Route
  # Data Method
  def getPath(x, y)
    return if @waymap[x,y].nil?
    way = @waymap.get(x,y)
    x, y, w = way.x, way.y, way.way
    ways = Array.new
    until w.zero?
      ways.push(w)
      way = @waymap.get(x,y)
      x, y, w = way.x, way.y, way.way
    end
    return ways.reverse
  end
  def getPoints
    return @points if defined?(@points)
    @points = Array.new
    @movmap.each_index do |x,y|
      e = @movmap.get(x,y)
      @points.push([x,y]) if e >= 0 && e <= MaxMoves
    end
    return @points
  end
  def points_each
    if defined?(@points)
      @points.each { |p| yield(*p) }
      return self
    end
    @movmap.each_index do |x,y|
      e = @movmap.get(x,y)
      yield(x,y) if e <= MaxMoves && e >= 0
    end
    return self
  end
end

# Using in TEST
module SRPG
  class Map
    # Print
    def printt
      mX, mY = [@x,MaxShowSize].min, [@y,MaxShowSize].min
      mY.times { |y| mX.times { |x| yield(x,y) }; print("\n") }
    end
    def prints
      printt { |x,y| print(self.get(x,y),' ') }
    end
  end
  class Route::Route_Way
    def to_s
      "[#{x}, #{y}],#{way}"
    end
  end
  def self.prints(map)  # Using in prints for passmap, movmap & waymap
    map.printt do |x,y|
      tmp = map.get(x,y)
      if (tmp.nil?)   # waymap
        print('[X, X],- ')
      else
        print(((tmp == Route::MaxMoves + 1) ? 'x' : tmp),' ')
      end
    end
  end
end[/pre][/fold]
[fold=测试代码][pre lang="ruby"]#=================================================
# Testing Code
#=================================================

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(msg); puts(msg); exit; end
  # Self Method
  def self.test
    t = Time.new
    yield
    Time.new - t
  end
end

module SRPG
  #---------------------------------
  # Set
  # Set Data for Test.
  #---------------------------------
  # Only Using in the Convert.
  M = Route::MaxMoves + 1
  MapData = [
      [ 1,  true  ],  # 0: Bland
      [ 1,  true  ],  # 1: Self
      [ 1,  false ],  # 2: Party
      [ 0,  false ],  # 3: Enemy
      [ 0,  false ],  # 4: Barrier
      [ 2,  true  ],  # 5: Hinder
      [ M,  true  ],  # 6: ZOC
      [ 0,  false ]   # 7: Other
  ]
  #---------------------------------
  # Test 1
  # Test class Map & class Route.
  #---------------------------------
  puts("\nTest 1:")
  # Pass One Dimensional Array.
  # Set Data.
  data = [
      [0,0,0],
      [0,5,0],
      [0,0,1],
  ].flatten
  map = Map.new(3,3,data)
  puts('realmap:')
  map.prints
  # Convert Map to Pass Map.
  map = map.new { |e| MapData[e][0] }
  # Or:
  # data.collect! { |e| MapData[e][0] }
  # map = Map.new(3,3,data)
  route = Route.new(map,2,2)
  route.search(3)
  # Print the Pass Map
    puts('passmap:')
    prints(map)
  # Print the Move Map
    puts('movmap:')
    prints(route.movmap)
  # Print the Way Map
    puts('waymap:')
    prints(route.waymap)
  #---------------------------------
  # Test 2
  # Test Correct Move.
  #---------------------------------
  puts("\nTest 2:")
  data = [
      [0,0,5],
      [4,0,5],
      [4,1,0],
  ].flatten.collect { |e| MapData[e][0] }
  map = Map.new(3,3,data)
  route = Route.new(map,1,2)
  route.search(6)
  path = route.getPath(0,0)
  # Print
    puts('passmap:')
    prints(map)
    puts('movmap:')
    prints(route.movmap)
    puts('waymap:')
    prints(route.waymap)
    print(path,"\n")
  #---------------------------------
  # Test 3
  # Test Correct Move 2.
  #---------------------------------
  puts("\nTest 3:")
  data = [
      [0,0,0],
      [0,4,5],
      [0,0,1],
  ].flatten.collect { |e| MapData[e][0] }
  map = Map.new(3,3,data)
  route = Route.new(map,2,2)
  route.search(5)
  # Print
    puts('passmap:')
    prints(map)
    puts('movmap:')
    prints(route.movmap)
    puts('waymap:')
    prints(route.waymap)
  #---------------------------------
  # Test 4
  # Test Correct Move 3. ZOC.
  #---------------------------------
  puts("\nTest 4:")
  data = [
      [0,6,0,0],
      [6,3,6,0],
      [0,6,1,0],
  ].flatten.collect { |e| MapData[e][0] }
  map = Map.new(4,3,data)
  route = Route.new(map,2,2)
  route.search(6)
  # Print
    puts('passmap:')
    prints(map)
    puts('movmap:')
    prints(route.movmap)
    puts('waymap:')
    prints(route.waymap)
  #---------------------------------
  # Test 5
  # Test Speed.
  #---------------------------------
  puts("\nTest 5:")
  x, y = 500, 500
  route = Route.new(Map.new(x,y,1),*[250,250])
  puts Chill.test { route.search(100) }
  puts route.getPoints.size
end
[/pre][/fold]
[fold=运行结果：] [/fold]
【2015.08.03补充】
[fold=RGSS1-3三版速度比较（移动力100）] [/fold]


历史版本：
V4:  https://rpg.blue/thread-378114-1-1.html
V3:  https://rpg.blue/thread-375993-1-1.html
V2:  https://rpg.blue/thread-374090-1-1.html

{:2_255:} 顺便庆祝GCC 5.1的发布





【2015.7.30补充】
关于在XP和VX的控制台问题，刚刚在VX测试的时候将它顺便解决了，如下：
[pre lang="ruby"]Win32API.new('kernel32', 'AllocConsole', 'v', 'v').call
$stdout = open('CONOUT$', 'w')
$stdin  = open('CONIN$')

def print(*args)
  $stdout.print(*args)
  $stdout.flush
  return
end
def puts(*args)
  $stdout.puts(*args)
  $stdout.flush
  return
end
def p(*args)
  puts args.map{|x| x.inspect}
  return args
end
def gets(*args)
  $stdin.gets(*args)
end
def printf(*args)
  $stdout.printf(*args)
  $stdout.flush
  return
end
[/pre]

寒冷魔王

路路 发表于 2015-7-24 09:57
没有看代码，范围的形状是什么？

十字形，以点为中心，上下左右四周扩散。

如图，上面是传入的移动力消耗地图，下面是生成的结果地图。

代码：[pre lang="ruby"]  map = Map.new(10,10,1)
  route = Route.new(map,*[5,5])
  route.search(3)
  prints(map);puts
  prints(route.movmap)[/pre]

移动力消耗地图表示在当前点移动时消耗的移动力（增加的移动步数）。
对于空地图来说，每一个点的移动力消耗均为1。
我们可以通过设定将某一个点变为其他值，用以表示阻碍。
表示0为不能到达此处的点，正数为可以到达此处但是移动后会消耗一定移动力；ZOC由于消耗移动力过大(为最大允许移动力Route::MaxMoves+1)，所以导致能到达此处不能继续通行。（关于负数的情况由于比较复杂将在后续版本研究）
我们假定起始消耗移动力为0，他的移动力为3，那么他最多消耗3点移动力。
因此会出现如图情况。

移动力消耗地图我们是可以手动更改的。
比如我们获取了某地图的地图分布情况。
data = [
  [0,0,0,0,0],
  [0,0,3,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,1,0,0],
].faltten

其中3表示敌人，我们需要在3的上下左右点设置为ZOC。由于Map传递的是引用，想要更改data，这种时候只需方便的调用Map书写：
[pre lang="ruby"]  data = [
    [0,0,0,0,0],
    [0,0,3,0,0],
    [0,0,0,0,0],
    [0,0,0,0,0],
    [0,0,1,0,0],
  ].flatten
  map = Map.new(5,5,data)
  map[2,0] = 6  // 在外面建议使用比较安全的[x,y]方法，而不是get(x,y)
  map[1,1] = 6
  map[3,1] = 6
  map[2,2] = 6
  p data[/pre]
我们可以看到data被完美地更改了。

关于支持的形状，SMRC允许地图分割。
[pre lang="ruby"]data = [
    [0,0,0,0,0],
    [0,0,3,0,0],
    [0,0,0,0,0],
    [0,0,0,0,0],
    [0,0,1,0,0],
  ].flatten[/pre]
如图地图，我们的1左面和右面希望是不同的，两个有着不同的移动力
只需分来，设置为不可移动即可。
[pre lang="ruby"]data1 = [
    [0,0,0,4,4],
    [0,0,3,4,4],
    [0,0,0,4,4],
    [0,0,0,4,4],
    [0,0,1,4,4],
  ].flatten
data2 = [
    [4,4,4,0,0],
    [4,4,4,0,0],
    [4,4,4,0,0],
    [4,4,4,0,0],
    [4,4,1,0,0],
  ].flatten
[/pre]
分别传给Route，然后将两个运算结果合并就行了。

由于传入参数为数组，我们可以方便地修改Ruby中便利的Array以达到修改数据的目的。
同时，由于传入为引用，我们可以方便地利用Map修改这一数据。

墨凌羽

有没有障碍判断？支不支持其他形状？以及二次配布是否允许？

寒冷魔王

墨凌羽 发表于 2015-7-24 13:20
有没有障碍判断？支不支持其他形状？以及二次配布是否允许？

关于障碍，只要将移动力消耗地图设置为0即可。（或者测试代码的待转化地图设为4）
地图形状是可以更改的。至于移动形状的话，利用分割差不多也可以？（表示实在不懂其他形状是何意思）

二次配布的话，本人希望能够保留作者信息及更新网址，因为如您所见，本版本只是一个BETA版。
如果出现BUG及版本变更的情况，本人希望使用者能够及时修改及更新。

刺夜之枪

XP 可以用吗

寒冷魔王

刺夜之枪 发表于 2015-7-25 22:18
XP 可以用吗

虽然SMRC是用纯Ruby写的，理论上RGSS三版均可以，但是目前只在VA上测试过。
XP和VX对Ruby的支持度不是很好。修改一下或许可以。

寒冷魔王

路路 发表于 2015-7-24 09:57
没有看代码，范围的形状是什么？

SMRC不仅可以默认支持4方位，还可以支持其他多种方位（刚刚才发现）
通过变更79-82行实现：

6方位
[fold]

[pre lang="ruby"]                judgeSet(x-1, y-1, x, y, move, 1)
                judgeSet(x+1, y-1, x, y, move, 2)
                judgeSet(x+2, y, x, y, move, 3)
                judgeSet(x+1, y+1, x, y, move, 4)
                judgeSet(x-1, y+1, x, y, move, 5)
                judgeSet(x-2, y, x, y, move, 6)[/pre][/fold]

正方形
[fold]

[pre lang="ruby"]                 judgeSet(x-1, y-1, x, y, move, 1)
                judgeSet(x+1, y-1, x, y, move, 2)
                judgeSet(x+1, y, x, y, move, 3)
                judgeSet(x+1, y+1, x, y, move, 4)
                judgeSet(x-1, y+1, x, y, move, 5)
                judgeSet(x-1, y, x, y, move, 6)
                judgeSet(x, y-1, x, y, move, 7)
                judgeSet(x, y+1, x, y, move, 8)[/pre][/fold]

基本上只要是有规律的形状，都可以实现

mxymxy

算法是没问题的，但是500x500的空地图其实并不是最坏情况，你可以试试这个：
[pre lang="ruby"]
  #---------------------------------
  # Test 6
  # Test Network.
  #---------------------------------
  puts("\nTest 6:")
  x = 500
  y = 500
  steps = 350
  map = Map.new(x, y, 0)
  (0...x).each{ |i|
    (0...y).each { |j|
      map[i, j] = (i % 4 == 3) ? 7 : 1 if j % 4 == 2
      map[i, j] = (i % 4 == 1) ? 7 : 1 if j % 4 == 0
      map[i, j] = (i % 2 == 1) ? 0 : 1 if j % 2 == 1
    }
  }
  route = Route.new(map,0,0)
  puts Chill.test { route.search(steps) }
  puts route.getPoints.size
[/pre]
SPFA算法经过每个点不止一次，因此复杂度不可估计。