|
|
（发晚了…………）
好的，现在先说一下，为什么使用N维数组。
在生活中，我们有很多地方，是会用到一个矩阵或者是一个立方体，用来存储数据。
拿编程来说，经典的【8皇后】问题就需要一个boolean类型的矩阵来存储棋盘上的点是否已被皇后们的攻击范围所覆盖，从而避免皇后能攻击其他的皇后。
问题的描述如下：
设在初始化状态下的国际象棋棋盘（8*8个点）上没有任何棋子（皇后）。顺序在棋盘的第1行、第2行……第8行上布放棋子。在每一行中有8个可选择位置，但在布置完毕后，棋盘的布局必须满足3个限制条件：任何两个棋子不得放在棋盘的：
1.同一行
2.同一列
3.同一斜线
上（其实可以理解为每个皇后都不能攻击别人，任何人不能在别人的攻击范围内）
试求解此问题的所有合法布局。
根据题意，我们很容易想到需要一个8*8的矩阵来存放棋盘上的点，是否已被皇后们的攻击范围所覆盖。可是，如果是使用jass的话，我们貌似是没法创建出一个矩阵的。原因就是我们没有办法创建一个二维数组来模仿矩阵。
再举一个例子：
迷宫（Maze）问题
迷宫需要一个二维矩阵来设置这里有没有墙（显而易见）。
如下就是一个【恶心的】迷宫了（但你不得不承认，最原始的电脑的迷宫就是这样的）（0=可通行，1=不可通行）：
1111111
0000011
1101001
1101101
1101111
现在，我们就来在jass里，实现这个方便人的N维矩阵吧！
首先，我们来研究一下一个2维矩阵吧：
首先，请大家把这句话理解（不理解，你看不下去）：
“数组的元素类型为一维数组”的一维数组，可以看成二维数组（矩阵）；
“数组的元素类型为二维数组”的一维数组，也可以看成三维数组（立方体）；
“数组的元素类型为三维数组”的一维数组，也可以看成四维数组；
……………………
依此类推
“数组的元素类型为N维数组”的一维数组，可以看成N+1维数组。
所以说，N维数组的概念，是由一维数组拓展过来的。
所以说，不管是几维数组，都可以由一维数组实现。
那么这样，在魔兽里，就可以用一维数组来实现N维数组。
但是，怎样才能将N维数组的点的坐标，转换成一维数组的序列（index）呢？
那么，我们先从二维数组开始，来研究一下
我们先将二维数组分为n个的元素个数为m的一维数组，再将它们进行头尾的拼接，那么，它们就连成了【传说中的一维数组】了。
…………………………………………
经过研究，我们发现：
一个二维数组[m][n]（转换的一维数组有m*n个元素）
其中的点pos[j][k](0<=j<m;0<=k<n)
转换成一维数组，pos的index为：
pos.index = k*m + j
那么，继续来分解一下三维数组的转换吧：
我们先将三维数组[m][n][v]切成v片，那每一片，就是一个[m][n]的二维数组了，将这个二维数组转换成一维数组，将它的尾巴与第二个二维数组的头相连……………………那这个是三维数组就是一个一维数组了。
…………………………………………
经过研究，我们发现：
一个三维数组[m][n][v]（转换的一维数组有m*n*v个元素）
其中的点pos[j][k][l](0<=j<m;0<=k<n;0<=l<m)
转换成一维数组，pos的index为：
pos.index = l*m*n + k*m + j
…………………………………………（继续分析4、5、6…………………………有穷大的数组）
我们可以得到公式：
一个N维数组[m_1][m_2]………………[m_n]（转换的一维数组有m_1*m_2…………*m_n个元素）
里的一个点：pos[v_1][v_2]………………[v_n](0<=v_1<m_1;0<=v_2<m_2………………0<=v_n<m_n)
他在一维数组中的位置：
pos.index = v_1 + v_2 * m_1 + v_3 * (m_2 * m_1) + v_4 * (m_3 * m_2 * m_1) + ………………………………………… + v_n * (m_n * m_n-1 * m_n-2 ……………… * m_1)
这样的话，函数是：
[codes=jass]globals
integer array Array_Sizes //N维数组的规模（m_1,m_2等）
integer Array_N //多少维的数组（N）
integer array Array_V //点的坐标（v_1,v_2等）
//以上NArrayPos2Index/Index2NArrayPos用
endglobals
function NArrayPos2Index takes nothing returns integer
local integer index = 0
local integer temp = 0
local integer i = 0
local integer j = 0
loop
exitwhen i >= Array_N
if i != 0 then
loop
exitwhen j >= i
set temp = temp + Array_Sizes[j]
set j = j + 1
endloop
else
set temp = 1
endif
set j = 0
set index = index + Array_V * temp
set i = i + 1
set temp = 0
endloop
return index
endfunction
function Index2NArrayPos takes integer index returns nothing
local integer i = Array_N - 1
local integer j = 0
local integer temp = 0
local integer temp2 = index
loop
exitwhen i < 0
if i != 0 then
loop
exitwhen j >= i
set temp = temp + Array_Sizes[j]
set j = j + 1
endloop
else
set temp = 1
endif
set j = 0
set Array_V = temp2 / temp
set temp2 = temp2 - Array_V * temp
set temp = 0
set i = i - 1
endloop
endfunction[/codes]
（请原谅：心情不好，函数不写注释）
这样的方法虽说能通吃N维数组，但是由于魔兽的ARRAY限制（8192个数组元素），所以，这个方法储存量很少。
重新来看一下我们魔兽中的实际问题，貌似除了矩阵外，其实像立方体什么的，用的很少，那么…………我再教你个方法：
GameCache储存法。
这个很简单，把missionKey当成X坐标，把Key当成Y坐标（你要是愿意的话，在X坐标前加标识符也没关系，只不过用的string更多了，我也是不赞成的）
比如，在迷宫中，我们把可以走的地方叫路径，那么，这个点是否为路径可以这样判断：
[codes=jass]function IsRoad takes integer x, integer y returns boolean
return GetStoredBoolean( the_Maze_gc, I2S(x), I2S(y) )
endfunction[/codes]
这样比转换成一维数组的方法好处在哪里呢？
1.x,y坐标可以为负数，如果是一维数组的话，是不能处理负数index的。
2.元素数量几乎无限，一维数组只能有8192个元素，而GameCache占用的内存很少，所以容量几乎是无限的。
缺点：
1.会产生很多string。（其实，也不多，因为如果x、y为100的话，还是在正常忍受范围之内的，元素还可以有10000个）
2.存储的元素的最多有boolean，integer，string，real，unit几个类型（还只能每种一个），如果要拓展的话，还需要其中的一个类型做index，指向另外的空间。
3.如果想要把N个矩阵存储在一个GameCache里，那么就必须在missionKey（X坐标）前加标识符，会产生大量string。
恩恩…………再来看一种方法：
string数组储存法。
string是什么呢？中文是： 字符 串。
也就是由字符组成的一个线性表（其实就是跟数组没什么两样了）。
那么，把字符看成元素，由字符串组成的一维数组，是不是就是二维数组了呢？
当然，这个办法比较恶心，不推荐使用。
最后，来一个：
地图上的区域法。
这个……………………
举个例子来说，这个点是否为路径，可以这样来看：
[codes=jass]globals
boolean IsRoad_bool = false
endglobals
function IsRoad_Action takes nothing returns nothing
set IsRoad_bool = true
endfunction
function IsRoad takes real minx, real miny, real maxx, real maxy returns boolean
local rect r = Rect( minx, miny, maxx, maxy )
local boolean b = false
set IsRoad_bool = false
call EnumDestructablesInRect( r, null, function IsRoad_Action )
call RemoveRect( r )
set r = null
set b = IsRoad_bool
set IsRoad_bool = false
return b
endfunction[/codes]
（这里是如果有地形装饰物【Destructable】，则为路径）
放在迷宫问题上，非常实际，不用抽象什么的。
当然这样，效率会比较低。
好了好了，总算说完了………… |
评分
-
查看全部评分
|
窥视卡
雷达卡
发表于 2009-2-15 10:07:10
提升卡
置顶卡
沉默卡
喧嚣卡
±????¨
千斤顶
???í?¨
发表于 2009-2-15 13:53:56
