For the sake of simplifying this discussion lets say I’m developing a tower defense-like game. Players maze how they’d like - so I’m always dynamically changing navmesh. As the minions navigate the maze I want certain towers to always attack the lead unit. Now this is where I’m getting hung up - if the minions traversing the maze were all the same speed this would be easy but they are of varying speeds.
Question: How do I keep track of who’s in first to target if it can change after they enter my “towers” collision range? Thanks in advance
The only thing I can think of is to get nav path information from the actors and calculate who is furthest along somehow? I’m not sure how to do that. Also sounds bad for performance if i have 100s of actors
for each (tower)
get (potential targets within radius)
for each (target)
calculate the distance to the objective/eggs/power-cores the target is going towards
target the target with the shortest distance
you, or a given tower, cannot readily know if a target has changed course, accelerated, decelerated. Luckily sphere-traces are just distance-traces and are decently-cheap, so doing many of them might not be awful.
Granted, I’m not always the best at algorithms, but I cannot see how a tower would know whom to target over time w/checking when it’s ready-to-fire. It, nominally wouldn’t be keeping track of the board so it couldn’t know what the new state is since it last took a shot. That would require each tower to maintain a map of the board, blegh. Better to just-check on the limited number of targets, winnowed down by distance-checks.
You could even go a bit more abstract and make sections/sectors of the board and then have the targets update which sector they are in when they move. Vs checking the entire target-set, you could winnow it down by sectors, then start with that more-limited list. Same rational as virtual-textures, or streaming-assets; chunk it up, make chapters, then books, then volumes, then libraries, etc, then start-looking at whatever level if index you want, as is most advantageous.
Problem with minion-distance-to-destination-point is, depending on the maze construction, it may not be 1 to 1 with who’s furthest through the maze. Also having minions move into the tower range, out and back in creates more problems.
The only way I can think of is your second point - scrap the navmesh, cut up map into grid squares, create a master dataset of each grid tile, on tick generate pathing based on tower placement, and like you said use minion tile overlapping to determine whose furtherest along the path.
If I can pull that off - then its as easy as saying “Is the minion in range? is he tagged with 1st position flag?”
Would calculating routes this way be really bad for performance if im sending 100s of units?
As for your solution, combine it with mine vis-a-vis sectors. In your case, each critter registers itself with whatever tile it’s currently on. Each tile keeps track of the critters registered to it, and each tower only check a certain set of tiles, recorded when you place the tower. That way the tower knows only-the-area it can fire upon to search, and each tile in the area knows what critters are there. Therefor each tower OUGHT to only look-through and potentially fire upon whatever critter you then decide to shoot at, based on distance, whatever. Point is you won’t have to search through the entire critter-set, per-tower.
Keep it light, likely not. Extend the extra-levels-of-organization/granularity to the critters themselves, maybe make squads and work on squad-leaders first, see if they are in-range, where they are on the path, etc then check the critters in the closest-squad. C++ would certainly be better vs BPs here but w/modern machines IMHO would be do-able in BPs…
I would imagine that as the game progresses and is mazed-out, the game itself would keep track of ‘the path(s)’ used by the critters vs a free-form navmesh each critter has to calc for itself?? Critters could then just-check the path they are on and all the distance calcs, and whatnot could descend from there?
BTW, I loved Defense Grid, so I know where you are going here…
An alternative: make a grid that covers the entire maze and use it to keep track of the pawns. Have each tower know when a pawn is inside a cluster (group of nodes) around it, much like the sector idea above, so that it can activate and search closest target to the node furthest node of the main path in the cluster.
A simple BFS could be enough to find shortest path and use it for priority for the towers so no need to trace or nav mesh.
It basically turns it all into managing an array, something that I assume will help with performance if 100s of pawns are to be running around.
