AI Movement Changes Beta

[Springheel]

we are meant to observe patrols and act upon the regularity of them.

 

Actually, random patrols are a well-established part of the game.

 

In fact now I think about it, it might simply be that they were the front door or front gate guards who do not have a patrol. Yes, that must be it. They should return to their original start positions but that failed.

 

According to the wiki, AI don't return to their original positions unless you give them at least one pathnode to go to. Doesn't mean they have to patrol; if you put just a single node they'll stand there like normal.

[Fidcal]

OK. I'll try that if I have any other AI in the map. I've just set up twin one step paths & waits for the four guards at the front and I'm just dmapping again to test it. I have about 3 other AI in the city who don't have paths so later I'll try those with just one path node.

[Tels]

Actually, random patrols are a well-established part of the game.

 

I think what Aprilsister means is that "not-regular-like-clockwork" patrol routes are more challenging and this is good (otherwise it becomes to easy), but "random-all-over-the-place" make the gaem completely unpredictable and this is bad.

 

Sitting in a corner, watching the AI and then deduce how their patrols are and when it is safe to move is an essential game-play thing of a stealth game.

[Fidcal]

This next text there were over 20 AI trying to cram in from every area of the manor and just outside. The front gate guards did indeed return to their posts but two women servants were left almost facing each around the bend. Neither could proceed and they were not trying any moves at all. Presumably they were in door queue mode, one to go out south door and the other to go out the door on the north side. There were 4 or 5 AI queued up outside that door on the north side who had come to alert but couldn't get inside. There were none outside the south door but the south going woman couldn't reach it because of the north going woman.

 

Of course, this is an extreme case and made worse because of the other problem of AI coming from everywhere. Later I'll increase the sound loss through doors even more but for now this is a good test of this code. Even if I increase sound loss, if AI actually run to fetch other AI then they will still come.

[grayman]

There are a lot of comments above, and instead of addressing them individually, I'll just make some general observations.

 

The goal is to keep the AI from getting stuck. And especially to keep them from treadmilling while they're stuck.

 

There will be plenty of situations where the code just can't handle what the AI have gotten themselves into. There might not be enough room to maneuver. Two doors might be so close to each other that their queues overlap. Lots of AI trying to get through the same space simultaneously might create a temporary standoff. I added timeouts to get them moving again if they stand around too long. So if two AI are touching and neither is moving, and something doesn't change in 10 or 20 seconds, then that's a bug. But it's probably a tough one to reproduce, given the randomness of how a crowd of AI jostle their way past each other.

 

Wrt AI suddenly back-tracking, it means they've bumped into a func_static and are circling around to try again. In 1.03, that's where they would get stuck treadmilling. To prevent this, that particular f_s needs to have its monster_clip adjusted so AI won't get near it. It would be great to avoid func_statics altogether, w/o monster_clip, but that adds a lot more work to pathfinding that we probably can't afford right now.

 

Three other factors affect AI behavior.

 

1) The code does what's called a trace to find out where an AI will fit, or how far along a path it can travel. A trace is very expensive, is done by the engine code, and doesn't always return correct results. So AI can use incorrect results and do something stupid. We can't fix this until the engine becomes open source.

 

2) The pathfinding code (95% id's) appears to do the same things over and over. Pathfinding is done every frame, for every moving AI, and many of the calculations done in frame N are unnecessarily repeated in frame N+1. This area needs to be looked at. If we can recover some cycles here, we could spend them on avoiding func_statics.

 

3) Pathfinding doesn't always identify the shortest route. Most times you won't notice, but some layouts will expose this problem.

 

 

If you encounter a situation that is unacceptable, post it here and I'll see what can be done.

 

Thanks again.

[i30817]

I haven't got any useful suggestion except looking at the work of this guy:

http://digestingduck.blogspot.com/

 

and his project

 

http://code.google.com/p/recastnavigation/

 

It's been used as a navigation mesh constructor in games i think.

[Fidcal]

grayman: I know I've asked this before but it seems to me it would solve the problem of overlapping door queues. Is it possible for an AI to timeout of their queue and go back where they came from? That would have solved my above problem. Two ways to do this:

 

After N seconds (say 45 to 60) if the AI is still in its queue then...

 

• 
   
  
• Restore its previous target (the one it just came from.) This seems ideal since it guarantees the AI would reverse (I think.) But it seems unlikely to me that the last target is stored.
  
• Get the next target from its current target (this is what AI already do if they cannot pathfind to their target so presumably 'safe'.) What would happen here is that either
  
  • 
     
    
  • the AI would find it couldn't pathfind forward so would pathfind a backward path to that target or...
    
  • it would consider it unreachable and increment to the next target and so on. Eventually, at the very least, in a circular patrol it would eventually retrieve the path node it came from.
    

Is there any downside to the above idea? Sorry if you've previously answered me on this.

[grayman]

Is it possible for an AI to timeout of their queue and go back where they came from? That would have solved my above problem.

 

AI are currently timing out of the queue after at least 10s. It varies, depending on where they are in the queue.

 

I can send them back the way they came; the previous path_corner is already kept. It will look like they got disgusted and walked away. Note that should the AI encounter another logjam during this reverse pathing, it will have to reverse itself again and walk forward to its original goal. Worst case, it can end up bouncing back and forth between two jammed-up doors.

 

However, if the AI is buried in a logjam, there's no guarantee that giving them a different place to go to will let them free themselves.

 

I'll try to release another DLL today with this change, and you can test it.

 

There are also some other things I can try that I've been thinking about.

[Fidcal]

However, if the AI is buried in a logjam, there's no guarantee that giving them a different place to go to will let them free themselves.

Not for one individual but ALL the AI in the logjam will likewise try to turn and go away. Some should succeed so those still stuck should eventually either get through the door or also turn away. In addition, even if it fails, we are no worse off.

 

Take the worst case in between my two doors which are close together. The woman trying to go south is blocked. If she gives up and tries to go back then all the AI outside the north door will block her. So she should then turn back and forth forever. But the AI outside the north door are queuing and they too should eventually time out and go back where they came from so the woman should eventually be able to return north thus freeing up the other woman who has probably returned south by now but if not, she can now proceed north.

[Aprilsister]

And... hopefully the whole mass alert thing will get cleared up too. Though, as already stated, it is kind of a good bug to have for this hard trial.

 

I like the idea of them "[getting] disgusted and walk[ing] away." It'd be neat for AI to have some barks for this. Even the rats. Rat-barks for rat-jams.

[Sotha]

I can send them back the way they came; the previous path_corner is already kept.

 

 

This is a bit off topic (sorry), but if the above is true, this bug could be solved quite easily:

http://bugs.angua.at/view.php?id=2282

 

So once the AI has been looking for the player and relaxes, it would target the previous path_corner, not the previous path_sit, like now it seems to do.

[grayman]

Rat-barks for rat-jams.

 

Mmmm. Rat-jam is good with crackers and hot soup on a cold day.

[grayman]

So once the AI has been looking for the player and relaxes, it would target the previous path_corner, not the previous path_sit, like now it seems to do.

 

 

If he's interrupted while sitting (or turning, or waiting, or whatever), and he comes down off alert later, he should look at his current path entity, and if it's not a path_corner, he should skip it and look at the next one, etc. etc. until he finds a path_corner. Then he should go there.

 

That should work better than making him go back to his previous path entity. I haven't looked to see if the previous path entity that's saved is actually a corner, or whether it could be any of the multiple path entities. If it's not a corner, then going back to it won't give us what we want.

[nbohr1more]

My paltry testings:

 

I tried twice to incite a massive search in Lockdown 1 because I recalled that I had seen some "wacky stuff" occasionally in the beta version (in the beginning courtyard). I still have the beta installed alongside the released version and I was not able to start the antics in either.

 

I also checked the behavior of waking the first AI in St Alban's and he did not fall through the floor as I have seen him do before.

[grayman]

I also checked the behavior of waking the first AI in St Alban's and he did not fall through the floor as I have seen him do before.

 

 

Thanks for testing.

 

Sometimes that happens and sometimes it doesn't. I'd be surprised if the movement changes fixed this problem.

[Tels]

Don't know if this was posted here or if I saw it somewhere else, but we should keep an eye on this (as a potential replacement for AAS):

 

http://code.google.com/p/recastnavigation/

 

His blog has interesting videos, which might give grayman some ideas:

 

http://digestingduck.blogspot.com/

 

Edit: One thing I stumbled over while browsing this is http://oldhome.schmorp.de/marc/liblzf.html which is a real-time compression library. The decompression runs essentially as fast as a copy, and the compression isn't slow, either. Not as comrepssing as good as ZIP, but much faster, and thus can f.i. be used a a "compress data we are currently not using, decompress when we use it" solution.

[grayman]

This is a bit off topic (sorry), but if the above is true, this bug could be solved quite easily:

http://bugs.angua.at/view.php?id=2282

 

So once the AI has been looking for the player and relaxes, it would target the previous path_corner, not the previous path_sit, like now it seems to do.

 

I tested this in 1.02, 1.03, and in today's SVN.

 

The problem's there in 1.02, but fixed in 1.03 and SVN.

 

So fixing something else in 1.03 fixed this.

 

I've marked it "resolved".

[grayman]

Don't know if this was posted here or if I saw it somewhere else, but we should keep an eye on this (as a potential replacement for AAS):

 

Yes, I saw that last week when searching for AI pathfinding methods.

 

Interesting stuff.

 

AAS is similar to a navigation mesh, but id uses rectangular areas rather than triangular. I'm suspecting some improvements can be made, but refactoring to use a different method is something for the future when the bug list is whittled down more.

[nbohr1more]

One thing I noticed before when a bunch of AI were buzzing about next to each other is that they didn't always seem to animate properly in close quarters. I have not seen this currently but I wonder if any of your movement changes should be accompanied by custom animations at some later juncture?

[grayman]

One thing I noticed before when a bunch of AI were buzzing about next to each other is that they didn't always seem to animate properly in close quarters. I have not seen this currently but I wonder if any of your movement changes should be accompanied by custom animations at some later juncture?

 

Possibly. Since they are jostled about in close quarters, they're turning and stopping and taking short steps. These actions probably weren't anticipated by the animation designers.

[grayman]

I have "leave a door queue and go back the way I came" working. I also made a couple other minor changes today and will release a new DLL sometime tomorrow.

[Tels]

Yes, I saw that last week when searching for AI pathfinding methods.

 

Interesting stuff.

 

AAS is similar to a navigation mesh, but id uses rectangular areas rather than triangular. I'm suspecting some improvements can be made, but refactoring to use a different method is something for the future when the bug list is whittled down more.

 

Yes, of course. Also, ripping out AAS might be best done when we have the full source because we then also have access to the AAS compiler. (which in itself has some problematic things, and some of them are because we cannot access it). Unifying this all ito a new, modern framework would be good.

[grayman]

The third round of movement changes is now in SVN.

 

Source rev is 4540.

 

The rev 11558 version of tdm_game01.pk4 has the Windows DLL.

 

The 1.03 DLL isn't ready yet. It will be a couple hours before that's available.

 

This round includes:

 

1. Fidcal's suggestion that AI walk away from a door queue if some time has passed. They'll return to their previous path_corner, then continue their patrol from there. They'll leave the queue 10-15s after joining. (Thanks for this; it helps keep them out of trouble.)

 

2. AI now close doors if they're the last one through, regardless of whether the door was initially found open or not. This helps with performance, though it might bother players who leave doors open on purpose to mark where they've been.

 

3. If an AI arriving at a door is very close to the door (perhaps he just walked around a corner and found the door), and he has to join a door queue, he will step away from the door to make more room.

 

4. AI who get pinned to the wall behind an opening door will now close the door to free themselves, if they're unable to find a way around the door first.

 

Edit: 5. Idle animations are turned off when an AI enters a door-opening or door-closing stage. Watching numerous arm-stretch or eating animations while a door is magically opening or closing drove me to make this change.

 

 

Please test. 1.04 is scheduled to enter code freeze Saturday.

 

If you see any AI getting stuck and staying that way for more than 20s, please write up a detailed description of the circumstances and post it here.

 

Thanks!

[Tels]

The third round of movement changes is now in SVN.

 

Thanx! It's fantastic to come home and read news like this

 

2. AI now close doors if they're the last one through, regardless of whether the door was initially found open or not. This helps with performance, though it might bother players who leave doors open on purpose to mark where they've been.

 

I think this is fine, we AFAIK never made any promise that an AI would not close a door. It is in fact human behaviour and thus fine. (It would be something else if the door would be closed automatically).

 

The only suggestion I have is to give the mapper some control, either by having a spawnarg on the AI, or the door, or both, that gives the probability that the door is closed in this case. That makes it seem more natural (sometimes the AI just doesn't bother) and also gives the player less predictable AI. However, this would still be fine post-v1.04.

[grayman]

The only suggestion I have is to give the mapper some control, either by having a spawnarg on the AI, or the door, or both, that gives the probability that the door is closed in this case. That makes it seem more natural (sometimes the AI just doesn't bother) and also gives the player less predictable AI. However, this would still be fine post-v1.04.

 

Good suggestion for 1.05. Thanks. I was considering adding a 50% chance of closure, but it would be just one more change too close to code freeze, and I opted to do it later. I'll replace it with your suggestion.

 

There are a number of other things that came out of a discussion on another thread. Once 1.04 is released, I'll post a list and we can decide which ones we want.