algorithms?

[Choscura]

hey, I've been bouncing some ideas through my head for the past couple of weeks months years and would like to compare notes with the programmers on this project. who should I bug?

[greebo]

Well, what do you want to know?

[Choscura]

Everything.

 

but I should probably be more specific, so here goes. and please keep in mind, if I sound like an idiot, it's because I'm unfamiliar with something and haven't done enough research/found the facts I need to understand something.

 

first, are you doing any hard coding on the game engine itself to change anything or is everything handled with scripting within the engine itself? and if you are doing hard coding, what type of stuff are you guys doing the coding on- AI? physics? object manipulation?

 

Second, I'm really interested in first how the AI interacts with the environment and the player. some of the stuff I've read here- such as the frequency of thoughts for an AI actor decreasing the further away from the player it gets- seems quite interesting. other things seem like a hassle, such as getting the AI to interract with doors or to realize that a moving box held in front of the player is not actually supposed to be doing that.

 

I'll go off on this first. I've been trying to figure out how to make AI work effectively. it seems like the same idea as a bounding box can be applied to a lot of things- not necessarily a box, though. An example I can give is a system for hearing sounds that I've worked out: a bounding sphere/circle/dome/etc can be used both for the 'ear' and the source of the noise. obviously, any NPC's inside the bounding sphere of the noise can hear it, and some NPC's with acute hearing (such as dogs) can hear things further away so they have their own sphere to increase their chances of hearing something. also, unlike graphics, sounds can take a second or two longer to be processed, so you don't have to waste a lot of processer power on them when you need it for the graphics. it seems like the developers who worked on the third splinter cell game realized this, although I've got nothing but my own observation to base this on.

 

The second thing that I've been itching to figure out is the "something suspicious is going on" AI. one concrete example I can give from TDM is the hiding behind a crate you're carrying and the AI not recognizing you because you're behind a crate. Please bear with me as I haven't had the chance to play the TDM yet. I have yet to see, in any of the demo videos, an AI actor doing the "hmm, something's not right" dance. once again, I point to bounding boxes, or more accurately, a bounding ray: it seems like the same hard coding that is used in lighting could be used for the detection by an NPC in the game. simply trace a ray from X point (somewhere around their eyes) for Y distance (everything past that is cut off/ignored) and then check for visiblity within that, and then within that visible area- then you do a check of something like switch (something fishy?): case |nothing is moving| {normal}: case |something is moving| {something fishy}: case |I know you're there!| {attack mode}:

 

ok, thats about it for now. it's almost 3 AM and I've gotta hit the sack.

 

thanks in advance for any input!

 

edit: speeling

Edited December 14, 2008 by Choscura

[greebo]

first, are you doing any hard coding on the game engine itself to change anything or is everything handled with scripting within the engine itself? and if you are doing hard coding, what type of stuff are you guys doing the coding on- AI? physics? object manipulation?

I think you have a different definition of "hardcoding" than me. You seem to understand hardcoding as messing around with the C++ code, whereas hardcoding usually refers to "baking" constants like gravity into the code, it refers to the lack of possibilities to change something from the "outside".

 

(That being said, coding for TDM is kind of "hard", so if you're a fan of puns, you're right to some extent.)

 

And yes, we're doing a lot of C++ coding. Not really on the engine itself (the engine is responsible for displaying the world, playing sounds and calculating collisions, all of which is still closed source, it's the gameplay code we're working on - AI, physics, lightgem, inventory, objectives, conversations, stim/response, sound propagation, grabbing items, doors, and so on and so forth).

 

As for the actual question: the Doom3 AI we were starting with were mostly scripted (as in D3 scripting), with the exception of pathfinding and some other stuff. The entire behaviour was in scripts.

 

This has been changed for TDM, as we were pushing against the boundaries of the existing D3 script-based system, it was getting harder and harder to get the AI doing what they ought to according to our designs. That's why we (that's angua and me) completely redesigned the AI framework a year ago and moved virtually all behaviour to the C++ code. Our AI are now some sort of stack-based state machine, with four (again) stack-based subsystems interacting with each other.

 

So far I'm quite satisfied with the framework (from the coding point of view, that is), it provides us with more flexibility when it comes to implement high-level goals like opening doors, but it's still not perfect. There are still some kinks to be ironed out, but we're getting there.

 

I wrote a few articles about our AI system on the wiki, if you're interested.

 

Second, I'm really interested in first how the AI interacts with the environment and the player. some of the stuff I've read here- such as the frequency of thoughts for an AI actor decreasing the further away from the player it gets- seems quite interesting.

It's actually necessary to tone down the processing speed of AI far away. D3 went as far as switching AI off completely as soon as they get out of your PVS, but this is not acceptable for a game like TDM, where guards are patrolling around the entire map and might have to react to things that are far away from your current player position.

 

other things seem like a hassle, such as getting the AI to interract with doors or to realize that a moving box held in front of the player is not actually supposed to be doing that.

They are a hassle. The door handling task is actually the most complex task our AI are performing. The corresponding code has more than 1000 lines and has been developed for months. Angua wrote it, she can tell you more about it.

 

I'll go off on this first. I've been trying to figure out how to make AI work effectively. it seems like the same idea as a bounding box can be applied to a lot of things- not necessarily a box, though. An example I can give is a system for hearing sounds that I've worked out: a bounding sphere/circle/dome/etc can be used both for the 'ear' and the source of the noise. obviously, any NPC's inside the bounding sphere of the noise can hear it, and some NPC's with acute hearing (such as dogs) can hear things further away so they have their own sphere to increase their chances of hearing something. also, unlike graphics, sounds can take a second or two longer to be processed, so you don't have to waste a lot of processer power on them when you need it for the graphics. it seems like the developers who worked on the third splinter cell game realized this, although I've got nothing but my own observation to base this on.

Actually, a bounding-box check is not really enough to get a well-functioning sound propagation system. Ishtvan's design is going a lot further than that, obviously. In fact, the first quick soundprop pass is actually using a radius-based distance check to cull all AI theoretically unable to hear the player, but from then on it get s a lot more complicated, as you need to consider doors (closed/open) and the actual path the sound is taking.

 

The second thing that I've been itching to figure out is the "something suspicious is going on" AI. one concrete example I can give from TDM is the hiding behind a crate you're carrying and the AI not recognizing you because you're behind a crate.

From what you all saw in Saint Lucia, the AI are not paying much attention to things flying around or go missing or making noise when moved by the player. This is something which is work in progress, but it won't be too hard to get this done. It's just a matter of extending the visual scan routine and setting up sound propagation for collision sounds, etc.

[Mortem Desino]

From what you all saw in Saint Lucia, the AI are not paying much attention to things flying around or go missing or making noise when moved by the player. This is something which is work in progress, but it won't be too hard to get this done. It's just a matter of extending the visual scan routine and setting up sound propagation for collision sounds, etc.

How about when a large prop is moved out of its original visportal'd region, it is considered "suspiciously misplaced?"

 

Note: I'm not very familiar with the D3 engine or how visportal brushes are dealt with in-game, so feel free to correct me; I just find this stuff fascinating.

[Ishtvan]

How about when a large prop is moved out of its original visportal'd region, it is considered "suspiciously misplaced?"

I think that would seem inconsistent from the player's perspective. Visportals are what divides up the map into different portal areas. Portals are often placed in doorways, archways, and other openings. If you define suspicious as crossing thru a portal to a different portal area, what happens if you have object #1 near a large archway that just happens to contain a visportal, and object #2 in the center of that portal area. The player obviously can't see that there's a visportal across this archway, but with that proposed system, moving object #1 one foot through the arch would creat a panic, but the object in the center of the area could be moved greater distances (say 15 feet) with no conesequence, as long as it didn't go thru a visportal. That would seem inconsistent to the player, and unpredictable since they have no idea where visportals have been placed.

[Mortem Desino]

There's probably a better way to indicate seperations between rooms and sections of geometry than visportals, yes...

 

Else, I suppose, you could set props being moved from their original place along with a certain sensitivity to axes.

 

Suppose a candle falls off of a table. If the candle falls off of the table (z changed) but not far from the table (x+y axis unchanged) It is not nearly as suspicious as flying across the room (x+y) and onto the floor (z). Or suppose the candle was moved from table A to table B in the same room (x+y changed). It's not as suspicious as the candle moving from on top of Table A to lying underneath Table B.

 

Perhaps it's overcomplicated, and I can already think of exceptions and possible exploits to this, but It's how I'd implemement it.

Edited December 16, 2008 by Mortem Desino