Factory Grid Movement

Hi everyone,

I'm trying to implement a system to move items on belts.
And I'm really struggling to find a good solution to make it work in a Job and use multi-thread.

Here are my components:

Spoiler

Code (CSharp):

1.     public struct GridNode : IComponentData
2.     {
3.      
4.     }
5.  
6.     public struct GridCoord : IComponentData, IEquatable<GridCoord>
7.     {
8.         public int2 Value;
9.  
10.         public GridCoord(int x, int y)
11.         {
12.             this.Value = new int2(x, y);
13.         }
14.  
15.         public static implicit operator float3(GridCoord d)
16.         {
17.             return new float3(d.Value.x, 0, d.Value.y);
18.         }
19.  
20.         public bool Equals(GridCoord other)
21.         {
22.             return this.Value.Equals(other.Value);
23.         }
24.  
25.         public override bool Equals(object obj)
26.         {
27.             if (ReferenceEquals(null, obj))
28.             {
29.                 return false;
30.             }
31.  
32.             return obj is GridCoord && Equals((GridCoord)obj);
33.         }
34.  
35.         public override int GetHashCode()
36.         {
37.             return this.Value.GetHashCode();
38.         }
39.     }
40.  
41.     public struct ConveyorPusher : IComponentData
42.     {
43.           public Directions Direction; //East,North,West,North
44.     }
45.  
46.     public struct ConveyorMovable : IComponentData
47.     {
48.     }
49.  
50.     public struct ConveyorAcceptMovable : IComponentData
51.     {
52.  
53.     }

And my Entities Archetypes:
- Empty Tile: GridNode / GridCoord (WHITE)
- Tile with Conveyor Belt: GridNode / GridCoord / ConveyorPusher / ConveyorAcceptMovable (YELLOW)
- Objects that needs to be transported: GridCoord / ConveyorMovable (RED)

And a little drawing:

I tried many different things in jobs, but most of the time I was block because I could read / write at the same time in a job.

So, maybe someone will have a good solution, or already done something similar and know the gotchas.

Important info:
Every objects (red) move at the same time, 1 tile in the direction of the Pusher, each turn, if the targeted tile has an ConveyorAcceptMovable component. (It is not a like in Factorio, realtime moving system )
The drawing shows the current state of the Grid.
I need to figure out which boxes can move, cannot move.

And that's the hard part. Since data can be accessed randomly. For instance:

- C5 is an intersections, so only B5 or C4 can go in C5. (already, kind of race condition, who wins ? )
- B3 can only move if C3 moves. C3 can moves only if C4 moves. And most importantly only if C4 had received priority over B5 at intersection C5

You can start to see that everything is connected at different places..
Which gave me a headache for some days now...

The problem is not trivial but not super hard if you do everything in a single thread.

But I don't think I have enough XP yet using Jobs to handle something like that.

So if someone has some pointers, that'll be awesome.

Also if you want a small challenge

Thanks everyone

 

While it might not be obvious at first, this is actually very similar to this thread: https://forum.unity.com/threads/can...at-plants-be-reliably-run-in-parallel.764534/ I posted an approach to the problem which I believe maps even better to your problem.

 

Thanks for the reply. Yes I commented on this post too. (I will read again the all post, just in case)
I think this post would maybe help for the intersection in C5. Gives priority.
But the hard part is the scaffolding after that will / or will not give others tile possibility to move..

 

I guess you can make this parallel, I have done something similar (not ECS) a long time ago, but had the added complexity that each block “had to move” if possible (if target was full had to move elsewhere)

In your case you make a list of the empty cells, decide which adjacent block moves there (random, clockwise, other logic) and build a list of new empty cells, then repeat until everyone has moved or no empty cell. This could partially be done parallel

 

Yep something that I though of but that's the "repeat" and "parallel" that I'm not quite sure how to do

 

Oh yeah. You were there. Sorry about that.

Yup. I am assuming you are talking about the "traffic jam" part of this problem?

So my proposed solution does solve the intersection problem. But there is still the caveat that an occupant of a targeted tile might not be able to leave. To solve this without a massive iteration headache, each entity that is in a targeted spot gets assigned the reference to the entity the tile gave claim to. This effectively builds a linked list of occupants where the head is the occupant that can move into an empty space and has won claim. So you then have a job that updates all heads, and then recursively updates the linked list chain. You have to use [NativeDisableParallelForRestriction] on the ComponentDataFromEntity, but in this particular case, it should be thread safe.

 

Edit: linked chain - did not use it in my case but in yours it should work (I had the added complexity of endpoints must move and branched chains)

— old cross post —

Does it have to be in the same frame?

If in the same frame, there is a deferred list job but I guess this could only work, if you could establish a maximum “repeat” count and effectively early out of list empty before that is reached

 

Hum not quite sure I'm following everything.
Will this solve the issue of B3 going/or not to C3 ?

If I recap:

- 1) FindEmptyCellsJob
Have a job that find empty cells that can accept a block and that have adjacent blocks that want to move there. I guess I would use a NativeMultiHashmap<GridCoord, CustomStructToStoreInfos>.
That would give me:
- C5 -> C4,B5
- A3 -> A2

- 2) GiveClaimsJob
Iterate over the NativeMultiHashmap (not sure which type of job to use in that case), and give the claim to the first one.
Then store this info in something (?) as a return from the job.

- 3) Now we know that we can move 2 blocks without any trouble. I could then maybe find every blocks that are linked (same direction) than C4 and moves them at the same time. (C3)

- 4) B3 didn't move in this solution

 

I think in your example the chains work
C5 -> c4, c3, b3

you would need to find a solution for branched chains, ie if c2 also had a block

 

Yep ... Saw this scenario also, not cool
Wondering if I should target Intersections instead of empty tiles.

Adding an image to show the 2 différents scenarios that can happens:

 

Ok I maybe got it:


Here an even worst case.

1) CollectGridDataJob
This job will just collect some info for each tile (is there blocks around, is this an intersection, ...)

2) ChooseWinnerIntersectionsJob
Iterate over each intersections (C5 / C3) and choose a winner. (In my case let's say C4 and B3) are the winners

3) MoveJob
Iterate over each empty tiles that want to get a block (C5 / A3)
For A3 easy, we move A2 done.
For C5:
- check winner (C4) add C4 to the move list.
- Then check linked block (same direction) -> C3, add C3 to the move list.
- C3 is an intersection, check which is the winner (B3)
- Add B3 to the move list
- B3 doesn't have any linked blocks. Stop

I think that might work... Just not sure which Containers or Job types to use to be the more efficient

 

Never looked at this problem but seemed interesting so had a crack. After a quick think it doesn't seem that difficult if your belt can't branch (it can merge with another belt but will always only go 1 direction) using a double buffer and iterating tiles instead of boxes.



Logic could be off though but here is my solution (not fully implemented) in a single parallel job.

Code (CSharp):

1. public class GridSystem : JobComponentSystem
2. {
3.     // I don't like keeping grid/world as entities
4.     // But you could populate these from entities if that's how you've setup your game instead.
5.     // key = world index, y * Width + x or whatever hash you want
6.     // if your world isn't too big i'd just use a grid
7.     // Empty tiles will == default
8.     public NativeArray<Tile> Tiles;
9.     public NativeArray<Tile> Buffer;
10.  
11.     protected override JobHandle OnUpdate(JobHandle handle)
12.     {
13.         this.Buffer.CopyFrom(this.Tiles);
14.  
15.         handle = new GridJob
16.         {
17.             Buffer = this.Buffer,
18.             Tiles = this.Tiles,
19.         }
20.             .Schedule(this.Tiles.Length, 64, handle);
21.  
22.         return handle;
23.     }
24.  
25.     [BurstCompile]
26.     public struct GridJob : IJobParallelFor
27.     {
28.         [ReadOnly]
29.         public NativeArray<Tile> Buffer;
30.  
31.         [NativeDisableParallelForRestriction]
32.         public NativeArray<Tile> Tiles;
33.  
34.         public void Execute(int index)
35.         {
36.             Tile tile = this.Buffer[index];
37.  
38.             // tile doesn't exist, or tile occupied skip
39.             // make sure to implement IEquatable<Tile> for the Equals
40.             if (tile.Equals(default) || tile.Owner != Entity.Null)
41.             {
42.                 return;
43.             }
44.  
45.             while (true)
46.             {
47.                 var neighbour = this.GetNeighbour(index);
48.  
49.                 if (neighbour == -1)
50.                 {
51.                     return;
52.                 }
53.  
54.                 var neighbourTile = this.Buffer[neighbour];
55.  
56.                 // move the block, don't touch the buffer
57.  
58.                 // Update new tile
59.                 tile.Owner = neighbourTile.Owner;
60.                 this.Tiles[index] = tile;
61.  
62.                 // Remove from old tile
63.                 neighbourTile.Owner = default;
64.                 this.Tiles[neighbour] = neighbourTile;
65.  
66.                 // Will also need to update block
67.                 // Set transform, destination, etc
68.  
69.                 // our neighbour tile must now be empty so we now so move onto that
70.                 // if there are no branching,
71.                 // no other thread will use this so it's safe even though we're indexing outside
72.                 index = neighbour;
73.                 tile = this.Buffer[index];
74.             }
75.         }
76.  
77.         /// <summary>
78.         /// Get the neighbours that could move here.
79.         /// </summary>
80.         /// <returns>index of neighbour, -1 if no valid neighbour.</returns>
81.         private int GetNeighbour(int index)
82.         {
83.             // check 4 neighbours, see what ones can move to this node.
84.             // check that this node has a box atm
85.             // resolve cases with multiple options however you want, first, direction etc
86.             return -1;
87.         }
88.     }
89. }

Just threw code together, not actually tested. I think the concept should work though, as long as there are no branches.

-edit- updated code to fix an issue

basically the idea is

0. double buffer giving you a readonly Buffer of the current state and Tile that is updated.
1. iterate Buffer, if you find an empty tile continue to 2.
2. find a neighbour that can move there, tie-break however you want, if no neighbour found, go back to 1.
3. move neighbour to Tile (update current and neighbour nodes in Tile, don't touch Buffer)
4. now repeat from 2. with the neighbour tile as it's empty (it won't be empty on the Buffer as we don't update this, so another thread will skip it)

 

Clever - nice solution!

 

Thanks @tertle ! that seems it could work, I'm gonna implement it ASAP.

When you said you don't like to store grid as entities.
How / Where would you store it then ?

The factory grid can become big, also I might have multiple factories in differents Worlds.

 

I'm not sure if you were intentionally going off of what I wrote or if it was just coincidence and I did a terrible job explaining, but this is very similar to what I was proposing of resolving intersections from the tiles' POV and then walking along chains to update. However, you went a step further and used double-buffering to combine the steps and move a lot of the variables to the stack!

I'm impressed!

You have the right idea. There's a couple different ways to keep track of what needs to move. I was originally thinking of storing the entity to move in the destination's occupant, as this generalizes to a multi-occupant use case with dynamic buffers and a hierarchy instead of a component and a linked list. However: @tertle 's approach can also generalize and is more efficient (might not be true if using Burst intrinsics).

 

Got it working and it's beautiful

Thanks Everyone ! @tertle @DreamingImLatios @sngdan

Timeline:

(not sure why so much space between the Fillers Job and the MoveJob... maybe the scheduler...)

Gif:


I didn't need a Double Buffer solution actually. It just worked

Here is the final code for anyone interested:

Spoiler

Code (CSharp):

1.         protected override JobHandle OnUpdate(JobHandle inputDeps)
2.         {
3.             //Hard coded for now
4.             var gridWidth = 13;
5.             var gridHeight = 8;
6.  
7.             var size = gridWidth * gridHeight;
8.  
9.             var pushers = new NativeArray<Pusher>(size, Allocator.TempJob);
10.             var acceptMoves = new NativeArray<AcceptMove>(size, Allocator.TempJob);
11.             var movables = new NativeArray<Movable>(size, Allocator.TempJob);
12.  
13.  
14.             var fillPushersHandle = new FillPushersJob
15.             {
16.                 GridWidth = gridWidth,
17.                 Pushers = pushers
18.             }.Schedule(this, inputDeps);
19.  
20.             var fillAcceptMovableHandle = new FillAcceptMovableJob
21.             {
22.                 GridWidth = gridWidth,
23.                 AcceptMoves = acceptMoves
24.             }.Schedule(this, inputDeps);
25.  
26.             var fillMovablesHandle = new FillMovablesJob
27.             {
28.                 GridWidth = gridWidth,
29.                 Movables = movables
30.             }.Schedule(this, inputDeps);
31.  
32.             var sync = JobHandle.CombineDependencies(fillPushersHandle, fillAcceptMovableHandle, fillMovablesHandle);
33.  
34.             var moveHandle = new MoveJob
35.             {
36.                 NeighboursIndexOffsets = new NativeArray<int>(new[]
37.                 {
38.                     1,
39.                     gridWidth,
40.                     -1,
41.                     -gridWidth
42.                 }, Allocator.TempJob),
43.                 Pushers = pushers,
44.                 AcceptMoves = acceptMoves,
45.                 Movables = movables,
46.                 MoveToEventQueue = EcsUtils.GetEventQueueParallel<ConveyorPushJobEvent>()
47.             }.Schedule(size, 8, sync);
48.  
49.  
50.             return moveHandle;
51.         }
52.  
53.  
54.         public struct Pusher
55.         {
56.             public GridCoord Coord;
57.             public bool HasPusher;
58.             public Directions PusherDirection;
59.         }
60.  
61.         public struct Movable
62.         {
63.             public GridCoord Coord;
64.             public Entity Entity;
65.         }
66.  
67.         public struct AcceptMove
68.         {
69.             public GridCoord Coord;
70.             public bool CanAcceptMove;
71.         }
72.  
73.  
74.         [BurstCompile]
75.         public struct MoveJob : IJobParallelFor
76.         {
77.             [ReadOnly]
78.             [DeallocateOnJobCompletion]
79.             public NativeArray<int> NeighboursIndexOffsets;
80.  
81.             [ReadOnly]
82.             [DeallocateOnJobCompletion]
83.             public NativeArray<AcceptMove> AcceptMoves;
84.  
85.             [ReadOnly]
86.             [DeallocateOnJobCompletion]
87.             public NativeArray<Pusher> Pushers;
88.  
89.             [ReadOnly]
90.             [DeallocateOnJobCompletion]
91.             public NativeArray<Movable> Movables;
92.  
93.             public NativeQueue<ConveyorPushJobEvent>.ParallelWriter MoveToEventQueue;
94.  
95.             public void Execute(int index)
96.             {
97.                 var movableInBuffer = this.Movables[index];
98.  
99.  
100.                 // tile doesn't accept a move, or tile occupied = skip
101.                 if (this.AcceptMoves[index].CanAcceptMove == false || movableInBuffer.Entity != Entity.Null)
102.                 {
103.                     return;
104.                 }
105.  
106.  
107.                 while (true)
108.                 {
109.                     var neighbour = this.GetNeighbour(index);
110.  
111.                     if (neighbour == -1)
112.                     {
113.                         return;
114.                     }
115.  
116.                     index = neighbour;
117.                 }
118.             }
119.  
120.  
121.             private int GetNeighbour(int index)
122.             {
123.                 // check 4 neighbours East - North - West - South
124.                 for (var i = 0; i < this.NeighboursIndexOffsets.Length; i++)
125.                 {
126.                     var neighbourIndex = index + this.NeighboursIndexOffsets[i];
127.  
128.                     //Check out of bound
129.                     if (neighbourIndex < 0 || neighbourIndex >= this.Pushers.Length)
130.                     {
131.                         continue;
132.                     }
133.  
134.  
135.                     //Check if there is a pusher
136.                     var pusher = this.Pushers[neighbourIndex];
137.                     if (pusher.HasPusher == false)
138.                     {
139.                         continue;
140.                     }
141.  
142.  
143.                     //Check if there is a movable
144.                     var movable = this.Movables[neighbourIndex];
145.                     if (movable.Entity == Entity.Null)
146.                     {
147.                         continue;
148.                     }
149.  
150.                     //Check if the pusher will push to the current index
151.                     var currentCoord = this.AcceptMoves[index].Coord;
152.  
153.                     if (pusher.Coord.WithDirection(pusher.PusherDirection).Equals(currentCoord))
154.                     {
155.                         this.MoveToEventQueue.Enqueue(new ConveyorPushJobEvent
156.                         {
157.                             MovableEntity = movable.Entity,
158.                             TargetCoord = currentCoord
159.                         });
160.  
161.                         return neighbourIndex;
162.                     }
163.                 }
164.  
165.                 return -1;
166.             }
167.         }
168.  
169.  
170.         [BurstCompile]
171.         private struct FillPushersJob : IJobForEachWithEntity<GridCoord, ConveyorPusher>
172.         {
173.             public int GridWidth;
174.  
175.             [NativeDisableParallelForRestriction]
176.             public NativeArray<Pusher> Pushers;
177.  
178.             public void Execute(Entity entity, int index, [ReadOnly] ref GridCoord gc, [ReadOnly] ref ConveyorPusher cp)
179.             {
180.                 var i = this.GridWidth * gc.Value.y + gc.Value.x;
181.  
182.                 this.Pushers[i] = new Pusher
183.                 {
184.                     HasPusher = true,
185.                     Coord = gc,
186.                     PusherDirection = cp.Direction
187.                 };
188.             }
189.         }
190.  
191.         [BurstCompile]
192.         [RequireComponentTag(typeof(ConveyorAcceptMovable))]
193.         private struct FillAcceptMovableJob : IJobForEachWithEntity<GridCoord>
194.         {
195.             public int GridWidth;
196.  
197.             [NativeDisableParallelForRestriction]
198.             public NativeArray<AcceptMove> AcceptMoves;
199.  
200.             public void Execute(Entity entity, int index, [ReadOnly] ref GridCoord gc)
201.             {
202.                 var i = this.GridWidth * gc.Value.y + gc.Value.x;
203.  
204.                 this.AcceptMoves[i] = new AcceptMove
205.                 {
206.                     Coord = gc,
207.                     CanAcceptMove = true
208.                 };
209.             }
210.         }
211.  
212.         [BurstCompile]
213.         [RequireComponentTag(typeof(ConveyorMovable))]
214.         private struct FillMovablesJob : IJobForEachWithEntity<GridCoord>
215.         {
216.             public int GridWidth;
217.  
218.             [NativeDisableParallelForRestriction]
219.             public NativeArray<Movable> Movables;
220.  
221.             public void Execute(Entity entity, int index, [ReadOnly] ref GridCoord gc)
222.             {
223.                 var i = this.GridWidth * gc.Value.y + gc.Value.x;
224.  
225.                 var movable = new Movable
226.                 {
227.                     Entity = entity,
228.                     Coord = gc
229.                 };
230.  
231.                 this.Movables[i] = movable;
232.             }
233.         }

 

Inspired by your post about eating trees or whatever it was the other day. I am on the forums as much to learn as to help.

 

You are trading the double buffering for having a single-threaded job to update the positions of objects moved by the conveyor belt using a NativeQueue. I can't say whether it is a good idea or a bad idea, and I'm guessing you won't find out either until you are 90% done with your game. In any case, it definitely is not a terrible idea. You are still sync-point-free and totally jobified with Burst to boot! That's an awesome place to be!

One quick tip, you can change NeighborIndexOffsets to be an int4. That will also clean up your construction and remove the new managed array each frame.

"Eating trees" lol! That's a game idea!

 

Will do, didn't though about that. Thanks !

 

Damn... I swear you guys are freakin reincarnated clones of Einstein existing as giant super-intelligent brains in a jar symbiotically attached to a supercomputer in a mysterious James Bond lab somewhere deep under Antarctica.