Additional project examples

[skison]

Hey there! I was recently testing out the WIP Godot 4 compatible version of DijkstraMap, trying to fix up some of the outdated GDScript, and as part of that effort I spent some time looking through the 3 project examples included here. I think they all do a good job for what they are;

• The visualization demo immediately lets newcomers see the fundamentals of the library, how it is used to calculate shortest paths & directions, and it has a nice visual aspect to it. It's great that it is included in the addons dir so Asset Store users have access to it as well.
• The turn based example applies DijkstraMap in a meaningful way to show how one could use it in a turn-based strategy game, a common use case for pathfinding.
• The other project example demonstrates some of the efficiency of DijkstraMap's implementation, that you can easily duplicate the graph's points and use different parameters to change the results of pathfinding on the same graph, and shows how you don't necessarily need individual graphs for each unit depending on the use case.

As nice as these examples are, I think there could be some value in creating additional ones to show more of DijkstraMap's aspects and practical applications, like:

• Its performance compared to Godot's built-in AStar class for the same operations, like finding the shortest path to an endpoint. I don't know how Godot 4's AStar nodes work internally, whether it is capable of efficiently caching paths like DijkstraMap does, but it would be interesting to see how long it takes to find X amount of paths on a large grid with either system. Maybe it's about the same? Who knows...
• How it can be used in a game where each unit needs its own pathfinding performed on the same terrain. The existing project example works with only 2 distinct DijsktraMaps, each one shared among 4 units of the same type, but the problem here is that they all share the same end goals. In many games with AI operations, each one will need to find a path to a unique endpoint separate from other units.

I would propose the addition of two new example projects to the repository (which I would be interested in developing in the Godot 4 branch):

1. A* Maze Comparison - Implement a procedural maze algorithm to fill in a grid with a maze, potentially with the option to change the bounds of the TileMap (either a number input or a dropdown with several dimension selections). Then both AStar and DijkstraMap can be applied (and maybe with the option to switch between the 'standard' point/connection methods or the 'shortcut' ones, i.e. AStarGrid2D and DijkstraMap.add_square_grid). Then finally, the path from the start to the end of the maze could be calculated for each, or, a random set of X points in the maze could be generated and paths calculated for each one. The computation time for each step would be calculated and displayed so users could see the real performance differences of each.
2. Patrolling Units Demo - Build a demo with a number of different units whose AIs make them patrol back and forth along Path2Ds defined in the editor. Each unit would need to have its own recalculate() calls because each one would be starting at and going to different positions than the others. This is probably a good use case for the proposed #98 Remote feature, but it can be implemented without it until then. It would be nice to implement it such that the units are as loosely coupled from the map as possible while still sharing a 'base' DijkstraMap for its points. Ideally, the user would be able to select tiles to draw with, which would then invalidate the existing paths for each unit and force recalculation. Some caching strategy could be used to reduce the total amount of recalculations needed when the map changes or a point is reached.

Are there any concerns about the scope(s) of these demo types, or whether they should be included in the repo? If it all sounds good, I could start working on them within the next week!

[astrale-sharp]

Hey there :) you're on a roll! :D

As long as the new examples are properly documented, clean looking and not all included in the addons (just the visualization demo), I don't see a reason why not!

Although I'm unsure you could show performance difference in a demo and if it's interesting.

The read me would need to be updated as well in order to direct people to the example !

Finally, the main scene could show a basic menu directing to each of the example!

[skison]

Great, then I'll get to work!

I agree that there are some uncertainties to how effectively any performance comparisons can be made, but at the very least it should still be a helpful reference for those who want to see the implementation differences between DijsktraMap and AStar. And I'm sure we can make the demos interesting!

I like the idea of making a main scene as a navigation to the other demos, will do!

[astrale-sharp]

Maybe let's just do those one by one, easier to review and the review will probably be useful for the other demos as well Plus, better one good demo than two medium!