SRPG on Map 地图处理代码测试

寒冷魔王

SRPG on Map
地图处理，用于角色在面向多位元素的路线巡查。
经过一个多月的编写和算法优化，目前发布V2版的公测版。
我是使用的多维数组来处理和保存数据。
数据输出基元数组【【点】，【路线】，【可否放置】】
其中路线用1234来表示，转化RM请自行Input::。
由于Ruby对数组的处理极度低效，Path类的get_path仅仅多循环10次（扩大移动10）。为了弥补这一问题，我将相同的算法用Java实现（= =可怜我这个菜鸟不知道要怎么调用）
这不是一个长距离寻路的算法，仅仅提供在密集位置的移动的可能性。刚好看见R君写的Dijkstra算法RM寻路程序，就用他的吧~
目前只是测试版，由于长时间的开发及频繁地变更，程序内部可能会出现一定的错误。还望大家指出。
另外，本版本是V2的完结版，不会考虑算法的变更。如果涉及程序数据结构的大幅度变更还请跳过该版本。
另外我只学了几天的Java，请不要对Java版提出高级的问题。。


[fold=Ruby版][pre lang="ruby" line="1"]#################################################################
# SMRC.rb
# Author     : Chill
# Version    : 2.4.3.2  Beta
# Date       : 2014-10-08 to 2014-11-24
# Description: SRPG on Map of Ruby by Chill
#################################################################
module SRPG
#================================================================
# Class Map
#----------------------------------------------------------------
# Print a map as 10*10 include 0,1,2,3,4.
#================================================================
class Map
  attr_accessor :map
  attr_reader  :x,:y
  #--------------------------------------------------------------
  # Initialize
  #--------------------------------------------------------------
  def initialize(x=10,y=10)
    @x,@y = x,y
    @map = Array.new(x) {Array.new(y,0)}
    return
  end
  #--------------------------------------------------------------
  # Data
  #--------------------------------------------------------------
  @@dat = Array.new
  class << @@dat
    def set(id,dat); @@dat[id]=dat; end
  end
  @@dat.set(0,[0,0]) # Bland
  @@dat.set(1,[0,0]) # Self
  @@dat.set(2,[0,1]) # Party
  @@dat.set(3,[1,1]) # Enemy
  @@dat.set(4,[1,1]) # Disorder
  class << self
    def data; @@dat; end
    def data=(value); @@dat=value; end
    def property(symbol)
      if (0..4).include?(symbol)
        return @@dat[symbol]
      else   # Other
        return [1,1]
      end
    end
    def transform(symbol)
      case symbol
      when 1; 3
      when 2; 3
      when 3; 2
      else;  symbol
      end
    end
  end
  #--------------------------------------------------------------
  # Method
  #--------------------------------------------------------------
  def point(*p)
    x,y = p
    return if x<0||y<0||x>=@x||y>=@y
    return @map[x][y]
  end
  def prints(x=@x,y=@y)
    x = @x if x>@x; y = @y if y>@y
    rx = 0...x; ry = 0...y
    ry.each{|y| rx.each{|x| print @map[x][y],","}; print "\n"}
    return
  end
end
#================================================================
# Class Route
#----------------------------------------------------------------
# The basic of geting path.
#================================================================
class Route
  attr_reader  :map
  #--------------------------------------------------------------
  # Initialize
  #--------------------------------------------------------------
  def initialize(*p)
    @map = Map.new(*p)
    return
  end
  #--------------------------------------------------------------
  # Data
  #--------------------------------------------------------------
  def point(*p); @map.point(*p); end
  def position(*p)
    x,y = p
    if x && y
      @position = [x,y]
      @map.map[x][y] = 1
    end
    return @position
  end
  #--------------------------------------------------------------
  # Search
  #--------------------------------------------------------------
  def search(move)
    @pots = [position]
    @route = Array.new
    @route[0] = [[position,[],true]]
    return @route if move<1
    @route[1] = fsearch
    return @route if move<2
    nsearchs(2,move)
    return @route
  end
  def fsearch
    route = Array.new
    1.upto(4) do |i|
      p = dirmove(i,position)
      if pass?(*p)
        route.push [p,,put?(*p)]
        @pots.push p
      end
     end
    return route
  end
  def nsearch(m)
    @pots ||= Array.new
    dat = @route[m-1]
    dat ||= []
    return [] if dat.empty?
    route = Array.new
    dat.each do |d|
      1.upto(4) do |i|
        p = d[0].clone
        r = d[1].clone
        r.push i
        p = dirmove(i,p)
        next if @pots.include?(p)
        if pass?(*p)
          route.push [p,r,put?(*p)]
          @pots.push p
        end
      end
    end
    return route
  end
  def nsearchs(a,b)
    a.upto(b) do |i|
      break if @route[i-1].empty?
      @route = nsearch(i)
    end
    return
  end
  #--------------------------------------------------------------
  # Search Methed
  #--------------------------------------------------------------
  def dirmove(dir,p,m=1)
    x,y = p
    return case dir
    when 0; [x,y]
    when 1; [x,y-m]
    when 2; [x,y+m]
    when 3; [x-m,y]
    when 4; [x+m,y]
    end
  end
  def pass?(*p)
    Map.property(point(*p))[0] == 0
  end
  def put?(*p)
    Map.property(point(*p))[1] == 0
  end
  #--------------------------------------------------------------
  # Methed
  #--------------------------------------------------------------
  def min(a,b); a<b ? a : b; end
  def max(a,b); a>b ? a : b; end
  def recpoint(dat=@route,m=nil)
    dat = m ? dat[m] : dat.flatten(1)
    return if dat.nil?
    dat.compact!
    dat.delete([])
    pots = Array.new
    dat.each{|d| pots.push d.first}
    return pots
  end
  def recrange; return @pots; end
  def judge(dat)
    p = position; r = true
    dat.each do |i|
      if pass?(*p)
        p = dirmove(i,p)
      else
        r = put?(*p); break
      end
    end
    return p,r
  end
  def distance(a,b,k=0)
    dicx = a[0]-b[0]
    dicy = a[1]-b[1]
    return case k
    when 0;  dicx.abs+dicy.abs
    when 1;  dicx.abs
    when 2;  dicy.abs
    when -1; dicx
    when -2; dicy
    end
  end
  def range(move)
    x,y = position
    pot = Array.new
    (-move).upto(move) do |dicy|
      dic = move - dicy.abs
      (-dic).upto(dic) do |dicx|
        pp = [x+dicx,y+dicy]
        po = point(*pp)
        pot.push [pp,po] if po
      end
    end
    return pot
  end
end
#================================================================
# Class Path
#----------------------------------------------------------------
# Give some methods to deal with data.
#================================================================
class Path < Route
  #--------------------------------------------------------------
  # Initialize
  #--------------------------------------------------------------
  def initialize(*p)
    super(*p)
    @targets = Array.new
    return
  end
  #--------------------------------------------------------------
  # Set_Data
  #--------------------------------------------------------------
  def set_map(*arg)
    arg = arg.flatten.compact
    return if arg.size<3
    x,y,i = arg
    return if x<0||y<0 || x>map.x-1||y>map.y-1 || i<0
    map.map[x][y] = i
    return
  end
  def set_maps(*arg)
    arg.flatten!(1) if arg.size==1
    arg = [arg] if arg.size!=1 && arg[1].class!=Array
    arg.each{|a| set_map(a)}
    return
  end
  def set_position(*arg)
    position(*arg)
    return
  end
  def set_element(pot,e)
    pot = [pot] if pot[0].class!=Arry
    pot.each{|p| set_map(p,e)}
    return
  end
  def set_target(*arg)
    arg.flatten!(1) if arg.size==1
    arg = [arg] if arg.size!=1 && arg[1].class!=Array
    arg.each{|a| @targets.push a}
    return
  end

  #--------------------------------------------------------------
  # Get_Data
  #--------------------------------------------------------------
  def get_position
    return position
  end
  def get_search(move=nil)
    return @search if move.nil?
    return @search = search(move) if @search.nil?
    if @search.size > move
      return @search[0,move+1]
    else
      nsearchs(@search.size,move)
      return @search
    end
  end
  def get_asearch(m,move=nil)
    get_search(move)
    return @search[m]
  end
  def get_points(move=nil)
    get_search(move)
    return @pots
  end
  def get_point(m=nil,move=nil)
    get_points(move) if m.nil?
    get_search(move)
    return recpoint(@search,m)
  end
  def get_route(*point)
    point.flatten!
    d = distance(position,point)
    return if @search.nil?
        return if !@pots.include?(point)
    s = @search.size
    return if d >= s
    @search.last(s-d).each do |s|
      break if s.nil?||s.empty?
      s.each {|d| return d[1] if point==d[0]}
    end
    return
  end
  def get_target(k=nil)
    return k ? @target.last : @target
  end
  def get_path(*point)
    point.flatten!
    r = get_route(*point)
    return r if r
        return if @search.nil?
    m = @search.size
    10.times do |i|
      get_search(m+i)
      r = get_route(*point)
      return r if r
    end
    return
  end
end
end

time=Time.new
test = SRPG::Path.new
mod=[[[4,5],3],[[3,7],3],[[5,6],3],[[4,7],4]]
test.set_maps(mod)
test.set_position(5,5)
test.map.prints(10,10)
test.get_search(10)
p test.get_points
p test.get_path(0,0)
p Time.new-time
[/pre]   [/fold]

[fold=Java版][pre lang="java" line="1" file="Main.java"]///////////////////////////////////////////////////////////////
// Main.java
// Aurhor      : Chill
// Version     : 1.1.1.7  Beta
// Date        : 2014-11-25 to 2014-11-27
// Description : SRPG on Map of Java by Chill
///////////////////////////////////////////////////////////////
import java.util.*;
public class Main
{
        public static void main(String[] args)
        {
                Map.initialize();
                Path test = new Path(100,100);
                int[][] mods = {{4,5,3},{3,7,3},{5,6,3},{4,7,4}};
                test.setMaps(mods);
                test.setPosition(5,5);
                test.getSearch(100);
                puts(test.getRPotSize());
                puts(test.getRPots(),test.getRPotSize());
        }
        
        static void puts()
        {
                System.out.println();
        }
        static void print(Object o)
        {
                System.out.print(o);
        }
        static void puts(Object o)
        {
                System.out.println(o);
        }
        static void print(boolean b)
        {
                System.out.print(b);
        }
        static void puts(boolean b)
        {
                System.out.println(b);
        }
        static void print(int[] a)
        {
                System.out.print(Arrays.toString(a));
        }
        static void puts(int[] a)
        {
                print(a);
                puts();
        }

        static void print(int[][] a)
        {
                if(a==null)
                {
                        print("null");
                        return;
                }
                print("[");
                print(a[0]);
                for(int i=1;i<a.length;i++)
                {
                        print(", ");
                        print(a);
                }
                print("]");
        }
        static void print(int[][] a,int s)
        {
                if(a==null)
                {
                        print("null");
                        return;
                }
                print("[");
                print(a[0]);
                for(int i=1;i<s;i++)
                {
                        print(", ");
                        print(a);
                }
                print("]");
        }
        static void puts(int[][] a)
        {
                print(a);
                puts();
        }
        static void puts(int[][] a,int s)
        {
                print(a,s);
                puts();
        }
        static void print(int[][][] a)
        {
                print("[");
                for(int i=0;i<a.length-1;i++)
                {
                        if(a==null)
                                print("null, ");
                        else
                        {
                                print(a);
                                print(", ");
                        }
                }
                if(a[a.length-1]==null)
                        print("null");
                else
                        print(a[a.length-1]);
                print("]");
        }
        static void puts(int[][][] a)
        {
                print(a);
                puts();
        }
       
        static int[] array(int... a)
        {
                return copy(a);
        }
        static int[] copy(int[] a)
        {
                return Arrays.copyOf(a,a.length);
        }
}

class Map
{
        // Initialize
        int[][] map;
        int x,y;
        Map(int... s)
        {
                if(s.length<2)
                        initialize(10,10);
                else
                        initialize(s[0],s[1]);
        }
        void initialize(int x,int y)
        {
                this.x = x;
                this.y = y;
                this.map = new int[x][y];
        }
       
        // Method
        void prints()
        {
                int x,y;
                for(y=0;y<this.y;y++)
                {
                        for(x=0;x<this.x;x++)
                        {
                                System.out.print(this.map[x][y]+" ");
                        }
                        System.out.println();
                }
        }
        int point(int... p)
        {
                int x = p[0];
                int y = p[1];
                if(x<0||y<0||x>=this.x||y>=this.y)
                {
                        return -1;
                }
                return this.map[x][y];
        }

        // Static Method
        static int[][] data = new int[5][];
        static void initialize()
        {
                set(0,0,0);  // Bland
                set(1,0,0);  // Self
                set(2,0,1);  // Party
                set(3,1,1);  // Enemy
                set(4,1,1);  // Disorder
        }
        static private void set(int i,int e1,int e2)
        {
                data = Main.array(e1,e2);
        }
        static int[] property(int i)
        {
                if(i>=0&&i<=data.length)
                {
                        return data;
                }
                return Main.array(1,1);
        }
        static int transform(int i)
        {
                switch(i)
                {
                        case 1:
                        case 2:  return 3;
                        case 3:  return 2;
                        default: return i;
                }
        }
}

class Route
{
        // Initialize
        Map map;
        private int[] position;
        Route(int... s)
        {
                map = new Map(s);
        }
       
        // Data
        int[] position()
        {
                return position;
        }
        void position(int x,int y)
        {
                position = Main.array(x,y);
                map.map[x][y] = 1;
        }
        int point(int... p)
        {
                return map.point(p);
        }
        int[][] getRPots()
        {
                return pots;
        }
        int getRPotSize()
        {
                return pbout;
        }
        int getSize(int i)
        {
                return size;
        }
        int getSizes()
        {
                return sizes;
        }
        int[][][] getRRoute(int i)
        {
                return routes;
        }
        int[][][][] getRRoutes()
        {
                return routes;
        }
       
        // Search
        private int[][] pots;
        private int pbout;
        private int[][][][] routes;
        private int[] size;
        private int sizes;
        void search(int move)
        {
                pots = new int[getMSizes(move)][2];
                pbout = 0;
                size = new int[move+1];
                routes = new int[move+1][][][];
                routes[0] = new int[getMSize(0)][3][];
                routes[0][0][0] = position;
                routes[0][0][1] = Main.array();
                routes[0][0][2] = Main.array(0);
                pushPots(position);
                if(move<1)
                        return;
                routes[1] = fsearch();
                if(move<2)
                        return;
                nsearchs(2,move);
        }
        private int[][][] fsearch()
        {
                int[] p;
                int bout=0;
                int[][][] route = new int[getMSize(1)][3][];
                for(int i=1;i<=4;i++)
                {
                        p = position;
                        p = dirmove(i,p);
                        if(repeat(p))
                                continue;
                        if(pass(p))
                        {
                                route[bout][0] = p;
                                route[bout][1] = Main.array(i);
                                route[bout][2] = Main.array(put(p)?0:1);
                                pushPots(p);
                                bout++;
                        }
                }
                size[1] = bout;
                return route;
        }
        private int[][][] nsearch(int m)
        {
                int[][][] route = new int[getMSize(m)][3][];
                int[][][] dat = routes[m-1];
                int bout=0;
                for(int n=0;n<size[m-1];n++)
                {
                        for(int i=0;i<=4;i++)
                        {
                                int[] p = Arrays.copyOf(dat[n][0],dat[n][0].length);
                                int[] w = Arrays.copyOf(dat[n][1],dat[n][1].length+1);
                                p = dirmove(i,p);
                                if(repeat(p))
                                        continue;
                                if(pass(p))
                                {
                                        route[bout][0] = p;
                                        w[w.length-1] = i;
                                        route[bout][1] = w;
                                        route[bout][2] = Main.array(put(p)?0:1);
                                        pushPots(p);
                                        bout++;
                                }
                        }
                }
                size[m] = bout;
                return route;
        }
        void nsearchs(int a,int b)
        {
                for(int i=a;i<=b;i++)
                {
                        if(size[i-1]==0)
                        {
                                sizes = i-2;
                                break;
                        }
                        else
                        {
                                routes = nsearch(i);
                                if(size!=0)
                                        sizes = i;
                        }
                }
        }
       
        // Search Method
        private int getMSize(int m)
        {
                if (m==0)
                        return 1;
                return 4*m;
        }
        private int getMSizes(int move)
        {
                int s = 0;
                for(int i=0;i<move;i++)
                        s += getMSize(i);
                return s;
        }
        private void pushPots(int... p)
        {
                pots[pbout] = p;
                pbout++;
        }
        private int[] dirmove(int i,int... p)
        {
                int x = p[0];
                int y = p[1];
                switch (i)
                {
                        case 1:  // Up
                                return Main.array(x,y-1);
                        case 2:  // Down
                                return Main.array(x,y+1);
                        case 3:  // Left
                                return Main.array(x-1,y);
                        case 4:  // Right
                                return Main.array(x+1,y);
                        default: // Wait
                                return Main.array(x,y);
                }
        }
        private int property(int i,int... p)
        {
                return Map.property(point(p));
        }
        private boolean pass(int... p)
        {
                return property(0,p)==0;
        }
        private boolean put(int... p)
        {
                return property(1,p)==0;
        }
        private boolean repeat(int... p)
        {
                for(int i=0;i<pots.length;i++)
                {
                        int[] pp = pots;
                        if(pp[0]==p[0]&&pp[1]==p[1])
                                return true;
                }
                return false;
        }
}

class Path extends Route
{
        Path(int... s)
        {
                super(s);
        }
        // Map Data
        void setMap(int... d)
        {
                this.map.map[d[0]][d[1]] = d[2];
        }
        void setMaps(int[]... dat)
        {
                for(int i=0;i<dat.length;i++)
                {
                        setMap(dat);
                }
        }
        void setPosition(int... p)
        {
                position(p[0],p[1]);
        }
        int[] getPosition()
        {
                return position();
        }
       
        // Search Data
        int[][][][] getSearch(int move)
        {
                if(getSizes()==0)
                        search(move);
                return getRoutes();
        }
        int[][][] getRoute(int i)
        {
                if(i>getSizes())
                        return null;
                return Arrays.copyOf(getRRoute(i),getSize(i));
        }
        int[][][][] getRoutes()
        {
                return Arrays.copyOf(getRRoutes(),getSizes());
        }
}
[/pre][/fold]  

呼叫：
T君   R君      

taroxd

寻路现成脚本无数，何必自己写= =

taroxd

To 楼上点评

如果你写这个的目的是为了锻炼你的脚本水平，那我完全支持你自己写一遍。

但如果你的目的是自己写一个 SRPG 系统，不重用现有的代码还是很浪费时间的不是吗？

另外，我的建议是，既然你没有用到 RM 的地图系统，不妨用 “图” 来表示数据。（不过拿 RGSS 表示图果然还是觉得很蛋疼）

RyanBern

Ruby版的给taroxd看好了
看代码看了两遍没看出来是Dijkstra算法，果然算法是除了自己以外别人都看不懂的东西啊……
而且这个Java程序写得，我可以说数组超过三维我就开始接受不了了吗？四维数组用起来真的好麻烦啊。如果你想要表示点对的话，还是新建一个类为好。
不过搞出一个脚本来也是很辛苦的，希望优化方面再多做做吧。

PS：我的代码60多行是如何变成450行的？

寒冷魔王

RyanBern 发表于 2014-11-28 19:21
Ruby版的给taroxd看好了
看代码看了两遍没看出来是Dijkstra算法，果然算法是除了自己以外别人都看不 ...

= =那个啥，我是用Java把Ruby版的算法复刻了……不是Dijkstra算法。。

这是第三次尝试，全部都用数组储存。
第一次尝试定义了好多的类，结果又慢又乱= =而且程序有600+
Java版的puts()和print()就占去100行，各种get又是N多行= =
东西没有Ruby的多，但是基本的还是有的。


PS：你的那个我能说我看不懂RGSS吗= =另外用Java的话Ruby的60行变成个400多行是没问题的。
没办法，定一个void put()就要一大堆= =如果新建类表示类型输出的话又要一大堆= =
还有
{
}
占去的行数又有一大堆= =

寒冷魔王

RyanBern 发表于 2014-11-28 19:21
Ruby版的给taroxd看好了
看代码看了两遍没看出来是Dijkstra算法，果然算法是除了自己以外别人都看不 ...

引用：

单说执行效率，不说开发效率。

首先，很明显，汇编是最高的，不需要解码，没有任何限制。
然后是C/C++等等直接静态编译到汇编的语言，它们的效率等同汇编，之所以是第二等是因为编译器本身产生的结果可能和【你自己】想要的结果有细微差异，从而降低效率——当然，虽然编译器越来越先进，这种事情越来越少了。
关于C++的编译期计算等等的问题，我们等会儿来说。
下一级别，估计有点超出你的想象了，是Java、JavaScript和LuaJIT/PyPy这些，也就是运行时编译到汇编的语言，它们的效率大概只比C/C++之类低50%的样子——也就是说，C做事需要1s，它们估计也就需要2s，问题是，现代的程序，大部分都是碎片化执行的，真正在CPU上面耗费的时间不多，因此，实际的包含大量IO的程序而言，其实效率上差多。
再下一个级别就是Lua、Python（这里是CPython）这种了，字节码执行，自带虚拟机，效率上大概比C慢出50倍这个数量级。但是某些操作如果语言直接内置（比如Python的列表合成），那效率就和C的相同，有些操作你手动搞，效率就比C慢50倍，因此语言的设计极其重要，要保证需要手动搞的东西都是对效率影响不大的。
再下一个级别就是内存里面直接放解析树，没有字节码的。比如Ruby，大概比C慢200倍左右，恩，不详细说了。
最后一个级别是连解析树都没有，直接一行一行分析完了就执行，比如VimL，大概比C慢1000倍（三个数量级）的样子。

执行效率上，就是这么个等级了。

再说说C和C++，很多人有误解，模板提高效率啊，constexpr提高效率啊什么的。其实，这些C编译器也可以做优化，只是难度会很高——没有语言级别的直接提示。比如说，gcc有一个优化已经出现很久了，就是自动内联函数指针——如果发现几次调用的时候，给出的函数指针都一样，那么直接把这个函数指针固化到函数里面，做成一个特殊的static函数给你调。这多么像C++的模板！我的意思是，不要迷信语言特性，C和C++的基本原理都是完全把一种概念模型上的表述换成另外一种表述，这种转换中的效率提升往往并没有那么明显，但的确是有的。它们的确是效率相差不大的两门语言。

chd114

寒冷魔王 发表于 2014-11-28 04:20
引用：

你的VA魔塔样板呢···