CanisTk

R&D build Navigation network graph from octree

Recommended Posts

Hi everyone, I'm new to learning AI pathfinding, although R&D for 3 month... so here is the problem that I had, hope there are someone can give me some advice.

I was trying to develop my Flight Agent in 3D space. and store all the obstacles reference into octree.

so I got the space & obstacle distribution represent in octree already, however I wanted to implement

1) Navigation network graph region (to define the space in region)

2) HPA* , to implement the high level path finding based on simplify network graph

the major issue : 

I know how to collect all remain space from octree node, but I didn't know how to segment the space, and build up a network graph based on it.

 

 

Share this post


Link to post
Share on other sites

Just traverse the octree from the root down to the leaves. If you traverse through a cell that is not occupied and is a leaf cell, you can create a corresponding AABB that surrounds the node and place it into your graph. Creating edges is just a matter of checking all octree neighbors and seeing which ones have vacant cells.

Share this post


Link to post
Share on other sites

thank @ApochPiQ I think I know what you mean, I also found article describe octree like this :

Quote

All neighbours of a white node cannot all be white because merging would take place and the node would not exist.

still working on the implementation, wish me luck.

Edited by CanisTk
quote

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

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

Create an account

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

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Announcements

  • Forum Statistics

    • Total Topics
      628344
    • Total Posts
      2982186
  • Similar Content

    • By Afambus
      Hello,
      I have a full experienced team that looking for a composer and another 3d designer, im expecting as much from you there are other people in this server that can help you we have a determined team, we have done many things in our game there is more information in the discord about everyone and there skills there region and about the game, if you join the discord pm asap
      https://discord.gg/b2teN3m
    • By idzohar
      I am trying to rotate my car sprite just slightly to the left or right depending on input up to a small maximum. When I use this code, the rotation doesn't stop at the maximum i give it. When i try to reset the rotation back to its original state when not pressing any input, the car also jitters between a z axis rotation of 0 and 2.5. I don't understand why the rotation doesn't stop at the given maximums, nor do I understand why its jittering. Can anybody provide me some insight?
              float movementHorizontal = 0f;
              float movementVertical = 0f;
              if (Input.GetKey(KeyCode.A) && Input.GetKey(KeyCode.D))
              {
              }
              else if (Input.GetKey(KeyCode.A))
              {
                  movementHorizontal = -1;
                  if (transform.rotation.z < 10f)
                  {
                      transform.Rotate(zAxis, 2.5f);
                  }            
              }
              else if (Input.GetKey(KeyCode.D))
              {
                  movementHorizontal = 1;
                  if (transform.rotation.z > -10f)
                  {
                      transform.Rotate(zAxis, -2.5f);
                  }
                  
              }
              else
              {
                  if(transform.rotation.z > 0)
                  {
                      transform.Rotate(zAxis, -2.5f);
                      //transform.rotation.Set(0, 0, 0, 0);
                  }
                  else if (transform.rotation.z < 0)
                  {
                      transform.Rotate(zAxis, 2.5f);
                      //transform.rotation.Set(0, 0, 0, 0);
                  }
                  
              }
    • By BAG Labs
      Mobile SoS

      Platform: Android
      Genre: Board
      Link: Google Play
       
      This games sharpen memory and test your strategies to place S-O-S pattern within time limit and serve 3 difficulties as Easy, Normal, and Hard.

      Goals of the game is to put S-O-S words in patterns (Horizontal, Vertical, and Diagonal) alternately with enemy.
       
      Features:
      Single Player Multiplayer Achievements Leaderboards  
       
      Screenshot:

       

       

       
      Link: Google Play
       
      Please help us improve this game with review
    • By abarnes
      Hello!
      I am a game development student in my second year of a three year program and I would like to start building my portfolio. I was thinking of creating some games to show what I can do to potential employers since I wont have any work related experience when I graduate. But as I'm sure you all know there are tons of ways to approach developing/designing a game and I'm curious if anyone had any insight as to any "standards" that come with this? Is it okay to use game engines like Unity, Unreal, Game Maker etc? Or would it be better to make a game from scratch to better show case your skills? Any and all advice will be greatly appreciated!
    • By Hilster
      Hello 2D Artists,
      I've started making a 2D Puzzle Adventure game for mobile and I'm looking for someone who would want in on creating assets for the game. The core of the programming is pretty much complete, you can walk within the grid laid out and push boxes, when there is an object on top of a pressure pad it will activate the linked objects or if there is one object with multiple linked pressure pads it requires you to activate all points for the object to become active. 

      The level iteration for the game is quick and simple, a Photoshop file that is made of individual pixels that represents objects is put into the game and it creates the level out of those pixels with the assigned objects.
      The objects that need sprites created so far is the character, box, pressure pad, door, trap door, the walls, the stairs and the tiled background.
      I intend to add more objects so the amount I'd like to add will be extended.
      My motivations for posting here is to have something that looks nice to be able to display on my portfolio, so if you're looking for a working game that you can place your art into and improve the look of your portfolio then we're in business.
      Please reply with a few past examples of your art below and I'll be in touch!
  • Popular Now