So I've come up with a way that I would augment video game AI. The premise is that you have a captive sandbox. Like you have an entire city, you can conceivably go anywhere in that city that you can get into by various means. If you can pick a lock you can open any door. If you can bust down a wall you can walk through it. That sort of thing.
But more specifically, every single character has a built-in personality made up of game-models that allow them to make decisions. No more pedestrians milling about for no apparent reason. The Cobbler actually makes shoes for people, the tailor actually makes clothes. No doubt it would take a great deal of processing power, but so does rendering real-time ballistics.
So it would look something like this.
The cobbler sees you murder someone. Does he hide and hope you don't find him? Does he move to defend that person? Does he move to avenge that person? Does he scream looking for help? You create a model of the character based upon the answers to questions like this. More specifically they'd have a bravery/cowardice index. And action would be weighted against the game model that governs the response. Like a Cowardly person could be hard-wired to avenge the death of a family member, but do a cost-benefit analysis regarding a neighbor. Each character will have a web of relationships that give them impetus toward particular actions related to each game model. Like, "If he is alone and sees you murder a neighbor, but you don't see him, he hides and waits to tattle to the town guards."
An important factor would be sensory inputs. You'd have to give people zones of sensory perception. If they cannot hear you they cannot hear you. If they cannot see you, they cannot see you.
Some of the things would be easy. The Palace guard will attack you NO MATTER WHAT, in the palace. Beggars will run and hide from you NO MATTER WHAT. Of course you'd have wildcards thrown in so that there is a small chance that the palace guard is a coward and the beggar is a hero. You wouldn't want the population to be too predictable.
You make the action modifiable by the reactions of others. If there is a charismatic coward, he might be persuasive on the side of doing nothing. If there is a charismatic brave person, they might tend toward action.
Another situation. THe blacksmith is a big manly man type and cannot handle having seen you murder someone, the cobbler is a coward, and the butcher is kind of in between. The blacksmith sees you do something he cannot abide and comes at you with his hammer. He was playing cards with the cobbler and the butcher. He forces people's hands, so the cobbler has to weigh loss of face and guilt against self preservation. But also, since the blacksmith forced his hand, he knows he has to do something, especially since the butcher has already made his choice. But while he was deciding (Because complex decisions would take longer to render) you take down both the smith and the butcher. The variables of social bolstering that applied some bleed of their attributes to his attributes dissolve, and he bolts. Now, you can chase him, but he's a fast runner that cobbler. Meanwhile he's screaming like a little bitch and other people are waking up.
Now, none of these characters is actually intelligent, or actually making choices. It applies the illusion of choice, because they take the best apparent option. You could even have it varied by the ability to make good decisions under pressure. Like the elite King's guard, they make decisions very quickly, and do not hesitate to act once the decision is made. But the cobbler, he could be paralyzed by fear, and thus makes his decision more slowly.
Also, it allows for social structures to change. The NPCs have relationships to one another. Say you kill the neighborhood tough guy, well his servile beta male becomes the Alpha in his region, and so the social order changes in relation to him. Or perhaps he's actually becoming a prick and throwing that neighborhood into turmoil. Maybe the cobbler would follow the blacksmith into battle just because the blacksmith has been tormenting him since childhood, and he knows that he'd never stop being the neighborhood bitch if he doesn't back the guy up, and that's weighed against the possible elevation in status if they are victorious.
Some characters could be bribed. You can do business with various people in their stations in life. Every time a character sees you under ANY circumstance, they recognize you. This is of course modified by clothing and disguises. But eventually they might come to recognize you and know who you are.