Now ChatGPT and Gemini recommended me to use quad tree, but recently it switched to use spatial partitioning and someone tell me to use an event based approach and maybe another approach off of Suphi Kaner where you would raycast a ray at a ray or something and get the distance to get into a tower radius and left tower radius, I can’t implement directly but can get an idea off of it and there an api in bezier path that let me calculate position based off of “t” and I just need to increment it and checking if it in the radius of the tower, but I fear it not precised enough, and I have to do it for every enemy when it gets in the “t” or not. But still I haven’t found any that performance enough.
I have tried quadtree able to get some average there and here still don’t know if it is good enough, it also seems like I am checking unnecessary cells that isn’t overlap by the path itself, and I’m thinking if there is a way I can avoid this. Still, what is the best you would recommend for me to do it?
TL;DR: Detector where we grab enemies in range of tower (most efficient way, runs every frame)
I need it for tower detection, says there an amount of enemies on the map and a tower with a range define by radius instead of checking through every enemy to check if its position is in the radius I would use spatial query or data structure I don’t really know what it called at this point anymore so that I could achieve O(log n) time complexity to reduce the amounts of time to check for every enemy.
For spatial partitioning, I check every cell around the hashed position correlate to the index of the cell of the tower and see if the cell fit in the radius, then loops through in each cell for each enemy and compare position.
For quadtree I start at the root or the most top node and make my way down till the nodes either doesn’t split anymore and in radius range and in each node I loop through with every enemy to compare the position based on the radius.
I’m so sorry if my post above was too confusing and yes that what I want “detector where we grab enemies in range of tower” like you say, never thought I could say it like that easier
okay, sorry for the late reply, but why don’t you just loop through the enemies, and put the ones that are in range, inside a table. then you have a table of enemies that are in range. thats quite easy. if you dont want that, you can do :GetPartsInBoundsRadius(TowerPosition, Range)
im not sure what the most efficient way of doing this is, you can test both to find out
Thanks for the suggestion, so I hope I am seeing your vision right, so I loop through every enemy and check if its position is in radius of the tower range? Right? I ditched the part where I would put it in a table again because I don’t quite know what to do with it when I can interact with the enemy directly. And for GetPartsInBoundsRadius I did use it one but deemed it not performance enough, and I only have data to work with and not a physical instance on the server. Still, thanks for bringing it up.
If you don’t have physical instances then thats much better for looping through them. What I am thinking, is that you loop through the positions you have, and put any enemies that are in range, inside a table. You do that so you can then choose which enemy you want to attack, instead of whatever enemy the script sees is in range first. So from that table, you can loop again to see which one is closer, or you can see which one has more health, or which one is closer to the end of the map. So you get a lot more control over which enemy the tower attacks.
The enemy isn’t stationary in my situation, so I have to update the table every frame and not all enemies are ordered or sorted since all of them could be having different speed which result in me needing to loop through all the enemy positions in the first place. And also kinda off-topic, but it’s getting late so I have to go, thanks for going through this.
Hello. glad to hear you are using my module. if you are interested i have another module in my github called “HashOctree”. its pretty much an optimized octree performance and memory wise. you can use it if you are interested
Check distance between node and enemy every let’s say 1/4 of second before it will detect something, when it detects something, you stop listening until enemy’s health is below 0 or enemy’s range is bigger than tower’s radius (you can check it every 1 second or so to reduce stress) and repeat
Because since each enemy could have different speed which result in different position every frame so that’s why the table is changing every frame, it is better if I directly deal with the position data itself instead of storing it in another table that holds enemies that are in range of the tower because the next frame either any of the enemy in the table could either have gone out of range, but I don’t know which one, so I have to check every one. And I can’t check every 1/10 of a second or unless there is something I haven’t thought of, but the way I check if an enemy is in range is by comparing position of the enemy and the tower and get the magnitude and enemy position must be updated every frame for accuracy.
That’s the best I could explain, am sorry if there is any confusion.
Could you explain more? I’m sorry if I don’t understand, here is the part that confuse me: Check distance between next node (Since I use BezierPath module, so I’ll use the node that use for creating the Path) and enemy every .25 second and before the tower detect something, which how or what it uses to detect?
Soo, you have parts on server that are nodes, i’m sure you have something like that, you lerp enemies positions between nodes, get node’s position, get percent of lerp, and determine distance based on it
I am so sorry if it is starting to annoy you, but I still don’t understand, it fines if you don’t want to continue the conversation anymore but it best if I can have an example code of how your system would work. Here is my current code naive version and all it does is get all enemies in the tower range.
Sadly i tried this aproach years ago and i can’t find you code, but main idea is to have node parts that enemy goes to, those nodes have id like 1,2,3… when enemy reaches node you lerp enemy’s position to next one, you give this time to your tower, and you only calculate distance to nodes instead of invidual enemies, soo you can store it all the time, at the end you compare percentage of enemy to node and use math to calculate distance from it
