分类: 2009 November

后缀数组–Suffix Array

作为一个真正的小白,我无时无刻不被大牛们晒得渣都不剩..这个星球上牛人太他妈多了,一不小心就被其四射的光芒彻底刺伤.后缀数组,是一个灰墙灰墙邪恶的东西,会的话自然是居家必备,杀人无形,很可怜的是,我不会..囧rz.这个星期看完论文就回来把下面两道题给切了..

(1) 从一大坨的字符串中找出最长的回文子字符串.

(2) 找出N个字符串的最长公共子序列.

使用Python语言和Pygame模块编写游戏.2

本文接上一篇 : 使用Python语言和Pygame模块编写游戏.1

欢迎回来

在本教程的第1部分中,我们创建了一个很简单的演示程序”Creeps”–可以在屏幕四处走动,并且碰墙能够反弹的生物.它并不是什么真正的游戏,但确实一个很好的起点.

在这一部分中,我们将会扩展这个程序,使它更像是一个游戏.当然,这还远不是终点.最终的程序比起真正有趣的游戏还相差甚远,但是我们将会介绍到很多游戏设计的概念,而且,演示程序也的确有点游戏的味道了.

creeps_screenshot_2

代码

这一部分的完整的代码可以从这里下载.跟以往一样,我强烈建议你下载代码并且运行它,在阅读本教程时不妨用编辑器打开它.

目标

在教程的这一部分中,我将会谈到:

  1. 更养眼的背景
  2. 用户消息的响应
  3. creep更为复杂的状态
  4. 简单的动画
  5. 绘制文本

好了,让我们开始吧.

背景

在第1部分中,我们仅仅是用沼泽地般的浅绿色喷绘在屏幕中,将之当成是背景.我们希望游戏更受欢迎些,因此,我们再也不能这么做了.

现在,我们将用漂亮的背景图片平铺到屏幕上,以此来创建一个有边界的creep的活动区域.

也许你会问,什么是平铺呢?简单点说,平铺就是重复地使用小的图层来覆盖一个大的图层.这里,我们将会用这张图片:

brick_tile

我们只是简单地用它铺满屏幕.实现此功能的是draw_background函数:

def draw_background(screen, tile_img, field_rect):
    img_rect = tile_img.get_rect()

    nrows = int(screen.get_height() / img_rect.height) + 1
    ncols = int(screen.get_width() / img_rect.width) + 1

    for y in range(nrows):
        for x in range(ncols):
            img_rect.topleft = (x * img_rect.width,
                                y * img_rect.height)
            screen.blit(tile_img, img_rect)

    field_color = (109, 41, 1)
    draw_rimmed_box(screen, field_rect, field_color, 4, Color('black'))

函数中的循环完成了平铺.最后一句代码创建了游戏区域–一个深棕色的矩形,creep的活动将被限制在这里.绘制游戏区域的函数是draw_rimmed_box–它非常简单,你可以独自学习它.[1]

在游戏截图的右方,你能看见另外一个格子,它的上面写了一些文字.它们是分开来绘制的,我们很快就会谈到.

嘿,你点中我了!

到目前为止,我们的游戏唯一能处理的用户生成的事件就是当用户点击关闭按钮时,退出游戏而已了.这并没有什么交互性,所以我们将提升这一点.下面是在主循环中全新的用户消息响应函数:

for event in pygame.event.get():
    if event.type == pygame.QUIT:
        exit_game()
    elif event.type == pygame.KEYDOWN:
        if event.key == pygame.K_SPACE:
            paused = not paused
    elif (  event.type == pygame.MOUSEBUTTONDOWN and
            pygame.mouse.get_pressed()[0]):
        for creep in creeps:
            creep.mouse_click_event(pygame.mouse.get_pos())

我们新增了许多特性.首先,有一个句柄,它对用户敲下空格键做出反应,使得游戏暂停–你现在就可以试试.

第二个句柄稍稍复杂了一点.当鼠标左键在游戏活动区域按下时,每个creep都会调用它的mouse_click_event函数,传入的参数是光标所在的坐标.

其中的想法是简单的:creep有生命值(health),一旦鼠标成功点中creep,它的生命值就会下降.在每一个creep的上方都会有一个生命条,它由红色与绿色的比例来表现生命值的多少(试着点击creep,看看它们生命值的变化).

这一特性的实现也是相当简单的,下面是鼠标点击的消息响应函数:

def mouse_click_event(self, pos):
    """ The mouse was clicked in pos.
    """
    if self._point_is_inside(vec2d(pos)):
        self._decrease_health(3)

你可以看到,当点击发生时,如果光标在creep内部,则creep的生命值就会下降.让我们看下程序是如何运行的:

def _point_is_inside(self, point):
    """ Is the point (given as a vec2d) inside our creep's
        body?
    """
    img_point = point - vec2d(
        int(self.pos.x - self.image_w / 2),
        int(self.pos.y - self.image_h / 2))

    try:
        pix = self.image.get_at(img_point)
        return pix[3] > 0
    except IndexError:
        return False

这一函数用于识别光标是否在creep内部,更具体一点说,是否在creep图像的实体部分内部.点中框住creep的边界却没点中creep的身体是不会返回真值的.它是这样实现的:

首先,如果鼠标点击时,光标不在屏幕内,那就谈不上点击creep了.就算光标在屏幕内,我们也不确定是否点中了creep实体部分.因此,点击点的像素将被计算,如果alpha值是正的,那么点击点是在creep体内的,否则,鼠标点中的是不在creep体内的那一部分.(查看[2])

绘制生命条是很简单的,你应该能够读懂实现它的代码(这里使用了draw函数来代替教程第1部分中的blitme函数).

Arthur1989 注 : 未完,待续

[ Update  2009/11/22 ]

简单的动画

当creep生命值下降到0时回发生什么呢?我希望你已经做过实验了,假如你没有的话,你可以看看下面的一张截图:

explode1

然而,如果你运行过这个演示程序的话,你肯定已经注意到了creep发生的爆炸动画–它随着时间而改变.

那么,什么是动画呢?简单地说,动画是一组图片快速地刷新在同一位置,这形成了动画的效果.其实,它与在屏幕上爬动的creep没有什么不同(毫无疑义地,你甚至可以认为一整个游戏都是动画),但是,对于这疑教程来说,这里的动画特指 静态 的,它仅限于发生在同一位置.

动画功能是由模块simpleanimation.py实现的,它包含在下载的代码包中,你可以试着单独运行该模块(通过if __name__ == “__main__”这一python命令).

simpleanimation.py的代码是简单易懂的,它并没有什么复杂的.SimpleAnimation接受一组图片对象,在指定的时段内将它们绘制在屏幕上.请注意爆炸是如何通过单独一张图片模拟出来的,它将该图片旋转90度,然后,SimpleAnimation很流畅的画出旋转后的图片,这将前后两张图片很好的衔接在一起.

回到creeps.py中,当creep的生命值为0时,程序调用SimpleAnimation模块来显示它的爆炸:

def _explode(self):
    """ Starts the explosion animation that ends the Creep's
        life.
    """
    self.state = Creep.EXPLODING
    pos = ( self.pos.x - self.explosion_images[0].get_width() / 2,
            self.pos.y - self.explosion_images[0].get_height() / 2)
    self.explode_animation = SimpleAnimation(
        self.screen, pos, self.explosion_images,
        100, 300)

这段代码是很直白的,真的..

Creep的状态

本部分教程中的creep比起第1部分教程中的creep要复杂了不少.它们有随时降低的生命值,而且它们还会爆炸然后消失.为了应付程序的复杂性,我们将会使用状态机(译注: 原文为state machine).

对于随意的一个creep,它可以处于什么状态呢?首先是爬来爬去的正常状态,然后是一个爆炸状态,最后是一个消失状态,creep对象不再存在.我们将这些状态用代码描述如下:

(ALIVE, EXPLODING, DEAD) = range(3)

查看一下update函数–每一creep的更新取决于它处于什么状态.对于draw函数也是如此.现在,我建议你找到self.state代码,仔细看看creep的状态是怎么被使用的,怎么被更新的.

Sprites和Sprites组

我希望你已经察觉到了,在教程的第1部分和第2部分中,Creep类都是从pygame.sprite.Sprite.继承的.Sprite是Pygame中的一个功能类,它实现了一些有用的功能,以此来控制构成游戏中角色的动画的图片.(在游戏编程中,这经常被成为sprites).

在教程第1部分中,我根本没有使用它的任何函数.这里,我通过一个sprite组来调用它.

现在,主函数中的一组creep已经被封装成一个sprite组了.很炫的一个效果是,任何时候一个sprite被添加进sprite组时,它会记下它所加入的组的标号,因此,调用self.kill()将使它从它属于的所有sprite组中被删除,这也就使得,它在整个游戏的层面上被删除了.Creep中的update函数是在一个creep爆炸发生后调用它的kill()函数的.通过这种方法,游戏主循环中不必显示地记下哪些sprite是活的–它们自己就会这么做了.

尽管如此,我还是不确定我是否会使用Sprites的完整功能.对我而言,这些不过是一个指引罢了,它并不是必须的.以后,也许我会发现,使用它我的代码可以组织得更加有效;但是,也许我也会发现,我根本就不需要它.见机行事吧.[4]

一点小结

就这样,教程的开始部分中提出的目标已经实现了.我们把一个非常简单的creep演示程序变成了一个初步的游戏.客观地讲,比起从这个小游戏中得到了什么乐趣,看起来你更像是在向危险的RSI症迈进.但是,对于450行的Python代码来说,我们已经做得相当不错啦!

在以后的教程中,我们将会继续开发这些代码,使之变成一个真正的游戏,所以,做好准备吧.哦,对了,有空就做做下面的练习题吧,我保证你会从中得到更深的启发的.

练习
  1. 按空格键使程序暂停,猛击creep,恢复游戏.注意到creep的生命值下降了没有?试着修复这个bug.提示,在程序暂停时,屏蔽鼠标事件响应.
  2. 注意到当creep斜线运动时,它的生命条比起直线运动时离身体更远一些吗?你能想出这是为什么吗?(提示:请再一次阅读教程第1部分中,我是如何处理旋转后的图片的大小的).提出一个改正的方法.
  3. 重新读一遍_explode函数的代码.注意我对爆炸位置的复杂计算.为什么这是必须的呢?试着修改它(比如说,删去考虑图片大小的那部分代码)然后看看右什么不同.
  4. 在比分板中添加一个计时器.它从00.00开始计时,每秒中加1.当游戏结束时,计时器应该结束计时.
  5. 让creep的速度来得更猛烈些吧!游戏会变得非常刺激的!

字典树–Trie树

今天做了两道水题,要多水有多水…

其中有一道题是这样子的:

(6)  已知手机按键上数目到字母的映射:( 除了 “Q” 和 “Z”)

Trie

给你一份dict.txt,然后给你一串数字(长度最长为12),要求你从dict.txt中找出匹配的字符串.如,给出4734,则dict.txt中与之匹配的只有GREG.
[解] 看完题目我是吓到了.因为我以为这道题的数据规模会是很大,虽然3^12≈5*10^5不算是很大,但是如果测试数据有很多组的话,应该还是会TLE的.既然这样,那就只得对dict.txt建字典树了吧..对于这道题来说,建树过程是很容易的,每个节点有26个子节点,顺着字符串一路建下去就OK了.但是,有点麻烦的是,对输入的一串数字,如何查找出与之匹配的所有字符串.一般的字典树查找的确定性是明显的,存在就是存在,不存在就不存在.而这题中,根据映射关系,一个数字是对应于3个字母的,因此实际上的查找需要用到搜索,对于每一数字,遍历它的3种可能..我写字典树时就卡在这里了,然后很无聊的想了下,这么做实际上复杂度就变成了1+3^1+3^2+…+3^len=3^(len+1),而一般的字典树的复杂度为O(len),因此其实还不如暴力来得快…在一筹莫展的时候,突然发现漏读了题目的数据规模了,测试数据竟然只有一个,于是直接将dict.txt中每一行字符串转为数字串看是否与目标相同就行了..大汗..

迅速秒完水题,觉得写了不短时间的字典树代码不能浪费了,于是修改了下,部分代码贴在下面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#define max_num 26
 
struct node
{    
     bool is_word ; // 根到该节点是否对应一个字符串
     node *next[max_num];
     node()
     {
         is_word = false;
         for(int i = 0;i<max_num;i++)
              next[i] = NULL;
     }
};
 
class Trie
{
public:
 
     node *root;  //根节点
 
     Trie(){root = NULL;}
 
     bool search(const string str) //查找
     {
         node *location = root;
         for(int i = 0;i<str.length();i++)
         {
              if(location->next[str[i]-'a'] == NULL)
                   return false;
              location = location->next[str[i]-'a'];
         }
         return location->is_word;
     };
 
     void insert(const string str)    //插入
     {
         if(root == NULL)
              root = new node;
         node *location = root;
         for(int i = 0;i<str.length();i++)
         {
              int site = str[i] - 'a';
              if(location->next[site] == NULL)
              {
                   location->next[site] = new node;
                   location = location->next[site];
              }
              else
                   location = location->next[site];
         }
         location->is_word = true;
     };
 
 
     bool del(const string str)       //删除
     {
         node *location = root;
         for(int i = 0;i<str.length();i++)
         {
              if(location->next[str[i]-'a'] == NULL)
                   return false;
              location = location->next[str[i]-'a'];
         }
         if(location->is_word)
              location->is_word  = false;
         else
              return false;
         return true;
     }
 
};

PS: 短发的小德把长发的纳豆横扫了,看来以后都留不了长发了..