Navigation, Astar, and Pathfinding for a 3D Turned Based Strategy Game

This is a READ-ONLY snapshot of the Godot Community Forums when TwistedTwigleg was the owner, which is hosted for archival reasons only. The current Godot Community Forums can be found here.

Some links may point to external websites, including the current Godot Community Forums. These websites are not associated with TwistedTwigleg.

Navigation, Astar, and Pathfinding for a 3D Turned Based Strategy Game

SalamiSam

There didn't seem to be a discussion on this topic, and I am very interested in it at the moment, so I thought I would create one.

Is anyone else attempting something similar?

I've been trying to create a 3D Turned Based Strategy game for the last few days. I have been realizing the major limitations with Navigation nodes in 3D. It has already been shown by many Godot users how easy it is to dynamically change the navigation area in 2D with the use of TileMaps. In 3D however, even with a GridMap, there doesn't seem to be a straight-forward way to dynamically change the navigation area when obstacles change position, since NavigationMeshes can only be baked before runtime. In a turned based strategy, you don't want to display a unit's movement path through another unit; the player will think the unit can actually reach it's destination instead of stopping when they collide.

I've been trying to program a work-around by manually altering the PoolVector3Array path that the Navigation node gives me, using ray casting. So far, this has been pretty complicated, buggy, and there seems to be ALOT of overhead, killing the frame rate occasionally. I'm sure it's possible, but I can't get it working properly so far.

I want the maps to be gridless and unit movement to behave similar to Divinity: Original Sin 2's combat. I'm thinking I might try using Astar with a speudo grid in the underlying implementation: having Astar essentially store a grid of verticies for pathfinding, while not restricting the start and end positions of the path.

TwistedTwigleg

I tried using path finding for a tower defense prototype in the past, shortly after Godot 3.0 was released. I dropped the navigation and instead used grid-based navigation instead, which for the tower defense prototype worked fairly well.

Hopefully navigation will get significantly better in 3D with Godot 4.0. There is a new NavigationServer that looks rather promising.

SalamiSam

I love tower defense games! Very cool! I will have to check out the NavigationServer. It's nice to see how active the devs are on the engine.

Gary_HCG

This guy may have something that works for you. The basics create an A* map on a gridmap, which looks to be something you could dynamically change by re-running the build routine when you change your map thus updating the movement paths/areas. It is based on a gridmap, but this could also be hidden or perhaps just an "underlayment" to your world.

Gary_HCG

I took the Youtube code, added in a couple of routines so now you can left click to add a navigatable point, right click to remove it and center click to move the avatar to the click location. As long as you clear the "all points" list before running reloading (when you add or remove a nav point) it the navigation works exactly as expected. I also tweaked it to avoid diagonal movements. So, this essentially allows for dynamic creation of 3D navi meshes. The only downside to your original request is that there is an underlying gridmap with this option but you already discussed doing an underlying grid so this just might work for you.

SalamiSam

Gary_HCG I love that guy's stuff! Yeah, atm, my implementation is similar, using a gridmap. It works pretty well! But yeah, like you said, I'd like a gridless system. I'm working on something with astar, dynamically creating points within a unit's move range based on the collisionshapes within the range. It's pretty slow and incomplete so far. After the semester is over, I'm hoping to get it finished then look into making it a c++ module.