Factory Grid Movement

Unity Engine
,
1

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:

    public struct GridNode : IComponentData
    {
     
    }

    public struct GridCoord : IComponentData, IEquatable<GridCoord>
    {
        public int2 Value;

        public GridCoord(int x, int y)
        {
            this.Value = new int2(x, y);
        }

        public static implicit operator float3(GridCoord d)
        {
            return new float3(d.Value.x, 0, d.Value.y);
        }

        public bool Equals(GridCoord other)
        {
            return this.Value.Equals(other.Value);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj))
            {
                return false;
            }

            return obj is GridCoord && Equals((GridCoord)obj);
        }

        public override int GetHashCode()
        {
            return this.Value.GetHashCode();
        }
    }

    public struct ConveyorPusher : IComponentData
    {
          public Directions Direction; //East,North,West,North
    }

    public struct ConveyorMovable : IComponentData
    {
    }

    public struct ConveyorAcceptMovable : IComponentData
    {

    }

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:
5124725--506327--upload_2019-10-30_22-32-27.png
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 :smile:

Thanks everyone

2

While it might not be obvious at first, this is actually very similar to this thread: Can such mechanics (herbivores eat plants) be reliably run in parallel? I posted an approach to the problem which I believe maps even better to your problem.

3

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…

4

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

5

Yep something that I though of but that’s the “repeat” and “parallel” that I’m not quite sure how to do

6

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.

7

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

8

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

    1. 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.
    1. 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)
    1. B3 didn’t move in this solution
9

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

10

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

Adding an image to show the 2 différents scenarios that can happens:
5124848--506369--upload_2019-10-31_0-16-15.png

11

Ok I maybe got it:

5124869--506372--upload_2019-10-31_0-23-56.png
5124869--506372--upload_2019-10-31_0-23-56.png414×502 2.59 KB

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

12

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.

5124929--506384--upload_2019-10-31_15-59-15.png

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

public class GridSystem : JobComponentSystem
{
    // I don't like keeping grid/world as entities
    // But you could populate these from entities if that's how you've setup your game instead.
    // key = world index, y * Width + x or whatever hash you want
    // if your world isn't too big i'd just use a grid
    // Empty tiles will == default
    public NativeArray<Tile> Tiles;
    public NativeArray<Tile> Buffer;

    protected override JobHandle OnUpdate(JobHandle handle)
    {
        this.Buffer.CopyFrom(this.Tiles);

        handle = new GridJob
        {
            Buffer = this.Buffer,
            Tiles = this.Tiles,
        }
            .Schedule(this.Tiles.Length, 64, handle);

        return handle;
    }

    [BurstCompile]
    public struct GridJob : IJobParallelFor
    {
        [ReadOnly]
        public NativeArray<Tile> Buffer;

        [NativeDisableParallelForRestriction]
        public NativeArray<Tile> Tiles;

        public void Execute(int index)
        {
            Tile tile = this.Buffer[index];

            // tile doesn't exist, or tile occupied skip
            // make sure to implement IEquatable<Tile> for the Equals
            if (tile.Equals(default) || tile.Owner != Entity.Null)
            {
                return;
            }

            while (true)
            {
                var neighbour = this.GetNeighbour(index);

                if (neighbour == -1)
                {
                    return;
                }

                var neighbourTile = this.Buffer[neighbour];

                // move the block, don't touch the buffer

                // Update new tile
                tile.Owner = neighbourTile.Owner;
                this.Tiles[index] = tile;

                // Remove from old tile
                neighbourTile.Owner = default;
                this.Tiles[neighbour] = neighbourTile;

                // Will also need to update block
                // Set transform, destination, etc

                // our neighbour tile must now be empty so we now so move onto that
                // if there are no branching,
                // no other thread will use this so it's safe even though we're indexing outside
                index = neighbour;
                tile = this.Buffer[index];
            }
        }

        /// <summary>
        /// Get the neighbours that could move here.
        /// </summary>
        /// <returns>index of neighbour, -1 if no valid neighbour.</returns>
        private int GetNeighbour(int index)
        {
            // check 4 neighbours, see what ones can move to this node.
            // check that this node has a box atm
            // resolve cases with multiple options however you want, first, direction etc
            return -1;
        }
    }
}

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

  1. double buffer giving you a readonly Buffer of the current state and Tile that is updated.
  2. iterate Buffer, if you find an empty tile continue to 2.
  3. find a neighbour that can move there, tie-break however you want, if no neighbour found, go back to 1.
  4. move neighbour to Tile (update current and neighbour nodes in Tile, don’t touch Buffer)
  5. 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)
3 Likes
13

Clever - nice solution!

14

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.

15

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).

1 Like
16

Got it working and it’s beautiful :smile:

Thanks Everyone ! @tertle @DreamingImLatios @sngdan

Timeline:

5127182--506684--upload_2019-10-31_13-3-55.png
5127182--506684--upload_2019-10-31_13-3-55.png1503×230 108 KB

(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 :smile:

Here is the final code for anyone interested:

        protected override JobHandle OnUpdate(JobHandle inputDeps)
        {
            //Hard coded for now
            var gridWidth = 13;
            var gridHeight = 8;

            var size = gridWidth * gridHeight;

            var pushers = new NativeArray<Pusher>(size, Allocator.TempJob);
            var acceptMoves = new NativeArray<AcceptMove>(size, Allocator.TempJob);
            var movables = new NativeArray<Movable>(size, Allocator.TempJob);


            var fillPushersHandle = new FillPushersJob
            {
                GridWidth = gridWidth,
                Pushers = pushers
            }.Schedule(this, inputDeps);

            var fillAcceptMovableHandle = new FillAcceptMovableJob
            {
                GridWidth = gridWidth,
                AcceptMoves = acceptMoves
            }.Schedule(this, inputDeps);

            var fillMovablesHandle = new FillMovablesJob
            {
                GridWidth = gridWidth,
                Movables = movables
            }.Schedule(this, inputDeps);

            var sync = JobHandle.CombineDependencies(fillPushersHandle, fillAcceptMovableHandle, fillMovablesHandle);

            var moveHandle = new MoveJob
            {
                NeighboursIndexOffsets = new NativeArray<int>(new[]
                {
                    1,
                    gridWidth,
                    -1,
                    -gridWidth
                }, Allocator.TempJob),
                Pushers = pushers,
                AcceptMoves = acceptMoves,
                Movables = movables,
                MoveToEventQueue = EcsUtils.GetEventQueueParallel<ConveyorPushJobEvent>()
            }.Schedule(size, 8, sync);


            return moveHandle;
        }


        public struct Pusher
        {
            public GridCoord Coord;
            public bool HasPusher;
            public Directions PusherDirection;
        }

        public struct Movable
        {
            public GridCoord Coord;
            public Entity Entity;
        }

        public struct AcceptMove
        {
            public GridCoord Coord;
            public bool CanAcceptMove;
        }


        [BurstCompile]
        public struct MoveJob : IJobParallelFor
        {
            [ReadOnly]
            [DeallocateOnJobCompletion]
            public NativeArray<int> NeighboursIndexOffsets;

            [ReadOnly]
            [DeallocateOnJobCompletion]
            public NativeArray<AcceptMove> AcceptMoves;

            [ReadOnly]
            [DeallocateOnJobCompletion]
            public NativeArray<Pusher> Pushers;

            [ReadOnly]
            [DeallocateOnJobCompletion]
            public NativeArray<Movable> Movables;

            public NativeQueue<ConveyorPushJobEvent>.ParallelWriter MoveToEventQueue;

            public void Execute(int index)
            {
                var movableInBuffer = this.Movables[index];


                // tile doesn't accept a move, or tile occupied = skip
                if (this.AcceptMoves[index].CanAcceptMove == false || movableInBuffer.Entity != Entity.Null)
                {
                    return;
                }


                while (true)
                {
                    var neighbour = this.GetNeighbour(index);

                    if (neighbour == -1)
                    {
                        return;
                    }

                    index = neighbour;
                }
            }


            private int GetNeighbour(int index)
            {
                // check 4 neighbours East - North - West - South
                for (var i = 0; i < this.NeighboursIndexOffsets.Length; i++)
                {
                    var neighbourIndex = index + this.NeighboursIndexOffsets[i];

                    //Check out of bound
                    if (neighbourIndex < 0 || neighbourIndex >= this.Pushers.Length)
                    {
                        continue;
                    }


                    //Check if there is a pusher
                    var pusher = this.Pushers[neighbourIndex];
                    if (pusher.HasPusher == false)
                    {
                        continue;
                    }


                    //Check if there is a movable
                    var movable = this.Movables[neighbourIndex];
                    if (movable.Entity == Entity.Null)
                    {
                        continue;
                    }

                    //Check if the pusher will push to the current index
                    var currentCoord = this.AcceptMoves[index].Coord;

                    if (pusher.Coord.WithDirection(pusher.PusherDirection).Equals(currentCoord))
                    {
                        this.MoveToEventQueue.Enqueue(new ConveyorPushJobEvent
                        {
                            MovableEntity = movable.Entity,
                            TargetCoord = currentCoord
                        });

                        return neighbourIndex;
                    }
                }

                return -1;
            }
        }


        [BurstCompile]
        private struct FillPushersJob : IJobForEachWithEntity<GridCoord, ConveyorPusher>
        {
            public int GridWidth;

            [NativeDisableParallelForRestriction]
            public NativeArray<Pusher> Pushers;

            public void Execute(Entity entity, int index, [ReadOnly] ref GridCoord gc, [ReadOnly] ref ConveyorPusher cp)
            {
                var i = this.GridWidth * gc.Value.y + gc.Value.x;

                this.Pushers[i] = new Pusher
                {
                    HasPusher = true,
                    Coord = gc,
                    PusherDirection = cp.Direction
                };
            }
        }

        [BurstCompile]
        [RequireComponentTag(typeof(ConveyorAcceptMovable))]
        private struct FillAcceptMovableJob : IJobForEachWithEntity<GridCoord>
        {
            public int GridWidth;

            [NativeDisableParallelForRestriction]
            public NativeArray<AcceptMove> AcceptMoves;

            public void Execute(Entity entity, int index, [ReadOnly] ref GridCoord gc)
            {
                var i = this.GridWidth * gc.Value.y + gc.Value.x;

                this.AcceptMoves[i] = new AcceptMove
                {
                    Coord = gc,
                    CanAcceptMove = true
                };
            }
        }

        [BurstCompile]
        [RequireComponentTag(typeof(ConveyorMovable))]
        private struct FillMovablesJob : IJobForEachWithEntity<GridCoord>
        {
            public int GridWidth;

            [NativeDisableParallelForRestriction]
            public NativeArray<Movable> Movables;

            public void Execute(Entity entity, int index, [ReadOnly] ref GridCoord gc)
            {
                var i = this.GridWidth * gc.Value.y + gc.Value.x;

                var movable = new Movable
                {
                    Entity = entity,
                    Coord = gc
                };

                this.Movables[i] = movable;
            }
        }
6 Likes
17

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.

2 Likes
18

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!

1 Like
19

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

20

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.