Leopold-franzens-university Innsbruck Development Of An Mmog

Transcript

Leopold-Franzens-University Innsbruck Institute of Computer Science Research Group DPS (Distributed and Parallel Systems) Development of an MMOG with Content Generation Bachelor Thesis Supervisor: Dr. Vlad Nae Bernd Altst¨ atter (0915944) [email protected] Daniel Gasteiger (0916600) [email protected] Innsbruck 15 January 2013 Contents 1 Introduction (by Bernd Altst¨ atter and Daniel Gasteiger) 2 Model (by Bernd Altst¨ atter and Daniel Gasteiger) 2.1 Massively Multiplayer Online Game . . . . . . . . . 2.1.1 MMO Role Playing Game . . . . . . . . . . . 2.1.2 MMO First Person Shooter . . . . . . . . . . 2.1.3 MMO Real-time Strategy . . . . . . . . . . . 2.1.4 MMO Crafting Game . . . . . . . . . . . . . 2.2 jMonkeyEngine . . . . . . . . . . . . . . . . . . . . . 2.2.1 Graphic engine . . . . . . . . . . . . . . . . . 2.2.2 Network engine . . . . . . . . . . . . . . . . . 2.3 Content generation . . . . . . . . . . . . . . . . . . . 2.3.1 Game content . . . . . . . . . . . . . . . . . . 2.3.2 Noise Algorithms . . . . . . . . . . . . . . . . 2.3.3 Graphical presentation . . . . . . . . . . . . . 2.4 Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Architecture 3.1 Content generation (by Bernd Altst¨atter) . . . . . . . . 3.1.1 Content generation . . . . . . . . . . . . . . . . . 3.1.2 The game world . . . . . . . . . . . . . . . . . . 3.1.3 Generation of the game world . . . . . . . . . . . 3.1.4 Block Engine . . . . . . . . . . . . . . . . . . . . 3.1.5 Controlls . . . . . . . . . . . . . . . . . . . . . . 3.1.6 Stand-alone client . . . . . . . . . . . . . . . . . 3.2 The network (by Daniel Gasteiger) . . . . . . . . . . . . 3.2.1 Messages . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Session Manager . . . . . . . . . . . . . . . . . . 3.2.3 Chunk Server . . . . . . . . . . . . . . . . . . . . 3.2.4 Client network classes . . . . . . . . . . . . . . . 3.2.5 Distributing the game world . . . . . . . . . . . . 3.2.6 Distributing the load . . . . . . . . . . . . . . . . 3.3 Other parts (by Bernd Altst¨atter and Daniel Gasteiger) 3.3.1 Client bot . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Configuration Files . . . . . . . . . . . . . . . . . 3.3.3 Graphical representation of server status . . . . . 4 Evaluation 4.1 Content generation (by Bernd Altst¨atter) 4.1.1 Block engine and Controls . . . . . 4.1.2 Correctness tests . . . . . . . . . . 4.1.3 Complexity . . . . . . . . . . . . . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . 3 3 3 4 5 6 7 7 7 8 8 9 10 13 . . . . . . . . . . . . . . . . . . 17 17 17 18 19 21 22 22 23 23 24 25 25 25 29 38 38 38 38 . . . . 40 40 40 42 45 4.2 4.1.4 Performance tests . . . Network (by Daniel Gasteiger) 4.2.1 Functionality tests . . . 4.2.2 Stress tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 48 48 51 5 Conclusion and Future work 63 5.1 Future improvements to content generation (by Bernd Altst¨ atter) . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Future improvements to the network (by Daniel Gasteiger) . 64 ii Abstract This thesis will cover the core aspects of the development of a massively multiplayer online game with content generation. Covering the whole topic would exceed the extent of this thesis, we therefore focused on the network and the content generation parts. We present ways to balance the network load depending on player connections and distribution of the game world. Furthermore we will show methods to generate a realistic looking world with seas and lakes, mountains and valleys and different types of resources that can be found in an ediTable world consisting of blocks. Covering these aspects we will show the difficulties we occurred to face and the solutions we chose to solve them. iii Acknowledgement We want to thank our supervisor Dr. Vlad Nae for the opportunity to work on this topic and the reliable help during the development of this project and paper; the Leopold-Franzens University of Innsbruck (especially the Unit Distributed and Parallel Systems Group) for providing the facilities to test the software. We also want to thank our families and friends that they helped us to find the time and motivation to create this work. Wir m¨ ochten uns bei unserem Betreuer Dr. Vlad Nae f¨ ur die M¨ oglichkeit dieses Thema behandeln zu k¨onnen und seine zuverl¨assige Hilfe w¨ ahrend der Entwicklung von Code und Abhandlung bedanken. Weiters der Universit¨ at Innsbruck (speziell dem Institut Distributed and Parallel Systems Group), die uns die M¨oglichkeit bot unsere Software zu testen. Wir m¨ ochten uns außerdem bei unseren Familien und Freunden bedanken, die uns halfen die Zeit und Motivation zu finden um diese Arbeit zu vollenden. iv CERTIFICATE OF AUTHORSHIP/ORIGINALITY We certify that the work in this thesis has not previously been submitted for a degree nor has it been submitted as part of requirements for a degree except as fully acknowledged within the text. We also certify that the thesis has been written by me. Any help that we have received in my research work and the preparation of the thesis itself has been acknowledged. In addition, we certify that all information sources and literature used are indicated in the thesis. Signature of Candidates v 1 Introduction (by Bernd Altst¨ atter and Daniel Gasteiger) Playing games is something that almost every computer scientist likes to do at least sometimes. But how are games programmed? What must a programmer consider when developing his own game? Is it possible for a really small team to create an attractive game? Finding answers to these questions led us to this bachelor thesis. Initially we had to decide which game genre the intended game should belong to. The most common genres are strategy games, first person shooters, simulation games and logical games. The second decision was if the game should be played locally, or together with lots of other players over some network (e.g. the internet). Online games are getting a still growing attention from the game industry since the beginning of this millennium. Setting up a game handling lots of players is a difficult task, but also at least as interesting as difficult and so we choose it to be one of our main objectives. Another aspect when developing a game is the need to fill the game world with content. Basically there are two approaches to fulfil this task: • Manually generated content: In most cases this approach leads to a more coherent and better looking game world, but it consumes a lot of time. • Automated generated content: Can result in a nearly endless variety of game worlds of arbitrary size, while creating nearly no work load for the developers during generation. As the development of the needed algorithms for the automatic content generation features promising challenges we decided to realize this approach and make it to the second main objective of this thesis. One of the most popular games using content generation as a key feature is Minecraft1 (see Figure 4 on page 6), where the player can explore a principally endless game world with different biomes and terrain formations. An interesting feature of a Minecraft-like game world is that it is ediTable and therefore consists of blocks (see chapter 2.3.1 for more informations), which complicates the generation. In order to simplify the development of our project we use the JMonkeyEngine 2 , which is a game engine completely written in Java. The JMonkeyEngine provides basic features such as a simple network layer and a graphic engine. 1 2 http://www.minecraft.net/, visited on 2012-09-16 http://jmonkeyengine.org/, visited on 2012-09-16 1 The goals of this thesis are: • Generating automatically the game world (e.g. surface, caves, seas, lakes and certain resource, such as coal and iron) • Creating a game server architecture that supports more than thousand players in a single session 2 2 Model (by Bernd Altst¨ atter and Daniel Gasteiger) In this chapter formal Definitions related to the project can be found. The first part contains the Definitions of the chosen game type, Massively Multiplayer Online Game (MMOG) and the most common genres. Second the used game engine and its used functionalities are presented. Next the content generation topic is treated by defining some common approaches and the used one. Finally implemented parts of the network are described. 2.1 Massively Multiplayer Online Game Definition 2.1. Online games are games that allow multiple players to play with and against each other over some sort of network, most likely the internet. Online games are getting more important for the game industry, because they are compelling for the player and occupying them for a long time. This can be related to the social aspect of the online games, as players can interact with each other. As described in Definition 2.2 the MMOGs have an even stronger social aspect. This peculiarity has the side effect that the server has to handle players in an effective way, such that they can handle huge player masses within the whole game session and even great player masses accumulated at some given region (e.g. a city). Definition 2.2. Massively Multiplayer Online Game (short MMOG) are online games (see Definition 2.1 that have the capability to a handle big amount of player, as the massively attribute describes. In most cases they encourage or even force the player to interact with other players in order to play the game. MMOGs can be deployed for nearly every game genre, the most common ones, plus the one we would like to introduce, are described in the following subsections. 2.1.1 MMORPG Massively Multiplayer Online Role Playing Games (short MMORPG) is the combination of the MMOG (see Definition 2.2) game type with RPG (see Definiton 2.3) elements. Definition 2.3. A Role Playing Game (short RPG) allows the player to play a virtual avatar that evolves and can be customized during the game. In most cases the customization can be done by learning different abilities and/or changing the appearance of the avatar. Figure 1 shows an in game screenshot of one of the most popular MMORPGs that are currently available (at the state of 03.01.2013), called World of Warcraft with over 10 million [8] active subscribers. An MMORPG most likely allows the player to explore the huge game 3 Figure 1: Ingame Screenshot of World of Warcraft [12] world, fulfil quests (tasks the player gets from non-player characters), fight monster alone or with a group of players (e.g. in World of Warcraft, a raid can consist of up to 40 players). 2.1.2 MMOFPS Figure 2: Ingame Screenshot of Planetside 2 [2] A Massively Multiplayer FPS (see Definition 2.4 for a formal Definition of First Person Shooters) allows a massive amount of players to fight alongside and against each other in a virtual war. 4 Definition 2.4. In First Person Shooters (short FPS) the player controls an avatar most likely representing a soldier. The main goal is to shoot down the enemy units as fast as possible and therefore surviving. There are multiple game modes, the most popular ones are last man standing (where each player has a limited amount of lives and the last survivor is the winner), death match (where the goal is to kill as much enemies as possible in the given time and the player respawns if he is killed) and capture the flag (where the players have to reach the enemy base getting their flag and retrieving it to their own base, while preventing the enemy team from getting the own flag). The most fitting example for this term is the game Planetside 23 (see Figure 2) that has been released on the 20. November 2012 [10]. It enables the players to fight for one of three factions on three different huge sized continents. Each continent can contain up to 2000 players [15]. 2.1.3 MMORTS Figure 3: Screenshot of Dawn of Fantasy [4] A Massively Multiplayer RTS (see Definition 2.5) allows multiple players to fight alongside and against each other. The term massive cannot really be fulfilled with the current common technology. MMORTS that support more than about 20 player at the same time either divide them on different maps or restrict the RTS features. An example of a restricted MMORTS is Age of Empires Online4 Never the less there are multiple attempts to create a real MMORTS, examples would be End of Nations5 and Dawn of Fantasy6 (see Figure 3). 3 Website Website 2012-12-15 5 Website 6 Website 2012-12-15 4 of Planetside 2: http://www.planetside2.com/ visited on 2012-12-15 of Age of Empires Online: http://ageofempiresonline.com/en/ visited on of End of Nations: http://endofnations.com/de/ visited on 2012-12-15 of Dawn of Fantasy: http://dof.reverieworld.com/index.php visited on 5 Definition 2.5. In Real-time Strategy games (short RTS) multiple units are controlled in a virtual warfare by a player. In RTS games the players and the computer-controlled enemies are acting simultaneously. In order to win the game the player has to gather materials, build up certain infrastructure and generate combat units. Most likely the final goal is to capture the control over the whole map by moving the own combat units and destroying the enemy units. 2.1.4 MMOCG Figure 4: Screenshot of Minecraft[1] In this project we would like to combine the MMOG game type with the possibility to edit the whole game world as in Minecraft. This new game type we call Massively Multiplayer Online Crafting Game. We aim to give the possibility to change the game world and interact with other players while handling a big amount of players. Definition 2.6. A Crafting Game (short CG) is a game with a fully ediTable game world and the possibility to create tools and objects using materials that can be collected in the environment (e.g. Minecraft). Figure 4 shows a screenshot of Minecraft after starting in a new world. Minecraft is the prime example for a crafting game as it is the first that got that much attention. Minecraft allows the player to start in an automatically generated world consisting of blocks (as you will see later, we adopted the concept of the game world, see Definition 2.13) and to add or remove blocks of the game world to change it. The generated world has different biomes, lakes, seas, vegetation and caves. 6 2.2 jMonkeyEngine Definition 2.7. A game engine is a software designed for the development of games. Game engines are most likely consisting of different software parts that are responsible for different functionalities in the game and therefore interact with each other, such as the graphic engine (responsible for the graphic appearance of objects in the game) and physic engine (responsible for a physically correct behaviour of the objects). The project has been realised using the jMonkeyEngine (short JME or jME). It is a complete game engine (see Definition 2.7) and provides the basic features needed by the developers to create a game, such as a graphic engine, physic engine, UI interface and a network layer. It has a friendly and active community, which is very helpful solving problems with their engine. The parts that were used in order to create this project are described in the following subsections. 2.2.1 Graphic engine Definition 2.8. A graphic engine - in terms of game development - is a software that is used to display the game objects in a graphical manner, either in 2D or 3D. Modern graphic engines most likely support a scene graph technology (see Definition 2.9) in order to display the game in a threedimensional way. Definition 2.9. A scene graph is a way of ordering graphical scene data into a hierarchy where parent nodes affect child nodes. [3] The jME graphic engine uses the scene graph technology as defined in Definition 2.9. In the scene graph technology ”the parent to child relationship is fundamental”[3] (i.e. we have a hierarchical inheritance concept, the child inherits the changes made on the parent node). This allows to create connected elements, e.g. the player’s avatar and the sword in the hand of the players avatar, and by rotating the parent of the connected elements it is possible to rotate all the connected elements. In particular in this project the scene graph technology is used as we have one world node and each chunk node is attached to it. Furthermore each chunk node has two nodes attached, one for the solid blocks and one for the transparent blocks (in the case of this project: the water), this enables the developer to change the settings (e.g. make it transparent) of the water independently of the solid blocks and makes it possible to calculate the collision only for the solid blocks, as the player can swim through the water. 2.2.2 Network engine Definition 2.10. The network engine - in terms of game development - is a software that allows to setup a network between different players. Most likely by either a classical server/client relationship with 7 a dedicated server or by starting a server software on one of the players pc. The network engine of the JME allows the creation of a simple client/server architecture. It provides implementations for UDP and TCP connections between two hosts where it is always defined which host is the client and which the server. A very important feature is the complete Thread safety of the provided classes that improves the safety of its use greatly. The framework provides also listeners for predefined (like starting or closing the connection to the server) and custom actions. 2.3 Content generation Definition 2.11. Content generation (also referenced as procedural generation) describes the principle of creating game content (see Definition2.12) algorithmically rather than manually. In this project content generation (see Definition 2.11) is used to generate the game world. In particular it is used to generate the terrain with hills, caves, lakes, sea and resources, as the game world (as described in Definition 2.13). In the first part of this section the formal Definition of game content and the particular type of game content that will be generated in this project can be found. The second part describes the algorithms used to generate the content. In the last part the graphical presentation of the generated content is presented. 2.3.1 Game content Definition 2.12. The term game content spans from the graphics displayed in the game to the story line. Simplified could be said it is everything the player actually sees while playing the game. Important is to distinguish it from the game logic, which would be the underlying game engine, the controls and features (e.g. the graphics used in the user interface are game content, but the actions that can be done by interacting with the user interface are features). In particular for this project the game world (see Definition 2.13) consists of blocks (see Definition 2.15) allowing the player to alternate the appearance of the game world by adding and removing such blocks. To divide the game world in a more efficient manner the world is divided in so called world chunks (see Definition 2.14). Definition 2.13. The game world is the landscape the players travel on in the game. It can contain decoration objects (e.g. trees, buildings, stones and grass) and terrain formations (e.g. caves and overhangs). In particular for this project the game world consists of so called world chunks (see Definition 2.14). Definition 2.14. As described in Definition 2.13 the game world in this project consists of so called world chunks. This is useful to handle the game world in a better way and to enable the generation of 8 additional content on the fly. Each world chunk consist of 16*16*128 world blocks (see Definition 2.15. Definition 2.15. A world block is a block with the size of 2x2x2 (as defined by the jME graphics engine, see chapter 2.2), for a better understanding the player has about the same size as 2 blocks on top of each other. A world block can be transparent, solid and has a defined hardness and block type. The block type defines the appearance of the world block (e.g. Stone). In order to generate a realistic looking world different types of blocks are needed. Each type has its particularities. The implemented ones are listed below: • Unset represents a block that has not yet been calculated • Air represents void space and is invisible • Earth normally found on the higher levels and under a grass block • Grass is a block of earth that has grass on its top, this can only be found on the surface • Stone can normally be found under the earth and in caves • Coal the most commonly found resource in the game world that can mostly be found under the earth and in caves • Iron a commonly found resource n the world, can spawn at the same areas as coal • Gold a more rare resource that can only be found in the deeper areas • Soulgem a really rare resource that can be found in the same areas as gold • Titan an extremely rare resource that can be found in the same areas as gold and soulgem • Sand spawns near water • Water is used to create seas, lakes and puddles In order to generate the game world automatically certain algorithms are used. A short overview about the common algorithms and the used one can be found in the following section. 2.3.2 Noise Algorithms In order to create some realistic looking world, the result have to look randomly and it should have equally distributed peak values. In order to satisfy this criteria, a noise algorithm (see Definition 2.16) with a seed value (see Definition 2.17), which allows to reproduce the same game world, is used. 9 Definition 2.16. A noise algorithm is an algorithm that uses some sort of pseudo-random function to create a lattice of random values. Given some values the noise-algorithm returns the corresponding random value. This value is either the lattice point if the given values are the lattice position or some interpolation of the neighbouring lattice points if the given values are between lattice points. A one-dimensional noise algorithm maps each given value to a corresponding random value. Analogous a n-dimensional noise algorithm maps n values to a corresponding random value. Definition 2.17. The seed value is used in pseudo-random functions (e.g. noise algorithm) while calculating the random number. In most cases the seed value is used to reproduce the generated random values and to create multiple possible random values by changing the seed value. There are two main types of noise algorithms: the value noise and the gradient noise, as described in defintion 2.18 (value noise) and Definition 2.19 (gradient noise). Definition 2.18. The value noise creates a lattice of points which are assigned with a random number. The values between the lattice points are interpolations based on the neighbouring points, to create a smooth transition. Definition 2.19. The gradient noise creates a lattice of points which are assigned with a random gradient number. The values between the lattice points are interpolations based on the neighbouring points, to create a smooth transition, like with the value noise. The results of the gradient noise are more detailed at the cost of a more complex algorithm. For the presented game world (see Definition 2.13) there is no need for such details and therefore the value noise is used. 2.3.3 Graphical presentation In order to visualize the generated content an addition to the jME graphic engine has been developed. The so called block engine is introduced in Definition 2.20 Definition 2.20. The block engine is used to display the Minecraftlike game world that is used in this project. It can also be called voxel engine, if considering the blocks as voxel with a type instead of a volume parameter. As already mentioned (see the Definitions 2.13, 2.14 and 2.15) the game world consists of world chunks and world blocks. To display this world it would be inefficient to create a cube for each of our world blocks. The most blocks don’t need to be displayed as they are surrounded by solid blocks and can’t be seen. Furthermore it is more efficient to construct a coherent model with square faces, each face for 10 one visible block wall. This functionality will be covered by the block engine. The exact functionality is described in chapter 3.1.4. In order to display different types of blocks multiple textures are needed. As the game world will consist of just one model it is necessary to gather all textures needed by this model in one texture file. Such files are called texture atlas (see Definition 2.21). Definition 2.21. A texture atlas is a collection of textures in one file (e.g. all block textures). Each texture part consists of three textures to be shown on different faces of the block. There is a part for the top, one for the bottom and one for the four sides. The different types of world blocks are listed in the Tables 1, 2 and 3, with their corresponding texture, like it can be found on the texture atlas and a picture how it looks on a block. World block Unset Air Texture Invisible Invisible 3D-Model Invisible Invisible Earth Grass Stone Table 1: List of the world block types. 11 World block Texture 3D-Model Coal Iron Gold Soulgem Titan Table 2: List of the world block types continuous. 12 World block Texture 3D-Model Sand Water Table 3: List of the world block types continuous. The textures are divided in quarters, were the top left quarter is the top face. The top right quarter is for the sides and the bottom left quarter is for the bottom. The bottom right quarter will not be displayed and can be ignored. 2.4 Network This subsection describes the model used for the network part. The first four Definitions provide the basic for the following parts. Definition 2.22. The game servers are the whole server landscape, without referring to a specific part of it. Definition 2.23. A player is the user of our software. As we aim to create a MMOG, it is obvious that we need some game program for the players. Definition 2.24. The game client is a stand-alone program with a graphical representation of the game world and a connection to the game servers. The players can use the mouse and keyboard in order to move around or change the game world. 13 Definition 2.25. The network is every part of the implementation that is involved in connecting clients and the different game server types. With this all basic terms needed for the network are introduced. Now follow the different server types. Definition 2.26. The Chunk Server is the program that handles parts of the game world and enables all player interactions within this part. The Chunk Servers are the part of the network with the highest work load. They make all calculations that are triggered when a client runs, jumps and changes the game world. Like already mentioned the game world consists of many world chunks. Because each world chunk is more or less independent from other world chunks it makes sense that dividing the load of handling lots of clients is done by letting different Chunk Servers handle as much world chunks as possible. Assuming that the overhead of letting a chunk server handle just handle a few world chunks (and therefore have many Chunk Servers involved in handling a small area of the game world) isn’t great (like it should be in our implementation), the only limitation on the number of concurrent players in the game is the number of players that can be handled on one world chunk at the same time. A Chunk Server will only send messages to clients that have their position currently on its own managed world chunks. But in order to send them the movements of other clients within range a Chunk Server must still receive the position and actions of all clients within a defined range to handled world chunks. Definition 2.27. The Session Manager is the core of the network. For each game world exists only one Session Manager which distributes the load between the Chunk Servers and accepts login requests of game clients. The network is created such that the shutdown of the Session Manager is tolerable for a short time period but a longer failure would be fatal. The only problems that this would cause are that players can’t connect to the game and that the load balancing is suspended. When the Session Manager is restarted the game flow should continue normally. Definition 2.28. The network client is the part of the game that sends and receives messages to and from the game servers. Because each client contains a network client it may happen that we write about clients but mean the contained network client. After the login at the Session Manager the network client connects to all Chunk Servers that are handling world chunks that are within a defined range from the actual position of the client. The client sends each movement to each Chunk Server within range. Other changes on the game world 14 (like picking up world blocks, or putting some down) are sent only to the Chunk Server that handles the specific world chunk where the change happened. The cause of this difference will be explained later. Figure 5 shows an overview of the network architecture. Chunk Servers Clients LogIn Play game Enable load balancing Session Manager Figure 5: Graphic network One of the goals of this thesis is to create a game server landscape where more than thousand players can be online at the same time. Because it is impossible to find enough people that would act as beta testers, a different approach was chosen: Because it is impossible to find enough people that would act as beta testers, we created some different automated clients (bots) which will be used to test the scalability of the network. Each bot is in its core a game client without graphical interface. In order to create different test settings we created clients that act in a different way. Definition 2.29. We define three classes of client bots with the following distinct behaviour patterns: 1. Hermit: Avoiding all other clients 2. Explorer: Moving around with randomly chosen temporary destinations 3. Social bot: Always moving to the most populated, currently visible area The last part of this section is the introduction of a tool that is not strictly necessary, but was useful during the development of the thesis. Definition 2.30. The administration interface (as seen in Figure 6) is a stand-alone program that displays the load of all connected Chunk Servers to a specified Session Manager. Actually it is only possible to see the name and load of each Chunk Server. In the future it would be possible to use the interface to give a Chunk Server the order to shut itself down, so it can be updated, 15 Figure 6: Picture of the Administration interface or for a quick manual relocation of world chunks, when the automatic mechanism encounters problems. 16 3 Architecture In this section the architecture of our implementation of a Massively Multiplayer Online Game is presented. We propose an organisation of the game world in single world blocks which are automatically generated by using value noise algorithms to form a realistic looking game world. The network part on the other hand will be organized in a central Session Manager, multiple Chunk Servers and a part of the game client which is responsible for the network communication. A short overview of the architecture is shown in Figure 7. Client Content Generation Network Chunk Servers Graphical representation of the game world Clients Clie nt N etw ork part LogIn Play game Enable load balancing Session Manager Figure 7: Overview of the architecture 3.1 Content generation (by Bernd Altst¨ atter) In the following subsections the implementation of the noise algorithm and content generation are presented. 3.1.1 Content generation In the class ValueNoise.java the implementation of the value noise can be found. It is implemented as given by Hugo Elias [6], which is one of the most cited sites for value noise. Unfortunately the author titled it Perlin Noise, which is clearly wrong. Out of the context, you would think, he just named it Perlin Noise because he thought its the name for noise function that uses the sum of different frequencies to get a more detailed noise, but as a matter of fact Perlin Noise is a popular noise developed by Ken Perlin[13]. The value noise described by Hugo Elias depends on a random number method that generates a value between -1 and 1 for some given input values (two values x and y for two dimensional noise and three values x, y and z for three dimensional noise); in the particular case of this 17 project noiseFunction(int x, int y) and noiseFunction(int x, int y, int z). The input values for the random number method are integers, so the lattice is aligned on them. To create smooth transitions the values between are interpolated and the lattice points are smoothed. The methods noiseValue(double x, double y) and noiseValue(double x, double y, double z) retrieve the final noise value for the given parameters. To get a detailed noise value different frequencies of the noise are combined, as show in Figure 8. The noise values are retrieved by passing the given parameters (x, Figure 8: Summation of one dimensional noise [6] y or x, y, z) to the interpolation method. The methods interpolatedNoise(double x, double y) and interpolatedNoise(double x, double y, double z) divide the given values into their integer value and their fractional portion and get the smoothed values (using smoothNoise(int x, int y) or smoothNoise(int x, int y, int z)) of the adjacent lattice points by using the above methods. Then it interpolates the values with the fractional portion which will lead to the actual noise value. The methods smoothNoise(int x, int y) for two dimensional noise and smoothNoise(int x, int y, int z) for three dimensional noise are used to smooth the lattice points. Therefore we take the sum of the adjacent corner and side values and divide them so that they each affect the result by a quarter and for the remaining half the actual value is used. In order to create reproducible noise values we use an integer seed value, which influences the random number method and is set at initialization time. 3.1.2 The game world As previously mentioned7 the game world consists of world chunks and they again consist of a three dimensional array8 of world blocks. The motivation to design the world like that, is that it is possible to create holes and overhangs. The world can be made ediTable by the player and could be generated endless (with the limitation of the variable boundaries e.g. the integer maximum or minimum). With the game world defined as above the automated generation bears new challenges. The main two challenges that arise are, that a three dimensional world has to be generated three dimensionally; i.e. it is not enough to just generate some sort of height map. So the issue to face is creating caves. There were to possible ways: To generate the landscape out of a height map and then sculpt the caves out of it or to create the landscape with a three dimensional algorithm that already 7 8 see Chapter 2.3.1 on Page 8 its a 16x16x128 array of world blocks 18 creates us caves. In this project the first approach is used, because that gives a more realistic looking result. The reason for that, is that the three dimensional algorithm would not create hills, vales and indents; it would rather generate some sort of cloud. This problem can be fixed by combining it with a two dimensional noise, but doing so is nearly the same as the first approach, because height maps are generated by two dimensional noise. 3.1.3 Generation of the game world Generating a world chunk starts in the class MapChunkGenerator.java, as the world chunk is passed to the method generate(ClientMapChunk mapChunk). Initially a height map using two dimensional noise is created. A 16x16 array containing the height value for each position is created for the chunk using the method getHeight(int x, int y) of NoiseUtil.java, which returns a value between MIN TERRAIN HEIGHT (we use 48) and MAX TERRAIN HEIGHT (127) for the given position. Then the methods generate(ClientMapChunk mapChunk) continues and starts each of the given height values and iterate over the remaining height into the depth of the terrain (i.e. from the height value to zero). By default the world block array is initialized with air blocks, so the block above of the height value are air blocks. If somewhere the height value is under the global sea level (a value between MIN SEA HEIGHT (70) and MAX SEA HEIGHT (90)) the difference will be filled with water. In that way seas and lakes are created. The class NoiseUtil.java is used to fit the generated noise values to the game world particularities. As the method generate(ClientMapChunk mapChunk) iterates over the height values the current position is given to the method getBlockAt(int x, int y, int z, int heightLevel) (see listing 1), which calculates which block should be at the given position. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public BlockEnum g e t B l o c k A t ( i n t x , i n t y , i n t z , i n t heightLevel ) { // p r e v e n t h o l e s i n t h e bottom i f ( reachedBottom ( x , y , z ) ) return BlockEnum .STONE; // c h e c k i f t h e r e s h o u l d be a i r i f ( isHole (x , y , z ) ) return BlockEnum . AIR ; // c h e c k i f i t i s sand i f ( isSand (x , y , z , heightLevel ) ) return BlockEnum .SAND; // c h e c k i f i t i s g r a s s i f ( isGrass (x , y , z , heightLevel ) ) return BlockEnum . GRASS ; // c h e c k i f i t i s e a r t h i f ( isEarth (x , y , z , heightLevel ) ) return BlockEnum .EARTH; // −−− Checking f o r r e s o u r c e s −−− // c h e c k i f i t is coal i f ( i s R e s o u r c e ( x , y , z , BlockEnum .COAL) ) return BlockEnum .COAL; // c h e c k i f i t i s iron i f ( i s R e s o u r c e ( x , y , z , BlockEnum . IRON) ) 19 23 24 25 26 27 28 29 30 31 32 33 34 return BlockEnum . IRON ; // c h e c k i f i t is gold i f ( i s R e s o u r c e ( x , y , z , BlockEnum .GOLD) ) return BlockEnum .GOLD; // c h e c k i f i t i s soulgem i f ( i s R e s o u r c e ( x , y , z , BlockEnum .SOULGEM) ) return BlockEnum .SOULGEM; // c h e c k i f it is titan i f ( i s R e s o u r c e ( x , y , z , BlockEnum . TITAN) ) return BlockEnum . TITAN ; return BlockEnum .STONE; } Listing 1: NoiseUtil.getBlockAt() calculates which block is generated at a certain position. Therefore it uses a couple of methods to handle the prerequisites of each type of world block as listed below. The player should have to dig into the game world to find resources (as this is one of the games key features), therefore resources can only be found below a given height value, e.g. coal can only be found below a height value of 100, more seldom resources are only found deeper in the world (e.g. soulgem at a height of 40 or lower). The probability value of the resources should simulate their rarity, titan and soulgem for example should be really rare (how accurate the presented algorithm is can be read in chapter 4.1.2). The algorithm returns the first matching block type, so the order in which the methods are called is crucial. • Bottom of the world: to ensure that the generated caves to not reach the bottom of the chunks, which would create a hole in the bottom, depending on the height the given position will result in stone. At the moment the user can just dig through the stone manually, but if that is an unwanted behaviour, it could be exchanged by some indestructible world block. • Caves and holes: using a three dimensional noise, the given position will be void space or simply air, if the absolute value of the resulting noise value is under a given threshold (in our case 0.35; i.e. 35%). • Sand: If the position is near water (i.e. the height value of either a surrounding position or this position is smaller than the global sea level) and the difference between its height and the height value is between 2 and 5 (the value is calculated by a different seeded noise function) it will be sand. • Grass: If the position on the surface (i.e. the height of the position is the height value) and not underwater it will be grass. • Earth: If the difference between the positions height and the height value 20 • • • • • is between 2 and 10(calculated the same way as with the water, just with a different seed) it will be earth. Coal: Coal is the most frequent resource. To be coal the given position has to be 100 or less high and a different seeded noise value is used to generate about 0.5% coal in the game world. Iron: Works same as coal, just that it can only be 88 high and there should be around 0.1% iron in the game world. Gold: Gold can be found at a height of 60 and lower, with a chance around 0.05% Soulgem: Soulgem can only be found at 40 and lower, with a chance around 0.01% Titan: Titan can be found at the same areas as gold, with a chance around 0.005% Tweaking the values to fit the game world and result in a realistic looking way, consumed an unsuspected amount of time and work. As the final version of the code generates a quite decent looking result, it is out of question that it still could be improved. 3.1.4 Block Engine As already mentioned (see chapter 2.3.3 a framework for the generation of the game world model has been implemented, the block engine. It is needed as the representation of a block world with a good performance can not be solved by displaying multiple blocks. The presented solution, which can be found in the class VoxelEngine.class (in particular the method processMapChunk(ClientMapChunk mapChunk)), iterates other the world block array and checks for each world block its surroundings to compute the visible faces. Each visible face will then be added to the model and depending on the block type the corresponding texture will be set. Considering three blocks in a row if checking the faces of the middle block, the algorithm will show the left and the right faces of the middle bock, as there are adjacent blocks, like shown in Figure 9. Figure 9: Block engine: red faces will be invisible and blue faces will be visible 21 3.1.5 Controlls To interact with the game world the player can move and remove or add blocks. To look around he has to move the mouse. He can walk - in relation to the current looking direction - forward by using the W-key, back by using the S-key, left by using the A-key and right by using the D-key. For simplicity and presentation purposes physics are not implemented, as it would be an unneeded performance loss. To display the generated world it is only necessary that the player can move the camera around the world. To interact with the blocks the player has to select one, this is done passively as he looks at a block in range. Removing the selected block can be done with the left mouse button and adding a block at the side the selected block is looked at can be done by using the right mouse button. To change the block that will be set, the player can iterate other the available blocks using the ”,”-key (comma) and the ”.”-key (dot). As a visual feedback for the player the selected block is highlighted as shown in Figure 10 and the block to be set is shown as text on the bottom of the window. Figure 10: Client window with the visual feedbacks: highlight box (red square) and the block to be set (blue square). 3.1.6 Stand-alone client For test and presentation purposes a stand-alone version of the client has been developed, which generates the game world by itself. After setting up the general generation on the server (i.e. the height map generation) so that the world can be generated by the servers, the further work in this area has been done on the stand-alone client. This simplified it to work in parallel at the cost that it is not anymore possible to display different clients running through the world. In 22 theory it could be done, but after all it would consume a lot of time and work, while not having a real effect on the thesis. As the generation and display of the world chunks have become resource intense (more in chapter 4.1.4) the current world size has been limited to seven times seven (i.e. 49) world chunks. This is enough for testing different seeds and analyse the generated worlds. The generation algorithms of course would also work to generate the world on the fly, but as a matter of fact it is really challenging to concurrently generate the game world and still enable the player to run smoothly through the world without any lags. Solving this problem is clearly out of the scope of this thesis. 3.2 The network (by Daniel Gasteiger) In order to achieve the goal of supporting more than a thousand clients within a single distributed and persistent session a good network architecture is necessary. There were already many researches made in the past to find appropriate solutions for different problems (some are described in [5]; [9]; [11]; [14]) . Because we already have a world that is divided in squared blocks a solution similar to microcells (see [16]) was well suited for us. Starting with the setup of the used message framework over the network parts of the Session Manager, the Chunk Servers and clients to the load balancing the most interesting parts of the network are presented in this subsection. 3.2.1 Messages Sending messages between different network parts is obviously necessary before anything else. The JME provides for this purpose the class AbstractMessage. In order to create a new customized message a new class must be implemented that extends AbstractMessage. All variables that should be sent with the message should be added as class variables (with getter methods). Because messages should be instantiated only one time there is no need for setter methods and a constructor with all variables is enough. An additional empty constructor is needed by the JME framework for internal setup. The following two limitations/restrictions of the jME must be considered when implementing the message classes: First it is necessary that each of the message classes must be registered to each end of the connection (client and game server). It is not enough that the classes are in the same project. In order to register the messages the JME provides the static method Serializer.registerClass(class cls) with which a message class can be registered. There are two ways to use this method. The programmer must either ensure that the order of the message class registration is always the same, or he must add an annotation (com.jme3.network.serializing.Serializable) to each message class where a unique ID can be assigned to the class. Ensuring that the ID is really unique is the duty of the programmer. All classes that 23 are sent with a message must add the above mentioned annotation and also implement the java.io.Serializable interface. The other restriction that must be considered is the limitation of 32k byte for the message content. Unfortunately our world chunks are with 16*16*128*1byte = 32768 bytes a little bit too great (one world block takes one byte because the used enumeration encodes the world block types into an integer). The solution for this problem is the implementation of a CompressedMessage class that compresses an arbitrary given message with standard java classes (java.util.zip.DeflaterOutputStream and InflaterInputStream). As long as there aren’t plenty of different world block types (which would worsen the compress effect), this solution works well. 3.2.2 Session Manager As mentioned the Session Manager is the core of the network. The class SessionManager implements the IServer interface and acts as the central game server for all registered Chunk Servers and clients. In order to do so it must handle the details of the connections to them. The Session Manager must also know which Chunk Server manages which world chunks in order to pass the information to newly connected clients. The Session Manager does also the calculations and agency for the automatic load balancing between the Chunk Servers. All Data that the Session Manager has about the Chunk Servers are saved in instances of the class CSDataForSM. Figure 11: Class diagram of the Session Manager When talking about the scalability of the network architecture it is important to point out that the Session Manager doesn’t have any ongoing calculation duties that may be a bottleneck with a huge amount of clients and a lot of Chunk Servers. The only exceptions are the frequent load updates from the Chunk Servers, but even that could be 24 handled in a non-frequent way (but the frequent updates are actually quite useful when evaluating the load balancing). Figure 11 shows the class diagram of the Session Manager. 3.2.3 Chunk Server As we saw in the model a Chunk Server (or better said an instance of the class ChunkServer ) must know about many parts of the network. Obviously it has to know everything about all handled world chunks and about the clients that have their position on one of these world chunks. In order to pass on information about other Chunk Servers that handles neighbouring world chunks (to the own handled one), the Chunk Server must have also information about selected other Chunk Servers. In order to manage these data the following classes were created: ClientDataForCS and CSDataForCS. Figure 12 shows the class diagram of the Chunk Server. Because most of the code is the same for both a Session Manager and Chunk Servers we decided to create only one java project and select the type of the started server at program start. 3.2.4 Client network classes The central class for the client part of the network is CClientSM. This class primary represents the connection to the Session Manager, but builds also the core at organizing the connections to the Chunk Servers. Each connection to a Chunk Servers is realized with an instance of the class CClientCS (see Figure 13 for the whole class diagram). The single instance of CClientSM manages also all interesting details (like name and position) about other clients which were once nearby during the actual session. In order to improve security and prevent unauthorized access to the Chunk Servers, a client sends its username and password to the Session Manager and receives in return a randomly created SessionID. This SessionID is passed from the Session Manager to each Chunk Server that handles a world chunk within a range of the actual client position. When a client sends a message to a Chunk Server the Chunk Server reacts only when the SessionID is valid. If a Chunk Server gives the client information about another Chunk Server (e.g. when the client requests information about a neighbouring world chunk) it sends also the SessionID and username of the client to the other Chunk Server. This way the client doesn’t have to send the password to each Chunk Server, but can nevertheless be sure that no other client can act in its name. 3.2.5 Distributing the game world Distributing the game world and everything that happens on it to each client is the main goal of the whole network. One goal when distributing the game world is to keep the handled areas of world chunks as compact as possible in order to lessen the amount of Chunk Servers a 25 26 Figure 12: Class diagram of the Chunk Server Figure 13: Class diagram of the network classes of the client client is connected to at the same time. On the other hand it would be also important to consider that some world chunks produce more CPU load (like world chunks with cities), while other consume nearly only memory (like world chunks with just a few clients on them). It would be optimal if this is also considered when distributing the world chunks. CS2 CS3 CS1 CS4 CS5 Unmanaged chunks are black Figure 14: Game world 27 Figure 14 shows a possible handling of a (very small) game world with five Chunk Servers. Supposed a client connects to the Session Manager. The Session Manager sends the client all information about the Chunk Servers that are handling world chunks within a defined range (e.g. 3 world chunks) from its start position (Figure 15). Visible chunks to player Player position Figure 15: Game world 2 In this case the client has information about the Chunk Servers CS3 and CS4 to which it sends all movements and other actions, while receiving messages about changes on the visible world chunks. Assumed that the client moves a little bit upwards, just enough to step on the next world chunk (Figure 16), a unknown world chunk is within sight of the client. chunk from unknown CS Figure 16: Game world 3 After a corresponding request CS4 will send the data of the world chunks it handles to the client. But what happens with the world chunk in the top left corner? The client has actual no information about the handling Chunk Server. It has only the possibility to ask either the 28 Session Manager or the already known Chunk Servers about information for this specific world chunk. Because asking the Session Manager would be fatal for the scalability of the network, the client sends a request regarding the needed information to the Chunk Servers that handle an adjacent world chunk. This is the cause why every Chunk Server must know who handles neighbouring world chunks. After receiving the message that CS2 handles this world chunk, the client asks it about the world chunk and will receive all necessary information. Let’s consider another possible case in Figure 17: unhandled chunk Figure 17: Game world 4 The client moves one world chunk up and asks CS4 for a world chunk (the top right one) that isn’t handled yet by any Chunk Server. But CS4 knows about this and sends a request to the Session Manager that it would like to handle this world chunk. After the Session Manager approves this, CS4 generates the world chunk (in lack of a central storage, from where it could be loaded) and sends it to the client. 3.2.6 Distributing the load The second main duty of the servers after distributing the game world is the distribution of the load. The load that a certain amount of world chunks creates to a Chunk Server depends greatly on how many clients are currently active on these world chunks and what the clients are doing on the world chunks. In order to react to these possible changes it is necessary to implement something better than a static distribution of the world chunks to the Chunk Servers. The solution to this problem would be an approach where the world chunks are distributed dynamically between the Chunk Servers, so that the load is evenly balanced between all Chunk Servers. There are three challenges: Finding the world chunks that should be moved, finding the best Chunk Server that should handle them in the future and finally moving them to the new Chunk Server. 29 Finding the best suited world chunks to remove We use the following algorithm to find the best chunks that should be removed from a Chunk Server. The method calcChunksToRemove is part of the ChunkServer class. 1: function calcChunksToRemove(Bottleneck bottleneck, 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: Integer range) M ap < M apChunkP osition, Integer > chunkM ap for all chunk in chunks do chunkM ap.put(chunk, 0) end for for all client in clients do chunkM ap.get(client.pos).incrementV alue() end for M ap < M apChunkP osition, Integer > chunkM apArea for all chunk in chunks do Integer population for all neighbor in chunk.neighbours(range) do population ← population + chunkM ap.get(neighbor) end for chunkM apArea.put(chunk, population) end for List < Entry < M apChunkP osition, Integer >> sortedDensityList if (bottleneck = CP U ∨ bottleneck = N ET W ORK) then sortedDensityList ← sortDescending(chunkM apArea) else sortedDensityList ← sortAscending(chunkM apArea) end if Integer toRemoveClients = M ath.min( Conf ig.getRemoveClientN umber, clients.size()) 28: Integer toRemoveChunks = M ath.min( Conf ig.getRemoveChunkN umber, chunks.size()) 29: 30: 31: 32: 33: 34: 35: Boolean f oundAllChunks ← f alse Set < M apChunkP osition > removeChunks while f oundAllChunks = f alse do for i = 0 % chunkM apArea.size do Entry < M apChunkP osition, Integer > actEntry = sortedDensityList.get(i) 36: if (removeChunks.contains(neighbor) ∨ (neighbor.isBorderChunk())) then 37: for all neigh2 in actEntry.neighbours(range) do 30 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: if neigh2.handledByT hisCS() = true then removeChunks.add(neigh2) toRemoveChunks.decrement chunkM apArea.remove(neigh2) end if end for removeChunks.add(actEntry.getKey()) toRemoveChunks.decrement toRemoveClients ← toRemoveClients − actEntry.getV alue() f oundChunk ← true sortedDensityList.remove(i) densityM apChunkArea. remove(actEntry.getKey()) break end if end for if (bottleneck = CP U ∨ bottleneck = N ET W ORK) ∧ (toRemoveClients ≤ 0) then f oundAllChunks ← true end if if (bottleneck = RAM ) ∧ (toRemoveClients ≤ 0) then f oundAllChunks ← true end if end while return removeChunks end function In the lines 2-9 the actual number of clients on each handled world chunk is calculated (Figure 18(a)). In the following nested for-loops the accumulated population of a wider area is calculated, where the range is a parameter of the method (a graphical representation of the results with range 2 is shown in 18(b)). This additional step is done in order to smooth the density of the clients, which is necessary when searching for larger suited areas instead of punctual world chunks. The map with the population is sorted by the number of clients. In order to avoid repeating code the sorting is ascending or descending, depending on the given bottleneck that caused the call of this function. The bottleneck may be the CPU, memory or network load. When the CPU or the network loads are the bottleneck it would be useful if world chunks with lots of clients are moved to another Chunk Server. If the bottleneck is the memory, it would be better to remove world chunks with a low population because they need a lot of memory without generating a lot of CPU or network load. The Config.getRemoveClientNumber and Config.getRemoveChunkNumber in the lines 27 and 28 are parameters that should be given either by a config file or dynamically calculated due to the situation of the network. 31 0 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 4 0 0 0 0 0 0 0 2 0 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 3 0 2 0 2 4 4 4 2 3 1 1 1 0 0 0 0 0 0 0 0 0 (a) printChunkMap 2 8 8 8 7 7 1 1 1 4 4 4 4 4 10 10 8 8 4 10 10 8 8 4 13 13 14 14 10 12 12 12 12 8 11 11 14 13 9 5 5 10 9 9 5 5 10 9 9 2 2 3 3 3 2 2 2 5 3 5 5 5 2 (b) printClientMap Figure 18: A possible distribution of the clients on the handled world chunks of a Chunk Server The second eligibility criterion (the first is the number of clients) is that the chosen world chunks are border world chunks(at least one of the eight neighbours isn’t handled by the actual Chunk Server). With this criterion a too scattered game world is prevented. In the last part of the algorithm (lines 33-59) the sorted map is checked repeatedly to find the world chunk with the highest population that also is a border chunk. When such a world chunk is found all handled world chunks are marked to be moved that are within the given range around the found one. One problem of a first version of this algorithm (without the additional map of the density of wider areas) was, that it happened that very small sections of the managed world chunks are moved to other Chunk Servers (like in Figure 19). move this chunks Figure 19: Move world chunks 32 Although this shouldn’t cause a high overhead, it would be better if greater areas of world chunks are moved to other Chunk Servers. When using the improved version of the algorithm we see (Figure 20) that the results improve. move this chunks Figure 20: Better way to move world chunks Although this still isn’t the best solution it should work well enough for a first approach to find the best fitting world chunk. Detect optimal Chunk Server to handle new world chunks After the world chunks are selected and sent to the Session Manager it must detect the best Chunk Servers to overtake the world chunks. The most important criterion when selecting the suited Chunk Servers is their current load. It makes no sense to move world chunks to a Chunk Server that has an even higher load than the previous one. And again it is important that the world chunks are assigned to Chunk Servers that handle adjacent world chunks in order to avoid a too scattered world. The following algorithm generates a map containing each Chunk Server with its newly assigned world chunks: 1: function calcBestHandlingCSForChunks(Set < M apChunkP osition > toHandleChunks, Set < String > exceptedCSs, Integer maxSearchDistance) 2: 3: 4: 5: 6: 7: 8: 9: 10: Integer maxN eighborW eight ← 1 for i = maxSearchDistance & 1 do maxN eighborW eight ← maxN eighborW eight ∗ i ∗ 8 + 1 end for M ap < String, Integer > priorityM ap for all chunk in toHandleChunks do priorityM ap.clear() 33 11: 12: 13: 14: 15: 16: Integer neighborW eight ← maxN eighborW eight String priorizedCS ← null for i = 1 % maxSearchDistance do for all neighbor in pos.getN eighborSquare(i) do if neighbor.isHandledByT hisCS() = true ∧ exceptedCSs.contains(neighbor.getCS() = f alse) then 17: priorityM ap.getV alue(neighbor.getCS()) .add(neighborW eight) 18: end if 19: end for 20: 21: 22: 23: 24: 25: 26: 27: Integer maxP riorityP oints ← 0 for all actCS in priorityM ap.keySet() do Integer actP riority ← priorityM ap.get(actCS) if actP riority > maxP riorityP oints then priorizedCS ← actCS maxP riorityP oints ← actP riority else if actP riority = maxP riorityP oints ∧ i 6= maxSearchDistance then 28: priorizedCS ← null 29: end if 30: end for 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: if priorizedCS 6= null then break end if neighborW eight ← (neighborW eight − 1)/(8 ∗ (i + 1)) end for if priorizedCS 6= null then newHandlingCSM ap.get(priorizedCS).add(chunk) else noCSN earByChunks.add(chunk) end if end for if noCSN earByChunks 6= empty then if waitingCSIsAvailable() then newHandlingCSM ap.put(nextF reeCS(), noCSN earByChunks) end if List < String > possibleCS.addAll(connectedCS) possibleCS.removeAll(exceptedCSs) if possibleCS 6= empty then newHandlingCSM ap.get(randomCS(possibleCS)) .add(noCSN earByChunks) end if end if 34 55: return newHandlingCSM ap 56: end function The method parameter toHandleChunks contains all world chunks that should be moved, the parameter exceptedCSs contains all Chunk Servers that are not suited to handle these world chunks (e.g. the actual handling Chunk Server and overloaded ones). The parameter maxSearchDistance indicates finally the maximum distance for which the method should search for suited Chunk Servers in the neighbourhood. Chunk Servers that handle closer world chunks should have the priority when the world chunks are distributed. In the lines 3-6 a weight is calculated to fulfil this task. In the for-loop (line 9-43) the neighbourhood of each given world chunk is searched for an appropriate Chunk Server. The for-loop from line 14 to 36 runs through each possible distance, beginning with the lowest. The next for-loop (line15-19) runs finally through all neighbours at a given distance and adds the actual weight to the value that its current managing Chunk Server already has for the actual world chunk. The last for-loop finds the Chunk Server that has the highest weight with the current search distance. If this Chunk Server is unique (or the search distance is maximal) the world chunk is assigned to this Chunk Server (line 39). If no other Chunk Server was found within the given range the world chunk is marked as not assignable yet. The last if-branch (line 45-54) assigns the marked world chunks to an idle Chunk Server if available or else to a randomly selected Chunk Server. For a better visualization the following three examples (Figure 21, world chunks A,B,C) are provided: A B C Figure 21: Possible world chunks to move The world chunk A has in its immediate neighbourhood three world chunks of the red Chunk Server, so it will be assigned to the red one. Chunk B has two world chunks of the red Chunk Server and two of the blue Chunk Server in its neighbourhood. If the search distance is greater than 1, then the world chunk will be assigned to the blue 35 Chunk Server because at the distance of two world chunks the ratio is 4 to 6. Chunk C on the other hand has no other managed world chunk by a different Chunk Server in its neighbourhood, so it will be assigned to a free Chunk Server or a random chosen one. Moving world chunks After the relatively simple part of deciding what world chunks should be moved to which Chunk Server (optimization would be the challenge here) the save movement of these world chunks is the final task. The clients shouldn’t notice that the Chunk Server has changed and of course there should be no loss of data or client actions when moving the world chunk. As already pointed out the Chunk Server informs the Session Manager which world chunks should be removed and the Session Manager finds the best Chunk Servers to handle these world chunks. After that the Session Manager sends each of these Chunk Servers a message containing all world chunks that should be handled by them with all necessary data to access the actual managing Chunk Server (first four actions of Figure 22). The new Chunks Server(s) enable a connection to the old one (through a double client-game server connection because the JME doesn’t support special P2P connections) and send a message to it that they are taking over the defined world chunks. After that they create dummies for all world chunks in order to be able to save changes on them and inform the clients even when the newly appointed Chunk Servers don’t have the old data about the world chunks yet. The old Chunk Server marks the world chunks as ready to move. This enables the forwarding (done by a second thread) of information (which is send to the old Chunk Server by clients) to the new Chunk Server without any other handling and delay. When all world chunks are marked, the old Chunk Server begins to send every data it has about the world chunks to the new Chunk Servers. The new Chunk Servers save only data about world blocks where they have received no new data yet (e.g. from forwarded messages). When all world chunks are sent the old Chunk Server informs the Session Manager that the movement was done. Only now the Session Manager sets the manager of the world chunks to the new Chunk Servers and sends clients and Chunk Servers the data of the new Chunk Server, when they request information about these world chunks. The old Chunk Server waits for a while (at the moment five seconds, but it would be necessary to reconsider this value) before cleaning up its own data about the world chunks. After that it reacts like it had never handled these world chunks. 36 37 Figure 22: Sequence diagram of the load balancing algorithm stop create dummies for chunks 3.3 Other parts (by Bernd Altst¨ atter and Daniel Gasteiger) 3.3.1 Client bot Each client bot is basically a client, who just has no graphical interface and therefore any implementation about how to display world blocks and world chunks. The network part on the other hand is pretty much the same as that of a regular client. The abstract class AbstractBot, which extends the class Thread, has basic methods (like moving and the run method) implemented, that are needed by every bot. The run method of this class contains an update management that ensures that a defined number of updates per second isn’t exceeded. When creating a new type of bots the AbstractBot class has to be extended and the abstract method update() be implemented. With this method the behaviour of the bot in each loop is defined. Like already mentioned we have implemented three different acting bots with the classes HermitBot, SocialBot and ExplorerBot. 3.3.2 Configuration Files Many parameters of the project depend on the actual circumstances and may be changed on the fly. For that purpose we created different xml configuration files to handle these parameters in a clean way. For each xml file exists a java file where each parameter is saved as a variable. These classes get their variables at the first access from the related xml file and have a method to save the variables into the xml file. In order to parse the xml files we used XStream 9 . 3.3.3 Graphical representation of server status For a better administration and functionality tests two different graphical representations of server status were implemented. These representations can be generated by calling the two methods printChunkMap( Map handledChunks, String fileName, String fileType ) and printClientMap( Set handledChunks, Set clientPositions, String fileName, String fileType ) of the class GraphicalOutput which will create a picture in the program directory with the given file name and type. If a picture under this name exists already a number will be added at the end of the file name to make it unique again. The method printChunkMap is made for the Session Manager in order to print a map containing all world chunks and the Chunk Server that is handling them. The Chunk Servers are marked with a unique color. The method printClientMap is designed for a Chunk Server and creates a picture containing all world chunks that are managed by this Chunk Server at the moment and the amount of game clients that are 9 http://xstream.codehaus.org/, 2012-09-16 38 positioned on each world chunk. Because writing the exact number would require an unnecessary great picture an encoding of the number of clients into colors (between green, over yellow to red, depending on the density) was used. A red world chunk means that on this world chunks are currently the most clients, while a green world chunk means that there is no client on this world chunk. The color is given with a linear function, e.g. a yellow world chunks signalizes that there are exactly the half clients on this world chunk regarding the most populated one. In Figure 23 we can see both representations (Figure 23 shows the output of the turquoise Chunk Server). (a) printChunkMap (b) printClientMap Figure 23: Graphical representations 39 4 Evaluation This section presents the result of the project. Therefore the test results were gathered and analysed. In the first part of this section the results of the content generation are presented. In the latter part the network results are analysed. 4.1 Content generation (by Bernd Altst¨ atter) The results of the content generation are presented in the following subsections. In the first part some simple functionality tests are showed. The second part analyses the resulted resource distribution values and compares them to the selected ones. The last part shows the complexity of the generation algorithm and presents the measured generation times on different machines. 4.1.1 Block engine and Controls Starting the game After starting the stand-alone client, the game will generate the 7x7 chunks near the player and display them using the block engine. The player’s camera will be above the game world and so in order to see the world he will have to look down. Afterwards the game world as shown in Figure 24 will be seen. Figure 24: Standalone client after starting the game. (Seed: Hello World!) 40 Moving around To move around the player has to use the W-, A-, S- and D-Keys (as described in chapter 3.1.5). By moving around in the world with the seed ”Hello World!” we can reach places as shown in Figure 25. Figure 25: Places that can be reached by moving around the world. (Seed: Hello World!) Removing Blocks By pressing the left mouse button the user can remove the block marked by the highlight box (as shown in Figure 26). Figure 26: Removing a block 41 Adding Blocks By pressing the right mouse button the user will add the block shown by the UI10 (as in Figure 10 the blue square). The new block will be added at the side of the selected block, at which the cross hair points. The progress is shown in Figure 27. Figure 27: Adding a block 4.1.2 Correctness tests As mentioned above (see chapter 3.1.3) the game world is created with given prerequisites. To evaluate the correctness - as far as possible information is collected during the generation of the chunks. In the following the results for the three seeds ”Test Seed 1” (Figure 28 and Table 4), ”Test Seed 2”(Figure 29 and Table 5) and ”Test Seed 3”(Figure 30 and Table 6) are presented. The Tables 4, 5, 6 and 7 show the results of the generation using the given seeds and the average of ten different seeds. The Tables 4, 5, 6 and 7 contain five columns and are divided in two parts, separated by a horizontal line. The following list describes the five columns. • The first one identifies the type of block the given values belong to. Maximum is the total amount of blocks that are possible in a world chunk times the amount of created world chunks (i.e. if the whole game world is just one big cube). Height map is the amount of blocks that lie under the height values. • The second column, amount, shows the amount of blocks that the generated game world contains of the given type. (In the first part of the Table, there is no particular type given, as described above it contains the maximum amount of blocks and the actual amount of blocks) 10 User Interface 42 • The column percentage, describes the amount of the blocks in percentage. Therefore maximum is always 100%. In the first part the percentage values are calculated in relation to the maximum value. In the second part of the Table the percentage values are in relation of each of the given resources maximum height level (e.g. for soulgem it is 40) i.e. the space under the given height value (in the last column) contains the given percentage of this block type. This value should be about the same value, as in the next column. • The column probability displays the defined probability value of each resource (see the list in chapter 3.1.3 on page 20 for more informations). • The last column, height, displays the defined height limit of the resources (see the list in chapter 3.1.3 on page 20). Figure 28: The world created by using the seed Test Seed 1 Blocks Maximum Height map Coal Iron Gold Soulgem Titan Amount 1605632 1163012 6502 1166 422 63 30 Percentage 100% 72.433285% 0.518335% 0.105628% 0.056069% 0.012556% 0.005979% Probability 0.500% 0.100% 0.050% 0.010% 0.005% Height 100 88 60 40 40 Table 4: Blocks generated by using the seed Test Seed 1 43 Figure 29: The world created by using the seed Test Seed 2 Blocks Maximum Height map Coal Iron Gold Soulgem Titan Amount 1605632 1097794 5603 1041 422 70 17 Percentage 100% 68.371457% 0,446668% 0,094304% 0,056069% 0,013951% 0,003388% Probability 0.500% 0.100% 0.050% 0.010% 0.005% Height 100 88 60 40 40 Table 5: Blocks generated by using the seed Test Seed 2 Figure 30: The world created by using the seed Test Seed 3 44 Blocks Maximum Height map Coal Iron Gold Soulgem Titan Amount 1605632 1106378 5865 1033 433 52 25 Percentage 100% 68.906076% 0.467554% 0.093580% 0.057531% 0.010364% 0.004982% Probability 0.500% 0.100% 0.050% 0.010% 0.005% Height 100 88 60 40 40 Table 6: Blocks generated by using the seed Test Seed 3 Blocks Maximum Height map Coal Iron Gold Soulgem Titan Amount 1605632 1117758 6302 1190,4 436,2 56,7 26,4 Percentage 100% 69,614825% 0,502392% 0,107839% 0,057956% 0,011300% 0,005261% Probability 0.500% 0.100% 0.050% 0.010% 0.005% Height 100 88 60 40 40 Table 7: Average values from ten different seeds Evaluation In the Table 7 it can be seen that the height map fills up about 70% of the possible space. This fits to the previous selected values as the height can vary between 48 (MIN TERRAIN HEIGHT ) and 127 (MAX TERRAIN HEIGHT ), which leads to an average of 81% . Therefore and as the values are varying in the whole range (see Figure 28, 29 and 30), it can be considered that the algorithm is quite equally divided. Also it is not a requirement of the algorithm to be fully optimal, the main goal is to have realistic looking results. Furthermore looking at the percentage value of the resource, where a probability value (shown in the column desired value) has been set, it can be observed that in the average percentage fits the set probability quite well. 4.1.3 Complexity In a first attempt we iterated over the world block array to generate the world with grass on top, then earth, then stone. Then another iteration for each creates the caves and the resources. Obviously this was a suboptimal solution. To improve this solution a method (see listing 1 in chapter 3.1.3 at page 19) was created that returns the block at the given position, like this it is not necessary anymore to iterate six times over the whole array. Now, after generating the height-map, the game world can be 45 generated in one iteration excluding the values higher than the given height map. Considering the noise calculation as the most important function to calculate the complexity, i.e. neglecting the other calculations and describing the complexity regarding the noise method calls. Furthermore, as the three dimensional noise method is rather performance hungry, a more simpler approach for three dimensional noise method has been implemented, which calculates the median of the xy noise value and the xz - noise value and generates very similar looking results. Therefore the two dimensional noise has a complexity of one. Analogous to the two dimensional noise the three dimensional noise has a complexity of two. Method reachedBottom() isHole() isSand () isGrass() isEarth() isResource() 2D noise 1 0 9 0 1 0 3D noise 0 1 1 0 0 1 Table 8: Number of noise methods used in the worst case. It can be concluded that the presented solution has a worst case complexity of O((x ∗ y) + ((x ∗ y ∗ z) ∗ (11 + (7 ∗ 2)))) where x is the width, y the length and z the height of the world chunk. 11 + (7 ∗ 2) is the times the noise methods is used in the getBlockAt()method as you can see in the Table 8(as it can be seen out of listing 1, isResource() is used for each resource and therefore 5 times). In the average case, as the height map values will vary between 48 and 127 and considering an equal distribution of the values, the chunks are filled by 80% of their maximum, therefore the average complexity will be around 80% of the worst case. In addition as the resources are only spawned in certain heights. As you can see out of Table 9, the average resource height limit is 65.5 i.e 51.25% of 128, and therefore it can be assumed that the five noise calls for the resource only occur in 50% of the time and they can be classified as two dimensional calls. This leads as to an average complexity of O((x ∗ y) + ((x ∗ y ∗ z) ∗ (16 + (2 ∗ 2))) ∗ 0.8) and is a more optimal solution than the first approach, but could still be improved. A way to fasten the generation is presented it in chapter 5.1, at the cost that the generated content can no longer be analysed. 46 Resource Coal Iron Gold Soulgem Titan Average Height limit 100 88 60 40 40 65.6 Table 9: The resources will only spawn in the given height or lower. 4.1.4 Performance tests In order to test the performance of the content generation algorithm the total time, the average time per world chunk and the time per processor core (which is the actual time needed to generate the world) needed for generating a seven times seven game world (i.e. 49 world chunks) has been measured. The tests were executed on 4 different computers, with different hardware. The list below shows the different hardware setup and Table 10 the measured time. • PC 1 : AMD FX-4100 Processor 3.60GHz (Quad-Core), 8.00GB RAM, Windows 8 Professional 64-bit • PC 2 : Intel Core2 Quad Q8200 Processor 2.33GHz (Quad-Core), 4.00GB, Windows 7 Professional 64-bit • PC 3 : Intel Core i5-2410M Processor 2.90GHz (Dual-Core), 8.00 GB, Windows 7 Home Premium 64-bit • PC 4 : Intel Core i7-920 Processor 2.67GHz (Quad Core), 6.00 GB, Windows 7 Ultimate 64-bit PC PC PC PC PC 1 2 3 4 Total time 78047 ms 66489 ms 81788 ms 74830 ms Time per chunk 1592.7 ms 1356.9 ms 1669.1 ms 1527.1 ms Timer per core 19511 ms 16622 ms 20447 ms 9353 ms Table 10: The measured times on the used hardware. Evaluation: The measured values (Table 10) indicate that the total time and the time per chunk don’t vary much over the hardware. PC 2 got the best values in these categories, which is weird, because it has the oldest hardware. It can be assume that other applications caused more overhead on the other machines. PC 4 is fastest regarding the actual generation time. It can be seen that it strongly depends on the number of cores, even the virtual ones as in PC 3 and PC 4 (which use 47 hyperthreading11 ). The algorithm used to generate the world chunks, splits the work on as much threads as the pc has cores. The processors of PC 3 and PC 4 are constructed to allow two threads per processor core and simulate a virtual core for that purpose. Therefore PC 3 and PC 4 had an advantage. 4.2 Network (by Daniel Gasteiger) The evaluation of the network is split in functionality and stress tests. While the functionality tests should present how the single parts of the network work, the goal of the stress tests is to point out the capabilities and limitations of the implemented network architecture. 4.2.1 Functionality tests Starting the Session Manager After the deployed game server was started s is written in order to start a Session Manager. The program tries now to start a game server with the port that was defined in the configSM.xml file. If this was possible a message is printed to the command line. If not an error message is put out in the console, that something went wrong (most likely the port wasn’t free). Adding Chunk Server In order to start a Chunk Server instead of a Session Manager c is written after the deployed game server was started. It is important that the connection details to the desired Session Manager and a free port and free name are written in the used configuration file (ConfigCS.xml). Otherwise an error message is printed on the screen. The program connects immediately to the Session Manager and is registered as unemployed Chunk Server. The Chunk Server waits now until the Session Manager gives orders to handle world chunks. When the connection to the Session Manager fails the Chunk Server tries to reconnect itself to the Session Manager until it is stopped by the administrator. Connecting client to server Before starting a network client it is important that the configClient.xml contains the correct connection details to the desired Session Manager. When starting the network client it tries to connect to the Session Manager without further input possibilities. Because the client is still in state of development an eventual appearing error message is only showed in the command line instead of a proper graphical message. At this stage of the client some possible error messages 11 see http://www.intel.de/content/www/us/en/architecture-and-technology/ hyper-threading/hyper-threading-technology.html visited on 2012-12-20 48 would be a failure in connecting to the Session Manager and a failure in connecting to the Chunk Server whose connection details were send by the Session Manager. If everything goes well the client has now all connections which it needs at this moment. This behaviour is the same for each a real client and a client bot (because they contain the same network client). Ordering world chunks When the network client is connected to the Chunk Server that handles its start position it begins to order the adjacent world chunks. The number of chunks that defines the visible range of the game client is given by the configClient.xml. The client creates for each unknown world chunk a dummy chunk that contains only the position where it would be in the game world. Each of these unknown positions is requested from a Chunk Server that handles an adjacent world chunk. If no adjacent world chunk is known to the game client the world chunk in question is ignored for the moment. This has the advantage that the world is loaded in pieces, beginning with the closest world chunks. Each world chunk that was requested from a Chunk Server is registered in a waiting map (together with the request time), in order to ensure that it isn’t requested another time. If the world chunk arrives within a defined time (actually 5 seconds) the ordering was successful and the world chunk is removed from the waiting map. If no message arrived after the defined time the world chunk is removed from the map, an error message is displayed in the command line and the world chunk may be ordered another time if it is still in the visual range. Manual load balancing A manual load balancing (practically moving world chunks from one Chunk Server to another) may be useful when testing the server architecture or when some circumstances occur that the automatic load balancing can’t know (like a shutdown of a Chunk Server). In order to trigger the removal of world chunks from a Chunk Server it must simply be written removechunk in the command line of the Chunk Server in question. The Chunk Server searches now for the best world chunks to remove (it assumes that the CPU load is the problem) and sends an according request to the Session Manager. If the Session Manager finds no suiTable Chunk Server (when every other Chunk Server has already a higher CPU load) an error message is given out on the command line. If a suiTable Chunk Server (or even more than one) was found, the world chunks are moved to them like described in the previous chapters. In order to trigger the complete removal of world chunks exit must be written in the command line of the Chunk Server. The Chunk Server will now give the Session Manager the order to find a Chunk Server for its entire world chunks (even when the best suiTable Chunk Server has a higher load of CPU, RAM and/or network). When all world chunks were removed (and all game clients have connected to the new handling Chunk Server), the Chunk Server quits. 49 Automatic load balancing In contrary to the manual load balancing the automatic load balancing is triggered when the Chunk Server has a too high load of one type (CPU, RAM or network). The Chunk Server sends then a message to the Session Manager containing the calculated (according to the actual bottleneck) world chunks that should be removed. At the moment the critical load is set to 80% of the available resources. Interaction between players When players move on the game field, each movement is reported to each Chunk Server that handles a world chunk in the player’s visible area. The Chunk Server that handles the new position forwards the position to all players that are within the visible area of the moving one. This information is together with the set or removed world chunks the only possibility of interaction between different players yet. Shut down client A game client may be simply closed. When the Session Manager and Chunk Servers register that the connection was lost, they handle this in an appropriate way. The Chunk Server that handles the last position of the client sends a message to each other client within range that the first client has closed its gaming session. Shut down Chunk Server In order to shut down a Chunk Server properly exit should be entered in the command line. This command triggers the above mentioned movement of all world chunks to another Chunk Server. If the Chunk Server is shut down by other means the Session Manager will assign the world chunks that were managed by the deceased Chunk Server to another Chunk Server. The clients will ask the Session Manager for connection details about the new Chunk Server. This way it is possible for the game clients to continue the game. But all changes on the world are lost in this case because the data of the world isn’t managed yet in a persistent way. Session Manager shut down The Session Manager can be shut down by entering exit in the command line. The connected Chunk Servers will immediately try to reconnect themself to the Session Manager (using the same IP address and port), while the game clients will ignore this connection loss until they don’t need new information from the Session Manager. If the game clients need something from the Session Manager, they will also try to reconnect them. This way it is possible that the Session Manager is shut down for a short while even when the game is still running (like for a system update). When the Session Manager is restarted, the Chunk Servers will connect them to it and send all details that the 50 Session Manager needs (like handled world chunks). If the Session Manager isn’t started for a too long time period the game will collapse because for example no client login or load balancing is possible. Print game world Each the Session Manager and the Chunk Server can print their view of the world into a picture file. The Session Manager prints with the command print one picture per time. The Chunk Server can print a picture each defined milliseconds with the command start print and the delay in milliseconds. This automatic printing can be stopped with stop print. 4.2.2 Stress tests Such tests as are presented in this subsection are only meaningful for the network part of this thesis because there is a need to test different setups with powerful machines that simulate a ongoing gaming session. We provide for each test the setup and the evaluation of the results. Testing single Chunk Server The goal of this test is to see how many client bots a single Chunk Server can manage. Setup As mentioned before three types of different acting client bots (as defined on page 15) were created, which should also create different load distributions. In addition to the selection of the running client bots, also the number of actions that are sent per second to the Chunk Servers, the movement radius (in each direction) and the number of movements per second should make a great difference. These parameters were changed in each subtest. All other parameters were the same for all subtests (e.g. sight width = 3 world chunks, max. speed = 10 world chunks per second). The Chunk Server for this tests run on a machine with a 16 core processor (2.3GHz), 64 GB RAM and an Infiniband SDR network interface. The client bots and the Session Manager run on a machine with a 16 core processor (2.2GHz), 100 GB RAM and a Gigabit network interface. For this test we present the following subtests (Table 11): The column Radius specifies the greatest distance to the center, that a client bot may have (measured in world chunks). The entry Mixed in the column started client bots means that there were started the same amount of each of the three different client bot types. In each test the maximum of client bots that were still supported without errors (like great delays when receiving messages) were started. 51 Subtest No 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 No client bots 275 Hermits 250 Explorer 225 Socials 650 Hermits 100 Hermits 55 Hermits 150 Explorer 270 Mixed Radius 40 40 40 200 1.5 1.5 40 40 Movements/sec. 10 10 10 10 10 30 30 10 Table 11: Subtests of network test No 1 For each subtest the percentage of CPU cores that the Chunk Server needed and the amount of incoming and outgoing messages of the Chunk Server were measured. Evaluation The first evaluation was made on the results of the different tests regarding the CPU load. The legend of each Figure contains the subtest number and the parameters. 1800 C 1600 P 1400 U 1200 l o a d (%) 1) (H;40;10) 2) (E;40;10) 3) (S;40;10) 1000 4) (H;200;10) 800 5) (H;1.5;10) 600 6) (H;1.5;30) 400 7) (H;40;30) 200 8) (M;40;10) 0 0 100 200 300 400 500 600 700 Number of supported clients Figure 31: Graph of the CPU load during the tests As it can be seen in Figure 31 the load of the CPU depends highly on the chosen setup of each subtest. It is observable that for most tests the CPU load was the bottleneck. A CPU load of approximately 1600 % means that each core is completely busy. But on the other hand it is observable that for the subtests with a small movement radius the CPU load wasn’t the real bottleneck. The suspicion that the the amount of messages that must be sent is the bottleneck will be followed later on this case. In the following lines some details will be investigated. Figure 32 shows the results (regarding the CPU load) of four subtests, where the only difference in the setup was the kind of client bots that were 52 1800 C 1600 P 1400 U 1200 1) (H;40;10) 1000 2) (E;40;10) l o a d (%) 800 3) (S;40;10) 600 400 8) (M;40;10) 200 0 0 50 100 150 200 250 300 Number of supported clients Figure 32: Graph of the CPU load for different client bot types started. It can be observed that the lowest server load was created by the hermits, closely followed by the mixed client bots, which are followed by social bots and the explorers. The fact that the explorers created the higher load was somehow surprising. But when looking at Figure 33 that displays the distributions of the client bots over the map, it can be seen that the social bots concentrate on a lot of different places, so that there are hardly more than 4 or 5 client bots that see each other. The explorer bots are just randomly moving around and so it happens with this world size that they have more interactions with themself than the social bots. It can also be seen from the Figure that with a higher client bot number the social bots are increasing the server load faster (like expected). (a) Distribution of social bots (1.3) (b) Distribution of explorers (1.2) Figure 33: Distribution of client bots over the map 53 In a real MMOG there are always different types of players active. So the test scenario with the mixed client bots should be the best to simulate a real game state. The performance of this setup is pretty good, in fact nearly the same as in the best case where the interaction between client bots is reduced to a minimum (when using only hermit bots). The next interesting aspect is the maximum of supported client bots on a single Chunk Server. For this the subtests 1, and 5 were used. In Figure 34 the CPU load and number of outgoing messages/second from the Chunk Server can be seen. 90000 1600 80000 1400 C 1200 P U 1000 Outgoing messages/sec 70000 60000 50000 800 40000 600 30000 l o a d 20000 400 (%) 10000 200 0 0 0 50 100 150 200 250 300 1) (H;40;10) Message 5) (H;1.5;10) Message 1) (H;40;10) CPU 5) (H;1.5;10) CPU 350 Number of supported clients Figure 34: Graph of the CPU and message load for different world map radii Here it can be clearly seen that the number of messages can also be a bottleneck to the Chunk Server. About 75000 messages per second is the limit that a single Chunk Server can manage (on our used computer). It is clear that the message system should be improved if possible. Our ideas to this matter follow in section Summary and outlook. For the subtest with a movement radius of 200 world chunks the bottleneck didn’t occur anymore on the Chunk Server, but was simply the fact that the started client bots used up all of the 100GB of memory that were available on our machine used to start the client bots (and no useful diagram could be derived). Until now results for the different types of client bots and different movement radii were presented. The last variable parameter was the number of messages that were send to the Chunk Server from each client bot. Figure 35 shows the CPU load and number of outgoing messages/second from the Chunk Server for the subtests 2,5,6 and 7. To triple the amount of messages send from each client bot reduces the amount of supported players by 40-45%, while the curves maintain nearly the same slope. This gives hope to the assumption that a better message system would really improve the performance of the whole architecture. 54 Outgoing messages/sec 5000 1800 4500 1600 4000 1400 3500 1200 3000 1000 C P U 2500 800 1000 400 l o a d 500 200 (%) 2000 600 1500 0 0 0 50 100 150 200 Number of supported clients 2) (E;40;10) Mess. In 7) (E;40;30) Mess. Out 250 2) (E;40;10) Mess. Out 2) (E;40;10) CPU 300 7) (E;40;30) Mess. In 7) (E;40;30) CPU Outgoing messages/sec (a) Difference between explorers in middle-sized world 90000 900 80000 800 70000 700 60000 600 50000 500 40000 400 30000 300 20000 200 l o a d 10000 100 (%) C P U 0 0 0 20 40 6) (H;1.5;30) Mess. In 5) (H;1.5;10) Mess. Out 60 80 Number of supported clients 6) (H;1.5;30) Mess. Out 6) (H;1.5;30) CPU 100 120 140 5) (H;1.5;10) Mess. In 5) (H;1.5;10) CPU (b) Difference between hermits in smallest possible world Figure 35: Graph of the CPU and message load for different message rates The last interesting observation is the comparison of the results from these subtests to the results of subtests with the same setup, except that the Chunk Server runs on the same machine as the Session Manager and the client bots. Even though we run all subtests another time it proved that comparing the subtests 1 and 5 shows already the differences between these two setups (Figure 36). Even though the bottlenecks are still the same for both subtests, it can be seen that running the client bots on the same machine as the Chunk Server improves the number of supported client bots by approximately 45%. From these results it can be assume that also using two different machines in the same computer laboratory is a little bit like cheating and the results in a real situation with many different clients distributed over all the world (or at least Europe) would be even worse. But unfortunately testing this case is out of reach for this thesis. 55 10000 1600 9000 1400 8000 Outgoing messages/sec 1200 7000 6000 1000 5000 800 4000 600 3000 400 2000 C P U l o a d (%) 200 1000 0 0 0 50 100 150 200 250 300 Number of supported clients 350 400 450 1) (H;40;10) Message - machine1 1) (H;40;10) Message - machine2 1) (H;40;10) CPU - machine1 1) (H;40;10) CPU - machine2 500 (a) Difference between hermits in middle-sized world 120000 900 800 100000 Outgoing messages/sec 700 80000 C P U 600 300 l o a d 200 (%) 500 60000 400 40000 20000 100 0 0 0 20 40 60 80 Number of supported clients 100 120 5) (H;1.5;10) Message - machine1 5) (H;1.5;10) Message - machine2 5) (H;1.5;10) CPU - machine1 5) (H;1.5;10) CPU - machine2 140 (b) Difference between hermits in smallest possible world Figure 36: Graph of CPU and message load for different message machines Testing multiple Chunk Servers The goal of this test is to see how many client bots multiple Chunk Servers can manage. Setup Like the previous test multiple subtests were run which differ in the number of client bots, the number of movements per second and the distribution of the clients on the map. For this tests were used two computers with the same hardware (16 core (2.3GHz), 64 GB RAM and an Infiniband SDR network interface) to start the Chunk Servers. The client bots and Session Manager were started again on the same machine (16 core (2,2GHz) with 100 GB RAM and an Gigabit network interface). 56 The first goal of these tests was to evaluate how the number of Chunk Servers improves the maximum of handled client bots. The second goal was to find out if running multiple Chunk Servers on one machine improves the performance. The last goal was to get data on how much the performance depends on the distribution of the world chunk between the Chunk Servers. The implemented network architecture was tested with the following setups (Table 12): Subtest No 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 started client bots 425 Hermits 300 Explorer 375 Socials 300 Explorer 325 Explorer 350 Explorer 330 Mixed 480 Mixed 360 Mixed 540 Mixed 450 Mixed Radius 40 40 40 200 40 200 40 40 40 40 56.5 No of Chunk Servers 2 2 2 2 4 4 2 2 4 4 2 distribution of map on the fly on the fly on the fly on the fly on the fly on the fly on the fly two areas on the fly four areas on the fly Table 12: Subtests of network test No 2 In the column distribution of map is written how the Chunk Servers received their world chunks. On the fly means that the Session Manager searched for the best suiTable Chunk Server. This leads to a very dynamic distribution of the world, but has the disadvantage that the game world is more scattered. Two areas or four areas means that the world was already evenly distributed between all Chunk Servers when the first client bots arrived. Like in the previous tests in each subtest the percentage of CPU cores that were used by each Chunk Server and the number of ingoing and outgoing messages of each Chunk Server were measured. Evaluation To show the difference that multiple Chunk Servers make on the maximum of supported client bots the sum of the CPU load of each Chunk Server was taken and divided by the number of used machines. Figure 37(a) displays the results from subtest 2 and 5 of this test and subtest 2 of the previous test. Figure 37(b) displays the results from subtest 7 and 9 of this test and subtest 9 of the previous test. As expected the CPU load is nearly the half for each machine when using two machines. But when more client bots arrive the curve grows 57 Average CPU load (%) per machine 2000 1500 1000 500 0 0 50 100 150 200 250 300 350 Number of supported clients 2.5) (E;40;4) 2.2) (E;40;2) 1.2) (E;40;1) (a) Difference between supported explorers with different Chunk Server numbers Average CPU load (%) per machine 2000 1500 1000 500 0 0 50 100 150 200 250 300 350 400 Number of supported clients 2.9) (M;40;4) 2.7) (M;40;2) 1.8) (M;40;1) (b) Difference between supported mixed client bots with different Chunk Server numbers Figure 37: Graphs of the CPU load for different Chunk Server numbers still exponentially and the servers can’t maintain the double amount of clients with the same world size. If the size of the world is doubled it is possible to nearly maintain the double amount of clients (as shown in Figure 38). A second observation is that having more than one Chunk Server running on the same machine seems to improve the performance as well under certain circumstances. When we further investigated this phenomenon we found out that the number of messages per second that a Chunk Server can handle may cause it. But in order to be sure about it we would have needed to do some deeper research (even into the jME) and so we decided not to put any unsecured results in this thesis. Figure 39 shows finally the differences in performance when using different distributions for the world chunks. In Figure 39(a) subtests 7 and 8 are compared, in 39(b) subtests 9 and 10. 58 Average CPU load (%) per machine 2000 1500 1000 500 0 0 100 200 300 400 500 Number of supported clients 2.11) (M;56.5;2) 1.8) (M;40;1) Figure 38: Graph of the CPU load for different world map radii Average CPU load (%) per machine 2000 1500 1000 500 0 0 100 200 300 400 500 600 Number of supported clients 7) (40;2;otf) 8) (40;2;ta) (a) Subtests 7 and 8 1500 machine Average CPU load (%) per 2000 1000 500 0 0 100 200 300 400 500 600 Number of supported clients 9) (40;4;otf) 10) (40;4;fa) (b) Subtests 9 and 10 Figure 39: Graphs of the CPU load for different Chunk Server numbers 59 The distribution of the world chunks has a great influence on the performance of the Chunk Servers. A further investigation of the exact connection between the border length the view range of the clients and the performance would be interesting, but again a lot of work. So we decided to conclude this subsection with Figure 40, that shows how the different distributed game worlds looked in our subtests (9 and 10). (a) Game world for subtest 10 (b) Game world for subtest 9 Figure 40: Different Game worlds Testing the load balancing The goal of the last network test is to see how well the load balancing works. Setup For this test we started two Chunk Servers on two different machines (same machines as in the last test) and some client bots (125 explorers) and the Session Manager on the third machine. The initial distribution of the client bots was manipulated so that the first Chunk Server had approximately twice the load than the second Chunk Server. Evaluation Figure 41 shows the game world like it was before any load balancing, when each of the client bots was already active for some minutes. After generating this picture the automatic load balancing was triggered with the adjustment that the bottleneck was the memory. With this the less populated world chunk were moved from the first Chunk Server to the second one. In Figure 42 is visible that the load balancing works more or less. The strange stripes that occur when moving the chunks may result from casting some floating point values into integers, or some strange 60 Figure 41: Game world before any load balancing. (a) Game world after removing 500 (b) Game world after removing 900 world chunks world chunks (c) Game world after removing 1400 (d) Game world after removing 1900 world chunks world chunks Figure 42: Game worlds after moving chunks 61 patterns in the used HashMaps. But this should have no great influence in the distribution of the load. The more interesting results are the changes of the CPU load (Figure 43(a)) and number of sent and received messages(Figure 43(b)). 250 CPU load (%) 200 150 100 50 0 0 500 1000 1500 2000 2500 3000 2500 3000 Number of moved world chunks machine1 machine2 (a) Change of CPU load 1600 ingoing Messages / sec 1400 1200 1000 800 600 400 200 0 0 500 1000 1500 2000 Number of moved world chunks machine1 machine2 (b) Change of message flow Figure 43: Changed load when moving world chunks Figure 43 shows clearly that the movement of world chunks from the first Chunk Server to the second Chunk Server has an effect on the load of the Chunk Servers. But it is also visible that the movement of the world chunks isn’t error free. After moving all world chunks (3000) to the second Chunk Server the load of the first Chunk Server still hasn’t reached zero. This results most likely from a concurrency bug when switching the responsibility for the client bots from one Chunk Server to the other one. When the client bots have restarted the gaming session the load of the first Chunk Server was zero, while the load of the second Chunk Server was a bit higher. 62 5 Conclusion and Future work Developing a more or less working server architecture was more work than expected. Even though it doesn’t seem to be that difficult after the basic structure is developed, the goal to create an architecture with a good performance is very tricky in its details. Also the optimization of the generation process and its results was a work intense task. The presented result are already good looking, but could still be improved and extended. The following subsections will present the future improvements that could be done on both the content generation and the network. 5.1 Future improvements to content generation (by Bernd Altst¨ atter) The implemented generation functionality generates nice results (as shown in chapter 4.1.2), but it could still be refined. The effort needed to achieve these improvements would exceed the scope of this thesis. In the following sections the thoughts on how to improve it are presented. • Block types: The presented block types were needed for a good analysis of the generation algorithms. A future improvement would be to add more block types. The presented implementation can support up to 64 different block types, which depends on the size of the texture atlas. Examples for new block types could be snowy earth and -stone (for mountains), more metal ores or even different types of earth and stone (e.g. clay). • Vegetation and animals: The whole world consists of blocks. Even the trees could be displayed by using this approach, as in Minecraft (see in Figure 4 on page 6). But it would be better (and look better) to create the vegetation using models. To place them it would be possible to extend the NoiseUtil-class or try to implement some sort of ecosystem. Analogous to the vegetation there could be spawned animated animals, making the world alive. • Biomes: A furhter way to make the world more realistic would be to use the noise algorithms to create different biomes. These biomes would differ in their ecosystem and would be home to various plants and animals. The first biomes we thought of would be desert and jungle. • Generation on Demand: As described in chapter 4.1.3 the performance is a major issue. We couldn’t find a better solution as the one mentioned in chapter 4.1.3 that would still generate us the whole chunk at once, but we found a solution that would only generate the content needed, rather that everything. 63 The first step in the generation of a chunk is creating the heightmap. Therefore it is already known, that above the height-map there is air or water and beneath lies the ground. As the player should always start above the height-map he does not need to know what lies beneath the surface, before he manually removes a block on the surface. It would be possible to initialize the world block array with a special block type (e.g. unset) and during generation set everything above the height map to air or water. At the surface the getBlockAt-method is used and if the generated block isn’t air the algorithm can stop here and go on with the next height map value. If the generated block is air the algorithm has to calculate the adjacent unset blocks too until it reaches a solid block or an already generated block. With this approach the algorithm would only generate the blocks the player can see, at the cost that the generated content can no longer be analysed and so it is not suited for this thesis. 5.2 Future improvements to the network (by Daniel Gasteiger) When programming the server architecture and writing this thesis we came up with some necessary features and some possible improvements. Here is a short overview of these ideas: • Persistence The persistence is one absolutely necessary feature if the game should be really published. We just didn’t implement a persistence layer because it would have been of no direct use for this thesis. • Administration tool for network The actual administration tool is missing many functions like a version management of the Chunk Servers or a better listing of the actual load, including the current active player number. Also an improved user interface would be nice when the game goes into production. • Game loop vs. instant server reaction We designed our server architecture for as quickly as possible server reactions. For this purpose the Chunk Server sends each message that will be sent to a client immediately without buffering them. While this leads to good results with a low player density it is fatal when a lot of clients are in the same spot of the game world. In order to improve the performance of the game we think about implementing a game loop like it is described in [7]. 64 • World chunk distribution and load balancing When testing our server architecture it became clear, that we must improve the algorithm which decides which Chunk Server is responsible for each new world chunk. The same goes for the algorithms that decide which world chunks are moved to which Chunk Server (for this we already found some ideas in [16]). We assume strongly that the performance of the server landscape can still improve a lot if the last two improvements are realized. 65 References [1] Minecraft screenshot after starting with a new world. Generated using Minecraft with the version 1.3.2, [2012-12-16]. [2] Planetside 2 - review, 2013. http://my.mmosite.com/767901/ blog/ritem/planetside_2_review.html/[visited on 2013-0106]. [3] Tech Soft 3D. What is a scene graph?, 2012. http://www.techsoft3d.com/getting-started/hoopsvisualize/what-is-a-scenegraph[visited on 2012-12-07]. [4] COMPUTEC Media AG. Dawn of fantasy (pc), 2012. http: //www.buffed.de/Dawn-of-Fantasy-PC-214901/News/Dawnof-Fantasy-Neue-Beta-Keys-zum-MMORTS-mit-Solo-undMehrspielermodus-zu-gewinnen-Keys-fuer-die-letzteClosed-Beta-822462/galerie/1515159/#?a_id=822462&g_ id=-1&i_id=1515159[visited on 2012-12-15]. [5] Marios Assiotis and Velin Tzanov. A distributed architecture for mmorpg. In Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, NetGames ’06, New York, NY, USA, 2006. ACM. [6] Elias Hugo. Perlin noise, 2003. http://freespace.virgin.net/ hugo.elias/models/m_perlin.htm [visited on 2012-11-16 ]. [7] Herbert Jordan, Radu Prodan, Vlad Nae, and Thomas Fahringer. Dynamic load management for mmogs in distributed environments. In Conf. Computing Frontiers, pages 337–346, 2010. [8] Luke Karmali. Mists of pandaria pushes warcraft subs over 10 million, 2012. http://www.ign.com/articles/2012/10/04/mistsof-pandaria-pushes-warcraft-subs-over-10-million [visited on 2012-12-15]. [9] Rajesh Krishna Balan, Maria Ebling, Paul Castro, and Archan Misra. Matrix: adaptive middleware for distributed multiplayer games. In Proceedings of the ACM/IFIP/USENIX 2005 International Conference on Middleware, Middleware ’05, pages 390–400, New York, NY, USA, 2005. Springer-Verlag New York, Inc. [10] Sony Online Entertainment LLC. Planetside 2 is now available, 2012. http://www.planetside2.com/news/planetside2-nowavailable-2012 [visited on 2012-12-15]. [11] Fengyun Lu, Simon Parkin, and Graham Morgan. Load balancing for massively multiplayer online games. In Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, NetGames ’06, New York, NY, USA, 2006. ACM. [12] MobyGamesTM . World of warcraft, 2012. http: //www.mobygames.com/game/windows/world-of-warcraft/ screenshots/gameShotId,91236/ [visited on 2012-12-15]. [13] Ken Perlin. Noise and turbulence. http://mrl.nyu.edu/ ~perlin/doc/oscar.html [visited on 2012-12-05]. 66 [14] Jae Soo Yoo Su Min Jang. Design of an efficient mmorpg distributed server. In Journal of the Research Institute for Computer and Information Communication, 2006. [15] Dean Takahashi. Sony online entertainment chief says online frag game planetside 2 is a smashing success (interview), 2012. http://venturebeat.com/2012/12/12/sony-onlineentertainment-chief-says-planetside-2-online-fraggame-is-a-smashing-success-interview/ [visited on 201212-15]. [16] Bart De Vleeschauwer, Bruno Van Den Bossche, Tom Verdickt, Filip De Turck, Bart Dhoedt, and Piet Demeester. Dynamic microcell assignment for massively multiplayer online gaming. In NETGAMES, pages 1–7, 2005. 67 List of Figures 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 Ingame Screenshot of World of Warcraft [12] . . . . . . Ingame Screenshot of Planetside 2 [2] . . . . . . . . . . . Screenshot of Dawn of Fantasy [4] . . . . . . . . . . . . Screenshot of Minecraft[1] . . . . . . . . . . . . . . . . . Graphic network . . . . . . . . . . . . . . . . . . . . . . Picture of the Administration interface . . . . . . . . . . Overview of the architecture . . . . . . . . . . . . . . . . Summation of one dimensional noise [6] . . . . . . . . . Block engine: red faces will be invisible and blue faces will be visible . . . . . . . . . . . . . . . . . . . . . . . . Client window with the visual feedbacks: highlight box (red square) and the block to be set (blue square). . . . Class diagram of the Session Manager . . . . . . . . . . Class diagram of the Chunk Server . . . . . . . . . . . . Class diagram of the network classes of the client . . . . Game world . . . . . . . . . . . . . . . . . . . . . . . . . Game world 2 . . . . . . . . . . . . . . . . . . . . . . . . Game world 3 . . . . . . . . . . . . . . . . . . . . . . . . Game world 4 . . . . . . . . . . . . . . . . . . . . . . . . A possible distribution of the clients on the handled world chunks of a Chunk Server . . . . . . . . . . . . . . Move world chunks . . . . . . . . . . . . . . . . . . . . . Better way to move world chunks . . . . . . . . . . . . . Possible world chunks to move . . . . . . . . . . . . . . Sequence diagram of the load balancing algorithm . . . Graphical representations . . . . . . . . . . . . . . . . . Standalone client after starting the game. (Seed: Hello World!) . . . . . . . . . . . . . . . . . . . . . . . . . . . Places that can be reached by moving around the world. (Seed: Hello World!) . . . . . . . . . . . . . . . . . . . . Removing a block . . . . . . . . . . . . . . . . . . . . . . Adding a block . . . . . . . . . . . . . . . . . . . . . . . The world created by using the seed Test Seed 1 . . . . The world created by using the seed Test Seed 2 . . . . The world created by using the seed Test Seed 3 . . . . Graph of the CPU load during the tests . . . . . . . . . Graph of the CPU load for different client bot types . . Distribution of client bots over the map . . . . . . . . . Graph of the CPU and message load for different world map radii . . . . . . . . . . . . . . . . . . . . . . . . . . Graph of the CPU and message load for different message rates . . . . . . . . . . . . . . . . . . . . . . . . . . Graph of CPU and message load for different message machines . . . . . . . . . . . . . . . . . . . . . . . . . . Graphs of the CPU load for different Chunk Server numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph of the CPU load for different world map radii . . 68 4 4 5 6 15 16 17 18 21 22 24 26 27 27 28 28 29 32 32 33 35 37 39 40 41 41 42 43 44 44 52 53 53 54 55 56 58 59 39 40 41 42 43 Graphs of the CPU load for different Chunk Server numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Different Game worlds . . . . . . . . . . . . . . . . . . . Game world before any load balancing. . . . . . . . . . . Game worlds after moving chunks . . . . . . . . . . . . Changed load when moving world chunks . . . . . . . . 69 59 60 61 61 62 List of Tables 1 2 3 4 5 6 7 8 9 10 11 12 List of the world block types. . . . . . . . . . . . . . . . List of the world block types continuous. . . . . . . . . . List of the world block types continuous. . . . . . . . . . Blocks generated by using the seed Test Seed 1 . . . . . Blocks generated by using the seed Test Seed 2 . . . . . Blocks generated by using the seed Test Seed 3 . . . . . Average values from ten different seeds . . . . . . . . . . Number of noise methods used in the worst case. . . . . The resources will only spawn in the given height or lower. The measured times on the used hardware. . . . . . . . Subtests of network test No 1 . . . . . . . . . . . . . . . Subtests of network test No 2 . . . . . . . . . . . . . . . 70 11 12 13 43 44 45 45 46 47 47 52 57