Jump to content
  • Advertisement

miimii1205

Member
  • Content count

    10
  • Joined

  • Last visited

Community Reputation

14 Neutral

1 Follower

About miimii1205

  • Rank
    Member

Personal Information

  • Industry Role
    3D Artist
    Game Designer
    Programmer
  • Interests
    Art
    Audio
    Design
    Programming

Social

  • Github
    MiiMii1205
  • Steam
    MiiMii1205

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. Here's a slash screen mockup. It could be shown when a level is being generated or wile all assets are loaded.
  2. We made some design concepts for trees and foods. It's pretty low poly, but that's the point! We'll plan to use foods as temporary stats boost. Some might even be in trees...
  3. Steering behaviors are use to maneuver IA agents in a 3D environment. With these behaviors, agents are able to better react to changes in their environment. While the navigation mesh algorithm is ideal for planning a path from one point to another, it can't really deal with dynamic objects such as other agents. This is where steering behaviors can help. What are steering behaviors? Steering behaviors are an amalgam of different behaviors that are used to organically manage the movement of an AI agent. For example, behaviors such as obstacle avoidance, pursuit and group cohesion are all steering behaviors... Steering behavior are usually applied in a 2D plane: it is sufficient, easier to implement and understand. (However, I can think of some use cases that require the behaviors to be in 3D, like in games where the agents fly to move) One of the most important behavior of all steering behaviors is the seeking behavior. We also added the arriving behavior to make the agent's movement a whole lot more organic. Steering behaviors are described in this paper. What is the seeking behavior? The seeking behavior is the idea that an AI agent "seeks" to have a certain velocity (vector). To begin, we'll need to have 2 things: An initial velocity (a vector) A desired velocity (also a vector) First, we need to find the velocity needed for our agent to reach a desired point... This is usually a subtraction of the current position of the agent and the desired position. \(\overrightarrow{d} = (x_{t},y_{t},z_{t}) - (x_{a},y_{a},z_{a})\) Here, a represent our agent and t our target. d is the desired velocity Secondly, we must also find the agent's current velocity, which is usually already available in most game engines. Next, we need to find the vector difference between the desired velocity and the agent's current velocity. it literally gives us a vector that gives the desired velocity when we add it to that agent's current velocity. We will call it "steering velocity". \(\overrightarrow{s} = \overrightarrow{d} - \overrightarrow{c}\) Here, s is our steering velocity, c is the agent's current velocity and d is the desired velocity After that, we truncate our steering velocity to a length called the "steering force". Finally, we simply add the steering velocity to the agent's current velocity . // truncateVectorLocal truncate a vector to a given length Vector3f currentDirection = aiAgentMovementControl.getWalkDirection(); Vector3f wantedDirection = targetPosition.subtract(aiAgent.getWorldTranslation()).normalizeLocal().setY(0).multLocal(maxSpeed); // We steer to our wanted direction Vector3f steeringVector = truncateVectorLocal(wantedDirection.subtract(currentDirection), steeringForce); Vector3f newCurrentDirection = MathExt.truncateVectorLocal(currentDirection.addLocal(MathExt.truncateVectorLocal(wantedDirection.subtract(currentDirection), m_steeringForce).divideLocal(m_mass)), maxSpeed); This computation is done frame by frame: this means that the steering velocity becomes weaker and weaker as the agent's current velocity approaches the desired one, creating a kind of interpolation curve. What is the arriving behavior? The arrival behavior is the idea that an AI agent who "arrives" near his destination will gradually slow down until it gets there. We already have a list of waypoints returned by the navigation mesh algorithm for which the agent must cross to reach its destination. When it has passed the second-to-last point, we then activate the arriving behavior. When the behavior is active, we check the distance between the destination and the current position of the agent and change its maximum speed accordingly. // This is the initial maxSpeed float maxSpeed = unitMovementControl.getMoveSpeed(); // It's the last waypoint float distance = aiAgent.getWorldTranslation().distance(nextWaypoint.getCenter()); float rampedSpeed = aiAgentMovementControl.getMoveSpeed() * (distance / slowingDistanceThreshold); float clippedSpeed = Math.min(rampedSpeed, aiAgentMovementControl.getMoveSpeed()); // This is our new maxSpeed maxSpeed = clippedSpeed; Essentially, we slow down the agent until it gets to its destination. The future? As I'm writing this, we've chosen to split the implementation of the steering behaviors individually to implement only the bare necessities, as we have no empirical evidence that we'll need to implement al of them. Therefore, we only implemented the seeking and arriving behaviors, delaying the rest of the behaviors at an indeterminate time in the future,. So, when (or if) we'll need it, we'll already have a solid and stable foundation from which we can build upon. More links Understanding Steering Behaviors: Seek Steering Behaviors · libgdx/gdx-ai Wiki Understanding Steering Behaviors: Collision Avoidance
  4. miimii1205

    Concept GUI Mockup 2

    After a play-test event at our workplace, we decided to re-evaluate our priorities and begin to gradually modify our backlog accordingly. So I decided to create a new HUD sketch that is an evolution of our previous design. So there is now a queue that shows context-based notifications (for example, when the player goes to a store or loots money, the queue shows the player's current amount of money) There is also a time limit / boss life bar that is big enough to be noticed by the player.
  5. miimii1205

    Idea: Iridescent shader

    I've tried the link and tried to translate the Unity shader into GLSL and it did this: It sure looks pretty...
  6. In our brainstorming, we had the idea of a type of item dropped by enemies that will have a very particular look: it will reproduce bismuth and, in particular, its iridescence. What is Iridescence? Remember CD? The under side of CDs had some trippy colors that changed based on which angle you're looking at. That type of effect is called iridescence. Many other things has that kind of effect. Things like bubbles, some metals and even some bugs (especially beetles). Wikipedia defines iridescence as: In order to reproduce the visual qualities of bismuth, we must find how to recreate this effect in a shader. One of my hypotheses is that we could do it with the normals and the viewing angle. I'm not an expert in shader writing but I'm sure that's possible ...
  7. When we started our game, we already knew it was going to be really abstract. Therefore, we also knew that, in term of shaders, it would be a real challenge. However, because we use jMonkey Engine (which is a shader oriented engine), we also knew that doing a custom shader with it was going to be a piece of cake. The Idea I used to be an avid TF2 player some time ago and I also started watching YouTubers TF2 just for fun. But the fact is that, surprisingly, some of these creators were trying to diversify their channel. Enter FUNKe, one of my favorite TF2 YouTubers. You see, he started as a normal TF2 content creator but later tried to diversify the topics of his videos. One of these videos was on the anime of Jojo's Bizarre Adventure. (I'm not a fan of anime but if I had to watch one, it will probably be that one) He said that the anime has a really abstract idea of color palettes: in some scenes, one character could be colored green while in the next, it is colored purple. That gave me an idea ... A Color Palette That Can Change The idea is to use a default color palette for each model and then, with a globally defined setting, dynamically change the specific palette used. In this way, we can change our palette according to the current level or even when events occurs in game. For example, this means that a sword can actively change its colors each time the player changes level. This can be really flexible. With some cleverness, we can make a truly abstract and unique game. In Practice All color palettes are stored on a single 512x512 texture where each pixel is a color. The coordinates are chosen according to whether the mesh is static or generated. Here's an example of a single palette: Keep in mind that it's zoomed in: each and every of these squares is supposed to be a single pixel. In our code, we load the material of the palette only once and apply it to almost all our meshes: paletteMaterial = assetManager.loadMaterial("path/to/palette/material/definition.j3md"); // The Palette material TextureKey atlasTextureKey = new TextureKey("path/to/palette/texture.png", false); m_atlasPalette = assetManager.loadTexture(atlasTextureKey); // The texture material For Static Meshes When we model our static meshes, we make sure that their UV mapping is properly aligned in the palette's texture in the appropriate pixel. Here is a simple sword model in blender. We can see that even though the UV map is really distorted, it fits well and is well aligned in the texture. Because our game is low poly and doesn't use detailed textures, there is no reason to ease these UV maps. In blender, there is a filter that changes the way our texture is displayed. Because we're going to change that in our code it doesn't really matter. We can actually fix that in our code, and it's very easy: // The Palette texture is loaded manually to overrite JMonkey's default filters paletteTexture.setMinFilter(Texture.MinFilter.NearestNoMipMaps); paletteTexture.setMagFilter(Texture.MagFilter.Nearest); We do that kind of UV mapping for (almost) all of our static meshes. For Generated Meshes Our game generates meshes that are used in our organic dungeon, but the UV mapping is quite basic... To make them compatible with our shader, we must explicitly modify the UV mapping of these meshes. Because our texture is actually an amalgam of all palettes, we have to take the first palette (which is our default palette) and use its UV coordinates to UV map our generated mesh. To help us with that, we made some enums that stores the UV coordinates of these colors. Technically speaking, in this case we use the middle of each pixel as UV coordinates. After having generated our mesh, we use a float buffer to store the UV coordinates of each of the mesh's triangles. That's why we need those enums. Here's the code we use to find out those UVs: public static FloatBuffer createDungeonTextureBuffer(FloatBuffer normalBuffer) { FloatBuffer textureBuffer = (FloatBuffer) VertexBuffer.createBuffer(VertexBuffer.Format.Float, TEXTURE_BUFFER_COMPONENT_COUNT, normalBuffer.capacity() / NORMAL_BUFFER_COMPONENT_COUNT); float skyUCoordinate = AtlasPaletteColor.SKY.getBaseTint().getUCoordinate(); float skyVCoordinate = AtlasPaletteColor.SKY.getBaseTint().getVCoordinate(); float soilUCoordinate = AtlasPaletteColor.SOIL.getBaseTint().getUCoordinate(); float soilVCoordinate = AtlasPaletteColor.SOIL.getBaseTint().getVCoordinate(); float wallUCoordinate = AtlasPaletteColor.WET_DETAIL.getBaseTint().getUCoordinate(); float wallVCoordinate = AtlasPaletteColor.WET_DETAIL.getBaseTint().getVCoordinate(); Vector3f normal = new Vector3f(); while (textureBuffer.position() < textureBuffer.capacity()) { normal.set(normalBuffer.get(), normalBuffer.get(), normalBuffer.get()); // Ground if (Direction3D.TOP.getDirection().equals(normal)) { textureBuffer.put(soilUCoordinate); textureBuffer.put(soilVCoordinate); } // Ceiling else if (Direction3D.BOTTOM.getDirection().equals(normal)) { textureBuffer.put(skyUCoordinate); textureBuffer.put(skyVCoordinate); } // Walls else { textureBuffer.put(wallUCoordinate); textureBuffer.put(wallVCoordinate); } } return textureBuffer; } With this, we can chose the UV based on the triangle's normal. The Shader The shader itself is quite simple. We took the generic shader provided with jMonkey Engine and added some uniforms and constants here and there. We take the dimensions of a palette (which is 8 x 5) and change the texture with this piece of code in our fragment shader: /* IN OUR FRAGMENT SHADER */ const int m_PaletteWorldWidth = 8; const int m_PaletteWorldHeight = 5; uniform int m_PaletteWorldIndex; // Later in the shader... ivec2 textureDimensions = textureSize(m_DiffuseMap, 0); newTexCoord.x += float(m_PaletteWorldWidth) * float(m_PaletteWorldIndex) / float(textureDimensions.x); We can then change the used palette by changing the PaletteWordIndex uniform in the code by doing this: // Palette Material is loaded manually to be able to change its PaletteWorldIndex value paletteMaterial.setInt("PaletteWorldIndex", paletteIndexUsed); // paletteIndexUsed is usually an Enum value Changing the palletIndexUsed value to a different one does that: And then we change the value of PaletteWorldIndex to 2: Although the colors are similar, they are also technically different. This can give us a lot of flexibility, but we still have to be careful: we still need to evoke the right emotions by using the right color at the right place at the right time. Otherwise, it can be harmful to our artistic style. We also need to maintain some visual consistency with the most crucial meshes. For example, our white crystal there could possibly be colored, and this color could be very important for the gameplay.
  8. I recently worked on a path-finding algorithm used to move an AI agent into an organically generated dungeon. It's not an easy task but because I've already worked on Team Fortress 2 cards in the past, I already knew navigation meshes (navmesh) and their capabilities. Why Not Waypoints? As described in this paper, waypoint networks were in the past used in video games to save valuable resources. It was an acceptable compromise : level designers already knew where NPCs could and could not go. However, as technology has evolved, computers got more memory that became faster and cheaper. In other words, there was a shift from efficiency to flexibility. In a way, navigation meshes are the evolution of waypoints networks because they fulfill the same need but in a different way. One of the advantages of using a navigation mesh is that an agent can go anywhere in a cell as long as it is convex because it is essentially the definition of convex. It also means that the agent is not limited to a specific waypoint network, so if the destination is out of the waypoint network, it can go directly to it instead of going to the nearest point in the network. A navigation mesh can also be used by many types of agents of different sizes, rather than having many waypoint networks for agents of different sizes. Using a navigation mesh also speeds up graph exploration because, technically, a navigation mesh has fewer nodes than an equivalent waypoint network (that is, a network that has enough points to cover a navigation mesh). The navigation mesh Graph To summarize, a navigation mesh is a mesh that represents where an NPC can walk. A navigation mesh contains convex polygonal nodes (called cells). Each cell can be connected to each other using connections defined by an edge shared between them (or portal edge). In a navigation mesh, each cell can contain information about itself. For example, a cell may be labeled as toxic, and therefore only those units capable of resisting this toxicity can move across it. Personally, because of my experience, I view navigation meshes like the ones found in most Source games. However, all cells in Source's navigation meshes are rectangular. Our implementation is more flexible because the cells can be irregular polygons (as long as they're convex). Navigation Meshes In practice A navigation mesh implementation is actually three algorithms : A graph navigation algorithm A string pulling algorithm And a steering/path-smoothing algorithm In our cases, we used A*, the simple stupid funnel algorithm and a traditional steering algorithm that is still in development. Finding our cells Before doing any graph searches, we need to find 2 things : Our starting cell Our destination cell For example, let's use this navigation mesh : In this navigation meshes, every edge that are shared between 2 cells are also portal edges, which will be used by the string pulling algorithm later on. Also, let's use these points as our starting and destination points: Where our buddy (let's name it Buddy) stands is our staring point, while the flag represents our destination. Because we already have our starting point and our destination point, we just need to check which cell is closest to each point using an octree. Once we know our nearest cells, we must project the starting and destination points onto their respective closest cells. In practice, we do a simple projection of both our starting and destination points onto the normal of their respective cells. Before snapping a projected point, we must first know if the said projected point is outside its cell by finding the difference between the area of the cell and the sum of the areas of the triangles formed by that point and each edge of the cell. If the latter is remarkably larger than the first, the point is outside its cell. The snapping then simply consists of interpolating between the vertices of the edge of the cell closest to the projected point. In terms of code, we do this: Vector3f lineToPoint = pointToProject.subtract(start); Vector3f line = end.subtract(start); Vector3f returnedVector3f = new Vector3f().interpolateLocal(start, end, lineToPoint.dot(line) / line.dot(line)); In our example, the starting and destination cells are C1 and C8 respectively: Graph Search Algorithm A navigation mesh is actually a 2D grid of an unknown or infinite size. In a 3D game, it is common to represent a navigation mesh graph as a graph of flat polygons that aren't orthogonal to each other. There are games that use 3D navigation meshes, like games that use flying AI, but in our case it's a simple grid. For this reason, the use of the A* algorithm is probably the right solution. We chose A* because it's the most generic and flexible algorithm. Technically, we still do not know how our navigation mesh will be used, so going with something more generic can have its benefits... A* works by assigning a cost and a heuristic to a cell. The closer the cell is to our destination, the less expensive it is. The heuristic is calculated similarly but we also take into account the heuristics of the previous cell. This means that the longer a path is, the greater the resulting heuristic will be, and it becomes more likely that this path is not an optimal one. We begin the algorithm by traversing through the connections each of the neighboring cells of the current cell until we arrive at the end cell, doing a sort of exploration / filling. Each cell begins with an infinite heuristic but, as we explore the mesh, it's updated according to the information we learn. In the beginning, our starting cell gets a cost and a heuristic of 0 because the agent is already inside of it. We keep a queue in descending order of cells based on their heuristics. This means that the next cell to use as the current cell is the best candidate for an optimal path. When a cell is being processed, it is removed from that queue in another one that contains the closed cells. While continuing to explore, we also keep a reference of the connection used to move from the current cell to its neighbor. This will be useful later. We do it until we end up in the destination cell. Then, we "reel" up to our starting cell and save each cell we landed on, which gives an optimal path. A* is a very popular algorithm and the pseudocode can easily be found. Even Wikipedia has a pseudocode that is easy to understand. In our example, we find that this is our path: And here are highlighted (in pink) the traversed connections: The String Pulling Algorithm String pulling is the next step in the navigation mesh algorithm. Now that we have a queue of cells that describes an optimal path, we have to find a queue of points that an AI agent can travel to. This is where the sting pulling is needed. String pulling is in fact not linked to characters at all : it is rather a metaphor. Imagine a cross. Let's say that you wrap a silk thread around this cross and you put tension on it. You will find that the string does not follow the inner corner of it, but rather go from corner to corner of each point of the cross. This is precisely what we're doing but with a string that goes from one point to another. There are many different algorithms that lets us to do this. We chose the Simple Stupid Funnel algorithm because it's actually... ...stupidly simple. To put it simply (no puns intended), we create a funnel that checks each time if the next point is in the funnel or not. The funnel is composed of 3 points: a central apex, a left point (called left apex) and a right point (called right apex). At the beginning, the tested point is on the right side, then we alternate to the left and so on until we reach our point of destination. (as if we were walking) When a point is in the funnel, we continue the algorithm with the other side. If the point is outside the funnel, depending on which side the tested point belongs to, we take the apex from the other side of the funnel and add it to a list of final waypoints. The algorithm is working correctly most of the time. However, the algorithm had a bug that add the last point twice if none of the vertices of the last connection before the destination point were added to the list of final waypoints. We just added an if at the moment but we could come back later to optimize it. In our case, the funnel algorithm gives this path: The Steering Algoritm Now that we have a list of waypoints, we can finally just run our character at every point. But if there were walls in our geometry, then Buddy would run right into a corner wall. He won't be able to reach his destination because he isn't small enough to avoid the corner walls. That's the role of the steering algorithm. Our algorithm is still in heavy development, but its main gist is that we check if the next position of the agent is not in the navigation meshes. If that's the case, then we change its direction so that the agent doesn't hit the wall like an idiot. There is also a path curving algorithm, but it's still too early to know if we'll use that at all... We relied on this good document to program the steering algorithm. It's a 1999 document, but it's still interesting ... With the steering algoritm, we make sure that Buddy moves safely to his destination. (Look how proud he is!) So, this is the navigation mesh algorithm. I must say that, throughout my research, there weren't much pseudocode or code that described the algorithm as a whole. Only then did we realize that what people called "Navmesh" was actually a collage of algorithms rather than a single monolithic one. We also tried to have a cyclic grid with orthogonal cells (i.e. cells on the wall, ceiling) but it looked like that A* wasn't intended to be used in a 3D environment with flat orthogonal cells. My hypothesis is that we need 3D cells for this kind of navigation mesh, otherwise the heuristic value of each cell can change depending on the actual 3D length between the center of a flat cell and the destination point. So we reduced the scope of our navigation meshes and we were able to move an AI agent in our organic dungeon. Here's a picture : Each cyan cubes are the final waypoints found by the String pulling and blue lines represents collisions meshes. Our AI is currently still walking into walls, but the steering is still being implemented.
  9. miimii1205

    Design GUI mockups

    I've came up with some GUI ideas for a Vaporwave roguelite I'm making with @thecheeselover I'm trying to find a really useful and clever way to display informations while keeping the AESTHETICS up... This is a kind of main view displaying health, mana and an enemy's health :
  10. I recently worked on a path-finding algorithm used to move an AI agent into an organically generated dungeon. It's not an easy task but because I've already worked on Team Fortress 2 cards in the past, I already knew navigation meshes (navmesh) and their capabilities. Why Not Waypoints? As described in this paper, waypoint networks were in the past used in video games to save valuable resources. It was an acceptable compromise : level designers already knew where NPCs could and could not go. However, as technology has evolved, computers got more memory that became faster and cheaper. In other words, there was a shift from efficiency to flexibility. In a way, navigation meshes are the evolution of waypoints networks because they fulfill the same need but in a different way. One of the advantages of using a navigation mesh is that an agent can go anywhere in a cell as long as it is convex because it is essentially the definition of convex. It also means that the agent is not limited to a specific waypoint network, so if the destination is out of the waypoint network, it can go directly to it instead of going to the nearest point in the network. A navigation mesh can also be used by many types of agents of different sizes, rather than having many waypoint networks for agents of different sizes. Using a navigation mesh also speeds up graph exploration because, technically, a navigation mesh has fewer nodes than an equivalent waypoint network (that is, a network that has enough points to cover a navigation mesh). The navigation mesh Graph To summarize, a navigation mesh is a mesh that represents where an NPC can walk. A navigation mesh contains convex polygonal nodes (called cells). Each cell can be connected to each other using connections defined by an edge shared between them (or portal edge). In a navigation mesh, each cell can contain information about itself. For example, a cell may be labeled as toxic, and therefore only those units capable of resisting this toxicity can move across it. Personally, because of my experience, I view navigation meshes like the ones found in most Source games. However, all cells in Source's navigation meshes are rectangular. Our implementation is more flexible because the cells can be irregular polygons (as long as they're convex). Navigation Meshes In practice A navigation mesh implementation is actually three algorithms : A graph navigation algorithm A string pulling algorithm And a steering/path-smoothing algorithm In our cases, we used A*, the simple stupid funnel algorithm and a traditional steering algorithm that is still in development. Finding our cells Before doing any graph searches, we need to find 2 things : Our starting cell Our destination cell For example, let's use this navigation mesh : In this navigation meshes, every edge that are shared between 2 cells are also portal edges, which will be used by the string pulling algorithm later on. Also, let's use these points as our starting and destination points: Where our buddy (let's name it Buddy) stands is our staring point, while the flag represents our destination. Because we already have our starting point and our destination point, we just need to check which cell is closest to each point using an octree. Once we know our nearest cells, we must project the starting and destination points onto their respective closest cells. In practice, we do a simple projection of both our starting and destination points onto the normal of their respective cells. Before snapping a projected point, we must first know if the said projected point is outside its cell by finding the difference between the area of the cell and the sum of the areas of the triangles formed by that point and each edge of the cell. If the latter is remarkably larger than the first, the point is outside its cell. The snapping then simply consists of interpolating between the vertices of the edge of the cell closest to the projected point. In terms of code, we do this: Vector3f lineToPoint = pointToProject.subtract(start); Vector3f line = end.subtract(start); Vector3f returnedVector3f = new Vector3f().interpolateLocal(start, end, lineToPoint.dot(line) / line.dot(line)); In our example, the starting and destination cells are C1 and C8 respectively: Graph Search Algorithm A navigation mesh is actually a 2D grid of an unknown or infinite size. In a 3D game, it is common to represent a navigation mesh graph as a graph of flat polygons that aren't orthogonal to each other. There are games that use 3D navigation meshes, like games that use flying AI, but in our case it's a simple grid. For this reason, the use of the A* algorithm is probably the right solution. We chose A* because it's the most generic and flexible algorithm. Technically, we still do not know how our navigation mesh will be used, so going with something more generic can have its benefits... A* works by assigning a cost and a heuristic to a cell. The closer the cell is to our destination, the less expensive it is. The heuristic is calculated similarly but we also take into account the heuristics of the previous cell. This means that the longer a path is, the greater the resulting heuristic will be, and it becomes more likely that this path is not an optimal one. We begin the algorithm by traversing through the connections each of the neighboring cells of the current cell until we arrive at the end cell, doing a sort of exploration / filling. Each cell begins with an infinite heuristic but, as we explore the mesh, it's updated according to the information we learn. In the beginning, our starting cell gets a cost and a heuristic of 0 because the agent is already inside of it. We keep a queue in descending order of cells based on their heuristics. This means that the next cell to use as the current cell is the best candidate for an optimal path. When a cell is being processed, it is removed from that queue in another one that contains the closed cells. While continuing to explore, we also keep a reference of the connection used to move from the current cell to its neighbor. This will be useful later. We do it until we end up in the destination cell. Then, we "reel" up to our starting cell and save each cell we landed on, which gives an optimal path. A* is a very popular algorithm and the pseudocode can easily be found. Even Wikipedia has a pseudocode that is easy to understand. In our example, we find that this is our path: And here are highlighted (in pink) the traversed connections: The String Pulling Algorithm String pulling is the next step in the navigation mesh algorithm. Now that we have a queue of cells that describes an optimal path, we have to find a queue of points that an AI agent can travel to. This is where the sting pulling is needed. String pulling is in fact not linked to characters at all : it is rather a metaphor. Imagine a cross. Let's say that you wrap a silk thread around this cross and you put tension on it. You will find that the string does not follow the inner corner of it, but rather go from corner to corner of each point of the cross. This is precisely what we're doing but with a string that goes from one point to another. There are many different algorithms that lets us to do this. We chose the Simple Stupid Funnel algorithm because it's actually... ...stupidly simple. To put it simply (no puns intended), we create a funnel that checks each time if the next point is in the funnel or not. The funnel is composed of 3 points: a central apex, a left point (called left apex) and a right point (called right apex). At the beginning, the tested point is on the right side, then we alternate to the left and so on until we reach our point of destination. (as if we were walking) When a point is in the funnel, we continue the algorithm with the other side. If the point is outside the funnel, depending on which side the tested point belongs to, we take the apex from the other side of the funnel and add it to a list of final waypoints. The algorithm is working correctly most of the time. However, the algorithm had a bug that add the last point twice if none of the vertices of the last connection before the destination point were added to the list of final waypoints. We just added an if at the moment but we could come back later to optimize it. In our case, the funnel algorithm gives this path: The Steering Algoritm Now that we have a list of waypoints, we can finally just run our character at every point. But if there were walls in our geometry, then Buddy would run right into a corner wall. He won't be able to reach his destination because he isn't small enough to avoid the corner walls. That's the role of the steering algorithm. Our algorithm is still in heavy development, but its main gist is that we check if the next position of the agent is not in the navigation meshes. If that's the case, then we change its direction so that the agent doesn't hit the wall like an idiot. There is also a path curving algorithm, but it's still too early to know if we'll use that at all... We relied on this good document to program the steering algorithm. It's a 1999 document, but it's still interesting ... With the steering algoritm, we make sure that Buddy moves safely to his destination. (Look how proud he is!) So, this is the navigation mesh algorithm. I must say that, throughout my research, there weren't much pseudocode or code that described the algorithm as a whole. Only then did we realize that what people called "Navmesh" was actually a collage of algorithms rather than a single monolithic one. We also tried to have a cyclic grid with orthogonal cells (i.e. cells on the wall, ceiling) but it looked like that A* wasn't intended to be used in a 3D environment with flat orthogonal cells. My hypothesis is that we need 3D cells for this kind of navigation mesh, otherwise the heuristic value of each cell can change depending on the actual 3D length between the center of a flat cell and the destination point. So we reduced the scope of our navigation meshes and we were able to move an AI agent in our organic dungeon. Here's a picture : Each cyan cubes are the final waypoints found by the String pulling and blue lines represents collisions meshes. Our AI is currently still walking into walls, but the steering is still being implemented.
  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!