Multidimensional structures in ECS - waypoint system

Hello all! Currently I am wrapping my head about proper data storing implementation for my pathfinding system. Problem description following.

Prerequisities:

  • I have a level split to X amount of parts
  • every part has Y amount of paths
  • each path has Z amount of waypoints
  • every waypoint is an Entity with IComponentData attached:
public struct Waypoint : IComponentData
{
    public int MapPartIndex;
    public int PathIndex;
    public int WaypointIndex;
    public int NumOfAgentsOnWaypoint;
    public bool IsBlockedByObstacle;
    // use links to neighbour waypoints for path navigation
    public Entity PreviousWaypoint;
    public Entity NextWaypoint;
}
  • X,Y,Z numbers vary from each other, there is no exact defined lenght (just needs to be greater than 0), but average values will be around 3 level parts, 15 paths on one part, 15 waypoints on each path

Usages:

  • each agent has one path assigned, going through path waypoints
  • I want to constantly monitor what is happening around each waypoint and update NumOfAgentsOnWaypoint and IsBlockedByObstacle properties accordingly - this will be monitored through trigger colliders assigned to each waypoint
  • if there are too many agents or the waypoint is blocked, agent chooses another path

Requirements:

  • I want to be able to access level paths data as fast as possible from various systems, ideally in parallel
  • typical usage will be spawner which throws random levelPart/path/waypoint indexes and I need to check whether chosen waypoint is eligible for spawn and eventually look on the next waypoints on the path to see how the path looks in general
  • or another usage: agent finds that next waypoint on its path is blocked → so let’s look on other available paths → In that case I will do sphereCast around the agent to find nearby waypoints and traverse the path it belongs to to see how it looks

Questions:

  • what would be the ideal solution of these paths data interpretation in ECS? In usual OO paradigm I would just do 3-dimensional array and access entity by [levelPartIndex] [pathIndex] [waypointIndex], I can do this by using nested UnsafeLists here, but if I got it right this won’t be eligible for parallel writing
  • I am able to create 3-dimensional blob asset array, but saving Entity references to BlobAsset is not really recommended, am I right?
  • so far the solution which makes the most sense would be to use NativeParallelHashMap<string, Entity> on singleton component, where I would be creating each key by concatening all the indexes, although I am not very satisfied with the need to do this operation in every single access to the map (although performance implication will be minimal I guess?)

Thanks in advance for your thoughs, I am looking forward to see what experience DOTS deveopers do in cases similar to mine!

What doesn’t change?

All paths and waypoints are static, so immutable data would be:

public struct Waypoint : IComponentData
{
    public int MapPartIndex;
    public int PathIndex;
    public int WaypointIndex;
    // use links to neighbour waypoints for path navigation
    public Entity PreviousWaypoint;
    public Entity NextWaypoint;
}

I only need to update NumOfAgentsOnWaypoint and isBlockedByObstacle properties.

Without knowing further details about the specifics of your project, I think my suggestion would be to make level parts and paths entities, and waypoints would be dynamic buffer elements on a path entity. This way, any traversal logic of a path will be cache-coherent, but you still gain parallelism of entities from the separate paths and level parts.

1 Like

I would consider either Entities with Dynamic Buffers, or Native collections for storing data.

Each way point has assigned own global ID.
Each path has own global ID and also way points IDs.
Each level has own global ID and paths IDs.
Etc.
Is just data base structure.

Agents can hold for example path ID and next waypoint ID.

This way, you can build all linear structures of data.

1 Like

Thanks for your answers, so I finally went with DynamicBuffer solution. Specifically:

  • LevelEntity on the top of the hierarchy
  • LevelEntity has DynamicBuffer containing LevelPartEntities
  • each LevelPartEntity has DynamicBuffer containing PathEntities
  • each PathEntity has DynamicBuffer containing WaypointEntities

When every logical block is an entity, I can later add more useful information to each one, such as additional details about each path or level part.

It is very likely that I will revisit this topic with more specific questions as I make further progress with this structure… For now thanks a lot!