Jump to content
  • Advertisement
  • entries
    18
  • comments
    7
  • views
    662

Implementing SEO in Video Games

Sign in to follow this  
GildedOctopusStudios

791 views

So we all know Google and other search engines use a variety of optimization techniques. How does that apply to video games? Well the classic example is the shortest path problem. You want your AI whether it be enemies or NPC’s to take the shortest path to the player or some other goal. The way to accomplish that dynamically is to use a search algorithm.

The first thing you need to know when implementing this sort of algorithm is how to set up the problem. There are essentially 3 variations you need to worry about single-source shortest path problem, single-destination shortest path problem, and all-pairs shortest path problem. The first one is essentially you have a starting location and you are trying to find a route to every other place on the map. The second is basically the opposite of the first. You are trying to find the shortest path from all possible starting locations to a single end point. The last one is both combined. You are trying to find the shortest rout between all possible starting and ending locations.

Now you have a variety of options for algorithms Dijkstra’s, Bellman-Ford, A*, as well as a few others that I’m not going to get into. The first two are excellent algorithms but the benefit of using the A* Search Algorithm in video games is that it adjusts for a heuristic(basically a rule or sort of hunch of which direction to go). Now this is where you can really let your creativity shine when it comes to AI characters. You can make some of them move more optimally. You can make them become stunned or disoriented and move less optimally. You can even add in another goal or end condition. Now traditionally the heuristics are used to speed up the algorithm. You can use it for that perhaps routing over terrain that lets the AI move faster and is more likely to connect two points for example roads. The thing to remember though when you are implementing them is that it is up to you how you want use and/or modify the search algorithms. This can be a bit of a scary thing if it isn’t something you’ve done before. Personally it is something I love. I really enjoy writing custom algorithms for problems. I once got very frustrated at a hashing library in the middle of the night and wrote my own single direction hashing algorithm but that is a story for another time.

Suppose you are wanting to use A* and you want to use the heuristic to actually optimize it. There are so many different heuristics you could use customized to your unique implementation. For example maybe because of the way your maps are designed there is a set max minimum distance between every two points say 9 squares, everything is normally within 9 squares of everything else. Well now you can use the heuristic to favor that search range. Maybe you know the direction the goal is in so you make your heuristic to favor paths that go in that direction. Now the problem with this is that if there is a problem with your heuristic it can throw off the entire algorithm.

Heuristics are not the only way to optimize search algorithms. You can also use a technique called pruning. Which like pruning a plant or tree refers to cutting away branches or options that you already know won’t lead to your desired outcome. One example of it is Alpha-beta pruning which is an algorithm that seeks to limit the number of nodes searched by the Mini-Maxi algorithm. It is used for games against an opponent.

Just because an algorithm was designed for a specific purpose doesn’t mean you can’t modify it to suit your specific needs. No one is judging you on how correct your implementation of a specific algorithm is. When considering how you can optimize your search algorithms you have a lot of options from setting up the problem in different formats, using different algorithms, heuristics, and pruning. Search Engines don’t release their algorithms but that doesn’t mean you can’t use some of the same techniques they do to improve your game.

The post Implementing SEO in Video Games appeared first on Gilded Octopus.


View the full article

Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
  • Advertisement
  • Blog Entries

  • Similar Content

    • By QwePek
      Hello, I want to make a game where i can procedurally generate caves. I found out that the best way to create this caves for me is by algorithm Perlin Worms, but I'm having problems with understanding it. Could someone explain how it works or write some code examples (best in SFML). Thanks
    • By shreya
      Hello everyone!
      I'm an IB student writing my extended essay in CS comparing Monte carlo tree search and minimax.
      For collecting my primary data, I wish to conduct a benchmark test on both these search techniques. For that I need to use a game that implements the monte carlo tree search and also has a version that implements minimax. Can someone please help me out and send the links of where I can find such an engine/game?
      Thank you!!
    • By Boris The Brave
      I recently discovered the source code to Diablo 1 has been reverse engineered to a readable state: https://github.com/diasurgical/devilution
       
      I did a write up of how the levels are procedurally generated: https://www.boristhebrave.com/2019/07/14/dungeon-generation-in-diablo-1/
    • By GameDev.net
      This is a blog about our development of Unexplored 2: The Wayfarer's Legacy. This game features state-of-the-art content generation, generative storytelling, emergent gameplay, adaptive music, and a vibrant art style.
      Part 1
       
      Unexplored 2 is a roguelite action adventure game where the hero is tasked to travel the world in order to destroy a magic staff. It features perma-death, but when your hero dies you get a chance to keep the world, so you can uncover its many secrets over the course of several runs. In a way, the world is one of the most important and persistent characters in the game. In this article, I'd like to share how we generate it.
      There are several ways in which you can approach world generation for fantasy games. For example, you can use simulation techniques to generate a realistic topography and populate the world from there. Instead, we choose a different approach for Unexplored 2: we used a process where we sketch a rough outline first and try to fill in the map with in a way that optimizes the affordances and gameplay opportunities the map has to offer.
       
      Rough Outline
      It all starts with a random Voronoi graph with 80 cells placed on a map with a 3:2 aspect ratio:

      Figure 1 - The initial Voronoi
       
      We use a Voronoi because it has a fairly natural distribution of cells and because the structure can be treated as a graph with each cell being an individual node and each edge a connection between nodes. This is useful as we use graph grammar rules to generate the map.
      In the first step, the cells on the western edge are set to ocean. Then we grow the ocean a little creating a more interesting coastline, and set the remaining cells to be land mass. A starting location is picked along the coast and a goal location is picked somewhere on the eastern side. Each cell in the graph marked with its distance to the start and the distance to the goal. Distance in this case is measured in the number of cells between two locations.
       

      Figure 2 - Land and Sea
       
      Obviously placing the ocean always on the west is just a choice (Tolkien made us do it). It is easy to make the whole map an island or have the ocean cover other edges of the map. What matters for us, is that this creates a consistently large playing area. But we don't rule out adding other templates and variations in the future.
      The next step is to make sure that the journey will not be too easy. After all, 'one does not simply walk into Mordor'. The way we achieve is also lifted directly from The Lord of the Rings: we simply make sure there is a mountain range between the start and the goal:

      Figure 3 - A Tolkienesque mountain range
       
      The mountains are started somewhere close to the goal and then allowed to grow using the following graph grammar rule, which basically changes one open cell into a mountain for an open cell that is next to one (but no more) mountain cell, relatively close to the goal, and relatively far from the starting location:

      Figure 4 - Graph grammar rule to grow the initial mountain range
       
      Unexplored 2 has a journey from the start location to the goal. In order to tempt the player to divert from the most direct route and explore the rest of the map a number of 'adventure sites' are placed at some distance of the start and goal location. Creating a nice spread of potential interesting travel destinations. Each site is placed inside a region of a different type. In this case, the goal is placed in swamp (s), a haven (green h) is placed in a hill area close to the start, and other sites are placed in a desert (d), forest (f), and a barren area (b). Orange edges indicate the borders between the regions.

      Figure 5 - Adventure sites
       
      Adding Topography
      The remaining cells are randomly grouped into additional regions until every cell is assigned a region on the map. The terrain types for these regions are left undetermined for now.

      Figure 6 - Regions and rivers
       
      Next rivers are added to the map. Initially, rivers are allowed to grow along the borders of regions. Unlike a realistic world generation process, we choose to start growing rivers at the ocean, selecting a new edge to grow into at random, favoring to grow alongside mountains as the go along.

      Figure 7 - Graph grammar rule that changes a region border next to an ocean into a river
       
      After rivers have been added, the region types are filled in and reevaluated. In this case, more forests are added and the desert area in the south is changed into a plain because it was next to the ocean and far to the south (our map is located in the southern hemisphere, hence the south is cold). At a later stage, we might take the opportunity to change the desert into something more interesting, such as a frozen waste.

      Figure 8 - Complete topography
       
      Once the regions are set, rivers are allowed to grow a little more, especially through terrains like hills and swaps. Depending on their length rivers be narrow, wide, or very wide. Only narrow rivers are easy to cross, for the wider rivers certain edges are marked to indicate points where the river can be crossed.

      Figure 9 - Graph grammar rule to grow a river through a swamp
       
      Adding Opportunities
      The topography is fairly basics and we still need to fill in a lot of details. From a design perspective regions (not cells) are the best unit to work with in this respect as we want regions to form coherent units in the experience of the game. To make working with regions a little bit easier, the Voronoi graph is reduced to a graph representation where all cells of each region are combined into one single node.
      Based on the relative distance to the start and the goal regions are assigned a difficulty and a number of opportunities and dangers are generated accordingly.

      Figure 10 - Region graph
       
      At this stage, the generator starts to look for interesting gameplay opportunities. Using several graph grammar rules a large forest with high difficulty will be assigned different attributes than a small, low difficulty swamp harboring an adventure site.
      At this stage, special terrains, such as purple 'obscuri' forests or red sand desert are also added to the mix. When generating the game in the world we have the option to request certain special features such as special rare terrain, or special quest content. These are processed first. To the best of the generator's ability, it might be that no good fit is found, at which point either we need to generate a new or continue without the requested feature.
      One interesting effect is that if certain special terrains require slightly rare conditions to emerge then the terrain type automatically becomes rare content. For example, a special quest might require a large swamp area with a river which will not be present in every world. The downside is that sometimes rarity becomes hard to control or design as there literally is no simple slider to push up if we want to make such a terrain type or quest more frequent.
       
      Creating Visuals

      Figure 11 - The map as it appears in the game
       
      Up until this point, the map is all data. The next step is to create the visual representation based on the map. To this end, we generated a new Voronoi diagram with a higher resolution (about 1200 cells) and map each smaller cell to the cells of the original map data. This creates a better resolution of details. Figure 10 shows how to original cells map to the visual map:

      Figure 12 - Original cells projected onto the map
       
      Individual cells can be raised and lowered to create elevation, and colored and decorated to suggest different terrains. Some of these decorations are assets such as trees which can vary in size and density based on the relative temperature and humidity of each cell. For now, we're using a very simple algorithm to approximate individual climate using longitude, latitude (it gets dryer towards the east), elevation and closeness to water.
      Other decorations are build from simple geometry based on the high-resolution Voronoi graph. This can be easily seen in image 13 below. This geometry includes slightly sloped mountain peaks, elevated patchwork to create the impression of a broken, barren landscape, and sunken centers to create pools.

      Figure 13 - Map detail showing how decorations use geometry based on the Voronoi graph
       
      Regions and their associated terrain types play an important role in the generation of these details. As can be observed in the figure above, forest rise towards their center, as do hills and mountains. Rivers are never elevated (to save us the trouble of trying to do so consistently). Terrain is blended a little so that height difference are not too pronounced where not intended, and interesting borders are created. In many cases, these blended terrains offer ample opportunities to liven op de map with rare features.
       
      Setting Up Nodes
      The world is of Unexplored 2 is not a continuous world. Players travel from node to node and can choose (or are forced) to explore gameplay areas each node represents. Connection between nodes determines where the player can travel. To place the nodes on the map we use to original low-resolution Voronoi diagram. A node is placed on each cell and on each border between cells, as can be witnessed in the image below:

      Figure 14 - Network of nodes placed on the Voronoi graph
       
      Certain connections are special. As mentioned above wide rivers can only be crossed at certain points, and mountains also create barriers. For uncrossable rivers the node that would have been placed on the river is split in two and each node is moved away from the river a little. Where a crossing is needed the node is actually split in three so that a bridge node is created that conveniently only has two connections (and exits) on each side of the river. For mountains and passes across mountains something similar is done.

      Figure 15 - Detail of the node network showing rivers and mountains
       
      Some of the nodes are already marked out as special sites in the generated data. The area templates associated with these sites often indicate special features to appear on the map (for example a volcano, a village, a mud pool, or a group of trees). Although, in some cases these features are only added after the player has visited the area and found its secrets. All other nodes are assigned templates based on the region they belong to and their relative position within that region.
      Each region has a number of types of locations. Typically a region has one 'heart' location assigned to a node quite central in the region, or a 'smallHeart' location if the region is relatively small. A number of 'rare' locations are scattered out across the locations not on the region's edge, and finally, all other locations are drawn from a random destination table associated with the region's terrain. Figure 16 shows sample entries from the table we use to populate forest and plain regions (the 'locations' in this table are the random encounter location the game uses when travelling between each node).

      Figure 16 - Random destination table
       
      Wrapping Up
      At the moment of writing the map generation is still a work in progress. We are constantly adding details as the game's content keeps growing. But I don't expect the general approach to change much.
      We are quite happy with the results, as in our humble opinion the maps are quite beautiful. But what's more important, they are readable: players can predict where barriers and dangerous terrains are to be found. A lot of information is there and we don't hide it behind a fog of war. The map facilitates anticipation and foreshadowing which are two key gameplay design features. We hope that when the game is released in full, players will enjoy simply pouring over the map and plan their journey.
       
      If you are interested in learning more about the game please check us out on Fig.co or on Steam.
       
      Note: This article was originally published on the Ludomotion website, and is reproduced here with the kind permission of the author.
    • By GameDev.net
      This is a blog about our development of Unexplored 2: The Wayfarer's Legacy. This game features state-of-the-art content generation, generative storytelling, emergent gameplay, adaptive music, and a vibrant art style.
       
      The content generator of Unexplored 2 generates tile maps. Typical output looks like this (you can read more about our level generator here😞

       
      These tile maps are stacked, using different tiles to indicate tiles ground types (grass or dirt in this example) and various decorations. In this case there are some bushes (large green circles), Rocks (black circles), plants (small green circles), flowers (white circles), and decorative textures (grey squares). There also are special tiles that indicate gameplay data such as the spawning point marked with an 's'. In addition, tiles can be tagged with additional information such as elevation or special subtypes.
      Tile maps are a convenient data structure for generators to work with. But they also are quite rigid, and often the grid has a tendency to be visible in game. Yet, in our case when the data is loaded into the game and assets are placed the result looks like this:

       
      I like to think we did a pretty good job at hiding the tiles, and here's how we did it.
       
      Voronoi Magic
      The trick is that individual tiles are matched to the cells in a Voronoi diagram. Which can be used to generate shapes that are much more natural looking. A Voronoi diagram is created from seeding a plane with random points and partitioning off cells so that each point in the plane belongs to the cell that corresponds to the closest seed point. There are quite a few interesting applications of Voronoi diagrams for procedural content generation (PCG).
      A typical Voronoi diagram created from a random but fairly even distribution of seed points looks something like this:

       
      For Unexplored 2 we use a different type of distribution of seed points. To start with, we seed one point for each tile. That way we are certain every tile in the tilemap can be mapped to one cell in the Voronoi diagram.
      Now, if you place the seed points in the middle of each cell you end up with straight grid that looks exactly like a tile map (for this image and the others below I also made a checkered version where half of the tiles are rendered yellow so you can see the patterns a little bit better):

       
      A simple way of making this look better is to simply randomize the position of each seed point. When shifting the points it helps to make sure the point does not move outside its original tile.
      The result looks something like this:

       
      Better, but very noisy, and you don't get nice flowing lines in this way. It can be improved by 'relaxing' the Voronoi diagram (a standard technique associated with Voronoi diagrams I won't go into here). But it will always stay a little noisy, and it is difficult to effectively suggest shapes on a scale that surpasses the scale of the individual tiles.
      To get around this you need to do is to move the points around smarter than simply using random displacement. Different types of movement have very different effects. For example, using Perlin noise can create interesting curved tilemaps. Or you can turn the whole thing into hexagonal shaped tiles simply by moving every other row of seed points to the left:
       

       
      The real breakthrough comes when we start moving around the seed points in particular patterns to create rounded corners. The first step of this process is already taken inside the level generator. Corners are detected between ground types and the corner tiles are marked with different shapes, indicating how they should be deformed to generate a better-looking environment:

       
      In this case, elevation differences also cause corners to appear in the tilemap. That's the reason you see the extra rounded corners in the grass in the top right and bottom left where slopes were generated.
      The game uses this information to displace the seed points of the Voronoi graph. Each rounded corner shifts the location of the seed point (see image below). In addition, it also shifts the seed points of its four orthogonal neighbors. This process is cumulative; seed points can be shifted multiple times if they are near several corners. However, after all displacement are processed, the seed points are randomized a little (about 10% of the width of a tile in either direction), and the final displacement is restricted to a maximum of 40% of the width of a tile.

       
      The result is already pretty astonishing:

       
      But we're not there yet...
       
      Smart Decoration
      The overall shape is better, but the edges are still very straight and somewhat ragged in appearance. The way we cover that up is by using curved assets placed along the edges where the colors are different. The real trick, however, is that one curve is often placed over two edges, using their relative angles to determine the direction of the curve.

       
      The result looks like this:

       
      Next, we use 3D assets to give extra texture to the cliffs:

       
      And finally, we add the other assets to fill out the level. The placement of these assets is dictated by the level data generated earlier, and in general follows a simple philosophy. We use smaller assets to surround larger ones creating natural and nice transitions. Of particular note is the rocks added to the bottom of cliffs to create more variety and to visually dampen the vertical slopes dictated by the gameplay:
       
      Local Variation
      The corners are not the only type of displacement we use. For example, near artificial structures (such as the ruined walls below) you want the edges to be straighter:

       
      In our system, this effect is easy to achieve. We simply introduce a different displacement rule that makes sure that tiles featuring artificial structures are not displaced. The generator uses smaller squares to mark these tiles and the game simply makes sure that all displacements are ignored:

       
      If you look at the ground you can clearly see how specific areas can be made straight while others curve more naturally:

       
      Isn't that neat?
      There are a few other rules you can use easily mix in with this technique. For example, we occasionally force the tiles into a hexagonal pattern to make sure narrow paths are wide enough to be traversed. And I am sure we will find other uses for other patterns as well.
      This is one of the many reasons I really love Voronoi diagrams. Another time I will write about how we use them to generate and decorate Unexplored 2 world maps.
       
      If you are interested in learning more about the game please check us out on Fig.co or on Steam.
       
      Note: This article was originally published on the Ludomotion website, and is reproduced here with the kind permission of the author.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!