DungeonBurst (Building DungeonKeeper with Unity ECS and Burst) Part 2 – AI and Pathfinding

In this blog post I will demonstrate how to use Unity’s EntityComponentSystem as well as Burst compiled Jobs to build a dungeon builder game like the good old DungeonKeeper.

This awesome old game turned out to be the perfect example to show of some techniques that will hopefully help you to get into the mindset of DOTS and EntityComponentSystems.

In the previous Part of this series we already covered how to load a GameMap and first steps of user input handling. If you have not read it yet I would strongly suggest to read it first and then come back to this post.
https://tech.innogames.com/dungeonburst-building-dungeonkeeper-with-unity-ecs-and-burst/

In this blog post we will cover the topics of:

– Creating and spawning creatures
– Implementing a PathfindingSystem (A-Star in Burst)
– Implementing a PathfindingAgentSystem (let creatures follow a path)
– Implementing an idle behavior for our creatures

Disclaimer:

This project is only for demonstration of usage of the Unity Data Oriented Tech Stack. Neither InnoGames nor I do own any rights on DungeonKeeper. This project is not developed by InnoGames.

Project setup:

Since the last blog post I updated the project to the latest Unity version and also updated some packages. Fortunately there were no major changes required to get the project running on the new versions. But the performance improvements are significant!

Using: Unity 2020.1.10f1

Packages:
– Entities 0.14.0 preview.19
– Hybrid Renderer 0.8.8 preview.19
– Unity Physics 0.5.0 preview.1
– Universal RP 9.0.0 preview.55

Creating and spawning creatures

Every unit that is able to walk through our dungeon will need some way to store information about its speed, target position and its current path. For this we will create the PathfindingAgent:IComponentData. Since a path consists of a list of positions with a varying amount of steps we will use a DynamicBuffer<PathStep> attached to every Agent.
We will use the GameObjectConversion flow to convert a Prefab of a creature into an Entity so we can make use of a AuthoringComponent that will be added to the Prefab of every creature.

PathfindingAgent

public struct PathfindingAgent : IComponentData
{
     public float Speed;
     public float3 TargetPosition;
     public int CurrentStepIndex;
     public int PathLength;
 }
 
 public struct PathStep : IBufferElementData
 {
     public float3 Position;
 }
 
 public class PathfindingAgentAuthoring : MonoBehaviour, IConvertGameObjectToEntity
 {
     public float Speed;
     public void Convert(Entity entity, EntityManager dstManager, GameObjectConversionSystem conversionSystem)
     {
         dstManager.AddComponentData(entity, new PathfindingAgent { Speed = Speed });
         dstManager.AddBuffer<PathStep>(entity);
     }
 }

Lets create the Prefab for our first unit – the Imp.
Its a simple GameObject with a child containing only a MeshFilter and a MeshRenderer (a simple sphere in this case). The root GameObject will have our PathfindingAgentAuthoring component.

Cheat System

Now we need a System that allows us to spawn those Imps into the gameworld. In order to keep things clean i will create a new CheatSystem:JobComponentSystem. This system will be used to implement various cheats and commands useful for debugging.

For it will do three things:

– It will change a diggable MapTile to an empty MapTile when clicking on it.
– It will spawn imps at the mouse cursors position when we press the “I” button.
– It will set the TargetPosition of all PathfindingAgents in the Map to the cursors position when we press the “p” button.

CheatSystem

[UpdateBefore(typeof(TileViewSystem))]
[AlwaysUpdateSystem]
public class CheatSystem : JobComponentSystem
{
    private BuildPhysicsWorld _buildPhysicsSystem;
    private UnityEngine.Camera _camera;
    private Entity _impPrefab;
 
    protected override void OnStartRunning()
    {
        _buildPhysicsSystem = World.DefaultGameObjectInjectionWorld.GetOrCreateSystem<BuildPhysicsWorld>();
        _camera = UnityEngine.Camera.main;
    }
 
    // called from MapLoaderAuthoring
    public void InitImpPrefab(UnityEngine.GameObject impPrefab)
    {
        using (BlobAssetStore blobAssetStore = new BlobAssetStore())
        {
            var conversionSettings = GameObjectConversionSettings.FromWorld(World.DefaultGameObjectInjectionWorld, blobAssetStore);
            _impPrefab = GameObjectConversionUtility.ConvertGameObjectHierarchy(impPrefab, conversionSettings);
        }
    }
 
    protected override JobHandle OnUpdate(JobHandle inputDeps)
    {
        // when left mouse is clicked
        if (UnityEngine.Input.GetMouseButtonDown(0))
        {
            var collisionWorld = _buildPhysicsSystem.PhysicsWorld.CollisionWorld;
            // raycast from camera towards mouse position, returns the MapTile Entity where the raycast hit
            if (InputUtilities.GetTileAtMousePositon(_camera, collisionWorld, GetSingleton<GameMap>(), false, out Entity mouseOverTile))
            {
                if (EntityManager.HasComponent<Diggable>(mouseOverTile))
                {
                    DigMapTile(mouseOverTile);
                }
            }
        }
        if (UnityEngine.Input.GetKeyDown(UnityEngine.KeyCode.I))
        {
            int amount = UnityEngine.Input.GetKey(UnityEngine.KeyCode.LeftShift) ? 100 : 1;
            SpawnImpAtMousePosition(amount);
        }
        if (UnityEngine.Input.GetKeyDown(UnityEngine.KeyCode.P))
        {
            inputDeps = MoveAllAgentsToMousePosition(inputDeps);
        }
        return inputDeps;
    }
 
    private void DigMapTile(Entity mouseOverTile)
    {
        // get MapTile data
        var tileData = EntityManager.GetComponentData<MapTile>(mouseOverTile);
        // change MaptileType to to be empty
        tileData.Type = MapTileType.Empty;
        tileData.Owner = 0;
        // apply data to Entity
        EntityManager.SetComponentData(mouseOverTile, tileData);
        // empty tiles are no longer diggable
        EntityManager.RemoveComponent<Diggable>(mouseOverTile);
        // we need to update the changed MapTile and all 8 surrounding neighbours
        var gameMap = GetSingleton<GameMap>();
        ref TileMapBlobAsset mapData = ref gameMap.TileMap.Value;
        var position = tileData.Position;
        for (int y = position.y - 1; y <= position.y + 1; y++)
        {
            for (int x = position.x - 1; x <= position.x + 1; x++)
            {
                var tileEntity = mapData.Map[x + y * gameMap.Width];
                EntityManager.AddComponentData(tileEntity, new UpdateTileView());
            }
        }
    }
 
    private void SpawnImpAtMousePosition(int amount)
    {
        var collisionWorld = _buildPhysicsSystem.PhysicsWorld.CollisionWorld;
        if (InputUtilities.RayCastFromMousePosition(_camera, collisionWorld, out RaycastHit result))
        {
            Entity hitEntity = InputUtilities.GetTile(result, GetSingleton<GameMap>(), true);
            if (hitEntity == Entity.Null || EntityManager.GetComponentData<MapTile>(hitEntity).Type.IsSolid())
            {
                return;
            }
            var spawnPosition = result.Position + result.SurfaceNormal * 0.1f; ;
            spawnPosition.y = 0;
            // instantiate all imps to spawn
            var spawnedImps = new NativeArray<Entity>(amount, Allocator.TempJob);
            EntityManager.Instantiate(_impPrefab, spawnedImps);
            //asign data to each
            foreach (var imp in spawnedImps)
            {
                EntityManager.SetComponentData(imp, new Translation { Value = spawnPosition });
                EntityManager.AddComponentData(imp, new IdleBehavior());
            }
            spawnedImps.Dispose();
        }
    }
 
    private JobHandle MoveAllAgentsToMousePosition(JobHandle inputDeps)
    {
        var collisionWorld = _buildPhysicsSystem.PhysicsWorld.CollisionWorld;
        if (InputUtilities.RayCastFromMousePosition(_camera, collisionWorld, out RaycastHit result))
        {
            float3 targetPosition = result.Position + result.SurfaceNormal * 0.1f; ;
            targetPosition.y = 0;
            // assign targetposition to every agent on the map
            return Entities.ForEach((ref PathfindingAgent agent) =>
            {
                agent.TargetPosition = targetPosition;
            }).Schedule(inputDeps);
        }
        return inputDeps;
    }
}

Implementing Pathfinding

Pathfinding Grid System

Every unit in the game needs to be able to find its path through our dynamically growing dungeon. Since this game is build on a tile map, we will write our own A-Star pathfinding algorithm implementation for DOTS. My implementation consists of two Systems: The PathfindingGridSystem and the PathfindingSystem.

The PathfindingGridSystem will be responsible for creating and updating the Pathfinding Grid. When there are MapTiles that recently received a UpdateTileView tag, it will check if the tile changed its status from a “non walkable” to a “walkable state” (or vice versa), and adjust the grid nodes accordingly. Every pathfinding node stores information about connections to its neighbors and a roomindex.

PathfindingGridSystem 1/2

public class PathfindingGridSystem : JobComponentSystem
{
    public struct Node
    {
        public float Weight;
        public int Room;
        public int south, north, west, east;
        public int southWest, southEast, northWest, northEast;
    }
 
    public NativeArray<Node> PathfindingNodes;
    public int MapWidth;
 
    protected override void OnCreate()
    {
        // only update this system when there are maptiles that need updating
        RequireForUpdate(GetEntityQuery(typeof(UpdateTileView), typeof(MapTile)));
    }
 
    protected override void OnDestroy()
    {
        if (PathfindingNodes.IsCreated)
        {
            PathfindingNodes.Dispose();
        }
    }
 
    protected override JobHandle OnUpdate(JobHandle inputDeps)
    {
        if (!PathfindingNodes.IsCreated)
        {
            // the first time we are running this system we will initialize the full grid from scratch
            InitializeGrid();
        }
        else
        {
            // update only grid nodes that require updating
            JobHandle jobHandle = UpdateGridNodes(inputDeps);
 
            // complete the jobhandle so that other systems can safely access our PathfindingNodes
            jobHandle.Complete();
            return default;
        }
        return inputDeps;
    }
 
    private void InitializeGrid()
    {
        var gameMap = GetSingleton<GameMap>();
 
        // we store all our nodes in a persistent array that can be accessed from other systems
        PathfindingNodes = new NativeArray<Node>(gameMap.Width * gameMap.Height, Allocator.Persistent);
        MapWidth = gameMap.Width;
 
        var mapTileData = GetComponentDataFromEntity<MapTile>(true);
        ref var mapData = ref gameMap.TileMap.Value;
 
        // assign a weight to all walkable pathfinding nodes
        int walkableMapFieldCount = 0;
        for (int t = 0; t < gameMap.Width * gameMap.Height; t++)
        {
            Entity tileEntity = mapData.Map[t];
            MapTile tileData = mapTileData[tileEntity];
            bool isWalkable = !tileData.Type.IsSolid();
            if (isWalkable)
            {
                PathfindingNodes[t] = new Node { Weight = 1f };
                walkableMapFieldCount++;
            }
        }
        // find all connections with neighbors
        for (int y = 1; y < gameMap.Height - 1; y++)
        {
            for (int x = 1; x < MapWidth - 1; x++)
            {
                UpdateNodeConnections(x, y, MapWidth, PathfindingNodes);
            }
        }
        // assign all connected nodes to rooms
        InitRooms(walkableMapFieldCount, PathfindingNodes);
    }
 
    private JobHandle UpdateGridNodes(JobHandle inputDeps)
    {
        int mapWidth = MapWidth;
        var mapNodes = PathfindingNodes;
 
        // iterate over all maptiles with UpdateTileView tag and evaluate if the node grid needs to be updated
        JobHandle jobHandle = Entities.WithAll<UpdateTileView>().ForEach((in MapTile mapTile) =>
        {
            bool isWalkable = !mapTile.Type.IsSolid();
            int x = mapTile.Position.x;
            int y = mapTile.Position.y;
            int tileIndex = x + y * mapWidth;
            Node node = mapNodes[tileIndex];
            if (node.Weight > 0 != isWalkable)
            {
                if (isWalkable)
                {
                    // node became walkable
                    node.Weight = 1f;
                    mapNodes[tileIndex] = node;
                    UpdateNodeConnections(x, y, mapWidth, mapNodes);
                    // find connecting rooms
                    AssignRoom(x, y, mapWidth, mapNodes);
                }
                else
                {
                    // node became non walkable
                    node.Weight = 0f;
                    node.Room = -(mapNodes.Length + tileIndex + 1); //TODO find safe negative room index
                    mapNodes[tileIndex] = node;
                    //TODO check if a room was split because of the removal of this tile
                }
                // update connections of all surrounding neighbours
                UpdateNodeConnections(x - 1, y, mapWidth, mapNodes);
                UpdateNodeConnections(x + 1, y, mapWidth, mapNodes);
                UpdateNodeConnections(x, y - 1, mapWidth, mapNodes);
                UpdateNodeConnections(x, y + 1, mapWidth, mapNodes);
                UpdateNodeConnections(x - 1, y - 1, mapWidth, mapNodes);
                UpdateNodeConnections(x + 1, y - 1, mapWidth, mapNodes);
                UpdateNodeConnections(x - 1, y + 1, mapWidth, mapNodes);
                UpdateNodeConnections(x + 1, y + 1, mapWidth, mapNodes);
            }
        }).Schedule(inputDeps);
        return jobHandle;
    }
 
    private static void UpdateNodeConnections(int x, int y, int mapWidth, NativeArray<Node> mapNodes)
    {
        int nodeIndex = x + y * mapWidth;
        if (!IsWalkable(nodeIndex, mapNodes))
        {
            return;
        }
        Node node = mapNodes[nodeIndex];
 
        // assign neigbour indices when neighbour is walkable
        node.south = GetWalkableIndex(x, y - 1, mapWidth, mapNodes);
        node.north = GetWalkableIndex(x, y + 1, mapWidth, mapNodes);
        node.west = GetWalkableIndex(x - 1, y, mapWidth, mapNodes);
        node.east = GetWalkableIndex(x + 1, y, mapWidth, mapNodes);
        node.southWest = (node.south != 0 && node.west != 0) ? GetWalkableIndex(x - 1, y - 1, mapWidth, mapNodes) : 0;
        node.southEast = (node.south != 0 && node.east != 0) ? GetWalkableIndex(x + 1, y - 1, mapWidth, mapNodes) : 0;
        node.northWest = (node.north != 0 && node.west != 0) ? GetWalkableIndex(x - 1, y + 1, mapWidth, mapNodes) : 0;
        node.northEast = (node.north != 0 && node.east != 0) ? GetWalkableIndex(x + 1, y + 1, mapWidth, mapNodes) : 0;
 
        mapNodes[nodeIndex] = node;
    }
 
    private static int GetWalkableIndex(int x, int y, int mapWidth, NativeArray<Node> mapNodes)
    {
        int nodeIndex = x + y * mapWidth;
        if (IsWalkable(nodeIndex, mapNodes))
        {
            return nodeIndex;
        }
        return 0;
    }
 
    private static bool IsWalkable(int nodeIndex, NativeArray<Node> mapNodes)
    {
        var node = mapNodes[nodeIndex];
        return node.Weight > 0f;
    }
 
    private static void InitRooms(int walkableMapFieldCount, NativeArray<Node> mapNodes) { ... }
 
    private static void TryAssignRoomAndAddToOpenList(int nodeIndex, int roomIndex, NativeArray<Node> mapNodes, NativeQueue<int> openList) { ... }
 
    private static void AssignRoom(int x, int y, int mapWidth, NativeArray<Node> mapNodes) { ... }
 
    private static void OverrideRooms(int targetRoom, int room1, int room2, int room3, int room4, NativeArray<Node> mapNodes) { ... }
 
}

The roomindex is the same for all MapTiles that are potentially connected to each other, this is very useful for quick checks if a certain MapTile can be reached by checking the start and destination tiles roomindices. If they are the same we can be sure a path will be found, otherwise we don’t even need to try finding a path.

Room 2 and 19 are not connected

As soon as we connect both rooms the higher roomnumber will be assigned

PathfindingGridSystem 2/2

private static void InitRooms(int walkableMapFieldCount, NativeArray<Node> mapNodes)
{
    var assignedRoomCount = 0;
    int roomIndex = 0;
    var nextTile = 0;
 
    NativeQueue<int> openList = new NativeQueue<int>(Allocator.Temp);
 
    while (assignedRoomCount < walkableMapFieldCount)
    {
        roomIndex++;
 
        // find first unassigned tile for new room
        for (; nextTile < mapNodes.Length; nextTile++)
        {
            var node = mapNodes[nextTile];
            if (node.Weight > 0 && node.Room == 0)
            {
                node.Room = roomIndex;
                mapNodes[nextTile] = node;
                openList.Enqueue(nextTile);
                break;
            }
        }
 
        // floodfill all direct neighbours
        while (openList.TryDequeue(out int nodeIndex))
        {
            var node = mapNodes[nodeIndex];
            assignedRoomCount++;
            TryAssignRoomAndAddToOpenList(node.south, roomIndex, mapNodes, openList);
            TryAssignRoomAndAddToOpenList(node.north, roomIndex, mapNodes, openList);
            TryAssignRoomAndAddToOpenList(node.west, roomIndex, mapNodes, openList);
            TryAssignRoomAndAddToOpenList(node.east, roomIndex, mapNodes, openList);
        }
    }
    openList.Dispose();
 
    // assign unique negative room ids to all non walkable nodes
    for (int t = 0; t < mapNodes.Length; t++)
    {
        var node = mapNodes[t];
        if (node.Room == 0)
        {
            node.Room = -(++roomIndex);
            mapNodes[t] = node;
        }
    }
}
 
private static void TryAssignRoomAndAddToOpenList(int nodeIndex, int roomIndex, NativeArray<Node> mapNodes, NativeQueue<int> openList)
{
    if (nodeIndex != 0)
    {
        var nnode = mapNodes[nodeIndex];
        if (nnode.Room == 0)
        {
            nnode.Room = roomIndex;
            mapNodes[nodeIndex] = nnode;
            openList.Enqueue(nodeIndex);
        }
    }
}
 
private static void AssignRoom(int x, int y, int mapWidth, NativeArray<Node> mapNodes)
{
    int nodeIndex = x + y * mapWidth;
    var node = mapNodes[nodeIndex];
    int northRoom = mapNodes[node.north].Room;
    int eastRoom = mapNodes[node.east].Room;
    int southRoom = mapNodes[node.south].Room;
    int westRoom = mapNodes[node.west].Room;
    // pick the highest room number from all neighbours
    int maxRoom = math.max(math.max(northRoom, eastRoom), math.max(southRoom, westRoom));
    if (maxRoom > 0)
    {
        node.Room = maxRoom;
        // if this room connects multiple rooms combine
        OverrideRooms(maxRoom, northRoom, eastRoom, southRoom, westRoom, mapNodes);
    }
    else
    {
        node.Room = -node.Room;
    }
    mapNodes[nodeIndex] = node;
}
 
private static void OverrideRooms(int targetRoom, int room1, int room2, int room3, int room4, NativeArray<Node> mapNodes)
{
    bool checkRoom1 = room1 > 0 && room1 != targetRoom;
    bool checkRoom2 = room2 > 0 && room2 != targetRoom;
    bool checkRoom3 = room3 > 0 && room3 != targetRoom;
    bool checkRoom4 = room4 > 0 && room4 != targetRoom;
    for (int n = 0; n < mapNodes.Length; n++)
    {
        var node = mapNodes[n];
        int currentRoom = node.Room;
        //if node is one of the 4 provided room ids
        if ((checkRoom1 && currentRoom == room1)
        || (checkRoom2 && currentRoom == room2)
        || (checkRoom3 && currentRoom == room3)
        || (checkRoom4 && currentRoom == room4))
        {
            //assign targetRoom
            node.Room = targetRoom;
            mapNodes[n] = node;
        }
    }
}

Pathfinding System

The PathfindingSystem will handle all path requests for the game. It will update all entities that have a PathRequest:IComponentData attached by doing pathfinding and assigning the found path back to the Entity. For that it uses the Pathfinding Grid from the PathfindingGridSystem and do some A-Star to find paths.

PathfindingSystem

[UpdateAfter(typeof(PathfindingGridSystem))]
public class PathfindingSystem : JobComponentSystem
{
    private PathfindingGridSystem _gridSystem;
    private EndSimulationEntityCommandBufferSystem _commandBufferSystem;
    private const float StraightCost = 1f;
    private static readonly float DiagonalCost = math.sqrt(StraightCost * StraightCost + StraightCost * StraightCost);
 
    public struct PathfindingRequest : IComponentData
    {
        public float3 Start;
        public float3 Target;
        public RequestStatus Status;
    }
 
    private struct NodeEntry
    {
        public int Index;
        public float TotalCost;
    }
 
    public enum RequestStatus
    {
        Pending,
        Unreachable
    }
 
    protected override void OnCreate()
    {
        _gridSystem = World.DefaultGameObjectInjectionWorld.GetOrCreateSystem<PathfindingGridSystem>();
        _commandBufferSystem = World.DefaultGameObjectInjectionWorld.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
    }
 
    protected override JobHandle OnUpdate(JobHandle inputDeps)
    {
        var commandBuffer = _commandBufferSystem.CreateCommandBuffer().AsParallelWriter();
        var mapNodes = _gridSystem.PathfindingNodes;
        int mapWidth = _gridSystem.MapWidth;
        // iterate over all PathfindingAgents that have a PathfindingRequest
        var jobHandle = Entities.ForEach((int entityInQueryIndex, Entity entity, ref DynamicBuffer<PathStep> pathBuffer, ref PathfindingAgent agent, ref PathfindingRequest request) =>
        {
            if (FindPath(request, ref agent, pathBuffer, mapWidth, mapNodes))
            {
                commandBuffer.RemoveComponent<PathfindingRequest>(entityInQueryIndex, entity);
            }
            else
            {
                request.Status = RequestStatus.Unreachable;
            }
        }).WithReadOnly(mapNodes).Schedule(inputDeps);
        _commandBufferSystem.AddJobHandleForProducer(jobHandle);
        return jobHandle;
    }
 
    public static bool IsReachable(int2 start, int2 target, int mapWidth, NativeArray<PathfindingGridSystem.Node> mapNodes)
    {
        int startNodeIndex = start.x + start.y * mapWidth;
        int targetNodeIndex = target.x + target.y * mapWidth;
        // compare start and target room index
        return mapNodes[startNodeIndex].Room == mapNodes[targetNodeIndex].Room;
    }
 
    private static bool FindPath(PathfindingRequest request, ref PathfindingAgent agent, DynamicBuffer<PathStep> pathBuffer, int mapWidth, NativeArray<PathfindingGridSystem.Node> mapNodes)
    {
        if (!IsReachable((int2)request.Start.xz, (int2)request.Target.xz, mapWidth, mapNodes))
        {
            return false;
        }
        int startNodeIndex = (int)request.Start.x + (int)request.Start.z * mapWidth;
        int targetNodeIndex = (int)request.Target.x + (int)request.Target.z * mapWidth;
        var buffer = pathBuffer.Reinterpret<float3>();
        if (startNodeIndex == targetNodeIndex)
        {
            // unit is moving on the same tile
            buffer.Clear();
            buffer.Add(request.Start);
            buffer.Add(request.Target);
            agent.PathLength = 2;
            return true;
        }
 
        int nodeCount = mapNodes.Length;
        var cameFrom = new NativeHashMap<int, int>(nodeCount, Allocator.Temp);
        var costs = new NativeHashMap<int, float>(nodeCount, Allocator.Temp);
        var openNodes = new NativeList<NodeEntry>(Allocator.Temp);
 
        // add start node to open list
        openNodes.Add(new NodeEntry { Index = startNodeIndex, TotalCost = 0 });
        cameFrom.TryAdd(startNodeIndex, startNodeIndex);
        costs.TryAdd(startNodeIndex, 0);
        while (openNodes.Length > 0)
        {
            // remove lowest cost node from openlist
            int nextIndex = FindLowestCostNode(ref openNodes);
            int currentNodeIndex = openNodes[nextIndex].Index;
            openNodes.RemoveAtSwapBack(nextIndex);
 
            if (currentNodeIndex == targetNodeIndex)
            {
                // we arrived at target positon
                buffer.Clear();
                // reconstruct path and add pathsteps to the buffer
                int currentResult = targetNodeIndex;
                while (currentResult != startNodeIndex)
                {
                    float3 position = new float3(currentResult % mapWidth, 0, currentResult / mapWidth);
                    buffer.Insert(0, position + new float3(0.5f, 0f, 0.5f));
                    cameFrom.TryGetValue(currentResult, out currentResult);
                }
                buffer[pathBuffer.Length - 1] = request.Target;
                agent.PathLength = pathBuffer.Length;
                costs.Dispose();
                cameFrom.Dispose();
                openNodes.Dispose();
                return true;
            }
 
            var currentNode = mapNodes[currentNodeIndex];
            costs.TryGetValue(currentNodeIndex, out float currentCost);
            var straight = currentCost + currentNode.Weight * StraightCost;
            var diag = currentCost + currentNode.Weight * DiagonalCost;
 
            // update all neighbours
            CheckNeighbour(currentNodeIndex, currentNode.south, straight, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
            CheckNeighbour(currentNodeIndex, currentNode.north, straight, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
            CheckNeighbour(currentNodeIndex, currentNode.west, straight, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
            CheckNeighbour(currentNodeIndex, currentNode.east, straight, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
 
            CheckNeighbour(currentNodeIndex, currentNode.southWest, diag, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
            CheckNeighbour(currentNodeIndex, currentNode.southEast, diag, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
            CheckNeighbour(currentNodeIndex, currentNode.northWest, diag, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
            CheckNeighbour(currentNodeIndex, currentNode.northEast, diag, request.Target, ref cameFrom, ref costs, ref openNodes, mapWidth);
        }
 
        // no path was found dispose maps
        costs.Dispose();
        cameFrom.Dispose();
        openNodes.Dispose();
        return false;
    }
 
    private static void CheckNeighbour(int currentIndex, int neighbourIndex, float newCost, float3 target, ref NativeHashMap<int, int> cameFrom, ref NativeHashMap<int, float> costs, ref NativeList<NodeEntry> openNodes, int mapWidth)
    {
        if (neighbourIndex == 0)
        {
            return;
        }
        // if neighbour was not visited yet or it is cheaper to visit neighbour from current node
        bool costFound = costs.TryGetValue(neighbourIndex, out float costSoFar);
        if (!costFound || newCost < costSoFar)
        {
            if (costFound)
            {
                costs.Remove(neighbourIndex);
                cameFrom.Remove(neighbourIndex);
            }
 
            // update costs
            costs.TryAdd(neighbourIndex, newCost);
            cameFrom.TryAdd(neighbourIndex, currentIndex);
 
            // add neighbour to open list
            float3 neighbourPosition = new float3(neighbourIndex % mapWidth, 0, neighbourIndex / mapWidth);
            float totalCost = newCost + math.distance(target, neighbourPosition);
            openNodes.Add(new NodeEntry { Index = neighbourIndex, TotalCost = totalCost });
        }
    }
 
    private static int FindLowestCostNode(ref NativeList<NodeEntry> openNodes)
    {
        int nextIndex = openNodes.Length - 1;
        float minCost = openNodes[nextIndex].TotalCost;
        for (int o = nextIndex - 1; o >= 0; o--)
        {
            float totalCost = openNodes[o].TotalCost;
            if (totalCost < minCost)
            {
                nextIndex = o;
                minCost = totalCost;
            }
        }
        return nextIndex;
    }
}

Implementing path following AI

With the data and pathfinding systems prepared we can write our PathfindingAgentSystem. It will iterate over all PathfindingAgents and request a path if it needs to move to a target position. if a path is assigned it will move the agent along the path until the target position is reached.

PathfindingAgentSystem

[UpdateBefore(typeof(PathfindingSystem))]
[UpdateBefore(typeof(TransformSystemGroup))]
public class PathfindingAgentSystem : JobComponentSystem
{
    private EndSimulationEntityCommandBufferSystem _commandBufferSystem;
 
    protected override void OnCreate()
    {
        _commandBufferSystem = World.DefaultGameObjectInjectionWorld.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
    }
 
    protected override JobHandle OnUpdate(JobHandle inputDeps)
    {
        var commandBuffer = _commandBufferSystem.CreateCommandBuffer().AsParallelWriter();
        float deltaTime = Time.DeltaTime;
        // iterate over all our PathfindingAgents
        var jobHandle = Entities.ForEach((int entityInQueryIndex, Entity entity, ref DynamicBuffer<PathStep> pathBuffer, ref PathfindingAgent agent, ref Translation translation, ref Rotation rotation) =>
        {
            // if we dont have a targetposition
            if (agent.TargetPosition.Equals(float3.zero))
            {
                return;
            }
            // if we arrived at targetposition
            if (math.distancesq(translation.Value.xz, agent.TargetPosition.xz) < 0.01f)
            {
                agent.TargetPosition = float3.zero;
                ResetPath(ref agent, ref pathBuffer);
                return;
            }
            var path = pathBuffer.Reinterpret<float3>();
            // if we dont have a path or a path to a wrong destination
            if (agent.PathLength == 0 || !path[path.Length - 1].Equals(agent.TargetPosition))
            {
                // request new path
                commandBuffer.AddComponent(entityInQueryIndex, entity, new PathfindingSystem.PathfindingRequest
                {
                    Start = translation.Value,
                    Target = agent.TargetPosition
                });
                ResetPath(ref agent, ref pathBuffer);
                return;
            }
            // move along the path
            float movementDist = agent.Speed * deltaTime;
            while (movementDist > 0)
            {
                var targetPosition = path[agent.CurrentStepIndex];
                var offset = new float3(targetPosition.x, translation.Value.y, targetPosition.z) - translation.Value;
                float distanceToNextPostion = math.length(offset);
                bool isLastStep = agent.CurrentStepIndex + 1 >= path.Length;
                // while on the path we only need to get close to current path step
                if (!isLastStep && distanceToNextPostion < 0.75f)
                {
                    agent.CurrentStepIndex++;
                    continue;
                }
                var direction = math.normalize(offset);
                rotation.Value = quaternion.LookRotation(direction, new float3(0, 1, 0));
                if (movementDist < distanceToNextPostion)
                {
                    translation.Value += direction * movementDist;
                    break;
                }
                // we arrived at current path step
                translation.Value += direction * distanceToNextPostion;
                if (isLastStep)
                {
                    agent.TargetPosition = float3.zero;
                    ResetPath(ref agent, ref pathBuffer);
                    break;
                }
                movementDist -= distanceToNextPostion;
                agent.CurrentStepIndex++;
            }
        }).Schedule(inputDeps);
        _commandBufferSystem.AddJobHandleForProducer(jobHandle);
        return jobHandle;
    }
 
    private static void ResetPath(ref PathfindingAgent agent, ref DynamicBuffer<PathStep> pathBuffer)
    {
        if (agent.PathLength > 0)
        {
            pathBuffer.Clear();
            agent.CurrentStepIndex = 0;
            agent.PathLength = 0;
        }
    }
}

Implementing a simple Idle Behavior AI

For demonstration purposes, lets create our first simple Idle Behavior. 

Every unit with this behavior will move to a random position within the dungeon and wait there for a while, before it searches the next random position.
Since we have a roomindex, we can pick one random tile from the room where the creature is currently located. We can assign this behavior to all Imps we spawn in the CheatSystem.

IdleBehaviorSystem

public struct IdleBehavior : IComponentData
{
    public float IdleDuration;
}
 
[UpdateAfter(typeof(PathfindingGridSystem))]
public class IdleBehaviorSystem : JobComponentSystem
{
    private PathfindingGridSystem _gridSystem;
 
    protected override void OnCreate()
    {
        _gridSystem = World.DefaultGameObjectInjectionWorld.GetOrCreateSystem<PathfindingGridSystem>();
    }
 
    protected override JobHandle OnUpdate(JobHandle inputDeps)
    {
        var deltaTime = Time.DeltaTime;
        uint seed = (uint)(UnityEngine.Time.timeSinceLevelLoad * 1000);
        var mapNodes = _gridSystem.PathfindingNodes;
        int mapWidth = _gridSystem.MapWidth;
        // iterate over all idle pathfinding agents
        var updateIdleBehavioursHandle = Entities.ForEach((int entityInQueryIndex, Entity entity, ref PathfindingAgent pathfindingAgent, ref IdleBehavior behaviour, in Translation translation) =>
        {
            // when unit has no targetposition
            if (pathfindingAgent.TargetPosition.Equals(float3.zero))
            {
                // wait
                behaviour.IdleDuration -= deltaTime;
                if (behaviour.IdleDuration <= 0f)
                {
                    behaviour.IdleDuration = 3f;
                    // after a while search a random target
                    var random = new Random(seed + (uint)entityInQueryIndex * 333);
                    pathfindingAgent.TargetPosition = GetRandomTargetPosition(translation.Value, mapWidth, mapNodes, random);
                }
            }
        }).WithReadOnly(mapNodes).Schedule(inputDeps);
        return updateIdleBehavioursHandle;
    }
 
    private static float3 GetRandomTargetPosition(float3 start, int mapWidth, NativeArray<PathfindingGridSystem.Node> pathfindingNodes, Random random)
    {
        int startNodeIndex = (int)start.x + (int)start.z * mapWidth;
        // find all tiles of the creatures room
        int roomId = pathfindingNodes[startNodeIndex].Room;
        NativeList<int2> targetPositions = new NativeList<int2>(pathfindingNodes.Length, Allocator.Temp);
        for (int n = 0; n < pathfindingNodes.Length; n++)
        {
            if (pathfindingNodes[n].Room == roomId)
            {
                targetPositions.Add(new int2(n % mapWidth, n / mapWidth));
            }
        }
        // pick random tile
        int2 randomTarget = targetPositions[random.NextInt(targetPositions.Length - 1)];
        targetPositions.Dispose();
        // return position in tile
        float2 offset = random.NextFloat2(0.2f, 0.8f);
        return new float3(randomTarget.x + offset.x, 0, randomTarget.y + offset.y);
    }
}

I included the whole project in this unitypackage

• InnoGames is hiring! Check out open positions and join our awesome international team in Hamburg at the certified Great Place to Work®.