Question
In continuous space (or a space that simulates bein continuous), the possibility of two paths with the exact same distance is negligible. On discreet playing space, however, it’s practically inevitable. Think chess, or grid-based strategy games, where distances are allways integers.
On such circunstances, how does AStar2D decide on wich path to follow? Will it be consistent? Is it possible to force it to use a certain parameter above another?
And, most importantly, is there a way to find every path with the minimal travel distance, should more than one exist?
I beleive it would be possible to force a certain preference by making certain paths have more weights, but to a level that doesn’t matter for actual paths (say, walking counterclockwise has 0.0001 more weight than walking clockwise), but this feels like it could easly lead to unwanted and unforseen behaviour, on top of not solving the main problem of finding all paths with the same distance (and possibly making it impossible to do so).
So, any solution? Or would custom code be necessary for this?
I really hope is the first, I don’t like the idea of having to code breath-first search
I dont think you can get all possible paths, and decide which path to choose. For grid-based pathfinding you can look at AStarGrid2D, which also allows you to set heuristics. You can also write your own compute_cost / estimate_cost- methods
Coding a-star yourself for grids is pretty easy, i have done that for my tactics rpg. If you need help with that just let me know
1 Like
Problem is that AStarGrid2D assumes a suqare grid, no? I am not currently working on the project that would need this tech, but it would defnitely have grids with irregular patterns.
And doing some more reading now, if I understood correctly, by setting heuristics you can set the tiebreaking loic, but it would be a fixed logic and you still wouldn’t be able to get all paths with the same distance, correct?
It would be important to get the paths because, itdealy, the tiebraking logic would be based on the game state. The game would be a board game-like where enemies move in predictable, predefined patterns acording to explicit rules. Idealy, they would be able to follow rules such as “prioritize paths with players in them”, or “avoid players”, etc. In some situations the player should be able to choose the path too.
So it seems a custom algorithim would be necesary after all. A simple breath-first would sufice, so not sure if I would go through the effort of coding A*. Thank you a lot for the offer thou!
A-Star is called a type of ‘best first’ search, but its also a ‘first best’ search, meaning it returns the first search that reaches the goal.
If you want to ensure the shortest path, you need a different algorithm, eg Dikjstra.
Also A* absolutely does not assume a square grid … the search space can be a state space of abstract connected concepts (see the 8-puzzle Astar or GDOAP)… the navagents in Godot will travel on a large variety of connected navgrid topolgy.
1 Like
I always recommend that people new to Godot start with NavigationRegion2D/3D and NavigationAgent2D/3D first, before spinning up their own pathfinding algorithm with A*. Even if they have experience with A* in another platform. Once you learn how to use it, it’s much easier to use and requires only a few lines of code. Plus it has a bunch of things you can tweak to improve your pathfinding in the Inspector.
Yeah i would always advise using Godots navagent and navgrid for pathfinding because its much better than most other versions.
The 8 puzzles was what i called actually a difficult undergrad problem and the goal oriented path planner was a bit easier because the search space was a graph and not a tree. It has nodes like ‘make sword’ connected to ‘forge at blacksmith’ connected to ‘hammer’ etc so the path finder goes for the hammer first etc.
1 Like
Don’t get me wrong, I love a good coded logic puzzle. But if I don’t have to wade into it to solve a problem, I’m happy. It’s crazy that A* is almost 60 years old!
And the navagent already solves pathfinding and the harder problems with navgrids etc
1 Like
Yes i agree, for your use-case a custom algorithm will fit best
1 Like
Thank you for your response
I meant that AStarGrid2D specifically assumed a square grid, I know that AStar2D is capable of other topographies. Have used it on Hexagonal grids myself
Dikjstra does seem more appropriate to what I have in mind, presenting all shortest paths that can then be chosen between, but would only be necessary should I opt for weightened paths, otherwise one might as well use Breath first
Thank you for your reply
NaviagtionRegion2D seems more suited to action games with continuous movement, thou, rather than a board-game like movement within discreet space. Is this not the case?
I fear it might be so not only because naveation itself is way simpler in discreet space, but because the game needs to ensure events that take place upon entering/leaving a node happen at the right time. As in, in an action game, a trigger happening a frame later than it should is not going to cause any significant issues, and movement can be stopped at any point without problem. On a turn-based strategy, however, things need to follow the established rules precisely
Yeah i see, i read fast and saw Astar not ‘AStarGrid2D’.
1 Like