毕业设计（论文）-Linux平台下基于C的贪食蛇游戏设计与实现

Linux 平台下基于 C 的贪食蛇游戏设计与实现 姓 名 系 别、 专 业 导 师 姓 名、职 称 完 成 时 间 目 录 摘 要 . I ABSTRACT . II 绪 论 . 1 1.1 论文选题依据 . 1 1.2 贪食蛇游戏选题背景 . 1 1.3 贪食蛇设计概述 . 1 平台简介 . 2 2.1 系统介绍 . 2 2.1.2 Linux 系统的主要特点 . 2 2.1.3 LINUX 的组成 . 2 2.2 开发工具 . 3 2.2.1 C语言简介 . 3 2.2.2 GTK简介 . 3 2.2.3 Linux 编译工具 GCC简介 . 4 2.3 GTK环境的搭建 . 4 3 系统分析 . 5 3.1 可行性分析 . 5 3.1.1 技术可行性 . 5 3.1.2 经济可行性 . 5 3.1.3 操作可行性 . 5 3.2 需求分析 . 5 3.2.1 功能要求 . 5 3.2.2 性能要求 . 6 3.2.3 运行要求 . 6 4 系统概要设计 . 6 4.1 程序初始化 . 6 4.2 程序流程 . 6 4.2.1 系统模块 . 6 4.2.2 系统流程 . 6 5 系统详细设计 . 8 5.1 系统界面 . 8 5.2 对象模型设计 . 11 5.3 食物及蛇状态的初始化及食物的出现 . 12 5.4 游戏运行中的设计思路 . 12 5.5 游戏规则 . 13 5.6 游戏实现以及其代码 . 13 5.6.1 蛇移动的实现 . 13 5.6.2 蛇死亡的判断 . 14 5.6.3 蛇到达边框时从另一端出现和传送的实现 . 14 6 贪食蛇 AI 的算法设计 . 15 6.1 蛇自己寻找食物的算法设计 . 15 6.1.1 贪心算法 . 15 6.1.2 利用贪心算法实现最短路径的选择 . 16 6.2 蛇避开吃到自己身体的算法设计 . 17 6.3 地图 2 需要新增的一些判断 . 18 7 调试以及测试结果分析 . 19 7.1 系统测试 . 20 7.2 在软件的测试过程中发现的几个小问题 . 20 7.3 系统需要的改进与提高 . 21 结束语 . 22 参考文献 . 23 致 谢 . 错误 !未定义书签。 附 录 . 24 I 摘 要 贪食蛇游戏操作简单方便，老少皆宜，是一款不错的小游戏。而 Linux挟其价格低廉、品质良好与稳定的优势，正吸引着众多以 PC为主工作、学习和娱乐的人们。 基于 Linux平台下的贪食蛇游戏采用的 Linux底下 C语言和 GTK图形化编程工具编写，操作简单。玩家首先进入游戏，在游戏中可以对游戏进行暂停、退出等操作，还加入了双人对战模式，丰富了 游戏，增大游戏的娱乐性。 本文分几部分阐述了基于 Linux下的贪食蛇游戏的开发过程，分章节较详细的介绍了游戏的结构和设计实现过程，并详细画出了系统流程图，还详细介绍了各个功能完成相关技术，写出了调试以及测试结果分析。 关键词 ： GTK； Linux操作系统；贪食蛇游戏 II ABSTRACT Snake game is easy and convenient to operate.It is a good game for all ages. Relying on its low price, good quality and stable competitive advantage,the Linux is invisibly attracting large numbers of people who base PC as main work、 Learning and entertainment platform. The Linux platform-based Snake game is easy to operate by adopting the C language and GTK graphical programming tools.After entering the game, the players can do some operations,like “pause”, “exit” ect.The added two-war mode enriches the game, and makes the game more entertaining. This paper describes the development process of the Linux-based Snake game in several parts. A comparatively detailed introduction is given to the structure of the game and the process of the designs implementation in sub-sections. A system flow chart is drawn in details.The technology related to the completion of various functions is also given in details. Debugging and an analysis of the test results is written out. Key words: GTK； Linux operating system； Snake Game 1 绪 论 1.1 论文选题依据 Linux 挟其价格低廉、品质良好与稳定的竞争优势，正无形无影地吸引众多以 PC为 主工作平台上的人们。随着科学技术日新月异的发展， Linux 提供了更多图形接口的桌面操作环境和应用软件，操作更加简单方便。 Linux 是源代码开放的操作系统，是当今优秀的操作系统之一。标准 Linux经过小型化裁剪之后的专用 Linux操作系统即嵌入式 Linux，已成为当今的一大热点，它能够固化于容量只有几 KB或者几 MB的存储器芯片或者单片机中，适合于特定嵌入式场合，目前已经开发成功的嵌入式系统中，大约一半的系统使用嵌入式 Linux。嵌入式 Linux得到众厂商的青睐，在工程实践中应用也十分广泛，我校的嵌入式系统课程 同样也采用嵌入式 Linux进行教学工作，因此，此次游戏设计环境也采用 Linux系统。 Linux内核的大部分代码是由 C语言编写的， Linux应用程序也多由 C语言编写 【 1】 。C 语言是结构化、模式化的语言，程序可移植性好，运算符丰富、代码效率高，它兼有汇编语言和高级语言的优点，既适合于开发系统软件，也适合于编写应用程序，被广泛应用于事务处理、科学计算、工业控制、数据库技术等领域。此次设计语言环境也选用 C语言。 GTK 是 Linux 平台下比较好的一个 C 语言图形开发工具，所以本次也选择了 GTK图形开发工具。 1.2 贪食蛇游戏选题背景 随着经济的快速发展，人们生活的步调日益加快，计算机的地位在人们的生活中已日益突出，基于各种操作系统的娱乐游戏也越来越多、越来越大众化，成为人们生活中必不可少的一部分。而随着人们生活品质的提高，电脑游戏也越来越多元化，贪食蛇就是其中一种。贪吃蛇这一游戏简单易行，操作方便，娱乐性较强，吸引了不少人。这一款游戏紧紧地抓住了人们的心理，虽然简单，却起乐无穷，贪食蛇游戏操作简单方便，老少皆宜，是一款不错的小游戏 ,而实现二人对战使游戏更具新意也更有趣。 该游戏给人们带来了追逐的快感，以及成 功后的满足感，对于一直处于高压下的现代人是很好的放松工具。 1.3 贪食蛇设计概述 该游戏主要功能包括：选择玩家人数与游戏模式、选择游戏地图、开始游戏、暂 2 停游戏、退出游戏等。 选择玩家人数：玩家可以选择单人模式、双人对战模式和人机对战模式进入游戏。 选择游戏地图：玩家可以选择玩哪个地图，暂时有 2个地图供选择，每一个地图将会有不同的墙壁和不同的传送点。 开始游戏：玩家 1通过方向键，玩家 2 通过 W S D A键，使蛇改变向去吃食，每吃一个食物蛇身加长，分数加 1。每局 300 秒。 暂停游戏：点击暂停按钮暂停游戏，点击继续按钮继续游戏。 退出游戏：点击退出按钮退出游戏。 平台简介 2.1 系统介绍 2.1.1 Linux 简介 Linux是一套免费使用和自由传播的类 Unix操作系统，它主要用于基于 x86系列CPU 的计算机上。这个系统是由世界各地的成千上万的程序员设计和实现的。其目的是建立不受任何商品化软件的版权制约的、全世界都能自由使用的 Unix兼容产品 【 2】 。 2.1.2 Linux 系统的主要特点 Linux操作系统作为当今主要的操作系统之一具有以下这些特点： (1)开放性 (2)多用户 (3)多任务 (4)良好的用户界面 (5)设备独立性 (6)提供了丰富的网络功能 (7)可靠的安全系统 (8)良好的可移植性 2.1.3 LINUX 的组成 LINUX的内核：内核是系统的核心，是运行程序和管理 像磁盘和打印机等硬件设备的核心程序。 LINUX SHELL: Shell 是系统的用户界面，提供了用户与内核进行交互操作的一种接口。 LINUX 文件系统 : Linux 文件系统是文件存放在磁盘等存储设备上的组织方法。Linux能支持多种目前主流的文 件系统，如 EXT2、 EXT3、 FAT、 VFAT、 ISO9660、 NFS、 3 SMB等。 LINUX应用系统：标准的 Linux系统都有一整套称为应用程序的程序集，包括文本编辑器、编程语言、 X Window、办公套件、 Internet工具、数据库等 【 3】 。 2.2 开发工具 在确定了操作系统后，就该选择开发工具了。考虑到是在 Linux 平台下开发而Linux的内核主要是由 C语言编写的，所以 C 语言在 Linux下的软件开发具有独到的优势 【 4】 。由于考虑到游戏开发需要一个良好的界面，终端程序显然无法达到 要求。于是 GTK图形化编程工具就成了必然的选择。下面将简要介绍本次贪食蛇游戏开发所要用到的主要工具。 2.2.1 C 语言简介 C 语言是目前世界上流行、使用最广泛的高级程序设计语言。 C 语言对操作系统和系统使用程序以及需要对硬件进行操作的场合，用 C语言明显优于其它高级语言，许多大型应用软件都是用 C语言编写的。 C 语言具有绘图能力强，可移植性，并具备很强的数据处理能力，因此适于编写系统软件，三维，二维图形和动画它是数值计算的高级语言 【 4】 。 C语言的特点有： (1)简洁紧凑、灵活方便。 (2) 运算符丰 富。 (3) 数据结构丰富。 (4) C是结构式语言。 (5) C语法限制不太严格、程序设计自由度大。 (6) C语言允许直接访问物理地址，可以直接对硬件进行操作。 (7) C语言程序生成代码质量高，程序执行效率高。 (8) C语言适用范围大，可移植性好 【 5】 。 2.2.2 GTK 简介 GTK(GIMP Toolkit)是一套跨多种平台的图形工具包 ,按 LGPL 许可协议发布的。虽然最初是为 GIMP 写的，但目前已发展为一个功能强大、设计灵活的一个通用图形库。特别是被 GNOME 选中使得 GTK+广为流传，成为 Linux下开发图形界面的应用程序的主流开发工具之一，当然 GTK+并不要求必须在 Linux 上，事实上，目前 GTK+已经有了成功的 windows 版本。 GTK虽然是用 C语言写的，但是您可以使用你熟悉的语言来使用 GTK，因为 GTK+已经被绑定到几乎所有流行的语言上，如： C+,PHP, Guile, Perl, Python, TOM, Ada95, 4 Objective C, Free Pascal, and Eiffel【 6】 。 GTK的一个简单例子如下： 该例子产生一个窗口。它不能 自己退出，只能通过 shell来杀死进程（调用 kill命令）。 /*例子 base.c */ #include int main( int argc,char *argv ) GtkWidget *window;gtk_init (&argc, &argv); /* 初始化显示环境 */ window = gtk_window_new (GTK_WINDOW_TOPLEVEL); /* 创建一个新的窗口 */ gtk_widget_show (window); /*显示窗口 */ gtk_main (); /*进入睡眠状态，等待事件激活 */ return(0); 从上面的程序可以看出， GTK是一个事件驱动工具包，当它运行到 gtk_main()函数时会自动睡眠，直到有事件发生，控制权转让给相应的函数调用，在该函数中可以用标准 C写出相应的事物逻辑。这与 windows 上的程序处理是一样的。 2.2.3 Linux 编译工具 GCC 简介 GCC是一个用于 linux系统下编程的编译器。 GCC=GNU Compiler Collection，是由 Stallman所开发的 linux下的编译器，可以编译的语言包括： C, C+, Objective-C, Fortran, Java,Ada 等。不过，现在 GCC也有了许多 Win32下的移植版本。如今的 GCC借助于他的特性，具有了交叉编译器的功能，即在一个平台下编译另一个平台的代码。 2.3 GTK 环境的搭建 我们以 Linux 系统 Ubuntu 为例简要介绍 GTK 环境的搭建， Ubuntu 桌面环境是gnome。 gnome 就是使用 GTK+编写，所以运行环境不需要另外配置了，要做的是安装开发 所需要的环境。 刚安装好的 Ubuntu 已经默认安装了 gcc，但是并没有安装所需要的头文件，我们需要手动添加，使用命令： sudo apt-get install build-essential 然后再安装 gnome 开发包，使用命令： sudo apt-get install gnome-core-devel 系统会自动找到所依赖的库，并一起下载下来。 5 这样安装过后使用下面的命令编译上面的代码： gcc main.c -o main pkg-config -cflags -libs gtk+-2.0 注意，这里的 是键盘上 1左面的反引号，不是单引号。 KDE桌面配置 GTK，步骤也类似，但是需要先安装 GTK的运行环境。 本次开发所使用 的 操作系统平台是 Fedora 12 完整版 安装时选择安装 GTK 开发工具与 gnome桌面，因此当系统完成安装所有 GTK的运行和开发环境就已搭建好。 3 系统分析 3.1 可行性分析 3.1.1 技术可行性 本系统的设计要求是一个能在 Linux操作系统下运行且界面美观运行稳定且将来可能用于嵌入式移植的系统。综合考虑选择 C 语言与 GTK技 术来实现本系统。 C语言是一门成熟的高级语言，可用于开发各种系统，也可用于开发游戏系统 【 7】 。同时 C 语言也拥有相当多的技术人员。 GTK是 Linux 下的一个图形化编程工具，其开发出来的程序能在装有 GTK 环境的 Linux系统下顺利运行。可以说在技术方面开发此系统不会有什么问题。 3.1.2 经济可行性 随着手机和电脑的普及 ,这样的小游戏也将随着普及因此其需求也将不断上升 ,而由于技术的成熟与为数众多的开发人员使得此系统的开发并不困难，再者此系统运行的平台 Linux操作系统是开源和免费的，所以开发此系统的成 本并不会很高。因此此系统具有相当的经济利益，到时候我们也可以静观其成 . 3.1.3 操作可行性 本系统是一个简单的单机游戏系统，对于这样一个系统 ,其操作只需要使用简单的几个按键和鼠标点击按钮就可以实现，因此本系统的操作简单易记，可以说一看就会的，系统在操作上是不会存在问题的 ,本系统需要在 Linux 操作系统下运行，而用户也可以在其受益不浅 . 3.2 需求分析 3.2.1 功能要求 本系统是一个简单的单机游戏，其功能要求实现单人游戏模式、双人对战模式和人机对战模式以提高游戏的可玩性，系统默认模式为单人模式 ，通过点击按钮选择不同游戏模式进行游戏。系统还要求实现至少 2个不同地图的选择，以提高游戏的趣味 6 与丰富性。单人模式时只有玩家 1通过上下左右键来控制蛇的方向，在规定时间内尽量多吃食物，双人模式时增加的玩家 2可以通过 W,S,A,D来控制蛇的移动方向，通过双人竞技比较谁吃的食物最多，人机对战是在只有一个人的情况下可以与电脑进行对战。游戏中要实现暂停与退出和关于帮助文档。 3.2.2 性能要求 游戏操作要求简单易行，游戏过程中画面移动要流畅，通过键盘对蛇移动方向控制时无明显延迟，由于本系统将来有可能在嵌入式 Linux上移植，而嵌入式系统一般存储较小，处理器的处理速度也不是很快，因此本系统对内存和处理器的使用的要求都要尽可能的小。 3.2.3 运行要求 本系统由于要使用到 GTK图形化编程工具，而图形化编程工具 GTK开发出来的程序需要有 GTK环境才能运行，由于是用 C语言实现，因此系统对硬件的要求并不是很高。所以本系统的运行要求是搭建有 GTK环境或是安装 gnome桌面环境的 Linux操作系统。 4 系统概要设计 4.1 程序初始化 程序初始化主要由初始化函数 init_game()在游戏开始时对各变量进 行初始化赋值。每次重新游戏时，得分将清零，游戏时间重设为 300 秒，蛇的长度与位置恢复为初始状态，但游戏模式与游戏的地图将不变，需要玩家自己选择才会发生改变 游戏的初始化流程如图 4.1 所示。 4.2 程序流程 4.2.1 系统模块 本系统分为：图形初始化 gtk_init()与游戏初始化 game_init()模块、图形界面设计 create_window()与地图设计 draw_map()模块、模式选择 cb_choose()模块、游戏 play_game()模块、成绩输出模块、电脑 AI模块、游戏退出模块、游戏中蛇通过判 断是否撞墙或吃到自己来判断蛇的死亡。 程序模块如图 4.2所示。 4.2.2 系统流程 本系统流程：当用户打开系统，系统首先对各参数进行初始化设定，当玩家点击“开始”时开始游戏，用户通过方向键进行游戏，游戏过程中 如果蛇死亡或游戏 7 时间完则停止游戏并显示分数与结束信息，当玩家选择从新开始时游戏进行初始化设定，当玩家选择退出时退出游戏。 游戏流程如图 4.3所示。 图 4.1 程序初始化流程图 图 4.2 游戏模块图 8 图 4.3 游戏流程图 5 系统详细设计 5.1 系统界面 用户界面是现代软件重要的组成部分，界面的好坏对于游戏软件来说也相当的重要，因为一个用户友好的界面能让玩家在游戏过程中感觉更舒心，而一个不友好的界面将使游戏的品质大打折扣。 本系统界面的设计遵循如下的指导规则： 1 让用户驾驭软件，而不是软件驾驭用户。 2 尽可能减少用户的记性。 3 保持界面的一致性 【 8】 。 本游戏的界面设计如图 5.1所示。 9 图 5.1 游戏界面的设计 此系统界面设计简约而不简单，用户使用此系统时能够很容易记住方便玩家使用，因此不会让人感觉复杂而乏味。 界面主要分为以下几大部分。 (1)主界面：所有信息都显示在主窗口上，其中主要有游戏显示区、游戏信息显示区和游戏按钮区。 主窗口创建代码如下： /创建窗口 window=gtk_window_new(GTK_WINDOW_TOPLEVEL); /设置主窗口标题 gtk_window_set_title(GTK_WINDOW(window),贪食蛇 ); /主窗口显示位置 gtk_window_set_position(GTK_WINDOW(window),GTK_WIN_POS_CENTER); /接受关闭事件并且关闭窗 口 g_signal_connect(G_OBJECT(window),destroy,G_CALLBACK(gtk_main_quit),NULL); /设置主窗口大小 gtk_widget_set_size_request(window,800,500); /边框大小 10 gtk_container_set_border_width(GTK_CONTAINER(window),10); (2)游戏显示区：此区域是游戏过程的显示区域，也是界面的主要设计部分。 通过 draw=gtk_drawing_area_new();创建游戏区域窗口。 (3)游戏开始界面如图 5.2 所示。 在打开系统时，游戏区显示一张欢迎界面的图片。 用 pixbuf = gdk_pixbuf_new_from_file (./test.jpg,NULL);将文件名为 test.jpg的图片添加进游戏区并设为背景 。 (4)信息显示区：主要显示游戏过程中的各种信息，如时间和得分等。 gtk_label_new()函数用于显示游戏分数等信息。 信息显示区如图 5.3所示。 (5)按钮区：主要显示游戏中需要点击选择的按钮。 通过 gtk_button_new_with_label（） 函数创建按钮。 按钮布局如图 5.4所示。 (6)通过 gtk_fixed_new()创建一个名叫 fixed 的固定容器，然后将游戏显示区 draw、信息显示和按钮添加进 fixed，最后把 fixed 容器添加进 window 主窗口，最后通过gtk_widget_show_all(window)函数将其显示出来。 图 5.2 游戏开始界面设计 11 图 5.3 游戏信息显示区 图 5.4 系统按钮布局 5.2 对象模型设计 在本系统中对象模型的设计主要是蛇的设计，食物的设计，和地图的设计。 蛇的设计主要是通过 2 个画圆函数 gdk_draw_arc()画出蛇的每一个结点同时设定颜色。而食物也是通过画圆函数画出。地图中的传送点和墙体是通过画方格函数gdk_draw_rectangle()画出。 图 5.5中 就是蛇， 即是食物，褐色长方形即使墙的设计， 是传送点。 图 5.5 地图二的设计 12 图 5.6 地图一的设计 5.3 食物及蛇状态的初始化及食物的出现 蛇状态的初始化是由定义蛇结构体时初始化决定的，每一次开始蛇的长度，出现位置和移动方向都是一样的，它们长度都为 6 个结点，方向都向右，蛇 1 初始位置是（ 3， 3），蛇 2 初始位置是（ 3， 30）。 无论是在游戏的开始还是进行中，食物都是随机出现的，通过 rand（）随机数产生函数随机产生食物出现的坐标，在产生的随机坐标上画出食物。 5.4 游戏运行中的设计思路 游戏中蛇的运动是靠通过对画面的不断清除与重画而实现的，每一次运动时先用背景色擦除掉原有蛇的图像，再将蛇画在其新出现的位置，由于每一次擦除与重画间隔的时间 非常短，利用人的视觉暂留性，让蛇看上去就像在连续不断的运动。而食物未被吃前，传送点和墙体被擦除后重画的位置与原来一样，所以让人感觉其并没有变化。 蛇身的移动与运动方向主要是受头结点控制，因为蛇每一次运动就是靠后一结点画在前一结点的位置上来实现的，所以对蛇的控制主要是对头结点的控制。 蛇 1 通过上下左右键，蛇 2 通过 W、 S、 A、 D 键来控制蛇的移动方向 游戏中蛇运动速度的快慢主要是通过设置画面重画频率来实现的，而具体实现是通过对函数的调用频率， GTK 中用函数 g_timeout_add ()来实现对函数的定时调 13 用。 游戏暂停则是通过 g_source_remove()函数中止对蛇运行函数的定时调用。通过g_timeout_add()来实现游戏的继续。 设计了传送点和墙体来增加游戏的复杂性与可玩性 5.5 游戏规则 1 单人模式 单人模式的规则比较简单，只要在规定的时间内不死亡和尽量得分最多即可。蛇撞墙或自己身体时即死亡，当蛇进入传送点时将从另一特定位置出来。 2 双人竞技模式 蛇进入传送点时将从另一特定位置出来，规定时间内蛇没死亡得分最多者赢，得分相等为平局，游戏中撞墙或自己身体死亡者输。两条蛇可以互相穿透。 3人机对战 模式 当用户选择此模式时将于电脑控制的蛇进行竞技，此模式规则与双人对战模式一样。 5.6 游戏实现以及其代码 5.6.1 蛇移动的实现 蛇的移动方向主要受头结点控制，所以每次画蛇时只要把前一结点的值赋给后一节点即可。 当蛇头的移动方向向右时， y 值不变 x 的值不断增加。 当蛇头的移动方向向左时， y 值不变 x 的值不断减少。 当蛇头的移动方向向下时， y 值增加 x 的值不变。 当蛇头的移动方向向上时， y 值减小 x 的值不变。 画蛇和蛇移动代码如下： /蛇身体节点位置的赋值 gint i; for (i=snake.node;i0;i-) snake.xi= snake.xi-1; snake.yi= snake.yi-1; /蛇移动的实现 14 switch( snake.dir) case 1: snake.x0+=1;break; case 2: snake.x0-=1;break; case 3: snake.y0-=1;break; case 4: snake.y0+=1;break; /*1向右， 2向左， 3向上， 4向下 */ 5.6.2 蛇死亡的判断 当蛇头的值与蛇身或与墙的值相等时，蛇即算死亡，代码如下： void judge_die(struct Snake *psnake) gint j; for(j=3;jnode;j+) if( psnake-xj= psnake-x0& psnake-yj= psnake-y0) psnake-life=1; 5.6.3 蛇到达边框时从另一端出现和传送的实现 当蛇头的 x或 y值达到边框的最大或最小位置时相应的给 x或 y赋以边框的最小或最大值以实现当蛇到达边框时能从另一端出来，同理当蛇头的 x， y 值等于传送点位置的值时将蛇头 x， y 的值赋以被传送到位置的值，这样将实现蛇的传送功能。 部分代码实现如下： if(snake2.x0=0|snake2.x0=59|snake2.x0=30) snake2.life=1; else if(snake2.dir=3&snake2.y0=47) snake2.y0=-1; /到达传送点的处理 if(snake2.x0=1&snake2.y0=3) 15 snake2.x0=58; snake2.y0=43; if(snake2.x0=58&snake2.y0=3) snake2.x0=1; snake2.y0=43; 6 贪食蛇 AI 的算法设计 本游戏设计了人机对战模式，因此电脑贪食蛇的实现就必须用到人工智能也就是AI，下面将详细介绍实现 AI的算法设计。 6.1 蛇自己寻找食物的算法设计 此部分的算法设计是蛇 AI 设计的最主要也是最基本的部分。在系统中电脑蛇主要通过搜寻最短路径来寻找食物，而最短路径的搜索可以通过很多算法来实现，本系统主要是通过寻找局部最优解的方法来搜索蛇到食物的最短路径，而其中有一个贪心算法符合此部分的设计。 6.1.1 贪心算法 所谓贪心算法是 指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法的基本思路如下： (1)建立数学模型来描述问题。 (2)把求解的问题分成若干个子问题。 (3)对每一子问题求解，得到子问题的局部最优解。 (4)把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解 出发； while 能朝给定总目标前进一步 do 16 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 6.1.2 利用贪心算法实现最短路径的选择 本系统中蛇主要是通过头结点的移动来控制蛇的移动，因此电脑蛇的移动也主要是通过头结点的的方向的选择来控制蛇的移动。 根据贪心算法得出最短路径的步骤： (1)选择一组解即在蛇头结点有可能移动的四个方向，每个方向选出一个点用于挑选最优解。 (2)挑选出来的四个点依次计算出其与食物的距离，然后进行比较。 (3)选出离食物最近的一个点。 (4)把蛇 头结点移动的方向设为移动到挑选出来离食物距离最近点的方向。 (5)移动到下一点后又从第 1步执行，直到最后得到最优解为止。 求可行解（第 2步）示意图如下： 图 6.1 求可行解示意图 计算距离通过比较选出最短距离然后选择蛇移动方向的实现代码如下，其中要考虑到选出来的四个点中有一个是被蛇身体所占据，蛇是不能往哪个方向移动的，因此要把这一情况排除。 算法实现代码如下： Void get_dir() gint a,b,a1,a2,b3,b4; gint d1,d2,d3,d4; a=snake2.x0-food.x; b=snake2.y0-food.y; 17 a1=(snake2.x0+1)-food.x; a2=(snake2.x0-1)-food.x; b3=(snake2.y0-1)-food.y; b4=(snake2.y0+1)-food.y; /计算与食物的距离 d1=a1*a1+b*b; d2=a2*a2+b*b; d3=b3*b3+a*a; d4=b4*b4+a*a; /选择最短距离的点后得到方向 if(d130&snake2.x030&snake2.dir!=4) snake2.dir=3; if(snake2.y0=3&snake2.dir!=2) snake2.dir=1; 此地图还需要考虑墙的存在，当蛇头到达墙时必须改变方向避开它，否则将撞墙死亡。 实现代码如下： 19 if(snake2.x030&(snake2.x0=58|snake2.x0=31)&snake2.dir!=4) snake2.dir=3; if(food.x30&snake2.y0=3) snake2.dir=1; 当蛇从一个区域到达另一区域的时候，有两个出口可供选择，这个时候蛇将选择离食物最近的那个出口出现。两个出口是上下分布的，因此只用判断食物所在坐标的y 值即可。 因为游戏区域 y 的大小是从 0 到 50，所以当 y 值小于等于 25 时从上面出口出现，当 y值大于 25时从下面出口出现。 部分实现代码如下： if(snake2.x0=1&snake2.y0=3) if(food.y25) snake2.x0=58; snake2.y0=43; if(food.y #define GTK_Up 65362 #define GTK_Down 65364 #define GTK_Left 65361 #define GTK_Right 65363 #define n 200 static GtkWidget *window = NULL; static GtkWidget *draw= NULL,*draw2=NULL; static GdkPixmap *pixmap = NULL,*pixbuf=NULL; GtkWidget *label; GtkWidget *score_label; 25 GtkWidget *score_label2; GtkWidget *inf_label; GtkWidget *win_label; GtkWidget *ti_label; GdkColor color; GdkGC *gc_blue; GdkGC *gc_red; GdkGC *gc_br; GdkGC *gc_tt; GdkGC *gc_a; GdkGC *gc_b; gboolean playing = FALSE; gboolean pauseing = FALSE; gboolean ai=FALSE; gint score=0,score2=0;/*得分 */ gint speed=130; guint timer=0; guint timer1=0; gint times=300; gint play_n=1; gint t=0; gint mp=1; struct Food int x; int y; int yes; /*判断是否出现食物的变量 */ food=6,16,0; struct Snake int xn; int yn; int node; 26 int dir;/*蛇移动方向 :1 右， 2 左， 3 上， 4 下 */ int life/*蛇的生命： 0 活着， 1 死亡 */ snake=4,4,7,1,0,snake2=4,30,7,1,0; /系统主程序 gint main(int argc, char *argv) gtk_init(&argc,&argv); create_window(); gtk_main(); return 0; /窗口的设计 void create_window() GtkWidget *exit,*start,*choose,*choose1,*choose2,*pause,*about; GtkWidget *fixed; GtkWidget *g_map1,*g_map2; window=gtk_window_new(GTK_WINDOW_TOPLEVEL); gtk_window_set_title(GTK_WINDOW(window),贪食蛇 ); gtk_window_set_position(GTK_WINDOW(window),GTK_WIN_POS_CENTER); g_signal_connect(G_OBJECT(window),destroy,G_CALLBACK(gtk_main_quit),NULL); gtk_widget_set_size_request(window,800,500); gtk_container_set_border_width(GTK_CONTAINER(window),10); g_signal_connect (GTK_OBJECT(window),key_press_event,G_CALLBACK (key_press),NULL); draw=gtk_drawing_area_new(); gtk_widget_set_size_request(draw, 600, 480); g_signal_connect (draw, expose_event,G_CALLBACK (expose_event), NULL); g_signal_connect (draw,configure_event,G_CALLBACK (configure_event), NULL); /按钮 start = gtk_button_new_with_label ( 开 始 ); g_signal_connect (start,clicked,G_CALLBACK(game_start),NULL); gtk_widget_set_size_request(start,70, 30); exit=gtk_button_new_with_label(退出游戏 ); 27 g_signal_connect(G_OBJECT(exit),clicked,G_CALLBACK(cb_exit),NULL); gtk_widget_set_size_request(exit, 70, 30); pause = gtk_button_new_with_label ( 暂 停 ); g_signal_connect (pause,clicked,G_CALLBACK(game_pause),NULL); gtk_widget_set_size_request(pause,70, 30); about= gtk_button_new_with_label ( 关于 ); g_signal_connect (about,clicked,G_CALLBACK(cb_about),(gpointer)欢迎使用此游戏！ n 游戏规则： n1）玩家 1 通过方向键控制游戏 n2）玩家 2 通过 W， S， A， D 字母键控制游戏 n3)游戏时间完得分多者赢 n4)游戏过程中死亡者输 nn 说明：此游戏可以选择单人模式和双人模式还有 2地图供选择 nn 希望你能喜欢本游戏！ ); gtk_widget_set_size_request(about,70, 30); choose=gtk_button_new_with_label(双人 ); g_signal_connec