Best way to find closest target on a large scale

Ok, so making a game which could have up to 100 targeting AI in effect at once and up to 300 different targets, in other words. I need to be using the least performance effecting methods possible if I wish to continue it running smoothly.

I need to know the most Efficient and at least a fairly accurate way to make an AI target the nearest target, and a for the sake of demonstration lets say all the targets are in the same folder in the workspace. This would ideally need to be handled on server since the game is multiplayer.

I know about magnitude checking, however I feel this could get very costly given the scale, however I did consider making the enemies move in packs towards selected targets which is still a running option for me. I also considered raycasting in 4 directions to see if it could find a target hit by the ray. However before I try any of these iā€™m wondering whats the most efficient method you use to handle targeting AI.

3 Likes

If there are a lot of parts needed to be detected, you will have to know how to utilize Region3/GetTouchingParts.


Basically what you do is you do is you get the parts returned from GetTouchingParts or FindPartsInRegion3 that is a specific size, and use Magnitude on the parts that are in the Region3 or Part.


I would recommend using GetTouchingParts, because it is efficient and easier to use.


Here are some variables you would have to consider:

The magnitude to detect an AI is 50 studs
A sphere part is used (named ā€œsphereā€), and welded to the targeting AI, with CanCollide = false
The sphere part and the script would be an immediate descendant to the AI model

The script would look somewhat like this:

local RS = game:GetService("RunService")

local AI = script.Parent
local Part = AI.Sphere -- The sphere size would be 2x the magnitude, so the size would be {100, 100, 100}

Part.Touched:Connect(function() end) -- Add a touch transmitter, so that GetTouchingParts could work

RS.Hearbeat:Connect(function()
    local Parts = Part:GetTouchingParts()
    for i, v in pairs(Parts) do
        if v.Name == "AI" then
            --Code
        end
    end
end)
1 Like

Donā€™t you feel this would start causing problems if this was run on 100 AI every heartbeat and there could potentially be about 300 different targets for the AI in that radius?

Maybe, Iā€™ve never tested it out, but you can always decrease the wait time. My game has 40 + while loops running at at least 20 times per second and it didnā€™t cause any frame drops or anything. Try it, if it lags, simply decrease the increment by utilizing a while loop instead:

while true do
    wait(0.1)
end

Perhaps the following strategy would work:

  • Every 5-10 seconds, create a map of all of the player positions, and separately, a map of all of the AI positions. The positions should fixed to the nearest grid square (5x5 grid)
  • Calculate a match for all the players in those grid squares. Thatā€™ll roughly target well enough that players wont notice and discrepancy.

Having 400 Humanoids is not advisable. Iā€™d recommend if possible using anchored blocks with no physics interactions enabled that you can move instead.

The targets will be models, not humanoids, sorry should have ben more specific. gonna try the grid method rq

Youā€™ll never get up to 100 AI running in one game. You can make a work-around by spawning in more AI as more are killed/destroyed.

Never say never, and I believe it is entirely possible through proper use of resources, distribution of the load between client and server and efficient use of targeting, hence this post.

1 Like

@LuaBearyGood, I like your confidence, but no one has been able to optimize 40+ AI running at once. Constantly checking for the nearest player even if you are checking every 5 or so seconds, will start overloading the server as you duplicate this with 20+ AI. Take Call of Duty Zombies for example. As the rounds get higher, the more zombies are spawned, but there is a cap off. After a total of so and so zombies are spawned, no more zombies will be spawned until 1 or more are killed from the cap off.

Im not talking deep learning ai, im talking, run at the nearest thing to it AI, which is entirely possible and has been demonstrated several times before in games such as zombie rush. Also I in no way intend on actually running searching algorithms on 100 AI, I reckon I could achieve near perfect results only searching with 6 from my current plan.

Also constantly checking for nearest player is an impractical solution, you search for a new target when your attack or when your Current target is eliminated.

I appreciate that it may be hard to give advice given im not giving my full use case of the AI to protect the idea of the project.

Spread the load of calculations across several frames. - A magnitude calculation isnā€™t so ā€œheavyā€ to do, but doing it 100 x 300 times per frame will cause problems.

Are there any reason for ā€˜one targeting AIā€™ to need to update its ā€œnearest targetā€ at a high frequency? - Most likely not, so you can already there further reduce how often to do ā€˜1 x 300ā€™ magnitude calculations.

Are there any relation between ā€˜a targeting AIā€™ and ā€˜a group of targetsā€™? Like an area they are within, so the set of calculations per ā€˜targeting AIā€™ can be reduced even further. - No need to calculate distance to a target that is across the map, in a completely different area out of reach of the ā€˜targeting AIā€™.

2 Likes

Even the simplest AI, down to the bare bones, cannot be duplicated passed 20-30 times without drop of frames/lag. This question has been asked before on the developer forum, ā€œwhether or not there is a way to optimize AI to allow 50+ running at onceā€. The simple answer is, no. In no way will the server will be able to handle that large amount of NPCā€™s running. I may not know the full use case of your AI, but I can tell you that the numbers you want to reach arenā€™t simply possible. You have to use a work-around.