Jump to content
  • Advertisement

Search the Community

Showing results for tags 'Algorithm'.

The search index is currently processing. Current results may not be complete.


More search options

  • Search By Tags

    Type tags separated by commas.
  • Search By Author

Content Type


Categories

  • Audio
    • Music and Sound FX
  • Business
    • Business and Law
    • Career Development
    • Production and Management
  • Game Design
    • Game Design and Theory
    • Writing for Games
    • UX for Games
  • Industry
    • Interviews
    • Event Coverage
  • Programming
    • Artificial Intelligence
    • General and Gameplay Programming
    • Graphics and GPU Programming
    • Engines and Middleware
    • Math and Physics
    • Networking and Multiplayer
  • Visual Arts
  • Archive

Categories

  • Audio
  • Visual Arts
  • Programming
  • Writing

Categories

  • Game Dev Loadout
  • Game Dev Unchained

Categories

  • Game Developers Conference
    • GDC 2017
    • GDC 2018
  • Power-Up Digital Games Conference
    • PDGC I: Words of Wisdom
    • PDGC II: The Devs Strike Back
    • PDGC III: Syntax Error

Forums

  • Audio
    • Music and Sound FX
  • Business
    • Games Career Development
    • Production and Management
    • Games Business and Law
  • Game Design
    • Game Design and Theory
    • Writing for Games
  • Programming
    • Artificial Intelligence
    • Engines and Middleware
    • General and Gameplay Programming
    • Graphics and GPU Programming
    • Math and Physics
    • Networking and Multiplayer
  • Visual Arts
    • 2D and 3D Art
    • Art Critique and Feedback
  • Community
    • GameDev Challenges
    • GDNet+ Member Forum
    • GDNet Lounge
    • GDNet Comments, Suggestions, and Ideas
    • Coding Horrors
    • Your Announcements
    • Hobby Project Classifieds
    • Indie Showcase
    • Article Writing
  • Affiliates
    • NeHe Productions
    • AngelCode
  • Topical
    • Virtual and Augmented Reality
    • News
  • Workshops
    • C# Workshop
    • CPP Workshop
    • Freehand Drawing Workshop
    • Hands-On Interactive Game Development
    • SICP Workshop
    • XNA 4.0 Workshop
  • Archive
    • Topical
    • Affiliates
    • Contests
    • Technical
  • GameDev Challenges's Topics
  • For Beginners's Forum
  • Unreal Engine Users's Unreal Engine Group Forum
  • Unity Developers's Forum
  • Unity Developers's Asset Share

Calendars

  • Community Calendar
  • Games Industry Events
  • Game Jams
  • GameDev Challenges's Schedule

Blogs

There are no results to display.

There are no results to display.

Product Groups

  • Advertisements
  • GameDev Gear

Find results in...

Find results that contain...


Date Created

  • Start

    End


Last Updated

  • Start

    End


Filter by number of...

Joined

  • Start

    End


Group


About Me


Website


Role


Twitter


Github


Twitch


Steam

Found 19 results

  1. bzt

    Optimized SLERP

    Hi, I was looking for a way to effectively interpolate between skeletons represented by list of bones with position vector + orientation quaternion pairs. To my surprise, I couldn't find any good solution, not to my taste that is. I can't use NLERP because I need a general solution, and NLERP is only good for small distance interpolations. SLERP would be perfect, but I couldn't find a decent implementation, only slow ones, so I spent a lot of time looking at game engines and quaternion libraries and reading academic articles on the topic. Finally, I decided to collect my findings and write my own optimized version of SLERP, which focuses on performance over precision, and which I now would like to share with you. Optimized cross-platform SLERP I've started from the well known formula, as implemented by most C++ libraries, and used all the tricks I could find on the net. Then I took it to the next level, and made some more adjustments on my own speeding up a little bit more. Finally I ended up with two solutions: 1. one that is cross-platfrom, ANSI C solution that is easily embeddable in C++ and compatible with any C / C++ quaternion class (provided their data can be seen as 4 floats), very simple, very minimal. Use it freely if you want, MIT licensed 2. a SIMD version, which I had to leave half-ready, because my compiler and Intel disagree on what intrinsics should be provided for SSE, moreover the compiler does not work the way its documentation say it should :-( Shit happens. I would only recommend this for experimental purposes, also MIT licensed Both versions are simpler and much faster than any implementations I could find, designed to be called in a loop several times. The only dependency they have is lib math (acosf, sinf). The SIMD version is half-ready, but even in this form it's almost 1.5 as fast as the other one, especially if you call it in a loop with memory prefetch on the quaternions. If I made any mistake, miscalculated or mistyped something, let me know. If anybody has an idea how to overcome that intrinsics blockade I have, that would be appreciated very much, because I can clearly see the path how to make the code several times faster, only if I could get rid of the library calls. I also plan to create an ARM NEON port once I have that. Cheers, bzt
  2. Hello everyone I am here to gather your opinion, remarks, ideas or any constructive criticism you may have about what I am going to present. Don’t be shy! A bit of background: I am working alone on an indy web-based game, a simulation of RPG (idle game) where the player controls a group of 4 characters that he can sent into battle and that will fight automatically based on some AI preference that are similar to the FF 12 system (but more complex / powerful). He then earns some experience and resources that he can use to improve his unit’s gear, talents and skills. He has a lot of control on what skills his characters will use and how/when. What brings me here today: The AI of Monsters. I have the AI settings for players covered (basically a bunch of if/then/and/or/else settings that he can combine and order so that his units will act as he intends in battle). I’ve been working on the AI of monsters for quite some time, made a long break and came back recently to it. Short description of the battle system: No movement involved. Battle is fully automated. Players setup its units AI settings before battle and monsters are controlled by a separate AI. This is a 4v4 battle, like FF7 with some kind of ATB and any time a unit fill its ATB, it can play and the then the next unit who will fill it will play, etc. The player is completely free of his playstyle and may create very offensive group or very defensive ones. 4 healers or 4 tanks is completely possible. The battle system is very complex and allows for very varied and sometimes unusual strategies, like killing your own allies to proc an “on death buff” that will be devastating for the opponent. What I want for my AI? It needs to be fun to fight against and challenging. Ideally, I would like an AI as smart as possible (not omniscient but thinking as a human would). I know that a super-smart AI is not always the best way to make a game fun or challenging but in the context of my game, this is the result I want to achieve. It may seem unfair to have the AI try to kill your squishy while your tank is standing right there but my class design gives the tools to players to counter that so it’s not an issue (tanks are not purely aggro based for example). I want players to always be challenged by AI moves and that they must carefully think about their strategy because if they leave a big hole in it, I want the AI to exploit it. In practice, it means a few requirements: No dumb decision / do not fall into obvious player’s traps Exploit obvious flaws of the opponent Act in coordination when appropriate with other units Able to find who should be their focus in the player’s team (some notion of threat) Find the best move to use and if there is some kind of combo possible, use it These requirements are harder to meet than it looks. The issue is the sheer number of different mechanisms and strategies available to players and to monsters as well. For example, there are many cases where killing or attacking a player unit might be detrimental (units that return damages or that gain power when you hit then for example). What I have tried before? I have tried or at least reviewed many different AI concepts so far. - A simple copy of my player’s AI system (hierarchical if/then/else). It was easy to script as I already have the UI in place for players so I can quickly define a basic AI for any new monster’s group. The main drawbacks are that it needs to be written for every monster group, it does not allow smart targeting and cannot find the best target or the best skill to use. It will also make dumbs decision as the targeting options cannot assess threats at all. I’ve rules out planners since for purely selecting the best pair of (skill, target), they do not seem to match my needs. (H)FSM or BT does not seems to match my needs as monsters do not have states / transition condition that can lead to something useful for me. I’ve ruled out aNNs as they might, with proper training, be able to find the best action at a given time but it’s very tedious to implement and will not solve my need of finding combo or coordinating with other units very well. (plus, let’s be honest, I’d be a bit out of my depth to program them) I have spent an extensive period of time trying with tree searches. Mainly: monte-carlo with random sampling and came to the conclusion that due to the complexity of my battle system, it is excessively costly to compute any kind of reliable data this way. - My current AI system is a version of my first one (the same as the players) but with access to some “smarter” targeting function that in theory allow to choose the best target. These functions work by gathering data for thousands of simulated fights during the AI time to play (1 second). It’s a first step to find the best target but not very accurate (lots of big flaws that can be exploited by players) and it is very time consuming and that is something I’m trying to get away from. I do not want to use 100% of the players CPU as I do now. What is my latest idea? I started to study more in-depth the Utility theory as described by Dave Marks (I read his book and watched his GDC AI lectures as well). I liked the idea. I like that I can start on something relatively simple and add more considerations as things progress to handle more and more situations. While my work began as something very close to utility theory, it evolved a bit afterward. Here is what I plan on doing to compute a unit’s best course of action: A – Score every of its move (each move is a pair [skill, target]). B – Chose the move according to a selection strategy (highest score, weighted random, random amongst the top scores… lots of different selection algorithm can be used there). So far, easy, right? Let’s dig deeper into our first phase of scoring (A), which is the hard part. For all the damage or healing skills: Step 1: The final scoring of the move [skill,target] will be function of the a “Survival” scoring for the player team and for the enemy team. An example of this relationship could be: Adding all the survival scores of each unit in Team A and divide the result by the addition of all the survival scores for each unit in team B. Step 2: The survival score of each unit will be its Health after the move we are evaluating, divided by the total damage per turn that we estimate other units can deal to her (minus the total heal it ca receive). [This a step where we can process damage and heal over time as well] Step 3: This damage per turn estimation will be, initially, the sum for every unit in battle of the damage or heal per second it can deal to that unit. For example: If I’m alone vs 2 bad guy that can deal 1 dmg/turn and if I can deal 1 heal/turn, the damage per turn estimation against me will be 2-1 = 1. [This is not optimal since we are counting the damage of each unit once per enemy unit but it’s a start] Step 4: To compute the DPS or HPS of each unit, we review the unit’s skills and compute their output against the unit we want to evaluate it against. From that, we construct a skill sequence to maximize the damage output and once we got the optimal skill sequence, we can compute its DPS or HPS output and pass it along for Step 3. It might seem like a lot of work, since, in a world with only damage or healing skills, the DPS or HPS sequence of each unit will be the same in every situation and as such only the damage done or healing done by the skill evaluated would be enough. But… The tricky part comes from buffs and debuffs. If we use the above algorithm, (de)buffs that changes the damage or healing someone does or receive will be evaluated correctly as it will change the damage or heal per second output of units and it would affect the survival score and the final scoring. That is why I chose to include DPS and HPS computations for each unit for each move. This is all fine until we consider (de)buffs that changes the power of other (de)buffs. Like: I cast a buff that double the length of all my future buffs. My algorithm can’t evaluate it correctly. It’s a situation that will be common enough in my game and I want my AI to deal with it. Note: there are more complex situations where a unit could buff a buff that buffs a buff that buff a buff [….] that will end-up buffing a damage or healing skills, but those cases will not be addressed as they will hopefully be rare and too cumbersome to compute anyway. So, my goal is to score properly buffs that: Buffs the damage or healing output of someone Buffs that buffs a skill that does the above L Long story short of how I am doing that. I’m using my initial algorithm but while also estimating damage or healing per second change for each dps or hps sequence.To do that I’m evaluating every move of the unit (or every unit in case of AoE but lets keep it simple with single target) that is targeted by the buff. So, we are switching PoV here compared to the initial unit we are evaluating (unless the move evaluated is buffing itself) - I’m doing the above in 2 situations: o A : After a cast of the buff skill I’m evaluating o B : Without the cast of the buff, just like if it was that unit’s turn to play - Using a sort of min/max approach: if the unit targeted by the buff is an ally, we will take the best branch of our tree in A and compare it with the same branch (pair [skill,target]) in B. If the unit targeted by the buff is an enemy, we want to lower their maximum score and will select the tree branch that does that in A to also compare it with the same branch in B. - The information we extract here are DPS or HPS delta for each sequence of DPS/HPS for each unit vs each other unit. - Then, we go back to our steps 1 to 5 and compute our scoring for the move (buff) while using our new dps/hps deltas to get better and more accurate dps/hps sequence for units affected by the buff. This is basically it. I’ve ran a manual version of the algorithm in 2 different battle settings to test it and see if it gave good results. It worked. Not flawlessly but it worked. Lots of cases will still require tweak and additions to the basic idea but I think its promising. (taunts and CCs are not easy to deal with but it’s manageable) What I like is that I can add more considerations later (as in the utility theory) like: resource cost, general unit strategy (cleave or focus), behavior (careful, lunatic, reckless). While this will still be a bit time consuming it should be a good order of magnitude faster than my current AI. It also does not prevent me from adding hardcoded AI move if I want to “script” more some monsters. Debugging and tweaking might be a bit painful though, especially when fights will involve lots of skills & stats but that’s an issue that most AI for my game would likely have anyway. To come back with my initial goals: No dumb decision / do not fall into obvious player’s traps o Not perfect but it should choose the best target whenever possible Exploit obvious flaws of the opponent o Same as above Act in coordination when appropriate with other units o This can be done simply by adding weight to some targets or computing moves for all units of a group before deciding which one to take (for example to take the best move vs a specific unit, on average) Able to find who should be their focus in the player’s team (some notion of threat) o It will naturally focus the unit who is the easiest to kill and debuff or CC the ones that deal the more heal/damage. But, to better solve this, we will need to add other considerations to the AI scoring process, It should not be *too* hard Find the best move to use and if there is some kind of combo possible, use it o Combo are very often in the form of buff/debuff setup before an actual damaging or healing skills and my AI can compute up to a 3 moves combo (buff > buff > skill that dmg or heal) which should cover most cases. I’m quite happy with my initial tests. I’m not going to be coding it now. My goal was to reflect on the subject on paper and try to see if designing my AI would be a roadblock or not for my project. There are a few other area I want to design and take time to really think about before getting back to my project full time. I’d love to hear your toughs and feedbacks about my AI ideas. Do you see huge roadblocks I’m missing? Does it sound ok to you? If you read that far…. thank you and I can"t wait to hear from you guys😊
  3. I googled for terrain collisions but found only some sources about flat worlds. I want collision detection for spherical terrain worlds. I have "3D Engine Design for Virtual Globe" book but it did not mention any algorithms about collision detection for landing, rolling, walking, crashing, etc... Does anyone have any good sources for spherical terrain collision detection?
  4. This was for a Dungeon Explorer home project I was working on. When researching labyrinth, maze, or dungeon generation algorithms I found many that would create hub or tree-style dungeons, but none that would 'loop back' on themselves. I created this algorithm with the intention of designers or artists still having full control over the look and contents of rooms and corridors. As long as certain rules are followed (e.g. attachpoints are assigned to rooms and snapped to a grid, rooms have a 'footprint' object that bounds their size) rooms and corridors can be any size or shape desired. This video demonstrates the process, which is also outlined below: giphy.mp4 I did go on to make a small game using this algorithm and bar some silly behaviour (like making corridors to from a room to itself), it's worked great! A short excerpt about the algorithm, for those that might like to re-create it! Steps Randomly Place rooms within the defined area Attempt to connect all rooms together in a large 'chain' Starting with random rooms, make smaller 'chains' of rooms within the network Prune room connections from rooms that have more connections than attach points Go through all room connections and connect actual attach points Use A* pathing to create corridors between the attach points Mark all of the corridors onto the grid Actually place straight, corner, T-Junction, and crossroad corridors oriented in the correct way There's a whole bunch more complexity in each of these steps, but that's the basic breakdown! The objects you see in the gif are 3d rooms complete with art and stuff inside them, but the camera is top down and lighting set to make the gif easier to see! Each room is a prefab game object. They have their own scripts that manage the stuff contained within them, in this case flickering torches, furnaces, and other puzzles. Each room has attach points that are defined by me (in this case acting as the designer), and the dungeon generator is given a list of all rooms it should use to generate, again defined by the designer. The rooms provide information like their size, shape, available attach points etc that the generator uses to position and connect them. There are different corridor types, straight, t junction, crossroad, and corners. Each has a different setup of walls. The algorithm places them just after the steps seen in the gif, choosing which to place base on what's adjacent to each grid position and orients them. Again these are prefab game objects with other things in them (e.g. Torches). I've just used debug lines to draw out the connections for the purpose of showing it in gif format, the original version doesn't do this at all! Another example but with 200 rooms rather than 50, at increased speed: giphy2.mp4 And another 200 room demo, with no speed increase: giphy3.mp4 Note: This article was originally shared via Reddit, and is recreated here with the kind permission of the author.
  5. 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.
  6. 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.
  7. In this Blog Entry I will translate examples from the tutorial Math for Game Developers from C++ to C# and TypeScript. I will add unit tests to the examples. I use: NUnit and NSubstitute for C# Jasmine for TypeScript C# and TypeScript are very similar. TS has: properties and generics. TS has keywords like C#: interface, abstract (for classes and methods). Author of C# and TS is Anders Hejlsberg 001. Character Movement (Points and Vectors) TypeScript TypeScript Demo: Click to run the example in Sandbox TypeScript Source Code: 001_PointsAndVectors C# C# Source Code: 001_PointsAndVectors
  8. Updated: 2/15/2019 - added "if...else" Double Selection Statement Visual Studio Enterprise 2015 has build in tool for creating UML Activity Diagrams. We can use this tool for creating flowcharts for describing algorithms. Creating UML Activity Diagram: Select: "File" -> "New" -> "Project..." -> "Modeling Projects" Write a name, for example: UseUMLInsteadOfFlowcharts_ModelingProject Press "OK" button Right Click on a name of the project Select: "Add" -> "New Item..." -> "UML Activity Diagram" Write a name, for example: UseUMLInsteadOfFlowcharts.activitydiagram Press "Add" button To add new items, drag them from the "Toolbox" I get these examples from the book: 2016 - 08 - C# 6 for Programmers - 6th Edition - Paul Deitel, Harvey Deitel. Code Examples: link 1. "if" Single-Selection Statement int studentGrade = 70; if (studentGrade >= 60) { Console.WriteLine("Passed"); } 2. "if...else" Double-Selection Statement int studentGrade = 70; if (studentGrade >= 60) { Console.WriteLine("Passed"); } else { Console.WriteLine("Failed"); } 3. "while" Iteration Statement int product = 3; while (product <= 100) { product = 3 * product; } 4. "for" Iteration Statement for (int counter = 1; counter <= 10; ++counter) { Console.Write($"{counter} "); }
  9. It's a story on how to write a plugin for Unity Asset Store, take a crack at solving the well-known isometric problems in games, and make a little coffee money from that, and also to understand how expandable Unity editor is. Pictures, code, graphs and thoughts inside. Prologue So, it was one night when I found out I had pretty much nothing to do. The coming year wasn't really promising in my professional life (unlike personal one, though, but that's a whole nother story). Anyway, I got this idea to write something fun for old times sake, that would be quite personal, something on my own, but still having a little commercial advantage (I just like that warm feeling when your project is interesting for somebody else, except for your employer). And all this went hand in hand with the fact that I have long awaited to check out the possibilities of Unity editor extension and to see if there's any good in its platform for selling the engine's own extensions. I devoted one day to studying the Asset Store: models, scripts, integrations with various services. And first, it seemed like everything has already been written and integrated, having even a number of options of different quality and detail levels, just as much as prices and support. So right away I've narrowed it down to: code only (after all, I'm a programmer) 2D only (since I just love 2D and they've just made a decent out-of-the-box support for that in Unity) And then I remembered just how many cactuses I've ate and how many mice've died when we were making an isometric game before. You won't believe how much time we've killed on searching viable solutions and how many copies we've broken in attempts to sort out this isometry and draw it. So, struggling to keep my hands still, I searched by different key and not-so-much-key words and couldn't find anything except a huge pile of isometric art, until I finally decided to make an isometric plugin from scratch. Setting the goals The first I need was to describe in short what problems this plugin was supposed to solve and what use the isometric games developer would make of it. So, the isometry problems are as follows: sorting objects by remoteness in order to draw them properly extension for creation, positioning and displacement of isometric objects in the editor Thus, with the main objectives for the first version formulated, I set myself 2-3 days deadline for the first draft version. Thus couldn't being deferred, you see, since enthusiasm is a fragile thing and if you don't have something ready in the first days, there's a great chance you ruin it. And New Year holidays are not so long as the might seem, even in Russia, and I wanted to release the first version within, like, ten days. Sorting To put it short, isometry is an attempt made by 2D sprites to look like 3D models. That, of course, results in dozens of problems. The main one is that the sprites have to be sorted in the order in which they were to be drawn to avoid troubles with mutual overlapping. On the screenshot you can see how it's the green sprite that is drawn first (2,1), and then the blue one goes (1,1) The screenshot shows the incorrect sorting when the blue sprite's drawn first In this simple case sorting won't be such a problem, and there are going to be options, for example: - sorting by position of Y on the screen, which is (isoX + isoY) * 0.5 + isoZ - drawing from the remotest isometric grid cell from left to right, from top to down [(3,3),(2,3),(3,2),(1,3),(2,2),(3,1),...] - and a whole bunch of other interesting and not really interesting ways They all are pretty good, fast and working, but only in case of such single-celled objects or columns extended in isoZ direction After all, I was interested in more common solution that would work for the objects extended in one coordinate's direction, or even the "fences" which have absolutely no width, but are extended in