next »

[mcc]

Just a random passing thought...

So you think about pathfinding in video games. Regardless of what pathfinding strategy you use, there's something in common: The NPC needs to get from point A to point B, so the instant it realizes it needs to do so it starts intently walking directly along the shortest path to B (even if B is on the other side of a wall and it shouldn't be able to see B's exact position...).

In short, the NPC behaves as if it has access to the level geometry. It behaves like it's working off of a perfect overhead map.

That's not how anything would behave in the real world. In the real world, someone like a security guard would know the complex they work in as well as if they had a map in their head, but many NPCs it seems like ought to be having to build a map in their heads as they go-- they'd be aware of any parts of the map they've line-of-sight "seen", but no more. And they shouldn't necessarily be able to make some of the mental leaps a pathfinding algorithm would (for example, maybe a wolf in an MMORPG shouldn't be as good at pathfinding as a human-- I originally started thinking about this watching our dog try to navigate around some clutter by the back door).

I'm just curious-- has anyone ever seen a game that actually approached pathfinding like this? Something like forcing individual pathfinding actors to "discover" the map by traveling it instead of just giving them access to the level data from the start. I'm wondering whether implementing pathfinding this way in a game would make NPC behavior seem more realistic, or just make it seem buggy...

[_Tommo_]

Halo pretty evidently does this, I love how they keep firing at your last known hideout only to be owned from behind.

[Nix]

Only allowing the "known world" to be used in path-finding would be pretty trivial. The tricky part would be how the AI decides which unknown hallway to try next if the region between its position and the target were unknown. And integrating some forgetfulness would add immensely to the realism.

[mcc]

Only allowing the "known world" to be used in path-finding would be pretty trivial. The tricky part would be how the AI decides which unknown hallway to try next if the region between its position and the target were unknown. And integrating some forgetfulness would add immensely to the realism.

Yeah, that would be awesome. What would be especially great, I think, is if NPCs could actually get lost. Like put metadata on the map describing parts of the map which look "similar", or coloring parts of the map with how visually repetitive that part of the map is. This would allow you to make it so that the "twisty little passages, all alike" ish a part of the map is less well the pathfinding works because the NPC briefly gets confused about where on the map they are, or maybe their "forgetfulness" increases in those parts of the map, just like would happen with a human player.

Though I'm still not certain whether, if a NPC were behaving this way, it would be obvious to a human observer that the NPC was doing so.

[Feral_P]

I suppose it would be easiest to implement A*, where unknown territory is assumed to be empty space/floor (ie. a pathing penalty of 1). Anything within the AI's LOS would be added to its map of the world, and if it hasn't seen a tile in x amount of time, it could forget it... Of course, this means the A* would have to be recalculated every time the AI reveals more territory (since the world has effectively changed for it), which would be very slow...

Although, like mcc says, this behaviour may well just seem like a bug, to the player, if it wasn't presented very obviously ie. you can always see the AI and where it's moving, and you're explicitly told it has this behaviour.

[_Tommo_]

I think this whole lot of things is of interest here.

AI is nowhere near a real Artificial Intelligence in videogames, nor it should be - it all boils down to the design problem "how I can make the player feel he's facing smart enemies?".
Feeling, and looking smart/capable of emotions, are two things very distant from any current AI research.

All of this to say that to me oblivious enemies could be good only if this was really evident to the player, having NPCs that forget things looks mighty useless and bug-like to me.
After all in 99% of FPSs the player has never enough time to track the NPCs and deduce what they're "thinking", usually they are found and then dead in seconds.
In a way, FPS AI is concerned on creating foes that "die well", not much more.

While the whole point of mcc makes enormous sense in any RTS, where AI has always been too artificially stupid, all-knowing and exploitable to be a good challenge.

[st33d]

I would A* but not with penalties. I would have a deactivated A* graph. Like the graph is made of solid wall.

Then use something like a roguelike shadowcasting algorithm (it's quite low overhead to run) to reveal graph nodes around the NPC.

This is what the NPC knows of the area. He can navigate as much of the graph as he has seen, and when chasing he will of course reveal more options.

[Core Xii]

I have a project where every entity has separate knowledge of the map. They pathfind the shortest route as usual, but as they navigate the map, changes previously unknown to them (this tunnel has collapsed) become known and they have to re-route.

Then as entities meet they "talk" and tell each other their most recent map knowledge, thereby updating both entities' maps to the sum of their up-date-to-ness.

[wolfx]

I have a project where every entity has separate knowledge of the map. They pathfind the shortest route as usual, but as they navigate the map, changes previously unknown to them (this tunnel has collapsed) become known and they have to re-route.

Then as entities meet they "talk" and tell each other their most recent map knowledge, thereby updating both entities' maps to the sum of their up-date-to-ness.

I love that method, if I ever get around to making an AI system I'll be sure to do this. 

[nahkranoth]

Would be cool to have helicopter's hovering the map and transmitting his findings to the enemies. Whenever the helicopter spots you everybody knows where you are and the waypoint for the A* would be you last known location.

[Sean A.]

Well I think in certain cases the enemy should know the hallways and routes. For instance if you are fighting a guard, they should know all the nearby routes because they were hired to guard them.

[dcarrigg]

This is a good talk on the subject of knowledge representation:

http://www.gdcvault.com/play/1267/(307)-Beyond-Behavior-An-Introduction

If you don't want to watch the whole thing, at least watch the one part called "Demo Knowledge Representation".

-Dave