Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

3D flood methods for variate 3D box sizes. Thoughts?

Discussion in 'Game Design' started by Antypodish, Feb 14, 2019.

  1. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    10,753
    Hi,

    I am trying figure out, best approach, for 3D flood algorithm. Not asking about algorithm of such, but rather suggestions and / or directions.

    Just for starter, I have 2D representation (rather 3D) of what I want to flood search.

    upload_2019-2-14_8-45-59.png

    Vid as part of the project, to get better idea, what I am dealing with (ECS).




    So as current,

    1.
    I got neighbouring working.
    Meaning, each side of 3D box, stores relevant information, regarding neighbour 3D boxes.
    Hence, I can traverse to every near boxes directly, knowing its location.

    2.
    I have octree, which I can ray cast if needed, or search groups of near 3D boxes.

    3.
    I don't use K-D tree, since I don't use points, but rather variety size 3D cubes. Octree in such case are more suitable, as I believe. Also, my structure can change many times over and often, and can be quite of the size. Hence as far I am concerned, K-D will not be suitable for that reason, as I would need regenerate it every time change occurs.

    On side note, an interesting article regarding K-D tree.
    https://blog.mapbox.com/a-dive-into-spatial-search-algorithms-ebd0c5e39d2a


    So for now, I am thinking of utilizing searching by traverse though neighbours, to build something like


    https://en.wikipedia.org/wiki/A*_search_algorithm

    but for 3D. Other than I don't need path finding part at this point.
    However, while this is rather straight forward for equally spaced grid, my tinkering is around "irregular grid" (see first picture).

    Alternatively, I am thinking about division of 3D boxes, into smaller equal sized cubes, to put them into the regular 3D grid. That seams resealable, but if I could avoid such, it would be nice.

    Or, are there better methods?

    I hope my problem is clear enough, but if not, give me a shout.
    Any thoughts, suggestions, comments?
     
    Last edited: Mar 7, 2023
  2. McDev02

    McDev02

    Joined:
    Nov 22, 2010
    Posts:
    664
    I am not sure what your question is or how far you are already.

    Regarding a pathfinding algorithim it will work just fine, a grid is nothing else than a linked node system. When you have all the neighbours of one room that is all you need. Even if your rooms are rotated as in the video that is no difference. You can use a flood fill (Dijkstra) rather than what you show above as you don't have a general direction to go.

    In addition you can add room size into the equation of the flood fill. It all depends on what you want to achieve and how detailed it should be.

    Once you actually need pathfinding of some sort, so when you can walk inside the rooms, everything gets more complex. For not there are only boxes snapped to one another.
    I mean you need to generate doors, define floor and ceiling etc.

    Maybe your question is about how to find out if a room is linked? In the generation process this seems to be no issue, once you add a box to another you automatically link them.
     
    Last edited: Feb 21, 2019
  3. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    10,753
    Thx for a response.

    For a clarification, each box knows about their neighbors respectively.
    And in fact, they know, at which position each box is attached, by using just index.
    So for example, Right biggest box has 3 neighbours on the left wall.
    Top (left) one is index 0, middle (left) is 1 and bottom (left) 2.
    Respectively, neighbours know about big box, and other adjacent blocks.

    Rotation in 3D space as per video is rather irrelevant. I meant rather to show 3D structure, that it can grow in any direction. Sorry for a confusion, if any.

    Problem is, that storing information in a 3D regular grid, where each axis at each "level", may have different number of blocks (nodes), which in result could become fairly large data structure. In normal case, where structures are fixed, perhaps that would be fairly acceptable. However, I expect to have hundreds to maybe even thousands structures, of variety sizes (small to large (10k, or even 100k)), which can change dynamically, when entering construction mode. In such case, octree structure data comes with help, to reduce amount of stored data, and accelerate searching through tree.

    Yet, I will be looking in grid mechanics again, which would be most convenient, form searching point of view.

    So far however, I use neighbouring references to adjacent blocks, so I can traverse through structure, without using ray cast. But refactoring atm, for better performance.

    What I want to achieve currently; imagine slicing grid diagonally, form left top to bottom right corner.
    upload_2019-2-22_9-23-9.png

    I need to ensure, they are disconnected, or not, using flood.
    Again, this is not that bad to achieve, with regular grid.

    But anyway, I will keep kicking my brain :)
     
    NeatWolf likes this.