Add ability to roll back and manually step navigation state

monitz87 commented 7 months ago

Describe the project you are working on

Top-down roguelite with rollback netcode that uses navigation for enemy pathfinding

Describe the problem or limitation you are having in your project

Currently, the navigation server is only being stepped at the end of the physics step. Rollback netcode relies on being able to load a previous snapshot of the game state and simulate several ticks worth of gameplay within a single frame.

This means that any simulation of past states that involves navigation would always rely on the navigation server's state at the present time, and simulation of in-between ticks from that past state to the current one wouldn't update the navigation's server state as they go either, resulting in inaccurate and unpredictable results.

This is similar in spirit to #2821

Describe the feature / enhancement and how it helps to overcome the problem or limitation

The idea would be to expose a way in the public API for users to:

1) Easily get all state of the navigation server that is relevant for the simulation (probably limiting it per-map is a good idea) 2) Easily set said state on the navigation server 3) Manually step the simulation with a custom delta time

It would be great if abstractions such as NavigationAgent and NavigationObstacle had similar features, such as: 1) A way to force them to update their state to the navigation server (an equivalent of what force_update_transform does for physics nodes) 2) Either a "path history" for NavigationAgent and a way to navigate it (i.e. go back to a previous path and/or a previous position in a specific path) or at least a way to save/load internal state so that you can get reliable results when calling get_next_path_position

This gives users full control of the state of the navigation simulation and would allow rollback-aware pathfinding, as well as other things such as games that play around with time (e.g. rewinding/ff).

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

This is just a conceptual idea of how this would be used in a typical rollback implementation:

# Set somewhere else or just the default map
var map_rid: RID

func _physics_process(delta):
  if _rollback_scheduled():
    _load_state(rollback_tick)
  while _is_rolling_back():
    # ... do past tick simulation
    # ...
    _save_state()
    _step_navigation()

  # ... do current tick simulation
  # ...
  _save_state()
  _step_navigation(delta)

func _save_state():
  # ... save state of all participating nodes
  # ...
  navigation_server_state[current_tick] = NavigationServer2D.get_internal_state(map_rid) # or something like this

func _load_state(tick: int):
  # ... load state of all participating nodes
  # ...
  var navigation_server_state := navigation_server_state[tick]
  NavigationServer2D.set_internal_state(map_rid, navigation_server_state) # or something like this

func _step_navigation(delta: float):
  NavigationServer2D.step_map(map_rid, delta) # or something like this

If this enhancement will not be used often, can it be worked around with a few lines of script?

Only workarounds I can think of are:

Forgoing built-in navigation and implementing your own, which I'm quite sure can't be done in a few lines
GDExtension or rolling out my own version of the engine (which is what I'm currently doing, but of course this is not a very good long term solution and it only helps me)

Is there a reason why this should be core and not an add-on in the asset library?

NavigationServer is as core as can be and while I can imagine an add-on that reimplements rollback-aware navigation, that would defeat the purpose of having a NavigationServer in the first place and I imagine it would be way less performant.

smix8 commented 7 months ago

For avoidance this is basically part of proposal https://github.com/godotengine/godot-proposals/issues/8939.

I think most functions are already available on the API to do this manually. At least I remember you can override the position and velocity state of an agent entirely in the simulation, but you can not do manual steps.

The NavigationServer does not track anything pathfinding related, it only holds the navmesh geometry. So every time an agent or user queries a path they are fully responsible for the book-keeping of the path.

smix8 commented 4 months ago

After tinkering with this some more:

Avoidance process mode to control the avoidance steps will be added (frame / physics / manual delta)
Missing API functions to get and set all relevant agent and obstacle properties will be added.

So games that need this for e.g. roll back can do this but they need to keep track of their objects and states manually.

What will not be added is an "official" snapshot feature as there are too many caveats. If you build such a system for just a specific project you can manage all the caveats because you are in full control of what you are doing, deleting, reshuffling, updating. An "official" implementation would need to deal with the abyss, long-term.

monitz87 commented 4 months ago

Missing API functions to get and set all relevant obstacle properties will be added.

Would this include being able to get/set the internal path list (and current path index) of NavigationAgents?

smix8 commented 4 months ago

Would this include being able to get/set the internal path list (and current path index) of NavigationAgents?

Yes that is planned that you have a function to set a path array manually on the agent node. You can already get both path and index.

godotengine / godot-proposals