论文部分内容阅读
【摘 要】在软件开发中数据结构有着提高程序性能的作用，如果将它运用于游戏开发，会使游戏的性能与运行速度得到更大的提高，玩家会有更好的游戏体验，提高可玩性。本文对数据结构在游戏程序中的应用进行了简单探讨，希望给出数据结构在网络游戏开发中一种新思路。
【关键词】数据结构；数据处理；动作响应；规则实现
数据结构现今被广泛应用于系统软件和普通应用软件开发。例如计算机操作系统中，利用高效的检索算法及索引技术，帮助计算机完成查找工作。数据结构对于网络游戏开发，其应用似乎并不广泛。数据结构的优势就在于提高程序的性能，如果数据结构与网络游戏很好的结合起来，可帮助提高游戏程序的运行速度，增强可玩性。
一、数据处理
网络游戏包括各种大量的数据，它们被存放服务器端的数据库内。当某个玩家成功登录后，该玩家就会从服务器的数据库里获得大量有关其自身的数据。玩家获得的数据包括他选择的角色、当前玩到的级别、已经得到的道具、已经完成的任务及将要完成的任务等等。数据信息种类繁多，数量庞大。为了处理方便，客户端程序首先应该根据数据的种类选择其合理的数据结构进行临时存储，便于后续的数据查询、显示及上传。
以玩家道具为例，如果用线性表的结构存储，就要为每一种道具建立一个线性表结构，会占用大量存储空间，因此，此类数据存储可以采用链式存储方式解决。例如剑的种类包括单手剑、双手剑、魔法剑及细剑等等，每种剑又会分为不懂级别。道具种类及道具之间可以采用树形结构链式存储，若将所有的剑均采用单链表存储，单链表长度过长，关系混乱，不便于查找。因此在采用链式存储同时，还应采用树形的逻辑结构，因此存储最终实现可采用树的链式存储结构中的孩子兄弟表示法。树的根结点为道具结点，此节点不包括任何数据，将已经获得的道具种类逐级分层，例如将剑、弓、魔法药水等为同一界别；下一级别各个种类详细划分，例如剑的下一级别就包括单手剑、双手剑、魔法剑及细剑等等；以此类推，最终的叶子结点就是某个具体道具。当玩家的某个角色需要获得自己的某种道具时，用遍历算法，先找到种类，再沿着种类找到所有的道具。当添加新道具时，首先判断道具是否已经在道具树中，如果已经在，那么就在树中该道具的数量加上新获得的数量；否则，应该判断新道具的种类是否已经在树中，如果在树中，则将道具放置所属种类的结点下面，如果此道具的种类未在树中存在，则应在道具树的种类层中加入新的种类，在把新道具放到此种类下面，同时更新服务器上数据库的道具信息，保持信息同步。通过这样的树结构，避免了每次玩家的角色浏览道具时都要访问数据库中数据，节省了时间，更便于对道具进行分类管理，查找道具的速度也更快。
二、玩家动作响应
玩家通过输入设备控制角色动作，经常同时控制运动动作和攻击动作。玩家同时输入多个动作的速度极快，需要系统快速响应。无论何种动作，众所周知都动作都是由线程来控制，多个动作同时提交等于向系统提交了多个线程。玩家希望多个动作能够同时运行，但对于系统而言，线程不能同时运行。因为系统响应每个线程的时间比较短，给玩家的感觉是同时响应的，实际上采用的是并发的方式。合理的安排线程运行的顺序，便于系统的调度，角色能够快速展现玩家输入的动作。可以按照玩家输入的动作到达系统的时间为线程排序，用队列存储线程。先到达的排在队头，后到达排在队尾。队列的特征为先进先出，因此，用此種结构组织线程的时候，系统直接调出队头的线程进行运行，节省了查找的时间。
随之而来的问题就是采用何种队列的存储结构？如果采用循环队列的结构，就需要预先知道大概需要的存储区大小，但是玩家随时都会输入新的动作，无法得知所需存储区的大小，那么可以采用链队列来存储玩家的动作线程更加适合。当有新的动作来时，可以将为其申请任意的空间存储，只需把地址告知之前的队尾，新的动作就顺利加入了队列。
三、规则实现
不管是何种游戏，游戏规则是游戏设计的核心，游戏规则的好坏不但会影响到玩家对游戏的兴趣程度，同样会影响到游戏的运行速度。制定了好的游戏规则后，如何实现就是难题，这就要求为其设计性能较好的算法。以连连看游戏为例，两个同样的图像选择后满足三根以内折线联通就可以消掉。满足条件的连线方式可能有多种，使用最短路径连接消除会大大提高游戏运行的速度，关键是如何找到最短路径？
因为算法要基于特定的存储结构，所以首先应解决存储结构的问题。将连连看的界面顶点进行存储，因为其具有顶点排列具有数据结构中二维矩阵的特点，将顶点采用二维矩阵方式的存储，而不是采用图的结构存储。界面中顶点包括图片顶点和非图片顶点，对于非图片顶点二维数组单元对应值为0；应为图片的种类的是固定的，给每个种类赋值，值均大于1，每个图片顶点的二维数组单元对应的值为其种类的值。由此可以看到，二维矩阵存储各个顶点信息后，找寻两个相同图片可消除的问题就，类似于小老鼠走迷宫的问题。将连连看的连线规则应用进小老鼠走迷宫的问题，假设选中两张相同图片对应的顶点分别是vij和vkl，在找路径的同时要记录已经有的折线数，一旦超出三条就结束查找。改进后算法如下：
将适当的算法应用于连连看的规则中，快速找到最短路径，并在在随时消除掉图片后，更新最短路径，且部分更新，提高程序的运行速度。由此可见，数据结构中的算法可以帮助在游戏实现其规则的同时降低程序复杂度，提高工作效率，加强了游戏的可玩性。但应用时数据结构的算法切忌照搬照抄，必须结合游戏的实际状况进行选择、改进，因为最终目的就是要提高游戏的工作效率。
经过上述讨论，可以发现数据结构适合于网络游戏程序开发的各个方面，使用时应灵活多变。如果为了引入某种错误的数据结构，使得程序变得复杂，反而会影响游戏的速度，使得玩家对游戏丧失兴趣。例如数据的处理应先观察各类数据的结构特点及组织规律，采用合适的逻辑结构以及便于操作的存储结构。
参考文献：
[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1997.
[2]王红梅，胡明，王涛.数据结构[M].北京：清华大学出版社，2011.
[3]韦斯（Weiss，M.A.）.数据结构与算法分析[M].冯舜玺.北京：机械工业出版社，2009.
【关键词】数据结构；数据处理；动作响应；规则实现
数据结构现今被广泛应用于系统软件和普通应用软件开发。例如计算机操作系统中，利用高效的检索算法及索引技术，帮助计算机完成查找工作。数据结构对于网络游戏开发，其应用似乎并不广泛。数据结构的优势就在于提高程序的性能，如果数据结构与网络游戏很好的结合起来，可帮助提高游戏程序的运行速度，增强可玩性。
一、数据处理
网络游戏包括各种大量的数据，它们被存放服务器端的数据库内。当某个玩家成功登录后，该玩家就会从服务器的数据库里获得大量有关其自身的数据。玩家获得的数据包括他选择的角色、当前玩到的级别、已经得到的道具、已经完成的任务及将要完成的任务等等。数据信息种类繁多，数量庞大。为了处理方便，客户端程序首先应该根据数据的种类选择其合理的数据结构进行临时存储，便于后续的数据查询、显示及上传。
以玩家道具为例，如果用线性表的结构存储，就要为每一种道具建立一个线性表结构，会占用大量存储空间，因此，此类数据存储可以采用链式存储方式解决。例如剑的种类包括单手剑、双手剑、魔法剑及细剑等等，每种剑又会分为不懂级别。道具种类及道具之间可以采用树形结构链式存储，若将所有的剑均采用单链表存储，单链表长度过长，关系混乱，不便于查找。因此在采用链式存储同时，还应采用树形的逻辑结构，因此存储最终实现可采用树的链式存储结构中的孩子兄弟表示法。树的根结点为道具结点，此节点不包括任何数据，将已经获得的道具种类逐级分层，例如将剑、弓、魔法药水等为同一界别；下一级别各个种类详细划分，例如剑的下一级别就包括单手剑、双手剑、魔法剑及细剑等等；以此类推，最终的叶子结点就是某个具体道具。当玩家的某个角色需要获得自己的某种道具时，用遍历算法，先找到种类，再沿着种类找到所有的道具。当添加新道具时，首先判断道具是否已经在道具树中，如果已经在，那么就在树中该道具的数量加上新获得的数量；否则，应该判断新道具的种类是否已经在树中，如果在树中，则将道具放置所属种类的结点下面，如果此道具的种类未在树中存在，则应在道具树的种类层中加入新的种类，在把新道具放到此种类下面，同时更新服务器上数据库的道具信息，保持信息同步。通过这样的树结构，避免了每次玩家的角色浏览道具时都要访问数据库中数据，节省了时间，更便于对道具进行分类管理，查找道具的速度也更快。
二、玩家动作响应
玩家通过输入设备控制角色动作，经常同时控制运动动作和攻击动作。玩家同时输入多个动作的速度极快，需要系统快速响应。无论何种动作，众所周知都动作都是由线程来控制，多个动作同时提交等于向系统提交了多个线程。玩家希望多个动作能够同时运行，但对于系统而言，线程不能同时运行。因为系统响应每个线程的时间比较短，给玩家的感觉是同时响应的，实际上采用的是并发的方式。合理的安排线程运行的顺序，便于系统的调度，角色能够快速展现玩家输入的动作。可以按照玩家输入的动作到达系统的时间为线程排序，用队列存储线程。先到达的排在队头，后到达排在队尾。队列的特征为先进先出，因此，用此種结构组织线程的时候，系统直接调出队头的线程进行运行，节省了查找的时间。
随之而来的问题就是采用何种队列的存储结构？如果采用循环队列的结构，就需要预先知道大概需要的存储区大小，但是玩家随时都会输入新的动作，无法得知所需存储区的大小，那么可以采用链队列来存储玩家的动作线程更加适合。当有新的动作来时，可以将为其申请任意的空间存储，只需把地址告知之前的队尾，新的动作就顺利加入了队列。
三、规则实现
不管是何种游戏，游戏规则是游戏设计的核心，游戏规则的好坏不但会影响到玩家对游戏的兴趣程度，同样会影响到游戏的运行速度。制定了好的游戏规则后，如何实现就是难题，这就要求为其设计性能较好的算法。以连连看游戏为例，两个同样的图像选择后满足三根以内折线联通就可以消掉。满足条件的连线方式可能有多种，使用最短路径连接消除会大大提高游戏运行的速度，关键是如何找到最短路径？
因为算法要基于特定的存储结构，所以首先应解决存储结构的问题。将连连看的界面顶点进行存储，因为其具有顶点排列具有数据结构中二维矩阵的特点，将顶点采用二维矩阵方式的存储，而不是采用图的结构存储。界面中顶点包括图片顶点和非图片顶点，对于非图片顶点二维数组单元对应值为0；应为图片的种类的是固定的，给每个种类赋值，值均大于1，每个图片顶点的二维数组单元对应的值为其种类的值。由此可以看到，二维矩阵存储各个顶点信息后，找寻两个相同图片可消除的问题就，类似于小老鼠走迷宫的问题。将连连看的连线规则应用进小老鼠走迷宫的问题，假设选中两张相同图片对应的顶点分别是vij和vkl，在找路径的同时要记录已经有的折线数，一旦超出三条就结束查找。改进后算法如下：
将适当的算法应用于连连看的规则中，快速找到最短路径，并在在随时消除掉图片后，更新最短路径，且部分更新，提高程序的运行速度。由此可见，数据结构中的算法可以帮助在游戏实现其规则的同时降低程序复杂度，提高工作效率，加强了游戏的可玩性。但应用时数据结构的算法切忌照搬照抄，必须结合游戏的实际状况进行选择、改进，因为最终目的就是要提高游戏的工作效率。
经过上述讨论，可以发现数据结构适合于网络游戏程序开发的各个方面，使用时应灵活多变。如果为了引入某种错误的数据结构，使得程序变得复杂，反而会影响游戏的速度，使得玩家对游戏丧失兴趣。例如数据的处理应先观察各类数据的结构特点及组织规律，采用合适的逻辑结构以及便于操作的存储结构。
参考文献：
[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1997.
[2]王红梅，胡明，王涛.数据结构[M].北京：清华大学出版社，2011.
[3]韦斯（Weiss，M.A.）.数据结构与算法分析[M].冯舜玺.北京：机械工业出版社，2009.