Navigation - PathFollowing

User Code & Projects zay-es
1

Hi, i try to outline what i need to convert from the OOP world to ES world by this two examples from which i hope to be able to learn the idea behind.

A navigation path followed by one or more entities. The path is not editable. I gets replaced or cleared when some goal is met.

//OOP Code:
class Path{
  enum TraverseMode{
    Forward
    Backward
    ForwardAndBackward
    Circular
  }

  TraverseMode mode;
  List<Vector2f> waypoints;
}

Now, in the ES world i would probably have something like:

Entity{
  PathIdComponent
  TraverseModeComponent
}

Entity{
  PositionComponent
  PartOfPathComponent{int position, EntityId id}
}

MyMovingEntity{
  FollowPath{EntityId path}
}

The problems i have in this case are:
a) i have lots of reverse lookups to get the actual path. (At the end i have the very same list as in OOP)
b) i have to reverse lookup if any entity follows the path, to be able to safely delete the path entities.

It seems i cannot find some other design that solves a and b

2

Before I answer, I have some questions.

  1. What is the motivation for putting this into the ES in the first place? I ask because it might imply some hidden requirements that you have not mentioned.

  2. By this…

Do you mean that you do not want to delete a path that is currently being ‘walked’?
None of your data structures (even the OOP style ones) support this. So how would you do it in OOP-land?

  1. This one…

I actually don’t understand. If there is a main path entity and all of the nodes refer to it then why wouldn’t it be just one query to find them all and delete them?

Or is it the separate deletes that are of concern? (In Zay-ES it’s one query and a loop, I think.)

But anyway, before I dive into details, I’m really curious where the motivation to put this into the ES is coming from. Those reasons are probably hidden requirements.

3

To be honest i have never thought about not to put this into ES. It seems to be “per entity data” and i kind of assumed that my EntityData should represent the full current world state.
It would however simplify my networking code if all data required by the clients is part of the EntityData.

No, just for the cleanup. If no entity follows the path then i can safely remove it. (What the GC does with Path in the OOP world as soon as there is no more reference to it)

With reverse lookup’s i am referring to that i would have to build a “List path” each frame to calculate the closestPointOnPath for the steering systems to have a target. In the OOP world i would have the List, while with the “separate entity for each waypoint” i would have some code like:

List<Vector2f> buildWayPoint(EntityId pathEntityId){
   List<EntityId> entities = EntityData.getEntities("Where PartOfPathComponent.id == pathEntityId");
   return entities.stream().sort().map().toList();
}

While i can cache the result in a map and it should not be a performance issue it seems strange that i actually split the waypoints into different entities just to collect the data again.

4

That may be true. If you are even persisting AI state then you would want to persist the current paths. Some (a lot?) of games would let the AI re-engage upon load… figure out what they want to do again, recalculate paths, etc…

Path finding is done on the client? That part seems weird to me so I’m interested in learning more about your situation.

But there must be some system managing the steering of active mobs, no? Does it really iterate the entities and reload everything every frame?

Also, do you use Zay-ES or something else? That may have affected your approaches, also… some ES libraries do things in a weird non-ES way.

Edit: note: I’m still collecting information for my real response. I’m not just punting everything back. I’m trying to avoid spending time writing something up that won’t apply.

5

I don’t think i have to persist and load. Once the game is finished or interrruped i do not plan to reload.

No, path finding is done on the server, but the client needs to visual the path afterwards. The player should know the exact path taken so he can take actions.

in the oop test code it does. at least the getClosestPoint on path is calculated every step.

Zay-ES with my own network layer

6

Just my two cents

If you are calculating a new path everytime a pathfinding request comes then I think it is totally fine to have a path info component that keeps a list of waypoints.

But if you want to generate a path and register it so it can be used multiple times by more than one entity then you can use a path registry to register path with a name.

public interface PathRegistery {

      public void register(PathInfo info, Path path);

      public Path getPath(PathInfo info);

}

internally path registry is just useing a Map to keep the path.

Now PathInfo is a component that just keeps the path name and probably path start, end and traverse mode. Then in your Steering System you can look up the path from registry and if not found then calculate a new path.

client side view then can watch for entities with PathInfo component and use a client side path registry that syncs itself with server side path registry (e.g. via network service layer using JME RMI)

or otherwise for client side visualization you can create one-use entities that has a PathDebug component that keep a list of waypoints and client side view state would then watches for them to draw the path.

Kind of in the same fashion SiO2 bullet-char demo does (a path can be thought like a collision shape that is generated once and used many times)

The component:

The registry:

client side view state:

7

Your path registry implementation can use guava LoadingCache to auto remove the path when there is no reference to a Path object.

LoadingCache<PathInfo, Path> pathCache = CacheBuilder.newBuilder().weakValues().build();
8

Ah, an important requirement: paths can be visualized by the player. That alone is enough to steer (pun intended) towards entities.

In all of my client/server games, there is some system on the server that is managing the movement of the mobs. So each mob already has an object managed by an EntityContainer and each frame I just iterate over the containers objects to get them to update… and then those objects can keep around a certain amount of state as needed (such as next waypoint, path ID, whatever).

…though especially if the navigation will be visualized, some of that state like next waypoint will likely be a component on mob entities.

What kind of level/world do you have? How is your path finding done? By geometry or is there an existing nav graph or something?

9

I am still thinking about this… Just want to understand the concept and test things out. I am getting back to this.

For now, my whole server side steering does not need any additional object. It works only on entity components.

The game world is split between not movable objects (buildings/terrain objects and so on) and movable objects. The reason behind this is that for path finding i only consider the terrain and the fixed objects.
The fixed stuff as well as terrain data is added to a sparse quad-tree. The path finder works by traversing the leafs.

The steering algorithms then have to implement collision avoidance considering all the moving objects as well.