What’s the best way to go about this while still having obstacle avoidance on a dynamic map where players can build? Ideally a 3D solution would be best since building will be 3D but 2D is fine too
Also what the player builds is destructible so potentially NPCs could destroy the obstacles to achieve the desired distance (additional number of seconds necessary to break the obstacle would be factored in)
The player is assumed to go in the most efficient path possible to the NPC
If you have a static map solution please share that too because I have no clue how to go about that either
Edit
I guess theres 2 parts of the solution: evasion and chasing
I know that for non NPC destructible chasing you can just use pathfinding service but for every other aspect idk what to do
I have been working on a tower defense game which does what you are describing: Tower Defense Developmental - Roblox
Currently it is only 2D due to other parts of the game not supporting it. The pathfinding system does work with 3D. It is just a matter of connecting nodes. The first units which spawn automatically will avoid defenses and target economic buildings. Use the command “/spawnunit Tank” for a ranged unit which targets defenses.
What I have done is implemented the A* algorithm and modified it with behaviors and goals by making the movement cost between nodes dynamic and having separate heuristics for each goals which are combined based on the goals of the unit which is getting the path. Instead of finding a path to a predetermined point, it searches for the optimal goal. In your case with evasion this could be a location of low heuristic which would be set based on distance from the player combined with the area around the player having a high movement cost.
Idk if you’re doing A* on a grid but I feel like in my scenario it would be best to have manually placed nodes because of the size of the map and its 3D nature
How would this be combined with destructible objects player can place? Eventually they could place so many that the predefined nodes become innaccessible. Would I have to create new nodes and edges (and potentially get rid of some) (and check accessibility via pathfinding service) each time different objects are added/removed?
Btw do you know how many nodes + density of the graph is reasonable for Roblox?
Also since I have manually placed nodes, do you think its a good idea to precalculate the pathfinding service path for all edges (since its anyways probably going to be necessary when players place mini blockades and such which may require jumping)
Also would this be an accurate weight value for my scenario: (total distance of edge (of Roblox Path of edge)) * (some weight heuristic)
How would this approach solve the problem of where there are obstacles completely blocking the path to get to the player?
Also for evasion, wouldn’t a problem with the approach you mentioned be that along the way to a node (especially when the nodes are not close together) the NPC might get closer to the player when there is a more optimal solution to always keep the NPC farther than X from the player when evading? (Eventually getting trapped in my case is better than getting super close to the player than reaching desired distance)
Edit Just realized what you were probably saying was that objects would have weights with the times needed to destroy them built into them?
So I guess that would probably work out for everything except evasion - I gtg so I’ll just leave my main reply as is w/o edits
The number of nodes does not matter because of the nature of A* as long as you are handling it properly. One map I use is made of 2526 nodes and it handles pretty well. Another is made of 8218 nodes and it is very laggy. Some of the lag is because my system does not check if there are any accessible targets before searching for a path, so a boat that has no targets in the sea will end up searching through all the ocean tiles. In addition, because of my behavior system, the path is calculated twice. The first time to find the best goal and the second to find the best path to it (don’t want heuristics from other goals to have gravity and cause the path to curve.) For another reference, the game has at most 20 units spawned at a time and for the first map (2526 nodes) a typical path is 20 nodes long, possibly considering 500 nodes if there are plenty of obstructions.
Another part to this is setting up the nodes and updating their values. If you calculate the values each time the node is referenced for a path it will be much less efficient. I suggest it be done with a meta table so it is calculated as needed and saved.
Beside all that, it is only a problem if you are trying to calculate the path in one step. In the game Clash of Clans, the units pause for a moment while looking for a new path. That is something I have not does which is why there are lag spikes and large maps. If the algorithm is run in the background over multiple steps, it would be a matter of waiting instead of lag.
I am not sure what you are saying by edges. This solution also does not use the pathfinding service at all.
For the weights, I have a base movement cost of one between nodes which works because it is a flat grid. Yours would be set based on horizontal and vertical distance. The obstruction is a weight which is based on its durability. If the obstruction were impassible then the node should not be considered in the path.
For evasion it would not be a goal to reach a desired distance, rather a tendency to get far away. The NPC is a ball and the player is a mountain. The NPC will roll down the slope of the mountain. It does not have to reach the absolute best spot. Of coarse the NPC will be able to climb the mountain in some situations. How it does this is up to how difficult you want it to be to catch it. The NPC could have a view distance which would make relative lows absolute to it while allowing it to path find around small obstructed areas and potentially get trapped into large obstructed areas.
Put a plateau on top of the mountain and the NPC will not stand idle after it has been trapped; if the areas around the player is an abrupt increase and flat like it did not matter how close once the NPC were within range, it may head toward the player to get on the other side and escape. The abrupt increase would just be so the NPC never willingly enters the area. The way you configure movement costs and heuristics is all up to the behavior you want.
Since my scenario is 3D and not necessarily a grid, I was thinking it might be more convenient to let roblox calculate some of the aspects such as when to jump etc and it would allow me to place much less nodes
I want long range NPCs to try to maintain a distance from the player (although I can just stop the evading once that distance is achieved I guess)
Also I don’t really think I understand how to apply your mountain and ball analogy
Are you saying to do something such as:
Find all the nodes accessible to the NPC within a view distance from the NPC
Travel to the node which has the (total weight)/(distance from npc) minimized where total weight is the integral from NPC position to node position of the player’s “mountain slope” (so not necessarily linear)
Is there a better way to do this (since this checks all nodes within the view distance), or am I completely misinterpreting what you’re saying?
Edit Actually instead of taking the integral and finding the average weight, it might be better to just find the max weight
Sounds good if you want to use less nodes and have pathfinding between them. If you were going to do that you should predetermine the paths between nodes if the path will always be the same.
The analogy is a representation of the heuristic value which will create the behavior that you want. The slope of the mountain could be whatever function you want. Unless you want a behavior from a function it is better to leave it keep it simple and linear. You may want to have the function similar to negative gravity so that there is less pressure compared to movement cost further away allowing the NPC to go toward the player to get around something.
The weight on a node as with A* is a combination of the movement costs from the start node to there and the estimated cost from the node to the goal. There is no need for integrals and averages, just adding movement cost and heuristic. The heuristic is calculated similar to how the moment cost between nodes is, just that there is predetermined goal for this case. Both are proportional to distance.
Yes with the view distance, all nodes in the distance will be checked. You don’t need to get a set of nodes within the range and search through them all. It could be done normally just when getting the movement cost between nodes if it is outside of the range ignore the node like it is one the NPC cannot access. When the NPC decides the path is found is up to you since there is no defined goal it would end up searching through all the nodes and pick the best spot. It sounds like your game has a low density of nodes. I am talking about a small view distance. For example If the map was a hotel the view distance would be a little larger than a room so the NPC could find its way around and out of the room and potentially get trapped at the end of a hallway.
Instead of having a view distance, you could set up a variable for the relative minimum in of the nodes that have been considered so far and compare it to nodes as they are checked ignoring ones that are too high above that minimum. This would end up creating a long path.
The benefit of the view distance path is that is happens in short segments. The player constantly moving will cause the heuristic to change and outdate the path. The long path would end up doing more calculations and have to be redone before it is fulfilled. Maybe if you use are large view distance also have tolerance to the relative minimum.
You could do something where unit the NPC get stuck into an area of low weight it take one node at a time moving to the one with lowest weight. When it does get stuck it could expand the view distance or tolerance from the relative minimum up to a limit until it finds somewhere better.
The A* algorithm does consider all nodes in the path using simple math as needed. The G score is the actual cost which is a sum of movement costs. The movement cost should be precise which could be pre calculated with the length of the path between them when you pre calculate paths between nodes using the pathfinding service.
The heuristic should be no more than an estimation. Normally the heuristic would not influence the path. It is just used to guess the direction and to save on calculations. In the adaption of the algorithm I described, having no defined goal, the heuristic is used to decide when the path is within range of a goal and should stop, a little different for evasion where the path is not stoping at a range from the goal.