细论数据结构与网络游戏

提到数据结构的应用，人们往往联想到其应用在系统软件开发中。例如计算机操作系统中，先来先服务的调度方式就应用队列结构帮助快速找到首要完成的任务，帮助提高系统的性能。谈到数据结构与网络游戏使人觉得似乎不相关，其实在网络游戏中随处应用到数据结构。如果数据结构与网络游戏很好的结合起来，可帮助提高游戏程序的运行速度众所周知一个好的程序应该包括合理的数据结构，即合理组织待处理的数据，以及相应的数据结构的好的算法。将数据结构要与网络游戏融合，就是网络游戏中需要处理的数据应用合理数据结构并应用高效算法处理。网络游戏中需要处理的问题包括游戏涉及的数据、角色的动作及游戏规则等等。接下来就浅谈一下对于数据结构在网络游戏中的各方面的应用。

一、游戏数据处理

网络游戏包括很多的数据，这些数据都被存储在服务器上的数据库里。当玩家成功登录到游戏的那一刻，玩家就会从服务器的数据库里获得有关其自身的数据。玩家获得的数据包括他选择的角色、当前玩到的级别、已经得到的道具、已经完成的任务及将要完成的任务等等。数据信息种类繁多，数量庞大。为了处理方便，首先应该根据数据的种类选择其合理的数据结构进行临时存储，便于服务器为登录成功的玩家处理数据。玩家的道具会随着级别的提升，种类和数量都会不断增多。如果用线性表的结构存储，就要为每一种道具建立一个线性表结构，那么多种道具要建立的线性表同时会有多个。如果玩家同时以多个账号登录时，这时就会产生一个难题，如何标志每个线性表涉及的道具是属于哪个账号的，此时不便于服务器查找。玩家在玩时随时都有可能获得新的道具对于新的道具如何快速存储到玩家的道具的数据结构中也是一个难题。这个问题可以通过链式存储的方式解决，如果采用单链表存储用户的所有道具就会是种类混乱，那么接下来亟待解决的问题就是对于种类问题的解决。玩家、道具种类及道具之间可以采用树形结构存储，为了使道具采用链式存储的方式，可采用孩子兄弟表示法为这种树的存储结构。树的根结点为玩家，下一层为该玩家正在使用的所有角色，每个角色的下一层为已经获得的道具种类，种类下为该道具。当添加新道具时，首先判断道具是否已经在道具树中，如果已经在，那么就在树中该道具的数量加上新获得的数量；否则，应该判断新道具的种类是否已经在树中，如果在树中，则将道具放置所属种类的结点下面，如果此道具的种类未在树中存在，则应在道具树的种类层中加入新的种类，在把新道具放到此种类下面，同时更新服务器上数据库的道具信息，保持信息同步。当玩家的某个角色需要获得自己的某种道具时，用遍历算法，先找到种类，再沿着种类找到所有的道具。通过这样的树结构，避免了每次玩家的角色浏览道具时都要访问数据库中数据，节省了时间，更便于对道具进行分类管理，查找道具的速度也更快。通过对道具的信息管理举例，可以发现，数据结构对于游戏数据在获取之后，有组织的管理，读取信息的速度更快，从而提高游戏的运行速度。

二、角色动作管理

玩家通过输入设备控制角色动作，经常同时控制运动动作和攻击动作。玩家同时输入多个动作的速度极快，需要系统快速响应。无论何种动作，众所周知都动作都是由线程来控制，多个动作同时提交等于向系统提交了多个线程。玩家希望多个动作能够同时运行，但对于系统而言，线程不能同时运行。因为系统响应每个线程的时间比较短，给玩家的感觉是同时响应的，实际上采用的是并发的方式。合理的安排线程运行的顺序，便于系统的调度，角色能够快速展现玩家输入的动作。可以按照玩家输入的动作到达系统的时间为线程排序，用队列存储线程。先到达的排在队头，后到达排在队尾。队列的特征为先进先出，因此，用此种结构组织线程的时候，系统直接调出队头的线程进行运行，节省了查找的时间。随之而来的问题就是采用何种队列的存储结构？如果采用循环队列的结构，就需要预先知道大概需要的存储区大小，但是玩家随时都会输入新的动作，无法得知所需存储区的大小，那么可以采用链队列来存储玩家的动作线程更加适合。当有新的动作来时，可以将为其申请任意的空间存储，只需把地址告知之前的队尾，就连入了队尾。采用链队列的方式调度动作线程，使角色的动作展现更加协调，系统响应速度明显提高。通过角色动作线程调度举例，可以看到数据结构对于角色的动作同样可以进行管理，进一步提高游戏运行的速度。

三、游戏规则的实现

不管是何种游戏，游戏规则是游戏设计的核心，游戏规则的好坏不但会影响到玩家对游戏的兴趣程度，同样会影响到游戏的运行速度。制定了好的游戏规则后，如何实现就是难题。首先就应该为其设计好的算法，以连连看游戏为例，两个同样的图像选择后满足三根以内折线联通就可以消掉。满足条件的连线方式可能有多种，使用最短路径连接消除会大大提高游戏运行的速度，关键是如何找到最短路径？对于图的逻辑结构存在这样的算法——每一对顶点间的最短路径算法，Floyd算法的基本思想是：假设从vi到vj的弧（若从vi到vj的弧不存在，则将其弧权值看为∞）是最短路径，然后进行n次试探，没找到最短路径之前，就在vi和vj之间加入顶点，直到找到最短路径为止。游戏玩家选中的两张一模一样的图片作为顶点vi和vj，判断它们是否能被消掉，也就是判断能不能找到满足条件的最短路径。每次试探的时候加入新顶点的位置不是任意的，除了vi和vj之外没有被消掉的图片区域是不能够添加顶点的。顶点与顶点之间的弧在连连看游戏中连线必须是水平直线和垂直直线，因此添加新的顶点的条件还应该满足按照连接方向，只用水平直线和垂直直线就可连接成功。总结一下消除满足的条件：（1）连线不能超过三根以上，因此添加的顶点不能超过两个；（2）添加顶点的位置不能是未消除图片的区域。（3）消除的路径为最短路径。按照这个条件的改进Floyd算法：（1）玩家选中两个一模一样的图片，两个图片分别作为顶点vi和vj；（2）如果vi和vj用垂直或水平直线连接后，不经过未消除的图片那么，此路径为最短，可以直接消掉，结束；否则转（3）；（3）在已经消除的图片区域，如果可以在vi水平或垂直方向添加一个顶点v0，这个顶点可以在水平或垂直方向上成功连接到vj?顶点，vi和vj可以消掉；否则新顶点保留，进行（4）；（4）如果可以在已经消除的图片区域，在v0水平或垂直方向添加一个新的顶点v1，使得v1在vj的垂直或水平方向，并且v1与vj的连线不经过未消除的图片区域，vi和vj消除；否则提示选择错误。由上述算法可以发现，数据结构可以帮助游戏提高工作效率，从而提高速度，加强了游戏的可玩性。很多类型的游戏均可以应用上数据结构及其算法，例如解谜游戏，可以应用智能算法，帮助实现复杂的游戏规则及其游戏策略。应用数据结构的算法切忌照搬照抄，必须结合游戏的实际状况进行选择、改进，必要时还要改存储结构，最终目的就是要提高游戏的工作效率。

经过上述讨论，可以发现数据结构适合游戏的各个方面的程序设计，但这不是硬性。如果为了引入数据结构，使得程序变得复杂，反而会影响游戏的速度，使得玩家对游戏丧失兴趣。数据结构的用得要合情合理，恰到好处。如果对于数据的处理首先要发现各类数据的结构特点及组织规律，采用合适的逻辑结构，在采用了合适的逻辑结构之后，就要考虑便于操作的存储结构。存储结构通常分为顺序存储和链式存储，结合数据操作特性选择最适合当前游戏的。对于角色的动作，利用数据结构的特殊线性表结构，更好的被系统调度，从而使动作在画面上更逼真协调。对于游戏规则，首先要根据游戏的类型进行选择，依据规则的要求选择合适的数据结构，并且找到高效的算法，提高游戏的可玩性，提升运行效率。

综上所述，数据结构可以被用在游戏的各个方面，关键在于程序设计人员的发掘。每进行设计的时候，都要针对问题的特点去找寻合适的数据结构，设计高效的算法。对于算法多种多样，不是已有的算法就一定适合当前的情况，要求设计人员发现应用已有的算法的问题，进行改进，并多次调试，测算算法的时间及空间复杂度，反复改进，争取尽可能提高算法的性能。如果某些方面不需要数据结构就不要硬搬硬套，避免使游戏程序复杂化。总而言之，用好数据结构可以帮助游戏被更多玩家接受和喜爱。