精华内容
下载资源
问答
  • 卡马克算法android版本底层封装(使用android游戏开发中地图基于Title块的绘制)
  • 卡马克算法

    2017-12-06 13:55:45
    卡马克算法 - dong - 北风寒*/ y = * ( float * ) &i; /* 取长整型数i的地址,将其存储单元转换成浮点型,然后再把转换后的数取出来*/ y = y * ( threehalfs - ( x2 * y * y ) ); /* 1st iteration 第一...

    原文地址:http://blog.163.com/lxd007_2005/blog/static/405618252015112410210140/

    这里写图片描述
    最原始的版本不是求开方,而是求开方倒数,也即。为啥这样,原因有二。首先,开方倒数在实际应用中比开方更常见,例如在游戏中经常会执行向量的归一化操作,而该操作就需要用到开方倒数。另一个原因就是开方倒数的牛顿迭代没有除法操作,因而会比先前的牛顿迭代(这里写图片描述这里写图片描述从Xi-1=1开始迭代)开方要快。
    这里写图片描述
    由这个公式我们就很清楚地明白代码y=y*(threehalfs-(x2*y*y))的含义,这其实就是执行了单次牛顿迭代。为啥只执行了单次迭代就完事了呢?因为单次迭代的精度已经达到相当高的程度。
    为什么单次迭代就可以达到精度要求呢?根据之前的分析我们可以知道,最根本的原因就是选择的初值非常接近精确解。而估计初始解的关键就是下面这句代码:

    i  = 0x5f3759df - ( i >> 1 );  
    

    正是由于这句代码,特别是其中的“magic number”使算法的初始解非常接近精确解。具体的原理是地址强转:首先将float类型的数直接进行地址转换转成int型(代码中long在32位机器上等价于int),然后对int型的值进行一个神奇的操作,最后再进行地址转换转成float类型就是很精确的初始解。
    float型浮点数和对应的int型整数之间的关系给出一个公式
    这里写图片描述
    有了这个公式我们就可以推导初始解的由来了。要求这里写图片描述,我们可以将其等价转化成这里写图片描述,然后代入上面的公式我们就得到:这里写图片描述
    这个公式就是神奇操作的数学表示,公式中只有这里写图片描述是未知量,其它都已知。这里写图片描述的值没有好的求解方法,数学家通过暴力搜索加实验的方法求得最优值为这里写图片描述0.0450466,此时第一项就对应0x5f3759df。但是后来经过更仔细的实验,大家发现用0x5f375a86可以获得更好的精度,所以后来就改用此数。
    算法的最终目的是要对浮点数开平方,该算法性能非常高,而且精度也很高,三次迭代精度就和系统函数一样,但是速度只有系统函数sqrtf的十分之一不到,相当了得。

    #include "stdio.h"
    
    #include "conio.h"
    
    float Q_rsqrt( float number )
    
    {  
    
        long i;  
    
        float x2, y;  
    
        const float threehalfs = 1.5F;  
    
        x2 = number * 0.5F;  
    
        y  = number;  
    
        i  = * ( long * ) &y;  /* evil floating point bit level hacking 烦人的浮点位级处理 */
    
        i  = 0x5f3759df - ( i >> 1 ); /* what the fuck? 0x5f3759df or 0x5f375a86 什么该死的? 卡马克算法 - dong - 北风寒*/
    
        y  = * ( float * ) &i;  /* 取长整型数i的地址,将其存储单元转换成浮点型,然后再把转换后的数取出来*/
    
        y  = y * ( threehalfs - ( x2 * y * y ) );   /* 1st iteration 第一次迭代*/   
    
        y  = y * ( threehalfs - ( x2 * y * y ) );   /*  2nd iteration, this can be removed 第二次迭代,能够移除*/ 
    
        return y;  
    
    }  
    
    int main()
    
    {
    
        float n,z=1.0;
    
        printf("请输入一个需要求其平方根的数:");
    
        scanf("%f",&n);
    
        z=Q_rsqrt(n);
    
        printf("平方根为%f\n",1.0/z);
    
        getch(); 
    
        return 0;
    
    }

    举例:X=2^e(1+f)=5.125=2^2(1+0.28125)
    Ix=EL+F=L(e+B+f)=2^23(2+127+0.28125)=2^23*10000001.01001=0(符号)10000001(阶码)
    01001000000000000000000(尾数)(8388608*129.28125=1084489728)
    Ix表示浮点数的整数表示,E=e+B表示IEEE阶码值,L=这里写图片描述表示阶码的起始位置,F=Lf表示尾数的整数表示
    这里写图片描述=

    12582912*(127-0.0450466)-1/2*1084489728=1597463007-542244864=1055218143=01111101 11001010101100111011111
    y=*(float*)&i=2^(-2)*1.791805148124694824≈ 0.447951287
    y1 =y(1.5-2.5625y^2)≈ 0.441593890
    展开全文
  • flash 卡马克算法

    2018-02-02 11:28:33
    flash 卡马克算法地图或是图片加载时候减少加载资源,降低内存
  • 游戏地图绘制的经典算法卡马克 卡马克算法 经典 详细 游戏地图绘制中的常用算法 值的研究的算法
  • J2ME卡马克算法源码

    2009-09-12 15:47:14
    卡马克算法源码绝对物有所值对初学者很有帮助
  • J2ME地图优化算法卡马克卷轴算法。 RPG地图优化。
  • 卡马克算法:由约翰·卡马克(John Carmack)开发的一种游戏地图处理方法,被广泛运用到2D卷轴式游戏和手机游戏中。约翰·卡马克:id Software创始人之一,技术总监。享誉世界的著名程序员,以卡马克算法和3D游戏...

    ----------------------------下面是理论知识--------------------------

     

    卡马克算法:由约翰·卡马克(John Carmack)开发的一种游戏地图处理方法,被广泛运用到2D卷轴式游戏和手机游戏中。
    约翰·卡马克:id Software创始人之一,技术总监。享誉世界的著名程序员,以卡马克算法和3D游戏引擎开发而闻名世界,被奉为游戏行业偶像。同时他也是个全面型的技术天才,现在致力于民用航天器开发,是民用航天器开发小组Armadillo Aerospace的主要创办人和技术骨干。
    约翰·卡马克(百度百科):
    http://baike.baidu.com/view/59118.htm 
    约翰·卡马克(维基百科):
    http://zh.wikipedia.org/wiki/約翰·卡馬克 



         地图是游戏中必不可少的一种预算元素,尤其是在RPG、ACT等类型的游戏中作用更为重要,一个漂亮的地图效果和一个流畅的卷动速度会大大增加玩家的游戏体验。而游戏中地图滚动的重绘有多种算法,由于手机性能的限制和开发周期等其他非技术条件,需要根据情况灵活选择所需的技术。本文将主要介绍如何使用OPhone API来绘制2D游戏中的场景,也即地图的绘制方法。

    地图绘制及滚动的常用算法
    无缝图片滚动画法
           最简单的一种画地图方法,无需使用数组,只需要使用一张无缝的背景图片,在屏幕上绘制两次,以此来实现最简单的地图滚动效果和图片的重复使用以节约资源。
    如下图,红色虚线部分为屏幕,使用一个偏移量在屏幕中错开位置贴上两次图片,通过不断改变偏移量的大小来实现动画效果。

            代码举例:
    view plain
    copy to clipboard
    print
    ?
        //imgBack图片对象  
        //posX图片在X轴方向上的偏移量  
    canvas.drawBitmap(imgBack, -posX, 0, paint);  
    canvas.drawBitmap(imgBack, imgBack.getHeight()+posX, 0, paint);  
        if(posX==-imgBack.getHeight())  
            posX=0;   //imgBack图片对象 //posX图片在X轴方向上的偏移量 canvas.drawBitmap(imgBack, -posX, 0, paint); canvas.drawBitmap(imgBack, imgBack.getHeight()+posX, 0, paint); if(posX==-imgBack.getHeight()) posX=0;
           优点与局限:此算法非常简单,由于是单张图片反复滚动生成的背景图片,所以对于美术人员的限制较少,利于发挥,而且外观效果好。但因为不是地图Tile组成的,资源复用率不高,只能用于生成不太复杂的地图。而且由于没有Tile的存在,无法针对不同的Tile计算碰撞。最终使得这种画法只能用于绘制简单屏幕背景图片,而无法用在有复杂物理碰撞的地图层。
    裁剪区画法
            我们平时所玩的游戏一般场景都是大于屏幕的尺寸的,也就是说在游戏中的主角移动的时候,后面的地图将会随着主角的位置变化而发生移动,我们称之为地图的卷轴效果。而对诸如RPG,ACT这类地图场景比较大的类型的游戏来说,地图都不是一整张的背景图直接使用,而是采用一种“拼接”的方式,这样做既能节省内存的占用,同时也能使图片资源的利用率达到最大化。下图就是2D游戏常用的图片样式:

             从图中我们能够看出,我们可以把整张图片进行分割,并将分割后的图片进行编号,如下所示:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
          
             为每块图素编号之后,就可以设计自己的地图了。这里需要使用一种叫做“地图编辑器”的工具软件。我们这里使用“mapwin”进行地图的设计,使用步骤如下图所示:

             上面的四个输入框分别代表地图小块的宽度和高度,以及我们要创建的整个场景的水平和垂直的地图块数,输入后点击“OK”如下图所示:

             下面需要引入一张图片,引入方法为“File——Import”,选取一张图片并点击确定,随后就能看到如下的图片:

               剩下的工作想必你就可以想到了,用鼠标在右边区域选取一个图块,然后将其放到左边黑色区域中即可,拼接完的效果如下图:

               接下来要把地图数据导出,导出放下如下图:

             最后我们需要的数据是这样的:
    const short ss_map0[10][10] = {
    { 1, 1, 1, 1, 1, 1, 1, 5, 1, 1 },
    { 10, 10, 10, 1, 1, 1, 1, 1, 1, 1 },
    { 8, 8, 8, 1, 1, 1, 1, 1, 1, 1 },
    { 9, 9, 9, 1, 1, 1, 1, 14, 15, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 16, 17, 1 },
    { 1, 1, 1, 6, 11, 1, 1, 1, 1, 1 },
    { 1, 1, 1, 1, 11, 1, 1, 1, 21, 1 },
    { 1, 4, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
    };
             实际上就是一个二维数组,数组中的数字即为地图块的索引号。
             使用二维数组保存地图信息,另外有一张图片素材,根据地图数组的不同下标,配合public boolean clipRect(float left, float top, float right, float bottom,Region.Op op) 裁剪区方法,将对应的Tile显示在正确的位置上。
            如下图所示,红色虚线部分为屏幕,红色实线为裁剪区,通过读取地图数组,将相应的位置设置为裁剪区,并用将图片素材相对于裁剪区偏移一定x,y位置的方法,使得要绘制的Tile正好对应出现在裁剪区中。

    代码举例:
    view plain
    copy to clipboard
    print
    ?
    // 绘制切割图片  
        public void drawClipImg(int XDest, int YDest, int Width, int Height,  
                int XSrc, int YSrc, Bitmap img, Paint g,Canvas canvas)  
        {  
            canvas.clipRect(XDest, YDest, XDest + Width, YDest + Height,  
                    Region.Op.REPLACE);  
            canvas.drawBitmap(img, XDest - XSrc, YDest - YSrc, g);  
            canvas.clipRect(0, 0, Const.SCREEN_WIDTH, Const.SCREEN_HEIGHT,  
                    Region.Op.REPLACE);  
        }     // 绘制切割图片 public void drawClipImg(int XDest, int YDest, int Width, int Height, int XSrc, int YSrc, Bitmap img, Paint g,Canvas canvas) { canvas.clipRect(XDest, YDest, XDest + Width, YDest + Height, Region.Op.REPLACE); canvas.drawBitmap(img, XDest - XSrc, YDest - YSrc, g); canvas.clipRect(0, 0, Const.SCREEN_WIDTH, Const.SCREEN_HEIGHT, Region.Op.REPLACE); }
           相对于前一种画法,图片资源的利用率提高了很多,可以绘制很复杂的地图。由于Tile的存在,可以针对不同的Tile计算碰撞,可以用于地图物理层的绘制。
    最常见的地图绘制优化——只绘制当前屏幕
           上面的绘制方法都是将整个地图的数据全部画出来的,这样做实际上也存在很大的浪费,因为玩家实际上只能看见屏幕中的一块区域,其他大部分的地图即使被绘制也不能反映到屏幕上,反而因为这个不必要的步骤大大增加了CPU的负担,从而影响了游戏的流畅程度。因此,在实际开发中,常用的优化方法就是只绘制当前屏幕的地图块。代码如下:
    view plain
    copy to clipboard
    print
    ?
        //计算单元格起始位置下标  
        int startIndexX =leftTopY/ MAP_TILE_SIZE;  
        int startIndexY =leftTopX/ MAP_TILE_SIZE;  
        //再使用上面得到的数据修改双循环绘制的条件即可,  
    for (int i = startIndexX; i 1; i++)  
                for (int j = startIndexY; j 1; j++)   //计算单元格起始位置下标 int startIndexX =leftTopY/ MAP_TILE_SIZE; int startIndexY =leftTopX/ MAP_TILE_SIZE; //再使用上面得到的数据修改双循环绘制的条件即可, for (int i = startIndexX; i
    卡马克卷轴算法的引入
           上面的算法虽然在一定程度上解决了地图绘制的效率问题,但对于某些资源严重不足的手机,或者由于地图块比较小、循环次数过多的情况,仍然会造成画图时屏幕闪烁。因此,在这种情况下,仍然需要对上述算法做进一步的优化。
            不论采用哪种优化算法,一个基本的思路就是尽量减少绘制的次数,从而减少对系统资源的消耗。卡马克卷轴算法就是这样算法的一个经典例子。
    单方向卷轴
            对于横版游戏来说,如果角色向右侧移动,则地图向左侧滚动。由于角色每次移动若干个步长,因此地图中新画出的区域宽度也为若干个像素,那么如果让系统重绘所有屏幕区域,很明显,大部分区域都是和上一屏幕区域相同的,如此造成成了资源的浪费。而卡马克算法的思路就是——如果上一次绘制过的地图也能够部分重用到本次地图绘制上来就好了。那么很容易想到在内存中建立一个和屏幕一样大或略大的缓冲区即可很好的完成这个设想。

           由上图可以看到,区域B为相同的地图区域,这个区域在下一次屏幕重绘时,可以被重新利用。区域A是在下一次屏幕重绘中不被采用的区域,这区域应当被舍弃,但是如果稍微留意一下的话,不难发现区域A和区域C的面积大小其实居然是一样的。
           那么如果建立一个和屏幕大小相同的缓冲,在其被舍弃掉的绘制区域A中画上新的区域C,再把区域B和区域C拼合到屏幕上,是不是就能达到减少系统资源消耗的目的了呢?卡马克卷轴的基本原理正是如此。

           图显示了卡马克卷轴的最基本原理,首先在内存中建立一块和屏幕一样大小(或略大)的缓冲区。然后在本应由于地图移动而被舍弃掉的区域1上面绘制,由于地图滚动而出现的新地图区域。最后把两个区域按照地图的实际位置拼合到屏幕上。
    双轴滚动的卡马克卷轴
            对于俯视游戏,或者有Y轴卷动的游戏来说,单单一个方向的地图卷动并不够用。那么如果是出现两个方向的卷动会如何呢。不必担心,上面的思路算法一样能适应这种情况。

            由上图可以看到,区域D为相同的地图区域,这个区域在下一次屏幕重绘时,可以被重新利用。区域ABC是在下一次屏幕重绘中不被采用的区域,可以在这个3个区域上绘制上下一次需要重绘的区域A’B’C’。再将绘制好的四个区域拼合到屏幕的对应位置。

           上图显示了双轴滚动的卡马克卷轴的基本绘制原理,需要特别注意的是:在缓冲区的绘制顺序和在屏幕上拼合的顺序是完全相反的。
    卡马克算法的实现
    卡马克卷轴缓冲画法的一般步骤如下:
    1. 初始化所有地图数据,并且全屏绘制初始的地图
    2. 若人物移动,则调用摄像机算法,修正地图偏移量
    3. 地图偏移量不满足地图的边界条件,就重绘缓冲区
    4. 重绘缓冲区
    5. 后台缓冲区的四个子区按照顺序画到屏幕上
    地图类——Map的设计
    字段定义
    view plain
    copy to clipboard
    print
    ?
    //地图数据  
    public byte mapData[][];  
    //移动缓冲区的当前坐标窗口  
    public int sx,sy;  
    //地图图片  
    private Bitmap imgMap;  
    public GameView m_View;  
    //常量  
    public final static int MAP_TILE_SIZE = 24;  
      
      
    private int bufWidth, bufHeight;  
      
    private int carTileWidth, carTileHeight;  
      
    private int scrWidth, scrHeight;  
      
    private int carx, cary;  
      
    private int mapOffx, mapOffy;  
      
    public Bitmap carBuffer;  
      
    private Canvas carGp;  
      
    private int buffSize;  
      
    private int imageTileWidth;  
      
    private Bitmap mapImage;      
    Paint paint=new Paint();  
      
    private byte mapArray[][];  
      
    private int tileSize;  
      
    private int tileW, tileH;  
      
    private int mapLastx, mapLasty;   //地图数据 public byte mapData[][]; //移动缓冲区的当前坐标窗口 public int sx,sy; //地图图片 private Bitmap imgMap; public GameView m_View; //常量 public final static int MAP_TILE_SIZE = 24; private int bufWidth, bufHeight; private int carTileWidth, carTileHeight; private int scrWidth, scrHeight; private int carx, cary; private int mapOffx, mapOffy; public Bitmap carBuffer; private Canvas carGp; private int buffSize; private int imageTileWidth; private Bitmap mapImage; Paint paint=new Paint(); private byte mapArray[][]; private int tileSize; private int tileW, tileH; private int mapLastx, mapLasty;
    方法定义
    CarMapBuffer(int, int, int, int)构造器
    CarMapBuffer(int, int, int)构造器的代理
    setMap(Image, byte[][])设置地图参数
    initBuffer()初始化绘制地图
    scroll(int, int)卷动地图算法
    updateBuffer(int, int)绘制缓冲区
    getIndexCarX()获得切割线所在的图块索引X
    getIndexCarY()获得切割线所在的图块索引Y
    getBufferCarX()获得切割线在Buffer中的X位置
    getBufferCarY()获得切割线在Buffer中的Y位置
    getIndexBuffLastX()获得缓冲区后面的X索引
    getIndexBuffLastY()获得缓冲区后面的Y索引
    getTitleHeight()获得当前要绘制的图块高度的数量
    getTitelWidth()获得当前要绘制的图块宽度的数量
    copyBufferX(int, int, int, int, int) 由于x方向卷动造成的重绘
    copyBufferY(int, int, int, int, int) 由于y方向卷动造成的重绘
    getMapX(int, int) 获得地图图片的X坐标偏移
    getMapY(int, int) 获得地图图片的Y坐标偏移
    paint(Graphics, int, int)将缓冲区的内容分成4块依次拼合到屏幕上
    drawBuffer(Graphics, int, int)绘制缓冲区方法
    drawRegion(Graphics, Image, int, int, int, int, int, int, int, int)封装的drawRegion()方法
    getGraphics()获得缓冲区画笔
    getImage()获得缓冲区Image对象
    步骤一的实现
    初始化所有地图数据,并且全屏绘制初始的地图,代码如下:
    view plain
    copy to clipboard
    print
    ?
      
        private void initBuffer()  
        {  
            int x, y, cx, cy;  
            for (int i = 0; i
            {  
                for (int j = 0; j
                {  
                    x = getMapX(i, j);  
                    y = getMapY(i, j);  
                    cx = j * tileSize;  
                    cy = i * tileSize;  
                    m_View.drawClipImg(cx, cy, tileSize, tileSize, x, y, mapImage, paint, carGp);  
                }  
            }  
    }   private void initBuffer() { int x, y, cx, cy; for (int i = 0; i
    步骤二、三的实现
    若人物移动,则调用摄像机算法,修正地图偏移量,若偏移量在[0,maplast]移动范围内移动,则有可能发生重绘
    view plain
    copy to clipboard
    print
    ?
      
        private void scroll(int x, int y)  
        {  
            try  
            {  
                x += mapOffx;  
                y += mapOffy;  
                // *************************************************  
                // 边界检测  
                if (x 0 || y 0)  
                {  
                    return;  
                }  
                if (x > mapLastx)  
                {  
                    mapOffx = mapLastx;  
                    return;  
                }  
                if (y > mapLasty)  
                {  
                    mapOffy = mapLasty;  
                    return;  
                }  
                updateBuffer(x, y);  
                // *************************************************  
            }  
            catch (ArrayIndexOutOfBound***ception e)  
            {  
            }  
        }  
           private void scroll(int x, int y) { try { x += mapOffx; y += mapOffy; // ************************************************* // 边界检测 if (x  mapLastx) { mapOffx = mapLastx; return; } if (y > mapLasty) { mapOffy = mapLasty; return; } updateBuffer(x, y); // ************************************************* } catch (ArrayIndexOutOfBound***ception e) { } }
    步骤四的实现
            重绘缓冲区,地图的x方向卷动会造成列方向上的重绘(调用copyBufferX()方法),地图的y方向上的卷动会造成行方向上的重绘(调用copyBufferY()方法)。updateBuffer()方法用于针对不同的四个方向上的卷动进行copyBuffer()参数的初始化。
    view plain
    copy to clipboard
    print
    ?
      
        private void updateBuffer(int x, int y)  
        {  
            mapOffx = x;  
            mapOffy = y;  
            // 右移  
            if (x > carx + buffSize)  
            {  
                // while (carx  
                int indexMapLastX = getIndexBuffLastX();  
                if (indexMapLastX
                {  
                    copyBufferX(indexMapLastX, getIndexCarY(), getTileHeight(),  
                                getBufferCarX(), getBufferCarY());  
                    carx += tileSize;  
                }  
                // }  
            }  
            // 左移  
            if (x
            {  
                // do {  
                carx -= tileSize;  
                copyBufferX(getIndexCarX(), getIndexCarY(), getTileHeight(),  
                            getBufferCarX(), getBufferCarY());  
                // } while (carx > mapOffx);  
            }  
            // 下移  
            if (y > cary + buffSize)  
            {  
                // while (cary  
                int indexMapLastY = getIndexBuffLastY();  
                if (indexMapLastY
                {  
                    copyBufferY(getIndexCarX(), indexMapLastY, getTitelWidth(),  
                                getBufferCarX(), getBufferCarY());  
                    cary += tileSize;  
                }  
                // }  
            }  
            // 上移  
            if (y
            {  
                // do {  
                cary -= tileSize;  
                copyBufferY(getIndexCarX(), getIndexCarY(), getTitelWidth(),  
                            getBufferCarX(), getBufferCarY());  
                // } while (cary > mapOffy);  
            }  
        }   private void updateBuffer(int x, int y) { mapOffx = x; mapOffy = y; // 右移 if (x > carx + buffSize) { // while (carx  mapOffx); } // 下移 if (y > cary + buffSize) { // while (cary  mapOffy); } }
            重绘缓冲区的具体方法,该方法涉及到大量的坐标运算,而且由于卡马克点的存在经常会分成两个区域分两次进行重绘。见下图:

                  下面以x方向卷动为例举例
    view plain
    copy to clipboard
    print
    ?
    private void copyBufferX(int indexMapx, int indexMapy, int tileHeight,  
                               int destx, int desty)  
      {  
          int mapImagex, mapImagey, vy;  
          // 拷贝地图上面到缓冲的下面  
          int timer=0;  
          for (int j = 0; j
          {  
              mapImagex = getMapX(indexMapy + j, indexMapx);  
              mapImagey = getMapY(indexMapy + j, indexMapx);  
              vy = j * tileSize + desty;  
              m_View.drawClipImg(destx, vy, tileSize, tileSize, mapImagex, mapImagey, mapImage, paint, carGp);  
      
              timer++;  
          }  
          // 拷贝地图下面到缓冲的上面  
          for (int k = tileHeight; k
          {  
              mapImagex = getMapX(indexMapy + k, indexMapx);  
              mapImagey = getMapY(indexMapy + k, indexMapx);  
              vy = (k - tileHeight) * tileSize;  
              m_View.drawClipImg(destx, vy, tileSize, tileSize, mapImagex, mapImagey, mapImage, paint, carGp);  
      
              timer++;  
          }  
          System.out.println("x:"+timer);  
      }   private void copyBufferX(int indexMapx, int indexMapy, int tileHeight, int destx, int desty) { int mapImagex, mapImagey, vy; // 拷贝地图上面到缓冲的下面 int timer=0; for (int j = 0; j
    步骤五的实现
            将后台缓冲区的四个子区按照顺序画到屏幕上:
    view plain
    copy to clipboard
    print
    ?
    public void paint(Canvas g, int x, int y)  
        {  
            // 地图在缓冲中的坐标  
            int tempx = mapOffx % bufWidth;  
            int tempy = mapOffy % bufHeight;  
            // 切割线右下角的宽与高  
            int rightWidth = bufWidth - tempx;  
            int rightHeight = bufHeight - tempy;  
            // 画左上  
            drawRegion(g, carBuffer, tempx, tempy, rightWidth, rightHeight, 0, x, y);  
            // 画右上  
            drawRegion(g, carBuffer, 0, tempy, scrWidth - rightWidth, rightHeight, 0, x + rightWidth, y);  
            // 画左下  
            drawRegion(g, carBuffer, tempx, 0, rightWidth, scrHeight - rightHeight, 0, x, y + rightHeight);  
            // 画右下  
            drawRegion(g, carBuffer, 0, 0, scrWidth - rightWidth, scrHeight  
                       - rightHeight, 0, x + rightWidth, y + rightHeight);  
    }  
      
      
      
      
      
          
        private void drawRegion(Canvas g, Bitmap img, int x_src, int y_src,  
                                int width, int height, int transform, int x_dest,  
                                int y_dest)  
        {  
            // 作宽度检测  
            if (width 0 || height 0)  
            {  
                return;  
            }  
            // 作超屏幕宽度检测  
            if (width > scrWidth)  
            {  
                width = scrWidth;  
                // 作超屏幕高度检测  
            }  
            if (height > scrHeight)  
            {  
                height = scrHeight;  
            }  
            m_View.drawClipImg(x_dest, y_dest, width, height, x_src, y_src, img, paint, g);  
    }  public void paint(Canvas g, int x, int y) { // 地图在缓冲中的坐标 int tempx = mapOffx % bufWidth; int tempy = mapOffy % bufHeight; // 切割线右下角的宽与高 int rightWidth = bufWidth - tempx; int rightHeight = bufHeight - tempy; // 画左上 drawRegion(g, carBuffer, tempx, tempy, rightWidth, rightHeight, 0, x, y); // 画右上 drawRegion(g, carBuffer, 0, tempy, scrWidth - rightWidth, rightHeight, 0, x + rightWidth, y); // 画左下 drawRegion(g, carBuffer, tempx, 0, rightWidth, scrHeight - rightHeight, 0, x, y + rightHeight); // 画右下 drawRegion(g, carBuffer, 0, 0, scrWidth - rightWidth, scrHeight - rightHeight, 0, x + rightWidth, y + rightHeight); } private void drawRegion(Canvas g, Bitmap img, int x_src, int y_src, int width, int height, int transform, int x_dest, int y_dest) { // 作宽度检测 if (width  scrWidth) { width = scrWidth; // 作超屏幕高度检测 } if (height > scrHeight) { height = scrHeight; } m_View.drawClipImg(x_dest, y_dest, width, height, x_src, y_src, img, paint, g); }
           当然,地图的卷动和精灵的移动是分不开的,在本文中我们只阐述了游戏的地图绘制方法,关于精灵的绘制以及地图随精灵的位移而卷动,我们会在另一篇文章中做以介绍。
    总结
          卡马克算法是在进行2D游戏地图卷动的算法中内存痕迹最小、效率适中的算法之一。其核心的思想就是把地图卷动过程中移出屏幕(不需要在显示的部分)所占用的buffer区域,绘制上新的需要图块,在往屏幕上绘制的时候,通过四次绘制buffer把完整的地图重现。
          我们在实际的代码编写中按以下的方式进行。根据上面的基本思想,把地图分为四个块(十字形的将buffer划分为四块),用carx和cary来记录十字分区的中心坐标(相对于buffer的坐标,我把这个点叫卡马克分区点)。
    当地图向右移动的时候这时把卡马克分区点的坐标X方向加上一个tile的width,然后在从现在的卡马克分区点的坐标Y开始绘制提取出来的tileID对应的图象,注意是从当前的卡马克分区点的坐标Y开始绘制,当超出carHeight时在从0开始绘制直到结束,这样就完成了在水平方向上的更新。
           还有就是在水平移动卡马克分区点的时候是在buffer中循环的,也就是从0到carWidth的一个循环过程,Y方向上完全一致。最后是绘制过程,也就是将四个分区绘制出来,口诀就是左变右上变下,掌握好卡马克算法对手游开发很有帮助的。
           注:本文参考了网上关于卡马克算法的一些介绍并引用了其中的部分文字和图片。
     
    展开全文
  • 游戏地图的绘制--卡马克算法(转)

    千次阅读 2012-03-31 10:04:21
    地图是游戏中必不可少的一种预算元素,尤其是在RPG、ACT等类型的...而游戏中地图滚动的重绘有多种算法,由于手机性能的限制和开发周期等其他非技术条件,需要根据情况灵活选择所需的技术。本文将主要介绍如何使用OPhon

    转载:http://bbs.chinaunix.net/thread-1669931-1-1.html

    地图是游戏中必不可少的一种预算元素,尤其是在RPG、ACT等类型的游戏中作用更为重要,一个漂亮的地图效果和一个流畅的卷动速度会大大增加玩家的游戏体验。而游戏中地图滚动的重绘有多种算法,由于手机性能的限制和开发周期等其他非技术条件,需要根据情况灵活选择所需的技术。本文将主要介绍如何使用OPhone API来绘制2D游戏中的场景,也即地图的绘制方法。



    地图绘制及滚动的常用算法

    无缝图片滚动画法
           最简单的一种画地图方法,无需使用数组,只需要使用一张无缝的背景图片,在屏幕上绘制两次,以此来实现最简单的地图滚动效果和图片的重复使用以节约资源。
    如下图,红色虚线部分为屏幕,使用一个偏移量在屏幕中错开位置贴上两次图片,通过不断改变偏移量的大小来实现动画效果。

            代码举例:
    view plain
    copy to clipboard
    print
    ?
        //imgBack图片对象   
        //posX图片在X轴方向上的偏移量   
    canvas.drawBitmap(imgBack, -posX,  0 , paint);   
    canvas.drawBitmap(imgBack, imgBack.getHeight()+posX,  0 , paint);   
        if(posX==-imgBack.getHeight())   
            posX= 0 ;   //imgBack图片对象 //posX图片在X轴方向上的偏移量 canvas.drawBitmap(imgBack, -posX, 0, paint); canvas.drawBitmap(imgBack, imgBack.getHeight()+posX, 0, paint); if(posX==-imgBack.getHeight()) posX=0;
           优点与局限:此算法非常简单,由于是单张图片反复滚动生成的背景图片,所以对于美术人员的限制较少,利于发挥,而且外观效果好。但因为不是地图Tile组成的,资源复用率不高,只能用于生成不太复杂的地图。而且由于没有Tile的存在,无法针对不同的Tile计算碰撞。最终使得这种画法只能用于绘制简单屏幕背景图片,而无法用在有复杂物理碰撞的地图层。

    裁剪区画法
            我们平时所玩的游戏一般场景都是大于屏幕的尺寸的,也就是说在游戏中的主角移动的时候,后面的地图将会随着主角的位置变化而发生移动,我们称之为地图的卷轴效果。而对诸如RPG,ACT这类地图场景比较大的类型的游戏来说,地图都不是一整张的背景图直接使用,而是采用一种“拼接”的方式,这样做既能节省内存的占用,同时也能使图片资源的利用率达到最大化。下图就是2D游戏常用的图片样式:

             从图中我们能够看出,我们可以把整张图片进行分割,并将分割后的图片进行编号,如下所示:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
           
             为每块图素编号之后,就可以设计自己的地图了。这里需要使用一种叫做“地图编辑器”的工具软件。我们这里使用“mapwin”进行地图的设计,使用步骤如下图所示:

             上面的四个输入框分别代表地图小块的宽度和高度,以及我们要创建的整个场景的水平和垂直的地图块数,输入后点击“OK”如下图所示:

             下面需要引入一张图片,引入方法为“File——Import”,选取一张图片并点击确定,随后就能看到如下的图片:

               剩下的工作想必你就可以想到了,用鼠标在右边区域选取一个图块,然后将其放到左边黑色区域中即可,拼接完的效果如下图:

               接下来要把地图数据导出,导出放下如下图:

             最后我们需要的数据是这样的:
    const short ss_map0[10][10] = {
    { 1, 1, 1, 1, 1, 1, 1, 5, 1, 1 },
    { 10, 10, 10, 1, 1, 1, 1, 1, 1, 1 },
    { 8, 8, 8, 1, 1, 1, 1, 1, 1, 1 },
    { 9, 9, 9, 1, 1, 1, 1, 14, 15, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 16, 17, 1 },
    { 1, 1, 1, 6, 11, 1, 1, 1, 1, 1 },
    { 1, 1, 1, 1, 11, 1, 1, 1, 21, 1 },
    { 1, 4, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
    };

             实际上就是一个二维数组,数组中的数字即为地图块的索引号。
             使用二维数组保存地图信息,另外有一张图片素材,根据地图数组的不同下标,配合public boolean clipRect(float left, float top, float right, float bottom,Region.Op op) 裁剪区方法,将对应的Tile显示在正确的位置上。

            如下图所示,红色虚线部分为屏幕,红色实线为裁剪区,通过读取地图数组,将相应的位置设置为裁剪区,并用将图片素材相对于裁剪区偏移一定x,y位置的方法,使得要绘制的Tile正好对应出现在裁剪区中。



    代码举例:

    view plain
    copy to clipboard
    print
    ?
    // 绘制切割图片   
        public void drawClipImg(int XDest, int YDest, int Width, int Height,   
                int XSrc, int YSrc, Bitmap img, Paint g,Canvas canvas)   
        {   
            canvas.clipRect(XDest, YDest, XDest + Width, YDest + Height,   
                    Region.Op.REPLACE);   
            canvas.drawBitmap(img, XDest - XSrc, YDest - YSrc, g);   
            canvas.clipRect( 0 0 , Const.SCREEN_WIDTH, Const.SCREEN_HEIGHT,   
                    Region.Op.REPLACE);   
        }     // 绘制切割图片 public void drawClipImg(int XDest, int YDest, int Width, int Height, int XSrc, int YSrc, Bitmap img, Paint g,Canvas canvas) { canvas.clipRect(XDest, YDest, XDest + Width, YDest + Height, Region.Op.REPLACE); canvas.drawBitmap(img, XDest - XSrc, YDest - YSrc, g); canvas.clipRect(0, 0, Const.SCREEN_WIDTH, Const.SCREEN_HEIGHT, Region.Op.REPLACE); }
           相对于前一种画法,图片资源的利用率提高了很多,可以绘制很复杂的地图。由于Tile的存在,可以针对不同的Tile计算碰撞,可以用于地图物理层的绘制。

    最常见的地图绘制优化——只绘制当前屏幕
           上面的绘制方法都是将整个地图的数据全部画出来的,这样做实际上也存在很大的浪费,因为玩家实际上只能看见屏幕中的一块区域,其他大部分的地图即使被绘制也不能反映到屏幕上,反而因为这个不必要的步骤大大增加了CPU的负担,从而影响了游戏的流畅程度。因此,在实际开发中,常用的优化方法就是只绘制当前屏幕的地图块。代码如下:


    view plain
    copy to clipboard
    print
    ?
        //计算单元格起始位置下标   
        int startIndexX =leftTopY/ MAP_TILE_SIZE;   
        int startIndexY =leftTopX/ MAP_TILE_SIZE;   
        //再使用上面得到的数据修改双循环绘制的条件即可,   
    for (int i = startIndexX; i  1 ; i++)   
                for (int j = startIndexY; j  1 ; j++)   //计算单元格起始位置下标 int startIndexX =leftTopY/ MAP_TILE_SIZE; int startIndexY =leftTopX/ MAP_TILE_SIZE; //再使用上面得到的数据修改双循环绘制的条件即可, for (int i = startIndexX; i 
    卡马克卷轴算法的引入
           上面的算法虽然在一定程度上解决了地图绘制的效率问题,但对于某些资源严重不足的手机,或者由于地图块比较小、循环次数过多的情况,仍然会造成画图时屏幕闪烁。因此,在这种情况下,仍然需要对上述算法做进一步的优化。

            不论采用哪种优化算法,一个基本的思路就是尽量减少绘制的次数,从而减少对系统资源的消耗。卡马克卷轴算法就是这样算法的一个经典例子。

    单方向卷轴
            对于横版游戏来说,如果角色向右侧移动,则地图向左侧滚动。由于角色每次移动若干个步长,因此地图中新画出的区域宽度也为若干个像素,那么如果让系统重绘所有屏幕区域,很明显,大部分区域都是和上一屏幕区域相同的,如此造成成了资源的浪费。而卡马克算法的思路就是——如果上一次绘制过的地图也能够部分重用到本次地图绘制上来就好了。那么很容易想到在内存中建立一个和屏幕一样大或略大的缓冲区即可很好的完成这个设想。


            由上图可以看到,区域B为相同的地图区域,这个区域在下一次屏幕重绘时,可以被重新利用。区域A是在下一次屏幕重绘中不被采用的区域,这区域应当被舍弃,但是如果稍微留意一下的话,不难发现区域A和区域C的面积大小其实居然是一样的。
           那么如果建立一个和屏幕大小相同的缓冲,在其被舍弃掉的绘制区域A中画上新的区域C,再把区域B和区域C拼合到屏幕上,是不是就能达到减少系统资源消耗的目的了呢?卡马克卷轴的基本原理正是如此。


           图显示了卡马克卷轴的最基本原理,首先在内存中建立一块和屏幕一样大小(或略大)的缓冲区。然后在本应由于地图移动而被舍弃掉的区域1上面绘制,由于地图滚动而出现的新地图区域。最后把两个区域按照地图的实际位置拼合到屏幕上。

    双轴滚动的卡马克卷轴
            对于俯视游戏,或者有Y轴卷动的游戏来说,单单一个方向的地图卷动并不够用。那么如果是出现两个方向的卷动会如何呢。不必担心,上面的思路算法一样能适应这种情况。


            由上图可以看到,区域D为相同的地图区域,这个区域在下一次屏幕重绘时,可以被重新利用。区域ABC是在下一次屏幕重绘中不被采用的区域,可以在这个3个区域上绘制上下一次需要重绘的区域A’B’C’。再将绘制好的四个区域拼合到屏幕的对应位置。

           上图显示了双轴滚动的卡马克卷轴的基本绘制原理,需要特别注意的是:在缓冲区的绘制顺序和在屏幕上拼合的顺序是完全相反的。

    卡马克算法的实现
    卡马克卷轴缓冲画法的一般步骤如下:
    1. 初始化所有地图数据,并且全屏绘制初始的地图
    2. 若人物移动,则调用摄像机算法,修正地图偏移量
    3. 地图偏移量不满足地图的边界条件,就重绘缓冲区
    4. 重绘缓冲区
    5. 后台缓冲区的四个子区按照顺序画到屏幕上

    地图类——Map的设计
    字段定义

    view plain
    copy to clipboard
    print
    ?
    //地图数据   
    public byte mapData[][];   
    //移动缓冲区的当前坐标窗口   
    public int sx,sy;   
    //地图图片   
    private Bitmap imgMap;   
    public GameView m_View;   
    //常量   
    public final static int MAP_TILE_SIZE =  24 ;   
      
    /** 缓冲区宽高,命名方式为:Carmack width or height */  
    private int bufWidth, bufHeight;   
    /** 缓冲区宽的图块数,与高的图块数*/  
    private int carTileWidth, carTileHeight;   
    /** 屏幕宽高命名方式为:screen width or height */  
    private int scrWidth, scrHeight;   
    /** 缓冲切割线,命名方式为:Carmack x or y */  
    private int carx, cary;   
    /** 地图在缓冲区的X 、Y偏移量,命名方式为:map offset x or y */  
    private int mapOffx, mapOffy;   
    /** 缓冲区,命名方式为:Carmack buffer */  
    public Bitmap carBuffer;   
    /** 缓冲区画笔,命名方式为:Carmack Graphics */  
    private Canvas carGp;   
    /** 缓冲区增大的大小(上下大小是一样的) */  
    private int buffSize;   
    /** 图片宽度的所切割的图块数量。 */  
    private int imageTileWidth;   
    /** 地图图片 */  
    private Bitmap mapImage;       
    Paint paint=new Paint();   
    /** 地图数组 */  
    private byte mapArray[][];   
    /** 图块大小,宽高一致 */  
    private int tileSize;   
    /** 图块的宽度数量,与高度数量 */  
    private int tileW, tileH;   
    /** 地图的宽高 */  
    private int mapLastx, mapLasty;   //地图数据 public byte mapData[][]; //移动缓冲区的当前坐标窗口 public int sx,sy; //地图图片 private Bitmap imgMap; public GameView m_View; //常量 public final static int MAP_TILE_SIZE = 24; /** 缓冲区宽高,命名方式为:Carmack width or height */ private int bufWidth, bufHeight; /** 缓冲区宽的图块数,与高的图块数*/ private int carTileWidth, carTileHeight; /** 屏幕宽高命名方式为:screen width or height */ private int scrWidth, scrHeight; /** 缓冲切割线,命名方式为:Carmack x or y */ private int carx, cary; /** 地图在缓冲区的X 、Y偏移量,命名方式为:map offset x or y */ private int mapOffx, mapOffy; /** 缓冲区,命名方式为:Carmack buffer */ public Bitmap carBuffer; /** 缓冲区画笔,命名方式为:Carmack Graphics */ private Canvas carGp; /** 缓冲区增大的大小(上下大小是一样的) */ private int buffSize; /** 图片宽度的所切割的图块数量。 */ private int imageTileWidth; /** 地图图片 */ private Bitmap mapImage; Paint paint=new Paint(); /** 地图数组 */ private byte mapArray[][]; /** 图块大小,宽高一致 */ private int tileSize; /** 图块的宽度数量,与高度数量 */ private int tileW, tileH; /** 地图的宽高 */ private int mapLastx, mapLasty;
    方法定义
     CarMapBuffer(int, int, int, int)构造器 
     CarMapBuffer(int, int, int)构造器的代理 
     setMap(Image, byte[][])设置地图参数 
     initBuffer()初始化绘制地图 
     scroll(int, int)卷动地图算法 
     updateBuffer(int, int)绘制缓冲区 
     getIndexCarX()获得切割线所在的图块索引X 
     getIndexCarY()获得切割线所在的图块索引Y 
     getBufferCarX()获得切割线在Buffer中的X位置 
     getBufferCarY()获得切割线在Buffer中的Y位置 
     getIndexBuffLastX()获得缓冲区后面的X索引 
     getIndexBuffLastY()获得缓冲区后面的Y索引 
     getTitleHeight()获得当前要绘制的图块高度的数量 
     getTitelWidth()获得当前要绘制的图块宽度的数量 
     copyBufferX(int, int, int, int, int) 由于x方向卷动造成的重绘 
     copyBufferY(int, int, int, int, int) 由于y方向卷动造成的重绘 
     getMapX(int, int) 获得地图图片的X坐标偏移 
     getMapY(int, int) 获得地图图片的Y坐标偏移 
     paint(Graphics, int, int)将缓冲区的内容分成4块依次拼合到屏幕上 
     drawBuffer(Graphics, int, int)绘制缓冲区方法 
     drawRegion(Graphics, Image, int, int, int, int, int, int, int, int)封装的drawRegion()方法 
     getGraphics()获得缓冲区画笔 
     getImage()获得缓冲区Image对象 
    步骤一的实现
    初始化所有地图数据,并且全屏绘制初始的地图,代码如下:

    view plain
    copy to clipboard
    print
    ?
    /**  
         * 初始化Buffer,全部地图绘制在此方法中完成  
         */  
        private void initBuffer()   
        {   
            int x, y, cx, cy;   
            for (int i =  0 ; i 
            {   
                for (int j =  0 ; j 
                {   
                    x = getMapX(i, j);   
                    y = getMapY(i, j);   
                    cx = j * tileSize;   
                    cy = i * tileSize;   
                    m_View.drawClipImg(cx, cy, tileSize, tileSize, x, y, mapImage, paint, carGp);   
                }   
            }   
    }  /** * 初始化Buffer,全部地图绘制在此方法中完成 */ private void initBuffer() { int x, y, cx, cy; for (int i = 0; i 
    步骤二、三的实现
    若人物移动,则调用摄像机算法,修正地图偏移量,若偏移量在[0,maplast]移动范围内移动,则有可能发生重绘

    view plain
    copy to clipboard
    print
    ?
    /**  
         * 卷轴滚动  *  
         * @param x  * X轴滚动  
         * @param y  * Y轴滚动  
         */  
        private void scroll(int x, int y)   
        {   
            try  
            {   
                x += mapOffx;   
                y += mapOffy;   
                // *************************************************   
                // 边界检测   
                if (x  0  || y  0 )   
                {   
                    return;   
                }   
                if (x > mapLastx)   
                {   
                    mapOffx = mapLastx;   
                    return;   
                }   
                if (y > mapLasty)   
                {   
                    mapOffy = mapLasty;   
                    return;   
                }   
                updateBuffer(x, y);   
                // *************************************************   
            }   
            catch (ArrayIndexOutOfBoundsException e)   
            {   
            }   
        }   
          /** * 卷轴滚动 * * @param x * X轴滚动 * @param y * Y轴滚动 */ private void scroll(int x, int y) { try { x += mapOffx; y += mapOffy; // ************************************************* // 边界检测 if (x  mapLastx) { mapOffx = mapLastx; return; } if (y > mapLasty) { mapOffy = mapLasty; return; } updateBuffer(x, y); // ************************************************* } catch (ArrayIndexOutOfBoundsException e) { } }

    步骤四的实现
            重绘缓冲区,地图的x方向卷动会造成列方向上的重绘(调用copyBufferX()方法),地图的y方向上的卷动会造成行方向上的重绘(调用copyBufferY()方法)。updateBuffer()方法用于针对不同的四个方向上的卷动进行copyBuffer()参数的初始化。
    view plain
    copy to clipboard
    print
    ?
    /**  
         * 更新缓冲区     *  
         * @param x     *            缓冲区新的地图X坐标  
         * @param y     *            缓冲区新的地图Y坐标  
         */  
        private void updateBuffer(int x, int y)   
        {   
            mapOffx = x;   
            mapOffy = y;   
            // 右移   
            if (x > carx + buffSize)   
            {   
                // while (carx   
                int indexMapLastX = getIndexBuffLastX();   
                if (indexMapLastX 
                {   
                    copyBufferX(indexMapLastX, getIndexCarY(), getTileHeight(),   
                                getBufferCarX(), getBufferCarY());   
                    carx += tileSize;   
                }   
                // }   
            }   
            // 左移   
            if (x 
            {   
                // do {   
                carx -= tileSize;   
                copyBufferX(getIndexCarX(), getIndexCarY(), getTileHeight(),   
                            getBufferCarX(), getBufferCarY());   
                // } while (carx > mapOffx);   
            }   
            // 下移   
            if (y > cary + buffSize)   
            {   
                // while (cary   
                int indexMapLastY = getIndexBuffLastY();   
                if (indexMapLastY 
                {   
                    copyBufferY(getIndexCarX(), indexMapLastY, getTitelWidth(),   
                                getBufferCarX(), getBufferCarY());   
                    cary += tileSize;   
                }   
                // }   
            }   
            // 上移   
            if (y 
            {   
                // do {   
                cary -= tileSize;   
                copyBufferY(getIndexCarX(), getIndexCarY(), getTitelWidth(),   
                            getBufferCarX(), getBufferCarY());   
                // } while (cary > mapOffy);   
            }   
        }  /** * 更新缓冲区 * * @param x * 缓冲区新的地图X坐标 * @param y * 缓冲区新的地图Y坐标 */ private void updateBuffer(int x, int y) { mapOffx = x; mapOffy = y; // 右移 if (x > carx + buffSize) { // while (carx  mapOffx); } // 下移 if (y > cary + buffSize) { // while (cary  mapOffy); } }

            重绘缓冲区的具体方法,该方法涉及到大量的坐标运算,而且由于卡马克点的存在经常会分成两个区域分两次进行重绘。见下图:

                  下面以x方向卷动为例举例
    view plain
    copy to clipboard
    print
    ?
    private void copyBufferX(int indexMapx, int indexMapy, int tileHeight,   
                               int destx, int desty)   
      {   
          int mapImagex, mapImagey, vy;   
          // 拷贝地图上面到缓冲的下面   
          int timer= 0 ;   
          for (int j =  0 ; j 
          {   
              mapImagex = getMapX(indexMapy + j, indexMapx);   
              mapImagey = getMapY(indexMapy + j, indexMapx);   
              vy = j * tileSize + desty;   
              m_View.drawClipImg(destx, vy, tileSize, tileSize, mapImagex, mapImagey, mapImage, paint, carGp);   
      
              timer++;   
          }   
          // 拷贝地图下面到缓冲的上面   
          for (int k = tileHeight; k 
          {   
              mapImagex = getMapX(indexMapy + k, indexMapx);   
              mapImagey = getMapY(indexMapy + k, indexMapx);   
              vy = (k - tileHeight) * tileSize;   
              m_View.drawClipImg(destx, vy, tileSize, tileSize, mapImagex, mapImagey, mapImage, paint, carGp);   
      
              timer++;   
          }   
          System.out.println("x:"+timer);   
      }   private void copyBufferX(int indexMapx, int indexMapy, int tileHeight, int destx, int desty) { int mapImagex, mapImagey, vy; // 拷贝地图上面到缓冲的下面 int timer=0; for (int j = 0; j 
    步骤五的实现
            将后台缓冲区的四个子区按照顺序画到屏幕上:

    view plain
    copy to clipboard
    print
    ?
    public void paint(Canvas g, int x, int y)   
        {   
            // 地图在缓冲中的坐标   
            int tempx = mapOffx % bufWidth;   
            int tempy = mapOffy % bufHeight;   
            // 切割线右下角的宽与高   
            int rightWidth = bufWidth - tempx;   
            int rightHeight = bufHeight - tempy;   
            // 画左上   
            drawRegion(g, carBuffer, tempx, tempy, rightWidth, rightHeight,  0 , x, y);   
            // 画右上   
            drawRegion(g, carBuffer,  0 , tempy, scrWidth - rightWidth, rightHeight,  0 , x + rightWidth, y);   
            // 画左下   
            drawRegion(g, carBuffer, tempx,  0 , rightWidth, scrHeight - rightHeight,  0 , x, y + rightHeight);   
            // 画右下   
            drawRegion(g, carBuffer,  0 0 , scrWidth - rightWidth, scrHeight   
                       - rightHeight,  0 , x + rightWidth, y + rightHeight);   
    }   
      
      
      
      
      
        /**  
         * 画图     *  
         * @param g           *           目标屏幕的画笔  
         * @param img        *            原图片  
         * @param x_src      *            原图片X坐标  
         * @param y_src      *            原图片Y坐标  
         * @param width      *            原图片宽度  
         * @param height     *            原图片高度  
         * @param transform *            旋转角度  
         * @param x_dest     *            目标屏幕的X坐标  
         * @param y_dest     *            目标屏幕的Y坐标  
         * @param anchor     *            画笔的锚点  
         */  
        private void drawRegion(Canvas g, Bitmap img, int x_src, int y_src,   
                                int width, int height, int transform, int x_dest,   
                                int y_dest)   
        {   
            // 作宽度检测   
            if (width  0  || height  0 )   
            {   
                return;   
            }   
            // 作超屏幕宽度检测   
            if (width > scrWidth)   
            {   
                width = scrWidth;   
                // 作超屏幕高度检测   
            }   
            if (height > scrHeight)   
            {   
                height = scrHeight;   
            }   
            m_View.drawClipImg(x_dest, y_dest, width, height, x_src, y_src, img, paint, g);   
    }  public void paint(Canvas g, int x, int y) { // 地图在缓冲中的坐标 int tempx = mapOffx % bufWidth; int tempy = mapOffy % bufHeight; // 切割线右下角的宽与高 int rightWidth = bufWidth - tempx; int rightHeight = bufHeight - tempy; // 画左上 drawRegion(g, carBuffer, tempx, tempy, rightWidth, rightHeight, 0, x, y); // 画右上 drawRegion(g, carBuffer, 0, tempy, scrWidth - rightWidth, rightHeight, 0, x + rightWidth, y); // 画左下 drawRegion(g, carBuffer, tempx, 0, rightWidth, scrHeight - rightHeight, 0, x, y + rightHeight); // 画右下 drawRegion(g, carBuffer, 0, 0, scrWidth - rightWidth, scrHeight - rightHeight, 0, x + rightWidth, y + rightHeight); } /** * 画图 * * @param g * 目标屏幕的画笔 * @param img * 原图片 * @param x_src * 原图片X坐标 * @param y_src * 原图片Y坐标 * @param width * 原图片宽度 * @param height * 原图片高度 * @param transform * 旋转角度 * @param x_dest * 目标屏幕的X坐标 * @param y_dest * 目标屏幕的Y坐标 * @param anchor * 画笔的锚点 */ private void drawRegion(Canvas g, Bitmap img, int x_src, int y_src, int width, int height, int transform, int x_dest, int y_dest) { // 作宽度检测 if (width  scrWidth) { width = scrWidth; // 作超屏幕高度检测 } if (height > scrHeight) { height = scrHeight; } m_View.drawClipImg(x_dest, y_dest, width, height, x_src, y_src, img, paint, g); }
           当然,地图的卷动和精灵的移动是分不开的,在本文中我们只阐述了游戏的地图绘制方法,关于精灵的绘制以及地图随精灵的位移而卷动,我们会在另一篇文章中做以介绍。

    总结
          卡马克算法是在进行2D游戏地图卷动的算法中内存痕迹最小、效率适中的算法之一。其核心的思想就是把地图卷动过程中移出屏幕(不需要在显示的部分)所占用的buffer区域,绘制上新的需要图块,在往屏幕上绘制的时候,通过四次绘制buffer把完整的地图重现。

          我们在实际的代码编写中按以下的方式进行。根据上面的基本思想,把地图分为四个块(十字形的将buffer划分为四块),用carx和cary来记录十字分区的中心坐标(相对于buffer的坐标,我把这个点叫卡马克分区点)。
    当地图向右移动的时候这时把卡马克分区点的坐标X方向加上一个tile的width,然后在从现在的卡马克分区点的坐标Y开始绘制提取出来的tileID对应的图象,注意是从当前的卡马克分区点的坐标Y开始绘制,当超出carHeight时在从0开始绘制直到结束,这样就完成了在水平方向上的更新。

           还有就是在水平移动卡马克分区点的时候是在buffer中循环的,也就是从0到carWidth的一个循环过程,Y方向上完全一致。最后是绘制过程,也就是将四个分区绘制出来,口诀就是左变右上变下,掌握好卡马克算法对手游开发很有帮助的。

           注:本文参考了网上关于卡马克算法的一些介绍并引用了其中的部分文字和图片。
    展开全文
  • 卡马克算法研究

    2008-12-26 11:02:17
    卡马克算法还是其中最高效的算法之一。卡马克真是一个程序的传奇开发者啊。他将地图缓冲起来,将缓冲分成4个部分,分别对应绘制在屏幕上来减少地图绘制次数从而提高游戏绘制效率。当然随之而来的一个问题是缓冲会...
    游戏引擎作为游戏制作的基础是保证游戏质量的最重要部分,目前主要包括两方面:背景绘制和动画播放。背景绘制在游戏中的直接体现就是地图的绘制方法。目前开发人员用的最多的还是Tiled Background方法。什么是Tiled Background,其实向大家都玩过的拼图游戏一样的绘制方式,将一幅游戏场景图切成几乘几的矩形,在绘制的时候用双循环将矩形重新排列拼成我们游戏中需要的场景。为了使用尽量少的图绘制出尽量多的背景,背景图像由无数的等大小的图形组成,这些图形通常使用正方形。而这些图形的种类是有限的,只是每一个都可能被使用了很多次。就好像墙上的瓷砖一样,可以通过有限的种类拼出无限的组合。那么组成背景的图形就被称为Tile,而使用Tile 拼成的背景就被称为 Tiled Background。这样的做法其实在早期的游戏开发中已经有了很广泛的应用,包括gba等游戏的开发也是如此绘制地图。该方法的优点是可以节省内存占用,减少重复图素所带来的内存压力。绘制方法上有很多不同的算法。但卡马克算法还是其中最高效的算法之一。卡马克真是一个程序的传奇开发者啊。他将地图缓冲起来,将缓冲分成4个部分,分别对应绘制在屏幕上来减少地图绘制次数从而提高游戏绘制效率。当然随之而来的一个问题是缓冲会占用一个屏幕大小图片的所占用的内存。该方法的绘制方式是:假如地图向右下移动也就是屏幕向左上移动,这时最上和最左的二排图块已经超出屏幕可视范围也就是不需要的图块。我们就用最新的最下的图块更新这个缓冲的最上的一排图块,用最新的最右的一排图块来更新该缓冲的最左一排图块。然后将屏幕缓冲按十字分成4块,右下角的块是地图当前没有改变的块可以不用更新直接用缓冲偏移绘制在
    屏幕的左上角位置,将缓冲中新更新后的最上部分图块绘制在当前屏幕最下位置,将最左新更新的图块绘制在屏幕最右位置将最新更新最左上角的部分绘制在最左下角这样就完成了屏幕的更新。我们在实际的代码编写中按以下的方式进行.根据上面的基本思想,把地图分为四个块(十字形的将buffer划分为四块),用KaMaKeX和KaMaKeY来记录十字分区的中心坐标(相对于buffer的坐标,我把这个点叫卡马克分区点).当地图向右移动的时候这时把卡马克分区点的坐标X方向加上一个tile的width,然后在从现在的卡马克分区点的坐标Y开始绘制提取出来的tileID对应的图象,注意是从当前的卡马克分区点的坐标Y开始绘制,当超出buffer Height时在从0开始绘制直到结束,这样就完成了在水平方向上的更新.还有就是在水平移动卡马克分区点的时候是在buffer中循环的,也就是从0到 buffer Width的一个循环过程,Y方向上完全一致.最后是绘制过程,也就是将四个分区绘制出来,口诀就是左变右上变下。一种简单的绘制方式是将地图缓冲分成3 块,不用更新的那块先绘制在屏幕上,需要更新的一个是水平方向的一排或是垂直方向的一排。那么将这两排更新后绘制在屏幕相应位置就可以了。具体位置计算是要用不需要更新的那个分区边界开始作为更新的起点到缓冲边界的循环绘制。动画播放也是和地图绘制方式差不多,就是把人物的各个动画帧拆开,用尽可能少的图素去拼出尽可能多的动画。
    展开全文
  • 卡马克缓冲算法

    2019-07-28 06:32:40
    NULL 博文链接:https://2528.iteye.com/blog/792164
  • 网上也有一些教程,也有很多解释,所以这里就不在介绍原理了,相信大家也都明白! 我这里只是将期封装成一个可以随便使用的类!~ 只是为了我和大家的使用方便! 如果有什么问题请与我联系!谢谢支持!...
  • 精度不是很高 代码如下 1 float SqrtByCarmack( float number ) 2 { 3 int i; 4 float x2, y; 5 const float threehalfs = 1.5F; 6 7 x2 = number * 0.5F; 8 y = number;... 9 i ...
  • 当屏幕在背景中移动时,实际上所涉及的 Tile 根本没有变化,或者只有一小部分发生了改变。所以我们可以创建一个背景图像缓冲(buffer),保存当前屏幕的背景图像,减少每帧得画图次数,可以大大提高速度。...
  • class MyMath { public: float GetSqrtMy(float num);...但是下午在公司电脑上测试的,当release时,卡马克的更快,大概快不到一倍,在debug,系统函数要快。但是在我自己电脑上却是上面的结果。很奇怪。
  • 卡马克卷轴算法实现android版

    千次阅读 2012-01-11 17:05:07
    相关资料 雨松MOMO带你走进游戏开发的世界之主角的移动与地图的平滑滚动 ...卡马克卷轴算法研究_地图双缓冲 http://wenku.baidu.com/view/a51f0b8ca0116c175f0e48c3.html 矩形相交判断 http://hi.baidu.co
  • 相关资料 雨松MOMO带你走进游戏开发的世界之主角的移动与地图的平滑滚动 ...卡马克卷轴算法研究_地图双缓冲 http://wenku.baidu.com/view/a51f0b8ca0116c175f0e48c3.html 矩形相交判断 http:/
  • 训练三-卡马克算法(郑鸿)

    千次阅读 2007-04-23 21:32:00
    今天仿照郑鸿的代码把这个算法搞懂了,他真是个高手。算法描述如下: 当屏幕在背景中移动时,实际上所涉及的 Tile 根本没有变化,或者只有一小部分发生了改变。所以我们可以创建一个背景图像缓冲(buffer),保存...
  •  快速平方根(平方根倒数)算法   日前在书上看到一段使用多项式逼近计算平方根的代码,至今都没搞明白作者是怎样推算出那个公式的。但在尝试解决问题的过程中,学到了不少东西,于是便有了这篇心得,写出来和...
  • 卡马克卷轴算法研究

    2011-10-05 20:14:02
    卡马克地图算法,用在RPG地图绘制中非常的广泛,有兴趣的可以下下来看看研究。
  • 1.5卡马克卷轴算法的引入 8 二、卡马克卷轴算法原理 9 2.1X|Y单轴滚动的卡马克卷轴 9 2.2X&Y双轴滚动的卡马克卷轴 10 三、卡马克卷轴的代码实现方法 12 3.1问题简化与算法步骤 12 3.2类CarMapBuffer设计 12 3.3步骤...
  • 卡马克算法-代码研究

    千次阅读 2007-04-27 15:06:00
    //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//@ CIRCULAR DIRTY BUFFER CIRCULAR DIRTY BUFFER CIRCULAR DIRTY BUFFER//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 944
精华内容 377
关键字:

卡马克算法