ID:1192822
 
I have a very simple wandering algorithm for mobs to only walk to open, non-dense spaces. It's a smarter way for AI's to move, instead of bumping against walls and whatnot.
wander()
set background = 1
var/list/spots = oview(3,src)
for(var/turf/t in spots)
if(t.density) spots -= t
var/turf/spot = pick(spots)
walk_to(src, spot, 0, 0, 2)

My current AI's are very inefficient with resources. I'm currently developing a zombie survival game, and as you can imagine, there will be many zombies in the world, wandering around. I already have functions handling a check whether or not a player is near, deactivating the AI's wander() function until a player is close, as to conserve resources.

The problem lies in the fact that even with only 50 AI's running and making an attempt to attack my character, the game CPU far exceeds 100, peaking at about 210.

I've narrowed down the problem functions to this wander() proc. I know that the constant checking of oview() along with omitting the dense turfs under the for() loop is causing the massive latency. I also know that this method is probably the most inefficient method of sorting through lists, but I honestly don't know any others.

What could be done to improve this code here?
1. "set background" isn't necessary (I have yet to figure out when it actually would be, other than to prevent runtime errors).

2. You shouldn't have to be calling wander() every tick, that would be pretty wasteful.

3. Are there really 50 enemies all chasing and attacking you all at once? Or maybe, there are 50 in the world but only a few in range at a time? They shouldn't be doing anything if a player can't see them, somewhat.
1. I was never sure exactly what set background really does optimally for the game.

2. I'm not calling it every tick. If I were doing that, then there wouldn't be any time for the AI to get to it's target location, it would just crash immediately.

3. I'm talking about all 50 AI's attacking me at once. As I said above, I've already optimized the actual AI loop to account for whether the player is close enough to see the mob or not.

Like I said, the problem I believe lies in the constant calls by the for() loop, but I know no other ways of sorting through lists any faster.
So when is wander() called, exactly?
AI_Init()
zombie_count++
sleep(rand(0,15)) //Delays initialization to offset zombie movement times.
while(src) //Beginning AI loop
set background = 1 //Obviously useless set background.
while(!AI_ACTIVE) sleep(10) //Debugging line to freely activate/deactivate AI's at runtime.
var/active/player/trgt = lookAround() //lookAround() function finds a valid (not dead) player target within 5 spaces.
if(trgt) //If there's a player close by
setTarget(trgt) //Sets the zombies target to the player.
attack(target) //Attacks/Moves to the player.
else
wander() //Otherwise wander around.
sleep(20)

However since I've obviously made some mistake, I'll add my attack() code as well, seeing as I get a great lag spike from that function.
attack(var/active/player/p)
while(p in oview(5, src))
walk_to(src, p, 0, 0, 2)
if(p.dead) return //If the player's dead, there's no point in attacking it. This is actually meant to keep other zombies from mindlessly attacking your dead body if they were chasing you while you died.
if(bounds_dist(src,p) <= 15) //Checks whether or not the player is close enough.
if(rand(1,100) > 30) //Chance to hit
p.setHealth(DAMAGE, 10)
p << "Zombie attacked you! You have [p.health] left!" //Debugging text
else
p << "Zombie missed!"
sleep(20)
else sleep(10)
var/lkp = p.loc //If the player steps out of the oview() range, move to his last known position to see whether the AI can find him again.
walk_to(src, lkp, 0, 0, 2)
sleep(20)

Also it's important to note that I am using pixel movement in my project. Oddly enough, I've discovered that the wander() proc only runs my CPU at about 20%. That's if zombies aren't attacking me and are just walking around. The lag comes whenever a large group targets and attacks me so I feel like I had made an incorrect assumption about wander(), however I would still like to be able to optimize that code as well, seeing as though 20% is still pretty high for that being the ONLY thing going on.
One comment I would have is that if you are wandering about, and have not reached your destination turf, you probably don't want to call wander() again on the next iteration of your AI loop, as you have a destination and so, don't really need to go picking another one.
That was the original reason that I had included the sleep(20) function, to give ample time for the zombie to reach its destination. As far as I understand, walk_to()'s don't exactly stack up on each other unless you're calling one every tick. There's where one would expect to find latency and crashes.
It's more it cancels and re-does it. The question more however is about un-necessarily re-calculating your destination turf again, and so, triggering that loop. It would seem better to store that destination turf, and check you're within it's bounds, before deciding to pick a new one.
walk_to, having A* pathfinding, costs relatively more than walk_towards, but you might not be able to sacrifice the pathfinding.

Also, Nadrew showed me this slight optimization: Instead of using oview, you can use ohearers. Since oview returns atoms, it's a much larger list than what ohearers gives you (only mobs).
ohearers, I know about that variable, but I've never bothered to use it. That's convenient. I didn't know that it only returned mobs though (However I haven't really looked at it in a while, so that might be why.)

@Stephen: I thought about doing that, but I was unsure whether more checks and calls would only make it slower. I'll try it out and see the difference, but it would have to be quite substantial seeing the amount of lag already present.

Also, what ideas do you have about the attack() proc? That seems to be the main source of the latency.
Well, checking if you're within the bounds of a turf you've got stored is cheap, cheaper definitely than iterating over 48 turfs at worst and deciding which ones are relevant to use, picking one and then walking to it, cancelling any existing walk.
Well, using walk_towards() in wander() instead of walk_to() is exponentially more efficient. Unfortunately, my attack() proc still requires the path finding algorithm found in walk_to. I've also taken the liberty of using walk(src,0) before each call to any walk functions, so it will successfully halt movement before selecting a new destination turf.

I'm still having trouble with my attack() proc however.
active/zombie/proc
attack(var/active/player/p)
if(p == null || p.dead)
setTarget(null)
stop() //Wrapper function for walk(src,0). I like my wrappers.
return
if(dist(p) <= 160) //dist(p) Wrapper for bounds_dist(src,p)
if(dist(p) <= 15) //If it's close enough to strike
if(rand(0,100) > 30) //Roll chance to hit
p.setHealth(DAMAGE, 10) //A complicated way of saying, p.health -= 10
p << "Zombie attacked you! You have [p.health] health left!!"
else
p << "Zombie missed!"
else
stop()
walk_to(src, p, 0, 0.5)
else
var/lkp = p.loc //The players last recorded position.
stop()
walk_towards(src, lkp, 0, 0.5) /*Zombie walks to the players
last known position. This is much more elegant than simply stopping
movement after the player reaches the end of the zombie's range,
adding a little more intelligence to the AI.*/

spawn(10) setTarget(lookAround()) //Looks around for the player again.
//If there's no player in range, it sets it's target to null
return

Is there anything in particular that would increase the productivity of this function? It may seem as though there's no delay, but the AI's delay is set within the main AI() function. It saves me from redundancy.

EDIT: I've actually narrowed it down entirely to the walk_to() proc. walk_to() uses 100% CPU with all of the zombies attacking. walk_towards uses 0% CPU with all zombies attacking. Is there a different path finding algorithm that I could soft code? I don't need perfect path finding, just something to get them around corners and around each other without much trouble.