I am trying to implement my own pathfinding solution in unity but cant figures out how to store data. Following is my grid class which stores height, length and neighbour tile of tile.

public class grid
{
public float XVal;
public float ZVal;
public int[] NId = new int [8];
}

With Length and Height of 1, I am creating a grid for terrain size that part of the code works nicely It creates a grid, finds its neighbours. I am saving data in Array

grid[] MyGrid ;

The problem occurs when terrain size is big ex 1024*1024 so for creating a grid, Considering row and column of terrain total elements of grid becomes row(1024)*column(1024) approx. 1 million. As creating such a big grid while running game is impossible So I created custom inspector and generate grid graph and populate array in the editor. But while loading game as Mygrid array size is 1 million game stucks while loading, To fix that I created subsystem which basically divides Mygrid array in multiple arrays which seems working but is there any other way to efficiently store grid data as dividing array adds complexity in code

  • 1
    All of the information you're storing in the grid class presently looks like information you can infer from its position in your array alone. So you might not need these members. What currently uses these grid instances in your game? – DMGregory Dec 5 at 13:55
  • It works like 2d grid where each tile of the grid contains information of its all 8 diagonal adjacent tiles and other basic information like If it is walkable or not etc. – paul p Dec 5 at 14:03
  • 1
    I think what you need is a Navmesh solution (doesn't necessarily be the one from Unity) with that big size. A grid graph isn't well suited for big areas. An idea for your current solution would be to use some sort of subdivision and only work with the data of a stripped down area. Just an idea. – M156 Dec 5 at 14:11
up vote 3 down vote accepted

Right now for each tile you're storing:

  • 4 bytes of x position
  • 4 bytes of y position
  • an array of neighours, entailing...
    • 32 bytes of IDs
    • 4+ byte address of the array
    • 4 byte array size
    • ? memory management overhead
  • 4+ byte address of this grid cell in you myGrid array
  • ? memory management overhead for this instance of the class

That's something over 50 bytes to store one bit of information: "this spot is navigable," and that means your 1024x1024 map uses over 50 megabytes of memory.

By contrast, we could store navigable/not navigable as a 0 or 1 bit in a sequence of bits. We know which tile a given bit is describing, and which 8 tiles are its neighbours, based on its position in the sequence.

For example:

public class BitGrid {
    int size;
    BitArray bits;

    public BitGrid(int size) {
        this.size = size;
        bits = new BitArray(size * size);
    }

    public void SetPassable(int x, int y, bool isPassable) {
        int index = CellToBitIndex(x, y);
        if(index < 0)
            return;

        bits[index] = isPassable;
    }

    public bool IsPassable(int x, int y) {
        int index = CellToBitIndex(x, y);
        if(index < 0)
            return false;

        return bits[index];
    }

    int CellToBitIndex(int x, int y) {
        if(x < 0 || x >= size || y < 0 || y >= size)
            return -1;

        // If desired, you could instead use Morton Ordering
        // here for better data locality between rows.
        return y * size + x;
    }
}

Now the pathfinder operates on ordered pairs of x, y coordinates (or x z if you prefer), and can query neighbours by checking myGrid.IsPassable(x-1, y-1) etc.

Doing it this way the 50 meg map takes only 128 KiB of memory, at least 400 times smaller. And it can be stored contiguously so we don't encounter so many cache misses from jumping around memory following pointers.

I'd suspect this method will run much faster and allow you to scale up to even larger maps if you choose.

  • Hello,I am storing neighbours data so the agent can navigate faster. My main problem is storing data as 1024*1024 grid makes array size to almost 1 million which makes impossible to load while starting out the game. Sorry If I made my question confusing – paul p Dec 5 at 14:20
  • 1
    Storing the neighbours will not make your agents navigate faster. In fact, doing it that way may make them navigate slower since they're likely to take three cache misses every time they try to select a neighbouring cell (one to reach their current cell, one to look up from its neighbours array, and a third to look up that ID). One million is not a big number to load if it's one million bits instead of 50 million bytes. – DMGregory Dec 5 at 14:42

Similar to what DMGregory mentioned, you have lots of memory overhead for things that can be mathematically determined (with a little bit of architecture changing).

First off, your grid data structure is ENTIRELY data. If you typed your data as a struct rather than a class c# wouldn't need to create additional memory management data (ptrs, reference counters, etc) per grid instance, which could save a decent chunk of memory.

Since you keep using the word "grid" I'm going to assume that's the general structure of your tiles. If that's the case, you may be better off using grid indices as a "hash" of vector2 information, resulting in a byte[][] to store terrain information. This way a tile's position AND neighbor information is exposed as part of the structure rather than data that needs to be loaded / saved. This saves you tons of memory and has potential performance improvements.

If you can't use a 2D array, consider splitting your data into separate structures, using a more "data oriented approach". So you'd have a Vector2[] for position data and an int[][] for neighbor information. This doesn't necessarily save you space, but it might due to data alignment. It also has potential runtime benefits.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.