5
\$\begingroup\$

For one of my exams, we have to make an AI for some sandbox survival game.

Well to be exact, we have been given a framework, and need to make a plugin that contains the AI logic.

So far, I already have the movement down, items, enemies, ... (movement uses a navmesh)

This is an image that show how the "world" could look like. (The AI has no way to get the exact layout of the map.)

World Layout

The AI does have a navmesh, but can only ask for the closest node to a certain vector (so that it can use that node to move to). It starts with nothing, and the world doesn't change once the program starts. However, the pickups respawn (only inside houses) and thus I want to map all the houses. The agent has an FOV (I can't really see how big it is) and items, enemies and houses inside that FOV suddenly reveal all their data (position, size, ...)

However, following the checkpoints is not the most optimal way of exploring the world... The teachers want us to have "smart world exploration logic". This is the part I am struggling with. Is there some kind of algorithm or logics to exploring this world?

I guess the question I'm asking is "How do I determine the goal to move to, if there's nothing in FOV?"

Maybe there's some "smart" wandering I could do? However, all I know for wandering is ones where it constantly changes its direction withing a certain limit.

\$\endgroup\$
  • \$\begingroup\$ Have a look into ray scanning the local environment for potential entry points - as with one's eyes, but in 2D - and see also the D* pathfinding algorithm which was used for some of the Mars rover's onboard logic. \$\endgroup\$ – Engineer Aug 29 '18 at 12:32
  • \$\begingroup\$ Hey @ArcaneEngineer thanks for your reply. My problem is not really finding the path (as I can already do that) But to determine in which way to "explore" the navmesh. So if I see a house, I'll explore that, but idk how I'd go about exploring outside of houses. \$\endgroup\$ – stevon8ter Aug 29 '18 at 12:52
  • \$\begingroup\$ Maybe the question "What graph Search algorithm (s) that can simulate the behaviour of a human searching in a forest" can help you? \$\endgroup\$ – Philipp Aug 29 '18 at 13:11
  • \$\begingroup\$ @stevon8ter Welcome to GDSE. You mentioned that the AI doesn't start with an exact map layout. It would be helpful to describe what information the AI does start with or can detect from its environment. How is the map represented? How far from its current location can the AI 'see'? Also, what parts of the world are subject to change? \$\endgroup\$ – Pikalek Aug 29 '18 at 13:35
  • 1
    \$\begingroup\$ @Pikalek Thank you. Well, the AI does have a navmesh, but can only ask for the closest node to a certain vector (so that it can use that node to move to). It starts with nothing, and the world doesn't change once the program starts. However, the pickups respawn (only inside houses) and thus I want to map all the houses. The agent has an FOV (I can't really see how big it is) and items, enemies and houses inside that FOV suddenly reveal all their data (position, size, ...). \$\endgroup\$ – stevon8ter Aug 29 '18 at 13:42
4
\$\begingroup\$

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:

enter image description here

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):

enter image description here

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ thank you for this useful information. I thought about doing a search pattern like this, sadly this would be rather confusing as my AI will prioritize searching a house as soon as it finds one, and thus pausing the search algorithm, potentially putting it in a weird spot to continue that same pattern. Someone came up with the idea to spread breadcrumbs around the world, and picking x-amount of random positions, then evaluate how many breadcrumbs there are left in that area, and how close it is, taking that as the "search-goal". Ofcourse, as soon as my AI sees a crumb, it would get deleted. \$\endgroup\$ – stevon8ter Aug 30 '18 at 10:19
1
\$\begingroup\$

First of all, your AI agent needs to remember which parts of the map it has and has not explored yet.

When the AI agent decides where to move next, it should look for some point where the explored territory transitions into unexplored territory and then just go there.

Now the question is how you prioritize different unexplored areas. The most simple one is distance. Simply keep moving towards the closest unexplored area until the whole map is explored. A more advanced heuristic could also prioritize areas by the likeliness of finding something interesting. For example, when the AI finds a wall, it might prioritize that area over empty spaces so it prioritizes exploring buildings over exploring empty fields.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you kind sir, this will help me tackle this problem. I was thinking of choosing a random point in an "unexplored" map, but going by an explored point closest to where my character is at right now, might be a better way. \$\endgroup\$ – stevon8ter Aug 29 '18 at 13:14
  • \$\begingroup\$ What would you suggest to store these "maps" in? I don't think it would be efficient to store all the positions with a flag in a vector \$\endgroup\$ – stevon8ter Aug 29 '18 at 13:15
  • \$\begingroup\$ @stevon8ter One way could be to give each agent its own navigation mesh which it builds by itself as it explores the world. This makes sure you won't "cheat" by having your route finding use knowledge about areas the agent did not explore yet. If you want to avoid all these copies of the navigation mesh in order to conserve memory, then you could just keep a set of all edges between visited and unvisited nodes for each agent. \$\endgroup\$ – Philipp Aug 29 '18 at 13:19
  • \$\begingroup\$ I did not think about a second nav mesh, but that's actually quite a good idea. Thank you. \$\endgroup\$ – stevon8ter Aug 29 '18 at 13:20
  • \$\begingroup\$ I'm having some issues with this. What my idea now is: "Create a navmesh of the entire world size" (thus being 300x300 square) and then when I see a house, cut it out, but I have no idea how I'd mark on that one where I already travelled, as I can't just mark the entire polygon I'm on right now. Do I just mark the vertices as visited? But then there's the problem that I might miss houses as I only travel along edges \$\endgroup\$ – stevon8ter Aug 29 '18 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.