Solution for Porting Pathfinding Calculations to Jobs System

I'm working on optimizing my A* pathfinding algorithm by using the Jobs system, and hopefully eliminate lag over long distance searches.

I've been porting our existing solution to be DOTS compatible -- creating structs to encapsulate class data, not calling anything static, trying to use `Unity.Collections` rather than Generics.

I'm hitting a roadblock with data structures, and I'd like to share what I have tried.

Let me post some snippets of the structs in question:

Code (CSharp):

1. public struct WorldGridData
2. {
3.     public readonly int Width;
4.     public readonly int Height;
5.  
6.     // Value<int> is representative of WorldCellData as bytes
7.     public NativeHashMap<int2, int> Cells;
8.     public WorldCellData this[int2 pos] => fromBytes(Cells[pos]);
9.     public WorldCellData this[int x, int y] => fromBytes(Cells[new int2(x, y)]);
10.  
11.     public WorldGridData(WorldGrid worldGrid)
12.     {
13.         Width = worldGrid.Width;
14.         Height = worldGrid.Height;
15.         Cells = new NativeHashMap<int2, int>(Height * Width, AllocatorManager.TempJob);
16.  
17.         for (var x = 0; x < Width; x++)
18.         {
19.             for(var y = 0; y < Height; y++)
20.             {
21.                 var cell = worldGrid.WorldCells[x, y];
22.                 Cells.Add(new int2(x, y), getBytes(new WorldCellData(cell, this)));
23.             }
24.         }
25.     }
26.  
27.     ....
28. }

Code (CSharp):

1. public struct WorldCellData
2. {
3.     public int2 Position;
4.     public int Height;
5.  
6.     public UnitPathfindingData? Unit;
7.     public WorldGridData WorldGrid;
8.  
9.     // Value<int> represents bytes of WorldCellTileData
10.     public NativeHashMap<int, int> TilesByLayer;
11.     public NativeHashMap<int, int> OverrideTilesByLayer;
12.  
13.    ...
14. }

Code (CSharp):

1. public struct WorldCellTileData
2. {
3.     public string TerrainName;
4.     public bool HasLineOfSight;
5.     public int StairsOrientation;
6.  
7.     public NativeHashMap<int, int> TravelCost;
8.     public NativeHashMap<int, int> BlockExit;
9.     public NativeHashMap<int, int> BlockEntrance;
10.  
11.     ...
12. }

The relationship:

WorldGridData has_many WorldCellData structs via Cells
WorldCellData has_namy WorldCellTile structs via TileLayers && OverrideTileLayers


Things I tried:

1. Using Generics like

Dictionary

. Got a deallocated error, so figured I was required to use only Unity.Collections

2. Doing something like

public NativeHashMap<int2, WorldCellData> Cells;

. But, apparently structs are not primitive or blittable, thus cannot be used in a

NativeContainer

EDIT: This is actually not true. NativeHashMap can take structs... apparently just not mine?



The struct in question:

(The constructor is called in the main thread and the resulting struct is passed to the Job struct, so it doesn't touch outside classes during execution)



The two

Dictionary<int, WorldCellTileData>

are

Dictionary

's because the error says:

"ArgumentException: WorldCellData used in native collection is not blittable, not primitive, or contains a type tagged as NativeContainer"

They were

NativeHashMap

's before, but I changed them to not use

NativeContainer

.

I even read this thread that claims

bool

's aren't blittable, so I'm using the Bool struct in all my structs.

^ bools are blittable now. disregard.

So, no idea why this struct isn't working with Burst Compiler.

EDIT 2: Found a stray usage of

NativeHashMap

in one of the structs!

New error:



So, my structs can't use

NativeContainer

or reference types like

List 

or

Dictionary

.

I guess I can only use

NativeContainer

within the job struct alone?

3. Tried to be crafty. I thought: why don't I just convert the structs into bytes and deserialize them at runtime? I can't use

byte[]

or

string

in a

NativeContainer

, since they're nullable... but

int

's arent!

So, I tried my hand at using

Marshal

or

MemoryStreamer

+

BinaryFormatter

to convert structs into bytes, then use

BitConverter

to generate `Int32`'s to represent the struct's bytes.

Thought I was a C++ wizard, until --- it didn't work.

NativeHashMap

and

Unity.Collections

in general are not

[Serializable]

, thus my structs couldn't be converted into byte arrays.

This is where I got stuck.

Is it possible to SOMEHOW store a Dictionary or List of structs within a

IJobParallelFor

struct? Without it, I won't have access to the state of my game's grid to perform the A* calculations correctly...

 

Code (CSharp):

1. struct A
2. {
3.     public NativeList<B> b;
4. }
5.  
6. struct B
7. {
8.     public float val;
9. }
10.  
11. struct Job : IJob
12. {
13.     public A a; // legal
14. }

Code (CSharp):

1. struct A
2. {
3.     public NativeList<B> b;
4. }
5.  
6. struct B
7. {
8.     public NativeList<float> indirectlyNestedContainer;
9. }
10.  
11. struct Job : IJob
12. {
13.     public A a; // Error. Nesting NativeContainers, even indirectly, is not allowed.
14. }

 

That's quite a limitation.

Is there no way around this?

Seems impossible to represent relationship data that uses List/Dictionaries (or NativeList/NativeHashMap).

The only workaround I can think of is serializing the dictionaries as ints and unpacking them within the job struct's Execute...

 

There is the unsafe API, but rarely do you actually need nested containers. I think you need to take a step back and redesign your data structure. It is unclear to me in what remains of your initial post what you actually need.