benegg blog

从本篇文章开始, 我将写一序列游戏开发的文章, 讲述做一个连连看游戏的例子, 既锻炼自己, 也帮助别人. 最终, 游戏会加上网络功能.

连连看算法

如图, 为了找出A, B两点之间的连接路径, 首先过这两点作4条线段, 线段的两端便是地图边缘, 两条与横坐标轴平行, 另两条与纵坐标轴平行. 先考虑与横坐标轴平行的两条.

在两条线段上各取一点C和D, 此两点处在一条与纵坐标轴平行的直线上. 那么, ACDB这条路径便是一条可能的A, B两点的连通路径.

Continue reading »

Written by benegg at 2009-05-31 13:41:30 | tags: 游戏开发, 连连看开发实践

网游服务器的主循环中, 必须做如下事情: 读取客户端请求(read_request), 把请求交给处理过程(handle_request), 读取异步过程的结果(read_result), 同步指令给客户端(sync_client). 因为read_request和read_result可能被阻塞, 所以先测试(test)再读取. 同时还要考虑时钟周期, 让主循环休眠一段时间. 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

while(1){
    n = test_clients();
    if(n > 0){
        read_request();
        handle_request();
    }
 
    n = test_async_handlers();
    if(n > 0){
        read_result();
    }
 
    sync_client();
 
    sleep();
}

显然, sleep白白浪费了计算资源, 应该避免. 可以把sleep浪费的资源用来做别的事. 可以变成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

while(1){
    while(还不足一个时钟周期){
        wait_request_and_result(timeout);
        if(first_request_of_each_client){
            handle_request();
        }else{
            new_request_queue.append();
        }
        read_result();
    }
 
    if(old_request_queue.count > 0){
        read_request();
        handle_request();
    }
    old_request_queue += new_request_queue;
 
    sync_client();
}

问题是, wait_request_and_result()会很难实现.

Written by benegg at 2009-05-28 18:13:19

如果需要同时从多个文件, 多个网络连接中读取数据, 除了使用多线程, 使用IO多路复用接口也是常用, 有时是更有效的方法.

最常用的IO多路复用接口是select, epoll, kqueue, signal. 但是, 这些接口除了性能各不相同, 连API也各不相同. 为了避免程序和IO多路复用接口绑定, 所以需要封装一层. 我参考了select, epoll这两种接口, 还参考了lighttpd对这些接口的封装, 并最终开发了一套封装接口.

首先看select:

数据结构: fd_set
初始化: FD_ZERO
注册: FD_SET
等待信号: select

再看epoll:

数据结构: epoll_event
初始化: epoll_create
注册: epoll_ctl
等待信号: epoll_wait

封装的接口如下:

/* 创建IO复用接口 */
struct fdevents *fdevents_init(int max_fds);

/* 添加文件描述符要监听的事件. */
int fdevents_add(struct fdevents *evs, struct fdevent *ev);

/* 删除文件描述符要监听的事件. */
int fdevents_del(struct fdevents *evs, struct fdevent *ev);

/* 修改文件描述符要监听的事件. */
int fdevents_mod(struct fdevents *evs, struct fdevent *ev);

/* 类似 FD_SET, 但fd在调用前必须已经被监听 */
int fdevents_set(struct fdevents *evs, int fd, int flags);

/* 类似 FD_CLR, 但fd在调用前必须已经被监听 */
int fdevents_clr(struct fdevents *evs, int fd, int flags);

/*
等待监听队列监听的事件, 返回就绪的文件描述符数目.
就绪的信号放在fdevents.ready_events数组中.
*/
int fdevents_wait(struct fdevents *evs, int timeout_ms);

相关阅读: The C10K problem

Written by benegg at 2009-05-26 16:15:37

服务器的各种不同服务占用的资源(成本)各不相同, 即使使用排队和重新安排次序的方式, 仍然不可避免低成本服务被高成本服务阻塞的情况出现. 一般会利用操作系统的多进程或者多线程将服务分成流水线, 交替的处理各个服务的一小段.

不过, 具体应该开多少个进程, 如何分发请求, 处理进程的分发请求的进程如何通信, 编程接口如何设计, 等等, 都需要确定. 本文讨论了我自己的一种想法.

Continue reading »

Written by benegg at 2009-05-15 22:43:02