Jump to content
  • Advertisement

thecheeselover

Member
  • Content count

    117
  • Joined

  • Last visited

Community Reputation

588 Good

2 Followers

About thecheeselover

  • Rank
    Member

Personal Information

  • Industry Role
    Programmer
  • Interests
    Art
    Business
    Programming

Recent Profile Visitors

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

  1. thecheeselover

    Latest from GameDev.net - May 2018

    Nice. As for tutorials, my friend and I are considering it, especially for the I mean everybody likes money but I would feel extremely bad for gaining money from gamedev.net. Also, would there be a way for 2 people to participate in a tutorial?
  2. The home page is the slowest but other pages are also slow (from my perspective as of 2018 standards, which again is also my opinion). Google Chrome for Windows (10), Version 66.0.3359.181 (Official Build) (64-bit). On mobile, I also use Chrome for Android. It used to be frequent when the huge gamedev update was pushed. However, nowadays it's pretty rare and the images not loading are mostly on old blog posts.
  3. Opening a gamedev.net tab is always slow but slower on mobile devices because of their CPUs. On my extremely powerful laptop, it takes 10 seconds to open gamedev. On my phone, which is a 2.5 years old Samsung S5 Neo, it takes forever. Go check his blog post. I opened the link 3 times. The first time, the images didn't load, only the names were displayed. The other 2 times it worked. Recent blog posts seem unaffected, as if it was a huge update from gamedev that changed the data format of blog posts and the transition from old data to new data wasn't perfect.
  4. thecheeselover

    Node Loops

    It looks like the string pulling algorithm but reversed. Instead the angle of the cone can only be reduced, in your case it can only be increased.
  5. Introduction In our 3D game (miimii1205), we use a dynamically created navigation mesh to navigate onto a procedurally generated terrain. To do so, only the A* and string pulling algorithms were more specifically used until our last agile sprint. We recently added two new behaviors to the pathfinding : steering and wall collision avoidance. In this article, I will describe how I achieved a simple way for agents to not walk into walls. Configuration 3D or 2D navigation mesh, as long as the 3D one is not cyclic. Navigation cells and their : polygonal edges, connections (other cell), shared edges (the line intersecting between two connected cells), centroids and normals. An A* and string pulled (not tested without string pulling) generated path consisting of waypoints on the navigation mesh. The Algorithm The agent is the pink low-poly humanoid and the final destination is the flag. The ideal algorithm (yet unoptimized) would be to cast an oriented rectangle between each consecutive waypoint where its width is the two times the radius. Think of the agent's center position being in the middle of the width. Anyway, this algorithm is too complicated, too long to develop for our game, too big for nothing and so I thought about another algorithm, which has its drawbacks actually. However, it's more suited for our game. Psss, check this article if you haven't seen it yet. The algorithm is the following : For each waypoint, pick the current one and the next one until the next one is the last. Iterate over the current navigation cell's edges, which is defined by the agent's 3D position. To do that, you need a spatial and optimized way to determine the closest cell of a 3D point. Our way to do it is to first have have an octree to partition the navigation mesh. After that, get all the cells that are close to the point plus an extra buffer. To find the cell that is the closest to the point, for each picked cell, cast a projection of the position onto each one of them. This can be done using their centroids and normals. Don't forget to snap the projected position onto the cell. After, that compute the length of the resulting vector and pick the smallest one. Convert each edge to a 2D line by discarding the Y component (UP vector). For each side left and right, which are defined by the agent's position and direction towards the next waypoint, cast a 2D line that start from the agent's position, that goes towards one of the two perpendicular directions related to the direction to the next waypoint and that has a length of the defined radius. If there's an intersection on a connection and that it's on the shared part of the connection, then continue with the connected cell's edges. If there are any intersections other than #5, create a new waypoint before the next waypoint. This new one's position is defined by the intersection's position translated by a length of two times the radius and projected towards the agent's current direction as a 2D line. The same translation is applied to the next waypoint. Cast two 2D lines, one on each side of the agent as described before, starting from the sides, going towards the same direction as the agent and of the same length between the current and next waypoint. Check for #5. If there is an intersection on a connection and that it's on the unshared part of the connection, then do #6 (no if). If there's an intersection on a simple edge, then translate the next waypoint as described in #6. Here's a video of the algorithm in action :
  6. thecheeselover

    Tower Defense Challenge : Progress

    The design reminds me of Emperor: Battle for Dune
  7. I found the pathfinding part very interesting! By the way, which Red Alert did you take your inspiration from? I'm certainly not a huge fan of Command & Conquer and Red Alert
  8. thecheeselover

    Navigation Mesh : Wall Collision Avoidance

    We are a small team of 2. I'm the "lead" programmer and my friend is the lead designer; whilst being what I believe is a talented junior programmer, the word lead really only means that I do the most programming. I still have a lot of work to do on my maturity / professionalism side however Nice for your jobs! My experimentations with voxels and procedural generation made me win all the internships that I really wanted in university and I chose one at Ludia, which is a video game development company naturally. It's been an extremely constructive discussion with you, so thank you very much I hope everything you have planned goes well for you too!
  9. thecheeselover

    Navigation Mesh : Wall Collision Avoidance

    We have different worlds for our game and everything is still "work in progress" and can change. Until yesterday, those were the planified worlds : Savannah - Zones made up of marching cubes voxels where they are applied like a heightmap Jungle - Organic brute force dungeon generation Goblin cave - Marching cubes voxels with a lot of tunnels and with layers Sky - Extremely organic and relying a lot on assets The world we are currently working on is the jungle, which needs generated navigation meshes. We put a lot of effort into navmesh and yesterday we changed the design of the jungle level generator for a classic 2D array dungeon digger. Reading your comment, it made me think that maybe we wasted our time on the navmesh because we could have just used the newly designed 2D array for the A* and string pulling. We could still use our work on the sky world but we will probably work on it in like 6 months... Damn it! We try to follow Agile methodologies and still fail to not waste our time. It just proves that I'm more of a bottoms-up and backend / engine programmer than what I should be for our game. Nice game by the way
  10. thecheeselover

    Navigation Mesh : Wall Collision Avoidance

    Initially, I tried what is described in this tutorial because our project is in Java and uses the jMonkey Engine 3.1. It was such a hassle just to configure the pathfinding librairies because CritterAI is so obscure. I had to modify the source code. What is CritterAI? According to the mentionned tutorial : Also, the navmesh generator just didn't work and is extremely old. Everytime I fix something related to it, something else would break. So I just rage quit and decided that we would make our own navmesh module. That would allow us to have more control over the AI. Another thing to note is that our game has differents worlds made of randomly generated levels. Each world geometry is quite different from each other. For example, we use a navigation mesh for the jungle level because of its organic nature but can directly use the A* in the savannah because it's made up of voxels with the marching cubes algorithm. Making our own library comes with downsides too. We cannot directly use the awesome features of the libgdx ai library for example. Furthermore, we have a lot of units with different radiuses : humanoids, snakes, bigger snakes, tigers, mini-bosses, bosses, legendary bosses and so on. That would make a lot of layers for the navigation mesh. Now for your problem and hobby project, more specifically the navigation mesh cells on top of buildings, what you can do is either check that each of them is indirectly or directly connection to a root cell or you could check that each of them has at least 1 connection. My second proposal is easier but will likely still sometimes outputs garbage. My first proposal is most expensive in terms of performance and also requires a human to flag the root cell or a certain root position if you can get the closer cell to a point. That's cool to have obstacles! Our needs and problems are actually different : you work on a prebuilt level (mesh) when we work with a completely generated level. The best designer for our generated world is the generator actually. That's why it is he (it?) which creates the navigation mesh for our game. The only things that is not in the generator are the octree, the automatic connections, which is a lot of work by the way, and cells metadata. What do you want to do with your navmesh generator? Is its purpose only to generate the navmesh of several prebuilt maps or is it to work for a community of modders? Do you plan to add a lot of new maps?
  11. thecheeselover

    Navigation Mesh : Wall Collision Avoidance

    There are two reasons for [that I can remember] : Our navigation mesh are generated in-house and originally, we weren't supposed to add the wall collision avoidance module. We actually don't want the navigations meshes to depend onto each agent's radius. There's actually a way to do what you're talking about with multilayered navigation meshes. Each agent can have different radius values.
  12. I wrote an unfinished and unpublished blog entry yersterday and I planified to finish it today, which I actually did. However, someone commented on it yesterday... so before it was published. Is there a way to fix this?
  13. thecheeselover

    Navigation Mesh : Wall Collision Avoidance

    @miimii1205 did the string pulling algorithm, so I'll tag him. As far as I know, the second option seems to be really complex. The easiest one would actually be the first option you proposed. I'm sure there are static ways that are better than what I just described. Static in the sense that they are computed before the path generation algorithm is done. However, my algorithm is dynamic. It runs during run time and can be limited to the two next waypoints. Also, the algorithm that I use to intersect two 2D lines is performant.
  14. thecheeselover

    Idea: Iridescent shader

    You forgot to mention that it should be a vertex shader, not a fragment shader. Also, I love doing shaders wink wink Let me do some shaders too.
  • 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!