I'm kind of new to creating AI, and we're doing an RTS-like project at school where we want groups of enemies with sight cones to somewhat effectively search for the player's units.

My teacher told me I could try using a scout map, but I can't seem to search it in a way that seems logical in the least. I only manage to either have the units try to spiral outwards around the center of the map (the map is built around the last known position of a player unit), which I guess would kind of work on an empty map, but not when there's a lot of walls and buildings blocking the way, as the AI starts to take the long way around to reach areas on the other side of walls. Perhaps I could solve this with Dijkstra now that I think about it....

Or I get them to just wander off to the edges of the scout map, which seems like the smart thing to do if you actually just wanted to scout the area, not track something which you have a last known position of.

So I'm thinking I might have to consider something completely different, but I'm unsure of what, and the deadline is approaching quickly. The ideal end result would be something like that of MGS2, where enemies intelligently clear rooms, though that's WAY beyond my abilities, but at least it might give you an idea of what I'm looking for.

I'm kind of new to creating AI, and we're doing an RTS-like project at school where we want groups of enemies with sight cones to somewhat effectively search for the player's units.

My teacher told me I could try using a scout map, but I can't seem to search it in a way that seems logical in the least. I only manage to either have the units try to spiral outwards around the center of the map (the map is built around the last known position of a player unit), which I guess would kind of work on an empty map, but not when there's a lot of walls and buildings blocking the way, as the AI starts to take the long way around to reach areas on the other side of walls. Perhaps I could solve this with Dijkstra now that I think about it....

Or I get them to just wander off to the edges of the scout map, which seems like the smart thing to do if you actually just wanted to scout the area, not track something which you have a last known position of.

So I'm thinking I might have to consider something completely different, but I'm unsure of what, and the deadline is approaching quickly. The ideal end result would be something like that of MGS2, where enemies intelligently clear rooms, though that's WAY beyond my abilities, but at least it might give you an idea of what I'm looking for.

I haven't implemented this myself, but I have thought about it a bit. You need two things:
(1) A map indicating the probability of there being a unit at each tile of the map.
(2) An algorithm to visit the most likely parts of (1).

For (1) you can use some simple heuristic as a proxy of the probability of there being a unit at a tile. For instance, you can set it to 0 whenever you verify that it's empty, and then propagate probabilities between touching tiles as in some sort of heat propagation. Or -even simpler- you can simply remember how long ago you visited each tile, and use that as an indication of the possibility that a unit could be there now.

For (2) you need some pathfinding of sorts. For instance, you can try to find a path that maximizes the probability of finding a unit in the next 5 steps, using depth-first search.

Does that help?

It sounds like what you might need to implement is something that Damián Isla (ex-Bungie) terms "occupancy maps". They are very similar to an influence map. In fact, that's how they start. However, there are a couple methods of updating them. Start with the last known location of the agent. That tile is "100%" the moment you lose site of him. Now, over time, spread that influence to other nearby tiles. You will also be decrementing the starting tile. (The goal is that all tiles should normalize to 1.0.) The exception to this is that, when you look a a tile and the agent is NOT there, that tile is automatically zeroed out and the value that it had is spread to the other "in play" tiles.

A simple example would include 3 tiles: A-B-C

If I saw the agent in B, it is 100%. Upon "dropping the curtain" -- so to speak -- he disappears from B and is now either in A or C (50% each). If I see A and he is not there, then that 50% is transfered to C... so I know he is in C with 100% certainty. Obviously, real examples are far more complex.

Now, the method of spreading needs to look a little flood-fill-like. That way, it will mimic the agent moving down halls, through corridors, into rooms, etc.

For prioritizing the search, you will obviously want to consider the tile with the highest likelihood of occupancy. The only exception to this is that you would also want to check stuff near to you that is reasonable. The best bet is to combine the occupancy percentage with a downhill spread from your current location. Depending on the slope of that spread, you will consider less likely positions that happen to be closer to you just simply because of the opportunity they present.

If you assume a particular probabilistic model for how the opponent moves between rooms, then from the point of view of the AI this is a partially observable Markov decision process (POMDP); these can be solved.

If you do not assume a model for your opponent but rather want to assume that he/she is "smart" in a way that takes into account the decisions you will make, this becomes a Zero-Sum Markov Game with incomplete information. Zero-Sum Markov Games with complete information can be solved by minimax Value Iteration. I'm not familiar with the case of incomplete information.

I also fully understand that, if you're short on time and doing this for a school project, getting up to speed on this research is probably too much. Nevertheless, if you're interested in pursuing this in the future, these are some search terms.

For now, I think something ad-hoc along the lines of what alvaro and IADave have suggested would be awesome -- and probably a lot cooler than typical game AIs as-is.

The occupancy map sounds cool and should be able to use some of my Scout Map code for it.
It's just a matter of figuring out how to implement it.

I'm a bit uncertain about the example though. How come you're certain the player is in C? What if the player went to C as the AI went to A, then returned to B?

You're too pedantic. IADaveMark described a simple example for an intelligent search, and stated "Obviously, real examples are far more complex." If the details aren't clear, then read his comments as "It's certain that room C is the next best place to search."

Remember the goal of a tool like occupancy maps isn't to precisely record the target's position - you can do that already with a trivial "get player coordinates" routine. The goal is to simulate knowledge of the target's position, which means a degree of fallibility goes a long way towards making the experience more interesting.

In other words, it's no fun to play against an AI that always wins.

Yeah, I guess. With the percentage I assumed he was explaining the algorithm (though obviously in an extremely simple scenario).

I think I'm finding a decent solution now, though the values in the tiles don't add up to 1. Thanks a bunch. I'll probably be back with questions later.

ApochPiQ: i'm well aware that the most fun part of any stealth game is to fool the enemy.

Another approach that is worth mentioning is a "particle filter". You have 10,000 hypothetical scenarios of where the player might be. You also have some probabilistic model of how the player moves, so you can update every scenario using some random moves. If you are not seeing the player, any scenario that is incompatible with this data (because it has the player as being in front of you) is eliminated from the pool and is replaced with a copy of one of the surviving scenarios (one at random, which will evolve differently from its parent because of the randomness in the simulated player moves). So your representation is not exactly a map, but a whole bunch of particles.

In order to decide where to move, you need to play the game of "capturing" as many of the particles as possible. You can measure the quality of an algorithm by placing the agent in an empty level and seeing how many particles it captures in a certain amount of time.

Oh, and another behavior that would be really cool: If you know with pretty high probability that the player is in a particular room, you can just throw a grenade in the room, even if you don't know exactly where the player is.

I'm a bit uncertain about the example though. How come you're certain the player is in C? What if the player went to C as the AI went to A, then returned to B?

I assumed you could still see B. Sorry.