I don’t know what algorithm the person in the video is using, but yes, it looks cool haha
Like I said, you can’t use a Dijkstra’s or A* normally to work for a game where the terrain can change, since you’d need to recalculate the shortest path graphs once new nodes are added in. You need to find either variations of these algorithms that can work with dynamically changing terrain (when a node is added/removed, small or simple calculations are done to update graphs) or entirely new algorithms based on that fact that terrain is dynamic.
This stack exchange post is interesting:
Anyways, under all circumstances, you should try to do some research (or if you can, take a course) on graph theory or advanced algorithms. At that point, you’ll be a lot better equipped to understand what’s going on with A*, Dijkstra’s or any of their variations. Learning to program (basically if you want to create anything as complex as a digging game) is also a must, my man.
You always mention digging. This let me think you want the NPC move through the ground (by digging). This would mean you need path finding that consider digging.
Here you say you say you want path finding over the ground (without digging). This is more the classic path finding.
You want dynamically modified ground (by the player or whoever). This means the path finding needs to consider dynamically changing ground.
These are three different requirements for pathfinding. Yes, they can be combined (an NPC that plans paths to the player that include digging while the terrain gets manipulated too).
So the question:
should the NPC dig too?
should the NPC create blocks too (e.g. to reach an upper floor)?
should the NPC always follow the shortest path (requires updating the path at each frame = eats performance).
In general You have two phases:
Pathfinding
Pathfollowing
Pathfinding means the NPC “plans” the next steps. This can be a single step or a sequence of steps (path). It is like you looking at a map and try to find out what direction to go first.
Pathfollowing means the NPC performs a single step of the (preciously calculated) path. This can have two results:
the step can be performed (so you can remove it from path)
the step can’t be performed (means the path is invalid) - in this case the npc needs to do path finding again.
You might have noticed the npc does not need a complete path. The minimum path is the next step. He can plan after a step again. Paths can be or can become invalid. This is as paths (plans) are separate entity. When the based terrain changes the path might not match anymore (the path was created based on parts of the terrain). When a path is invalid it should be recalculated.
“Shortest path” is ambiguous. This can be shortest in distance or shortest in time (or other aspects). You should mention what you mean especially as a digging npc can follow the shortest path without much planing ;).
1.should the NPC dig too?Some npc’s dig some not.
2.should the NPC create blocks too?
The npc’s should create blocks to reach the upper floor.
3. should the NPC always follow the shortest path?
Yes the npc’s should follow the shortest path.
What i mean by the shortest path is the shortest in distance for the npc.
When that is your requirement you do not even need much path finding.
Assumption: The shortest path is a straight line to the target.
As the NPC can always follow the straight line (walking, digging, building) the next step is always the cube towards the target. The decision what to do depends on the ground to reach the next cube. It is either turning, walking, digging, or building.
The NPC will never go around obstacles as there are no obstacles for the NPC.
The above thoughts are only valid for npcs that can perform all of these operations.
NPCs with a subset of operations e.g. walk only. They will discover obstacles. A path finding like A* can help. The NPC can follow the path until it discovers an obstacle or the target changes (because the player moved). As posted earlier, the NPC needs to perform pathfinding again (path finding is not path following!). As path finding eats processing time and/or memory it should be performed as less as possible.
To answer your question yes you can use Dijkstra. Be aware any Path finding algorithm will produce a path that is valid at the moment of creation. Whenever the situation changes the path might be invalid or another (yet unkown) path can be shorter.
You can even apply Dijkstra to digging. You need to define the costs of digging and it can be part of your path finding.
I think digging is fine. You need to consider “undigged” nodes. Usually you would not include them into your node graph. With digging you do. Regardless of that digging (as well as any step the NPC takes) will consume time. As mentioned earlier a path is most valid at the time of creation.
I think you are right regarding the size of the graph as it will be much larger than without diggable nodes. The same belongs to building nodes as they add to the graph too.
The important issue is - how long does it take to create the nodes graph (time) and how large is that graph (memory usage).
It is easier to use the camera actuator for pathfinding in digging videogames.I will use that.It is very useful.I know it has some limitations but it works for the most part.