There's a couple of different ways to approach the problem of searching a space for something of interest.
First, you need to separate the related ideas of searching versus patrolling:
- Searching just examines a space. Once you've checked it, you don't need or want to recheck it.
- Patrolling involves repeatedly checking a space (or if you want to get technical, you're searching not just in space, but also over the dimension of time).
Many ideas on how to search are connected to patrolling, but the time aspect can have a significant impact & often needs to be considered up front. If your target of interest is dynamic, you have a patrolling problem as a regular search can fail if the object 'doubles back' & moves into a region that has already been searched. With that out of the way, here's an overview of techniques:
One approach seeks to eventually net as much information as possible. As such, the ultimate objective is an exhaustive search of the space. The key idea here is to minimize overall wasted effort (that is, revisiting the same location more than once). Here are some of the relevant search patterns used when looking for missing persons, lost objects, etc:
Computationally, these are basically what are called space filling curves.
Another approach is to find as much information as possible, as soon as possible. As opposed to the previous approach, the key idea here is to trade potential wasted effort in the interest of getting information sooner. This only works if you have some reason to favor certain areas over others. Essentially, these amount to conducting search in one area until some threshold is met & then moving into a new area. Here's an example where the search starts spiralling in one area (black), then moves to another (green), transitions back to expand the search around the first area (blue) and then moves on to a third region (gray):
In your situation, the transition threshold might be based on previous buildings you've seen, last known heading of an enemy, or maybe picking up supplies that you didn't need/have room for when first discovered, but need now.
Last, there's a connection between this problem & the travelling saleman problem (TSP) and its related problems. The TSP is well studied, challenging problem. In generally, the main thing to keep in mind is that you often don't need an ideal solution - you just need one that's good enough & can be computed quickly enough with the resources (memory & processor) available to you. So if you approach your problem through this lens, I would start with the various well know heuristic & approximation algorithms.
One final point - any search or patrol that's observed by someone with more information than the searchers will eventually look dumb. At some point, you'll say to yourself "Over there! Just turn! It's so close!". This isn't unique to AI. To some extent, meeting your teacher's expectation of a "smart world exploration logic" will depend on your ability to explain what decisions it makes & why, not just implementing the logic.
