[游戏架构设计]利用观察者模式和虚函数实现多语言解决方案

 - by Hector

[游戏架构设计]利用观察者模式和虚函数实现多语言解决方案

游戏实现多语言的思路很简单:

把需要翻译的内容做出一个key-value的字典,不同语言加载不同语言的字典文件,程序设计时用一个单例类管理i18n,提供全局的根据key取得翻译的方法。

可以想象,多语言的游戏(或其他app)可能存在在各个Layer,可能有字体,语言翻译,图片翻译等等,而这些界面基本要不同程序协同完成,如果不统一管理挺势必会各种杂乱,用户切换语言也很让不同界面即时更新相当麻烦。这里我解决这个问题的一种方法,希望能起到抛砖引玉的作用。

基类有设置更新的虚函数

我在所有界面类(Layer)中继承了一个基类(或者利用多重继承单独做成一个接口),父类有设置和更新多语言的虚函数(根据复杂度,可分为设置、更新两个函数,或合并为一个)。

我们在所有需要设置多语言的界面中实现这个函数,并把所有多语言的设置和更新操作放在里面。这样,在多语言界面中,会自动按照界面的继承关系,一层一层的设置或更新其当前层的多语言,而互不影响。一个界面中加载的其他界面也会运行自己的多语言函数。

观察者模式实时更新

观察者模式:我们在程序的很多地方都有观察者,当通知者发送一个通知时,会将这些通知告知这些观察者,观察者收到通知后进行后续处理。

NotificationCenter是cocos2d-x的一个通知者类,我们可以在OnEnter的时候进行观察,在OnExit时结束观察。

结合上面的虚函数,我们在什么多语言相关的父类的OnEnter和OnExit中开始观察和释放观察者,子类不需要任何处理。这样,当用户更换语言后,发送一个更新语言的通知,由于所有界面都继承自这个基类,将层层更新本界面的语言设置。

优点

多语言方案简单统一,一个通用的基类负责监听多语言更新的通知,所有子类界面的多语言只需在规定的函数中完成即可,多程序员协同作业简单高效。

— 废话很多,以上

游戏中A*寻路算法的优化与改进

 - by Hector

游戏中A*寻路算法的优化与改进

上一遍文章中,我对A*算法进行了实现,并用跳步算法进行了优化。在游戏项目中,根据游戏的特点有很多优化的方式,可以选择使用。

在游戏中,一般将地图划分为一个一个的格子,将这些格子当做节点,进行寻路。

选择适当的地图大小和格子大小

  1. 如果地图太大,进行A*算法难免耗时过久,因此可以将地图划分为几部分,划分为阶段目的地,进行分段寻路。
  2. 格子的大小会是A*的消耗成倍增长,在不影响寻路效果的情况下,尽量让格子尽可能的大一些。

可以直接到达的点避免进行A*寻路

如果起点和终点直接并没有阻碍,则可以直接通过,避免进行A*寻路。具体做法:

  1. 计算起点和终点之间的直线方程y = a + bx,将格子的边界带入方程,得到边界点。
  2. 寻找边界点的格子,看是否可通过(可能有2,4个格子)。
  3. 两个边界点可能跨过一个格子,那么这个格子可能就漏掉了,可以根据直线是否大于45度来确定是由x得到y,还是由y得到x。

这里有详细介绍的:http://www.iamsevent.com/post/33.html

解决目的地不可到达造成的角色不移动

如果目的地不能到达,A*无法寻路,角色就无法移动,这对于游戏来说是很不合理的,最好的方式是走到离目的地最近的可通行的点上去。

解决方法一:将不可通行点设置为通行代价极高的点

解决这个问题很简单,原来不可通行的点直接被我们排除了,我们可以将这些不可通行的点通过代价设置很大就可以放到open列表中去,这样A*寻路到最后实在找不到通行的节点,会硬着头皮走这些不可能通过的点。这样我们总能找到一条可通行的路径。

最后,当角色移动时,如果通过的节点是不通行的,角色停止移动就达到我们的目的了。此方案精确,但是加入了不可通行的节点,A*算法的代价变大很多。

解决方案二:寻找替代点

假如,目的节点是草地(不可通行的),我们可以找个离目的节点和起始节点最近的节点,作为替代的目的地。寻找目的节点的方法如下:

  1. 寻找目的节点周围第一圈所有可通行的节点,将节点放在一个数组。
  2. 若第一圈一个可通行的节点都没有,则寻找第二圈,依次类推。
  3. 比较可通行的节点中最接近起始节点的节点作为替代目的地。

弊端:寻找替代点在孤岛回字形的目的节点中会失效。

弗洛伊德路径平滑算法

参考文章:http://www.iamsevent.com/post/34.html
当寻找到路径之后,进行路径的平滑处理。

  1. 合并共线的路径节点。
  2. 尽可能的去除多余的拐点。

合并共线

A,B,C三个节点,如果AB,与BC,斜率一样,则可以由A到C,去除B点。

比如A~Z点,循环处理AB,BC,CD…YZ节点,一遍循环则可以处理完毕了。

去除拐点

A,B,C,D四个节点,若,AD直接不存在障碍物,则去除B,C两点。算法如下:

for(int i= len-1; i>=0; i--)
{
    for(int j = 0;j<= i-2;j++)
    {
        if(Node[i]和Node[j]直接没有障碍物)
        {
            1. 去除i,j之间所有的点
            2. 重新计算len
            3. i = j;
            break;
        }
    }
}

ps: 以上方案并不是所有游戏必须的,根据游戏情况灵活运用。

A*算法和A*跳步算法的CPP实现

 - by Hector

A*算法本身很简单,很早之前就了解过,用c++简单实现了一下,并又跳步算法进行了优化。

A*算法

A*算法不同于深度和广度优先算法,是一种启发式搜索算法
其主要逻辑是不断估算当前点到目的节点的大概距离,选取最优的路径不断前进,直至到达终点。过程如下:
1. 将当前点放如一个未处理的节点列表,叫做openList,另外有个已处理的节点列表叫做closeList.
2. 从openList中找到最优节点n(可用堆算法|优先队列),针对其每一个子节点x:

  • a. 如果x在open中,如果x比open中节点的更好,则替换open中的节点,否则跳过x
  • b. 如果x在close中,如果x比close中的节点更好,则要删掉close中的节点,并将x放到open中,代表重新处理。否则跳过x.
  • c. 如果x不在open和close中,则放入open中,代表需要处理。

3. 重复2,直至到目标节点。到了目标节点后,从目标节点一步步后退,即可找到来的路径。

估价函数 f'(n) = g'(n) + h'(n)
f'(n)是估价函数,g'(n)是起点到终点的最短路径值,h'(n)是n到目标的最短路经的启发值。

跳步优化

跳步优化不同于常规的A*算法寻找当前节点所有的子节点,而是在于“跳过”一些明显不必经过的路,
抽象地说,就是在搜索时大量减掉明显无用的分支,使得朴素的搜索过程变得高效。
参考:

  • 1. 代码:https://github.com/qiao/PathFinding.js/blob/master/src/finders/JumpPointFinder.js
  • 2. 解说:http://plusplus7.com/lemonbag/jpsstudy

源码放在github: https://github.com/myourys/Algorithm 其中AStar.cpp文件。

/*=============================================================================
#     FileName: AStar.cpp
#         Desc: A星寻路算法
#       Author: Hector
#        Email: myourys@gmail.com
#     HomePage: http://www.yiwuye.com
#      Version: 0.0.1
#   LastChange: 2014-08-21 18:48:40
#      History:
=============================================================================*/
/*
 * A*算法不同于深度和广度优先算法,是一种启发式搜索算法
 * 其主要逻辑是不断估算当前点到目的节点的大概距离,选取最优的路径不断前进,直至到达终点。过程如下:
 * 1. 将当前点放如一个未处理的节点列表,叫做openList,另外有个已处理的节点列表叫做closeList.
 * 2. 从openList中找到最优节点n(可用堆算法|优先队列),针对其每一个子节点x:
 *      a. 如果x在open中,如果x比open中节点的更好,则替换open中的节点,否则跳过x
 *      b. 如果x在close中,如果x比close中的节点更好,则要删掉close中的节点,并将x放到open中,代表重新处理。否则跳过x.
 *      c. 如果x不在open和close中,则放入open中,代表需要处理。
 * 3. 重复2,直至到目标节点。到了目标节点后,从目标节点一步步后退,即可找到来的路径。
 *
 * 估价函数 f'(n) = g'(n) + h'(n)
 * f'(n)是估价函数,g'(n)是起点到终点的最短路径值,h'(n)是n到目标的最短路经的启发值。
 */

/*
 * 跳步优化
 * 跳步优化不同于常规的A*算法寻找当前节点所有的子节点,而是在于“跳过”一些明显不必经过的路,
 * 抽象地说,就是在搜索时大量减掉明显无用的分支,使得朴素的搜索过程变得高效。
 * 参考:
 * 1. 代码:https://github.com/qiao/PathFinding.js/blob/master/src/finders/JumpPointFinder.js
 * 2. 解说:http://plusplus7.com/lemonbag/jpsstudy
 */

#include <iostream>
#include <queue> /* priority_queue不支持遍历,利用vector容器和push_heap(堆算法)模拟一个优先容器 */
#include <vector>
#include <sstream>

#define kUseJumpNode 0

#define STR(A) #A

using namespace std;

/* 地图
 * 第一行 行列数
 * 第二行 起点,终端坐标
 * 地图 0:可通过 1:不可通过 坐标起点为左下角
 * 这里我们设定一个节点到相邻节点消耗为10,如果是对接线则为14.
 */

const char* MapStr = STR(
9 10                \n
6 3    6 6          \n
0 0 0 0 1 0 0 0 0 0 \n
0 0 0 0 1 0 0 0 0 0 \n
0 0 0 0 1 0 0 0 0 0 \n
0 0 1 1 1 0 0 0 0 0 \n
0 0 1 1 0 0 0 0 0 0 \n
0 0 1 0 0 0 0 0 0 0 \n
0 0 1 0 1 0 0 0 0 0 \n
0 0 0 0 1 0 0 0 0 0 \n
0 0 0 0 1 0 0 0 0 0 \n
);

class Point
{
public:
    int x,y;

    Point(int _x,int _y):x(_x),y(_y){};
    Point(){x =-1;y=-1;};
    Point& operator=(const Point & other){this->x = other.x;this->y=other.y;return *this;};
    bool operator==(const Point & other){return this->x == other.x && this->y== other.y;};
};

typedef struct _Node{
    Point pos;//当前点在迷宫中的位置坐标
    int g;//起始点到当前点实际代价
    int h;//当前节点到目标节点最佳路径的估计代价
    int f;//估计函数:f = g + h。
    _Node *father;//指向其父节点的指针
}Node;

//比较函数,用于堆操作
struct NodeCompare
{
    bool operator ()(Node *&n1, Node *&n2) const
    {
        return n1->f > n2->f; //小值优先
    }
};

class AStar{

public:
    AStar():_map(nullptr){};
    ~AStar(){clear();};
    int readMap(const char* str);
    void printMap();
    bool findRoad();
    void printRoad();
    void clear();
private:
    int estimate(const Point& pos); //估计点到目的地的值
    void initNode(Node &node,const Point& pos,int g,Node* father);
    void expandNode(Node* n);
    void getNabors(vector<Point> *nabors,Node* n);
    void getJumpNodes(vector<Point> *jumps,Node* n);
    bool validPoint(const Point& p);
private:
    Point _mapSize;
    Point _startPos;
    Point _endPos;
    int **_map;
    vector<Node*> _closeList;
    vector<Node*> _openList;
};

void AStar::clear()
{
    for(auto iter:_closeList)
        delete iter;
    for(auto iter:_openList)
        delete iter;
    if(_map)
    {
        for(int i =0;i<_mapSize.x;i++)
            delete []_map[i];
        delete []_map;
    }

}

int AStar::estimate(const Point& pos)
{
    return 10* (abs(_endPos.x - pos.x) + abs(_endPos.y-pos.y));
}

int AStar::readMap(const char* str)
{
    istringstream istr(str);

    istr>>_mapSize.x>>_mapSize.y;
    istr>>_startPos.x>>_startPos.y;
    istr>>_endPos.x>>_endPos.y;

    _map = new int *[_mapSize.x];
    for(int i = _mapSize.x-1;i>=0;i--)
    {
        _map[i] = new int[_mapSize.y];
        for(int j = 0;j< _mapSize.y;j++)
        {
            istr>>_map[i][j];
        }
    }
    return 0;
}

void AStar::printMap()
{
    for(int i = _mapSize.x-1;i>=0;i--)
    {
        for(int j = 0;j< _mapSize.y;j++)
        {
            cout<<_map[i][j]<<" ";
        }
        cout<<endl;
    }
}

void AStar::initNode(Node &node,const Point& pos,int g,Node* father)
{
    node.pos= pos;
    node.g = g;
    node.h = estimate(pos);
    node.f = node.g +node.h;
    node.father = father;
}

bool AStar::validPoint(const Point& p)
{
    if(p.x< 0 || p.y<0 || p.x > (_mapSize.x -1) || p.y > (_mapSize.y -1) )
        return false;
    return true;
}

bool AStar::findRoad()
{
    Node *start = new Node();
    initNode(*start,_startPos,0,nullptr);

    _openList.push_back(start);
    push_heap(_openList.begin(),_openList.end(),NodeCompare());
    while(1)
    {
        if(_openList.empty())
        {
            cout<<"can't find the road."<<endl;
        }
        Node *n = _openList.front();

        if(n->pos == _endPos) //到达终点
        {
            cout<<"Find the Road:"<<endl;
            return true;
        }

        //将第一个元素移到最后,并将剩余区间重新排序,组成新的heap
        pop_heap(_openList.begin(),_openList.end(),NodeCompare());
        _openList.pop_back();//删除最后一个元素n
        expandNode(n);
        _closeList.push_back(n);
    }
    return false;
}

void AStar::expandNode(Node* n)
{
    vector<Point> nodeList;
    if(kUseJumpNode)
        getJumpNodes(&nodeList,n);
    else
        getNabors(&nodeList,n);

    for(auto& pos:nodeList)
    {
        if(_map[pos.x][pos.y] == 1) //不可通过的点
            continue;

        int gVal;
        if(pos.x == n->pos.x || pos.y == n->pos.y)
            gVal= n->g +10;
        else
            gVal=n->g +14; //对角线

        vector<Node*>::iterator openResult;
        for( openResult=_openList.begin();openResult!= _openList.end();++openResult)
        {
            if((*openResult)->pos == pos) //在open列表
                break;
        }

        //在open列表,并且open列表中已经是最优的,跳过
        if(openResult!= _openList.end() && (*openResult)->g <= gVal)
            continue;

        //closed列表
        vector<Node*>::iterator closeResult;
        for( closeResult=_closeList.begin();closeResult!= _closeList.end();closeResult++)
        {
            if((*closeResult)->pos == pos) //在close列表
                break;
        }

        //在close列表,并且close列表中已经是最新的了,跳过
        if(closeResult!= _closeList.end() && (*closeResult)->g <= gVal)
            continue;

        //新节点为最优节点
        //如果在close列表
        if(closeResult != _closeList.end())
        {
            _closeList.erase(closeResult);
            delete *closeResult;
        }

        //如果在open列表
        if(openResult!= _openList.end())
        {
            _openList.erase(openResult);
            make_heap(_openList.begin(),_openList.end(),NodeCompare());
            delete *openResult;
        }

        Node *child = new Node();
        initNode(*child,pos,gVal,n);
        _openList.push_back(child);
        push_heap(_openList.begin(),_openList.end(),NodeCompare());
    }
}

void AStar::getNabors(vector<Point> *nabors,Node* n)
{
     for(int x = n->pos.x-1;x<= n->pos.x+1; x++) //针对每一个子节点
    {
        if(x < 0 || x > _mapSize.x -1)
            continue;
        for(int y = n->pos.y-1; y<= n->pos.y+1; y++)
        {

            if(y < 0 || y > _mapSize.y -1)
                continue;
            Point pos(x,y);

            if(pos == n->pos)
                continue;
            nabors->push_back(pos);
        }
    }
}

void AStar::getJumpNodes(vector<Point> *jumps,Node* n)
{
    if(!n->father)
    {
        getNabors(jumps,n);
        return;
    }

    auto fPos = n->father->pos;

    int x = n->pos.x;
    int y = n->pos.y;

    int dx = x - fPos.x;
    int dy = y - fPos.y;

    /*
     * 这里假设 1 0 从左下角不能到右上角
     *          0 1
     */
    if(dx!= 0 && dy!= 0) //父节点和当前节点在对角线上
    {
        //当前节点旁边的两个点,并且远离父节点
        if(validPoint(Point(x,y+dy)) && _map[x][y+dy]==0)
            jumps->push_back(Point(x,y+dy));
        if(validPoint(Point(x+dx,y)) && _map[x+dx][y]==0)
            jumps->push_back(Point(x+dx,y));

        //对角线的另一个点
        if(validPoint(Point(x+dx, y+ dy)) && ( _map[x][y+dy]==0 || _map[x+dx][y]==0))
            jumps->push_back(Point(x+dx,y+dy));

        //靠近父节点的两个角
        if(validPoint(Point(x-dx,y+dy)) && _map[x - dx][y] ==1 && _map[x][y+dy]==0)
            jumps->push_back(Point(x - dx, y + dy));
        if(validPoint(Point(x+dx,y-dy)) && _map[x][y-dy] ==1 && _map[x+dx][y]==0)
            jumps->push_back(Point(x + dx, y - dy));
    }
    else //父节点和当前节点在水平或者垂直线上
    {
        if(dx == 0) //水平线上
        {
            if(validPoint(Point(x, y + dy)) && _map[x][y + dy]==0)
            {
                jumps->push_back(Point(x, y + dy));
                if(validPoint(Point(x+1, y) ) && _map[x+1][y]==1)
                    jumps->push_back(Point(x+dx, y+dy));
                if(validPoint(Point(x-1, y) ) && _map[x-1][y]==1)
                    jumps->push_back(Point(x-1, y+dy));
            }
        }
        else
        {
            if(validPoint(Point(x+dx, y))  && _map[x+dx][y]==0)
            {
                jumps->push_back(Point(x+dx, y));
                if(validPoint(Point(x, y+1) ) && _map[x][y+1]==1)
                    jumps->push_back(Point(x+dx, y+1));
                if(validPoint(Point(x, y-1) ) && _map[x][y-1]==1)
                    jumps->push_back(Point(x+dx, y-1));
            }
        }
    }
}

void AStar::printRoad()
{
    int **tmpMap = new int*[_mapSize.x];
    for(int i=0;i<_mapSize.x;i++)
        tmpMap[i] = new int[_mapSize.y];
    for(int i=0;i<_mapSize.x;i++)
        for(int j=0;j<_mapSize.y;j++)
            tmpMap[i][j]=_map[i][j];
    Node* n= _openList.front();
    while(n)
    {
        tmpMap[n->pos.x][n->pos.y] = -1;
        n = n->father;
    }

    for(int i=_mapSize.x-1;i>=0;i--)
    {
        for(int j=0;j<_mapSize.y;j++)
        {
            if(tmpMap[i][j] == -1)
                cout<<"# ";
            else
                cout<<tmpMap[i][j]<<' ';
        }

        cout<<endl;
    }

    for(int i=0;i<_mapSize.x;i++)
        delete []tmpMap[i];
    delete []tmpMap;
}

int main()
{
    AStar astar;
    astar.readMap(MapStr);
    astar.printMap();
    cout<<endl;
    if(astar.findRoad())
        astar.printRoad();
    return 0;
}

vps自动备份数据到百度网盘

 - by Hector

1.编写脚本

我把数据分为三类

  1. mysql数据库,需要导出sql
  2. 文件夹
  3. 文件

将数据拷贝到一个以当前日期命名的文件夹下面,最后压缩打包。
新增减少备份的数据新增减少要备份的目录或文件即可。

2.上传到百度网盘脚本

上传文件有两种方式,调用百度个人网盘接口和存储cookie模拟登陆。
尝试自己调用百度pcs接口,不但要申请权限(要一个星期审核),还很麻烦。网上搜了一下代码,发现这个是最好用的:https://github.com/houtianze/bypy
使用很简单:python bypy.py [命令] [参数]
第一次使用需要根据提示,打开一个网页,输入授权码。

请先确认此脚本可以上传文件后再加入备份脚本里面自动上传。

数据是存放在网盘的App/bypy目录下,这里我建立了vps-backup目录存放vps的数据。

3.定时任务

定时任务用到了crontab.

  1. 安装:yum install -y vixie-cron
  2. 添加任务crontab -e,格式如下:

    *  *  *  *  *  command
    分 时 日 月 周 命令
    注意服务器可能是utc时间,比如我的:30 19 * * * /home/vps-backup.sh,实际是每天晚上三点半执行备份命令。

  3. 启动服务:service crond start

附我的备份脚本,你可以根据实际情况新增需备份的文件或目录,以及脚本和数据存放路径。https://gist.github.com/myourys/ba7edd3d19b8e3ba09a4