Implement a "dumb" navigation mode for navigation agents as an alternative option

[SysError99]

Describe the project you are working on

A game that requires simple navigation.

Describe the problem or limitation you are having in your project

The newly-implemented navigation server is a very powerful tool that got implemented into both Godot 3 and Godot 4, and it gives a lot of flexibility for making games that require adaptable navigation. However, this new feature is still somewhat difficult to understand, use, and also quite computationally expensive even with modern computers, especially with larger numbers of bodies. In certain cases, users may not expect the level of complexity given by the current implementation, or just wanting a "simple enough" navigator that could be used immediately with simple scenes, or wanting some sort of simple navigation algorithms for games with large number of entities, such as "Vampire Survivors" and similar games.

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

Introduce a new pathfinding algorithm with very simple navigation logic, and doesn't need any pre-plotting mechanisms. Techically, it's not even a pathfinding algorithm since it doesn't even try to calculate optimal path, but rather it uses some sort of simple seek & avoid type of mechanism to reach a desired target. This algorithm automatically avoids anything that is considered obstable such as collision body and other navigation agents. It may or will ignore NavigationObstacles2D/NavigationObstacle3D completely since it's not required for this type of navigation.

The simplest implementation exists in this game called Planet X16 that runs under an 8-bit machine. We could use more work to get it to work a little more accurately. The greatest example exists in GameMaker

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

There are two ways to implement it

• Add a new pathfinding algorithm PathfindingAlgorithm::PATHFINDING_ALGORITHM_SIMPLE as another option, and add a GUI option control for it to be selected. After this, users only need to focus on properly setting up collision elements in the game without worrying about fiddling with navigation layers.
• Introduce a new node type that's used exclusively for this feature. Since this feature only cares about collision bodies, it could be difficult to merge it as part of the main NavigationAgent2D/NavigationAgent3D.

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

No.

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

This is a direct feature addition that may be added as part of the navigation agents that still don't offer any of the virtual methods for GDScript-based pathfinding algorithms yet.

[Calinou]

How does this proposal compare to using the AStar classes?

[SysError99]

It offers both a lot (steeply) more performant and easier to use navigation algorithm since it doesn't even require multiple navigation node type setups especially navigation meshes since it only cares about its target and any "obstacles", which means even with rigidbody it will try to avoid by default. It will not replace AStar algorithm since it's not even pathfinding algorithm (see the video attached in the proposal). This type of navigation algorithm is common to see in games with low navigation complexity and high amount of objects in priority. It's very ideal for most games that don't offer a complex mesh (open area) and/or multitude amounts of nodes.

[timothyqiu]

I like the simplicity & retro-silliness behavior :)

But according to the Planet X16 video, I guess the algorithm only works well with grid-based four/eight direction movement? The GameMaker video did not work well in the end, and the author switched to AStar in the next episode.

[SysError99]

As I stated earlier, the algorithm isn't better at navigation nor is it going to replace AStar. However, it works well enough for most projects that entities don't need to navigate through maze, plus it's a lot easier to use and a lot more performant than AStar in multitude of nodes.

It will work with any type of world since the algorithm isn't relying on the grid (as you can see in the GameMaker's video), but it can be adapted to grid-based systems.

[timothyqiu]

As I stated earlier, the algorithm isn't better at navigation nor is it going to replace AStar.

I mean, the algorithm seems limited to very specific scenario. First, the character should be using grid-based movement. Second, the user should think this kind of retro AI behavior is acceptable.

It will work with any type of world since the algorithm isn't relying on the grid (as you can see in the GameMaker's video)

The video shows that without grid-based movement, it's hard to work correctly for slightly more complex maps.

In the screenshot below, enemies have difficulties reaching the player. Even the enemy from Point 1 can't navigate to Point 2:

[SysError99]

@timothyqiu This is exactly what I was talking about, I stated that it'll not work well with maze types of obstacles (as what the figure already suggested). It works fine with a large blob of obstacles (which is very common in many games. If you only look at this "specific" use case, this proposal will not fix it.

This is only intended for simple games (which are a lot of them that work well with this type of navigation, hence it's integrated with GameMaker in the first place).

[SysError99]

If you look at so many examples of commercial games (commonly, JRPG), you'll see that so many games don't even have maze types of obstacles nor even need the enemies to navigate through mazes until the player reaches them, it's mostly open space, which this proposal works well enough without special setups and learning curve to get it working. It just works. It's a "good enough" tool for quick development and easy to grab and use. If they want the enemy to navigate through maze-level of a complex map, the AStar is also always there. It's not going to replace the previous algorithm by any means.