next »

[diegzumillo]

As usual, I encountered a technical problem and completely underestimated its complexity. My attempt at solution on the fly while coding became an entangled mess. So I took a step back and started noticing its complexity. But as I dig deeper it feels like this is a problem that must have elegant solutions across basic programming textbooks out there. Maybe someone can help me out.

The intended behavior is like this (1D for sake of illustration). Imagine you have a center position C (a player, for ex), then I sample the space around it at specific intervals to load a model M, or whatever.

------(-M---M---M-C-M---M---M--)-----

Parenthesis represent the radius around C we want to sample.

So then as C moves I want to update the models shown, unloading some (X) and loading some new ones (N)

-------X-(--M---M---M-C-M---M---N--)---

The naive approach is too expensive. You basically just unload everything, resample every point within the radius and load what you need.

Unloading could be done agent-based, that is, every model checks to see if it's still within radius, if not it unloads itself. But that still leaves the loading part to be defined. I'm thinking it should be just a matter of resampling the area ahead. Which is trivial in 1D but in 3D it's a bit annoying. Using a cube is easy but wasteful. Using the complex volume of the boolean combination of two sphere volumes is weird.

So anyway, I burnt a fuse thinking of ways to do this with an array of gridElement class that contains relevant information. The idea was to always keep this list updated. Each element knows its equivalent model. But then you need to update the position of the grid every now and then, and we are back to the same problem of moving the unloaded models forward, to the new volume ahead. Sounds complicated and dumb.

Before going ahead with whatever my lazy ass comes up with, I thought it would be wise to ask, as this has all the traits of a problem already solved a million times before.

[Daid]

I've done the grid based solution before. Where you load/unload things if the player crosses the grid boundary. It wasn't that hard to setup, I just added knowledge on the objects themselves that the knew which grid cell they where in, and moved to a different cell if their position was updated.

Few things to watch out for are:

• Objects larger then your grid size. If you want this, you need a multi level grid with different sizes, which does become more complex fast. Or you need to split your objects into smaller objects (for static geometry)
• You might want to load/unload static geometry 1 cell beyond dynamic objects. For collision/physics reasons.
• Loading on a distance of X and unloading on a distance of X+1 will give objects 1 cell of room to exists on not exist, and won't cause a lot of loading/unloading if the player is constantly crossing the same boundary.

[nova++]

So, sounds like there are two problems here - calculating the grid in a reasonable way, and moving the objects around the player while the player traverses some limited grid space.

Perhaps you could do something I did for my star generator and have a "walking grid" where it quantizes the viewer position, iterates across a fixed sized grid of that position, and keeps track of a set of positions that either fall inside or outside of the current grid.

When points are no longer in the radius, discard them from that set, and, using the point's position value as an index of some sort (C# dictionary for instance), unload the corresponding items. When a new point is added, call the load function for that position, and add the position to the same tracking set mentioned earlier.

The actual logic for doing this can be a bit complicated, but it ensures that all you are ever running is load/unload functions for positions that have had a state change of some sort.

Because it sounds like you are also wanting the player to stay centered with objects moving around you, I would recommend keeping some sort of "global position" (I use the Unity.Mathematics double3 class for such things, basically universally, not to mention int3 for grids and the like) that you use for tracking grid positions, and keep the "real position" (aka, in-engine coordinates) relative to that global position.

Quantizing the player position is a good way to do that sort of floating-origin approach, also. You can just map the position to an arbitrarily sized grid and, if the grid changes, offset all relevant objects by the appropriate amount to put them on the opposite side of the grid cell.

Some faux-C#:

Code:

GridPosition newGridPosition = RoundToGrid(realPosition);

if (newGridPosition != oldGridPosition)
{
    GridPosition gridDelta = newGridPosition - oldGridPosition;
    RealPosition realDelta = new Vector(gridDelta.x * gridSize, gridDelta.y * gridSize);

    foreach(Thing t in allThings)
    {
        t.position -= realDelta;
    }

    oldGridPosition = newGridPosition;
}

You can also do it by way of measuring the player's distance from an arbitrary point and calculating the deltas from that, but by doing it on a grid like this, you could easily pair it with the other grid-based function I mentioned, only ever having to run that test when the player's grid position changes, so you don't waste time running the check a thousand times for the same grid cell.

[diegzumillo]

Thanks for the help, everyone. This subforum is much better for this kind of question than dedicated programming forums or Unity's.

NovaSilisko: I'm having trouble following your description. If I understand correctly you keep a list of all positions in the grid centered around the player. So the player moves by, say, one grid unit, then you again quantize the player position and iterate over the new grid around. Then you check against the list you had, add the new positions and unload/remove from list the positions no longer relevant. That never crossed my mind because I find it difficult to use position as an identifier, because of floating point precision and all that. Maybe the new position calculated are 0.0001f off the previous grid, which means it won't recognize the elements currently in the list. How did you handle that?

I never used dictionaries, I'm looking it up right now.

[nova++]

You don't use the floating point position as any sort of identifier, as you said, precision issues make that not viable. Instead you convert the position value to some integer representation. Here's my snap-to-grid function for instance:

Code:

private int3 FitToOriginGrid(double3 toFit)
{
    return new int3()
    {
        x = (int)math.round(toFit.x / originGridSize),
        y = (int)math.round(toFit.y / originGridSize),
        z = (int)math.round(toFit.z / originGridSize)
    };
}

This uses the int3 struct from the Unity.Mathematics library: https://docs.unity3d.com/Packages/[email protected]/manual/index.html

which already has the equality tests that let it be used as a key for a C# dictionary object: https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?view=netframework-4.8

You test this against the "true" player position (meaning the floating point position, be it the typical 32 bit float, or a 64 bit representation... I use 64 bit because I'm dealing with actual planets, but that is a bit of a special case) and compare it to the stored position.

So, each time that position changes, you iterate something like this, counting through -1, 0, and 1, on the X and Y axes:

Code:

for (int y = -1; y <= 1; y++)
{
    for (int x = -1; x <= 1; x++)
    {
        int realX = playerGridPos.x + x;
        int realY = playerGridPos.y + y;
    }
}

It's a little hard to work through the logic just writing about it. I'd have to make a functional example to properly demonstrate it, I think. I might do that sometime soon.

[diegzumillo]

Ah! this is where the int3 comes into play. It makes sense now. You compare integers, a thing computers like comparing.

Sounds good, I'm going to try that later today and report back 

[diegzumillo]

That did the trick! using the position as identifier was the big facilitator here.

I would still need to work on some optimization code. Adding and removing from lists seems wasteful. But that's for future Diego.

[oahda]

Hooray!!

[qMopey]

What's wrong with adding and removing from lists?

[diegzumillo]

I guess it depends on how often the operations are being made and how many. I still don't know where my case stand and whether I should switch to a more efficient system with static lists and pooling.

[nova++]

Wait, what? What sort of lists are you using? In my case I was using a list that's just a global variable in the class and testing against that. Please don't make new lists every time the function gets called 

[diegzumillo]

Right now I'm using C# List with Add and RemoteAt functions. Is that what you mean by "make new lists every time the function gets called"? is that what's happening behind the curtains? Doesn't seem too bad! at least for prototyping purposes.

The future solution would be to have a static list of the class I'm calling 'gridpoint', which contains (will) a 'vacant' bool. Whenever a new point enters the radius I just look for a vacant gridpoint and repurpose it. It works because I know the number of current gridpoints will never change, unless I change the radius.

[nova++]

I think I am going to go ahead and make my example project because that would let me get across some of these points a lot easier. Possibly. I'm dealing with an ear problem and it's hard to program when you're dizzy.

Edit: there we go



I'll explain how it works + provide code soon

edit2: here it be: https://github.com/NovaSilisko/Griddotron

I added a bunch of comments and stuff to hopefully help explain things...

[diegzumillo]

Awesome! I'll have a look at the code later. At least the functionality is similar but not identical to mine. In yours the gameobjects exist and are inactive until inside the grid, mine are procedurally generated.

[nova++]

Awesome! I'll have a look at the code later. At least the functionality is similar but not identical to mine. In yours the gameobjects exist and are inactive until inside the grid, mine are procedurally generated.

I'm pre-generating a list of positions to use and then spawning/deleting objects when those positions arrive, but it can have whatever functionality really.

[qMopey]

Wow Nova, that was really nice of you! Cheers 

[oahda]

Indeed!