Effective Ai Targetting Code

ID:2142439
 
Sep 2 2016, 6:51 pm
Code:
            Targeting()
                var/list/l=orange(8,src)
                src.target=null
                for(var/atom/movable/A in l)
                    if(src.TargetECheck(A))
                        src.target=A
                        break



Problem description:

Basically AI code is causing lots of cpu, I'm pretty sure its cuz of the looking thru the view/range. The reason I have it looking for a movable atom is cause they are able to target/attack objs aswell. When it comes to this type of code do you know bypasses or alternatives.

Also I would like to note I originally had it loop thru view() which was much worse, and I remember a recent post where kaiochao was mentioning view has to look for visibility etc, so I was like maybe range is more efficient. I just thought this was very counterintuitive since one would expect range to pick up more objects which in return will create a longer list to loop. Please share any ideas.

Sep 2 2016, 7:01 pm (Edited on Sep 2 2016, 7:10 pm)
A few questions:

How often are you calling this code?

How much is "lots of CPU?"

How many mobs are using this function at once?


Just because it's an intense function doesn't mean the optimization needs to happen that function itself. Sometimes, it's better to leave the function well enough alone and find other methods of optimizing simply by calling the function less often, or maintaining data that eliminates the need for calling the function all the time.

One initial pointer for optimization though, is this:

atom/movable
    var/targetable = 0

mob
    targetable = 1

<dm>
for(var/atom/movable/A in l)
    if(A.targetable&&TargetECheck(A))


Not every movable atom needs to be targetable. Simply defining a variable to prevent TargetECheck() will prevent a lot of proc call overhead before finding a worthy target. That's a very simple optimization.

Another, higher effort optimization is investigating a quadtree rather than looping through view. Track the movements of all targetable atoms and maintain their position in a quadtree. Find the smallest tree node that the AI's range covers and then loop through all targetable atoms in that quadtree's tracked objects list and check targetability manually. This will reduce quite a lot of list generation and manipulation, which is the source of the slowness.

I have no good advice as far as building quadtrees in DM. I've done it a few times, but you will really want to understand the theory yourself before you tackle such a project. Read up on quadtrees and Binary Space Partitioning.
Sep 2 2016, 7:05 pm
Give it a cooldown so it isn't called too often. Make sure it's not a constant delay so not all AI call this in the same tick. The key here is that some CPU-heavy procedures don't need to be called every tick, so it's best to spread out their calls over time.

Also, locate() in list is faster than a for() list loop. That might help if you have specific types to look for or prioritize.
Sep 2 2016, 7:10 pm
It gets called like every second, by like 30-40 npcs. was causing a slight spike every few seconds. What I manage to do was use viewers instead of view(), and if they found no mob target then can search for objects, and I had I loop thru a list of potential objects it could be and check to see if it was the right distance.
            Targeting()
                var/list/l=viewers(8,src)
                src.target=null
                for(var/mob/A in l)
                    if(src.TargetECheck(A))
                        src.target=A
                        break
                if(target==null)
                    var/list/objects=Turrets+Bases
                    for(var/obj/O in objects)
                        if(src.TargetECheck(O)&&z == O.z && abs(O.x - x) <= 8 && abs(O.y - y) <= 8)
                            target=O
                            break

The lag spike has been fixed, but I wanted some feedback on this cause I've ran into this issue before and was wondering what kind of solution you guys have came up with. It seems like if you just put all the mobs in a list and loop thru them all and see if they are close, it would be much more effective than using view(). I just wonder to what size list will it start to become uneffective.
Sep 2 2016, 7:16 pm
In response to Fat Albert
Well, you could always try this:
var list/nearby = orange(8, src) & (AllMobs + AllTurrets + AllBases)

I'm not sure if it would be any faster, but you'll probably end up looping through a much smaller list; `nearby` contains only mobs, turrets, and bases within 8 tiles of src. No turfs, no particles, no projectiles, etc.
Sep 2 2016, 7:17 pm (Edited on Sep 2 2016, 7:23 pm)
was causing a slight spike every few seconds.

How big of a spike are we talking? Quantitative, please.

It seems like if you just put all the mobs in a list and loop thru them all and see if they are close, it would be much more effective than using view(). I just wonder to what size list will it start to become uneffective.

That's the basic idea behind a quadtree. A quadtree divides space into logarithmically smaller segments and tracks information about the segments as a whole:



The idea is that you can treat each node of a quadtree as having information that describes the whole area it encapsulates. BSP as a whole is a discipline that is widely used in speeding up image processing, rendering, and artificial intelligence.

The basic idea is that that Node 0 holds a list of every targetable object on the entire Z-layer. Nodes 1-4 hold a list of every targetable object in their specific 1/4th of the map. Every subnode of nodes 1-4 holds a list of every targetable object in their specific 1/4th of that 1/4th of the map, and so on until you get to your minimum subdivision.

If you can figure out the maximal area that a mob is interested in investigating, you can reduce the number of nodes that you have to investigate and therefore the number of objects that you have to loop through. Meanwhile, you gain the advantage of having all of that data on what objects are where on hand and not having to rebuild the lists of nearby objects every time an NPC wants to find a new target. Since you already have them on hand, it's SIGNIFICANTLY faster to just look at the existing lists than to build new ones.

You follow?

The thing that makes Quadtrees difficult to implement is that you HAVE to maintain these lists, making movement and basic housekeeping slow your game down throughout its entire lifetime. The tradeoff for this is making AI much more scalable and overall the entire game faster. There are a few problems that arise when you use quadtrees though:

1) It will break automatic garbage collection if you don't maintain the lists properly.

2) You can't move things by setting their loc manually, because the movement will not be tracked properly and the quadtree's data structures will fall out of alignment. (This is yet another reason why I incessantly insist no one should ever set loc or step_x/step_y variables manually!)

3) You introduce worst-case scenarios where edge cases can induce much larger searches than should reasonably be necessary with a naive solution.
Sep 2 2016, 8:01 pm
Thanks Kaio, Ill try that out. And Ter that's a great concept, I had to read it over a dozen times to get a full grasp of it. Now my question is this best done with multiarrays or I guess just create a specially design class with list variables.
Sep 2 2016, 8:29 pm
Best with datums. multi dimensional arrays are slow and inflexible.
Sep 2 2016, 8:29 pm
Also the lag spike was very subtle, for a split second every few seconds. Just from my own experience other lag problems can stack on it, so I just want to eliminate any issues like this, which I have. Also Kaiochao, your above code wouldn't work for me cause all players are stored in an associative list.
Sep 2 2016, 8:32 pm (Edited on Sep 2 2016, 8:52 pm)
Kaio but I was able to limit it to one loop from your idea.
                var/list/l=viewers(8,src) + (Turrets+Bases)
                for(var/atom/movable/A in l)
                    if(src.TargetECheck(A))
                        if(isobj(A))
                            if(z == A.z && abs(A.x - x) <= 8 && abs(A.y - y) <= 8)
                            else return
                        src.target=A
                        break
Sep 3 2016, 8:43 pm
I agree with much of the above but what has been posted has been fairly high level discussion, which may or may not be appropriate for your code. But what hasn't been touched on here is what your scheduling system or process loop looks like, using proper scheduling can make a HUGE difference.

It may be that this function is getting grouped together and called at nearly the same time, which is causing tick overruns. Tick overruns are the primary source of 'lag', even with code that averaged out over time wouldn't be causing any lag at all!

Now I don't want to say this will solve your problem without any more information, but it may help if you use
Targeting()
    set waitfor = 0 //YMMV on this, since I don't know how you're queuing up your code to know if this is blocking
    while(world.tick_usage > 80) //80 is arbitrary, but some value less than but near to 100 is ideal
        sleep(world.tick_lag) //Sleep just until the next tick begins
    otherstuff


The basics of this code logic is that if you're calling all of the targeting functions in the same tick it will cause a lag spike, but by doing this it will at least somewhat even out the Targeting() calls. Note: this is NOT an ideal fix, as a process loop/scheduling system that is calling Targeting() would be a better place to hold the if(world.tick_usage) sleep(world.tick_lag) between calls to Targeting().
Sep 3 2016, 11:25 pm
Thx for the input, ill be using that for future projects