Jump to content
  • Advertisement
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
Advertisement

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

  • Advertisement
  • Advertisement
  • Popular Tags

  • Similar Content

    • By Alexander_Vovk
      Hello Guys!
      Please share your experience, where is it better to find sales manager  specialists for indie team of 6 + people(remotely)?
      Maybe someone has a good experience of cooperation with finding projects through sale managers(USA and Canada)?
      Thank you
      Best Regards
      Alex Vovk
      Co-Founder of Sixteen Squares
      Alexander_Vovk@outlook.com
       
    • By RoKabium Games
      Been a bit quiet recently, but we've been busy bug fixing and tweaking things... Now we have lots more 'Particle effects' in the game, specifically here the Flamethrower and Enemy attacks!
    • By JoshuaFraser
      Hi and thanks for reading, I have an issue with this reactive crosshair script, everything works fine until I start changing the offset. Give the script a go and you will see what I mean, when I do SetOffset(0f); it doesnt always set back to the origional state, if anyone can spot a fix I'd be super appreciative!
      using System.Collections; using System.Collections.Generic; using UnityEngine; public class ReactiveCrosshair : MonoBehaviour { [SerializeField] GameObject c_limb_prefab; private float center_offset = 0f; private float current_offset = 0f; private float max_offset = .5f; private int number_of_limbs = 4; private float limb_length = .05f; private float limb_width = .005f; private List<GameObject> c_limbs = new List<GameObject>(); public void SetupCrosshair(){ for (int i = 0; i < number_of_limbs; i++) { GameObject line_go = (GameObject)Instantiate (c_limb_prefab); line_go.transform.SetParent (this.transform); Vector3 limb_pos = new Vector3 (0f,0f,0f); //line_go.transform.position = limb_pos; line_go.transform.localPosition = limb_pos; LineRenderer line = line_go.GetComponent<LineRenderer>(); line.startWidth = limb_width; line.positionCount = 2; line.SetPosition (0, line_go.transform.localPosition + new Vector3(center_offset, 0f, 0f)); line.SetPosition (1, line_go.transform.localPosition + new Vector3(center_offset + limb_length, 0f, 0f)); line.useWorldSpace = false; c_limbs.Add(line_go.gameObject); } if (c_limbs != null) { OrientLimbs (); SetOffset (0f); } } public void OrientLimbs(){ for (int i = 0; i < c_limbs.Count; i++) { float rotation_step = 360f / (float)c_limbs.Count; c_limbs [i].transform.RotateAround (c_limbs[i].transform.position, c_limbs[i].transform.forward, 90f + (rotation_step * (float)i)); } } public void SetOffset(float _current_spread){ float offset = Mathf.Lerp (0f, max_offset, _current_spread); for (int i = 0; i < number_of_limbs; i++) { if (offset > current_offset) { Vector3 pos = c_limbs [i].transform.position + (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } if (offset < current_offset) { Vector3 pos = c_limbs [i].transform.position - (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } } Debug.Log ("SetOffset() offset: " + offset.ToString () + " _current_spread: " + _current_spread.ToString() + " localPos: " + c_limbs[1].transform.localPosition); current_offset = offset; } }  
    • By Erik Nivala
      So, as the title says i am trying to figure out a good way sync all that information with other players in Unity. My problem is that i can't come up with a good solution since i am used to creating classes for everything e.g. attachments are its own class and then the weapon would save a reference to that attachment. But since you can't send custom classes over [Command] & [ClientRPC] i am a little stuck. A solution for this would be giving each attachment for a slot a unique ID and then passing the ID to other player but i feel like that is very error prone if other ppl add a new attachment or the IDs get mixed up.
      Is there a "standard" way that this is usually done that i am missing?
      I am fairly new to programming so any help is appreciated!
    • By MintyLyton
      I'm looking for any team / people that need a programmer for their project. I'm looking to expand my portfolio which you can see Here. I'm more experienced with Unity but I can spend the time to learn new Engines if that's your preference. I have worked on Unreal Engine 4 before but I might take some time to re-learn it, if the project requires it. Feel free to DM here or use the contact info on my website. 
    • By Woody Stevens
      Hi,
       
      I am looking for a TCP or HTTP networking library similar to Lidgren (UDP).
       
      This is primarily for sending game map data and potentially other large messages from Server to Client.
       
      I do want to keep Lidgren for my chat messages, player position, small fast updates etc. I especially love the flow of data and the library usage in general, so any libraries of a similar style would be excellent. Preferably something open source, free and reliable.
      I also must be able to swap between localhost and an ip address with ease, like Lidgren, as I run a server for singleplayer/mp/lan.
       
      My game maps are similar to minecraft, but it is 2d and only one Z-level, so i'm sending a jagged array of Tile object data (currently only enum TileID.Grass) down the pipe to the Client. Problem is if i'm sending a large map 1024 x 1024 tiles down the to client that's quite a lot of data, and Lidgren is relatively slow to build the writes (before the message is even sent!). It is fine when i'm using smaller maps < 512 x 512 ( xTiles * yTiles ).

      I know about chunking and will look into implementing this later, whilst taking into account the user's position in the world to only send nearby chunks.
       
      An example of my code that can be slow:
      private void WriteWorld(NetOutgoingMessage outgoing) { try { var world = WorldManager.Instance.CurrentWorld; outgoing.Write(world.XTiles); outgoing.Write(world.YTiles); for (int x = 0; x < world.XTiles; x++) { for (int y = 0; y < world.YTiles; y++) { // Write Tile obj data outgoing.Write((int)world.Tiles[x][y]); // <-------- Slow here when xTiles and yTiles are each > 512 ! } } } catch (Exception ex) { // log send error } }  
      I'd love to hear from you guys, especially if any of you have come across a similar challenge.
    • By ethancodes
      I'm working on a system for my game that will allow the player to stack pick ups in a queue. As one pick up expires, the next automatically activates. I'm having an issue though where if I pick up the first one, it activates fine, but if i pick up a second directly after it, it overrides the first one, activates the second one, and then once it has run it's course, everything goes back to normal gameplay, no first pick up. I'm not sure why this is happening. Hopefully someone can spot what I'm doing wrong in my code.
      Here is the code for the pick up manager:
      // Update is called once per frame void Update () { if (pickUpQueue.Count != 0 && !pickUpActive) { pickUpActive = true; pickUpQueue[0].ActivatePickUp(); } DeactivatePickUp(); } void DeactivatePickUp () { if (pickUpQueue.Count != 0 && pickUpActive) { Destroy (pickUpQueue [0]); pickUpQueue.RemoveAt (0); pickUpActive = false; } } And here is the PickUp:
      public override void ActivatePickUp () { ball.GetComponent<Ball>().Speed = 2.0f; //increase ball speed... ball.GetComponent<Ball>().StartCoroutine(timer); //...set time that power up is active }  
      There is also a Base Pick Up:
      public void OnCollisionEnter2D (Collision2D collision) { Vector2 tweak = new Vector2 (Random.Range(0f, 0.2f),Random.Range(0f, 0.2f)); this.gameObject.GetComponent<Rigidbody2D>().velocity += tweak; //if the pickup makes contact with the paddle or ball.... if (collision.gameObject.tag == "Paddle" || collision.gameObject.tag == "Ball") { GameObject.FindObjectOfType<GameManager>().GetComponent<PickUpManager>().pickUpQueue.Add(this); Destroy(gameObject); //...and finally destroy power up object } } As a side note, I am trying to find a solution to this that will work for all of my pickups. Some pickups are ammo based, some are timed. 
    • By Hellados
      Hello guys, my name is Giorgi and i'm newbie game developer i'm learning Pixel art and after pixel art  i want learn C# and don't know how and where start i'm bad with programming language and know only HTML/CSS
  • Advertisement
  • Popular Now

  • Forum Statistics

    • Total Topics
      631393
    • Total Posts
      2999763
×

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!