1
\$\begingroup\$

We are building a game , where a group of humans(AI agents) have to wander seperatly throughout the forest looking for a collectable item. The forest is represented as a 2d graph with the item randomly placed at an (x,y) coordonate. Having a random search, while the easiest, doesn't guarantee that in a such big map I will reach the item and doesn't take into account that humans have memory and are able to tell, to a certain degree, weather the have traveled that path before.

A more systematic approach such as DFS, while guarantees that eventually the item will be reached, doesn't feel like a human wandering throughout the forest, it lacks the element of randomness and loss.

What I have in mind so far, is to run DFS to randomly selected batch of the forest. So the forest would be subdivided into randomly placed chunks for each human to wander, overlap and revisit is possible, and it would run DFS in that chunk traversing the subgraph eventually if item not found randomly select another chunk.

What do you guys think of the approach? How would you simulate human like search in a graph?

\$\endgroup\$
  • \$\begingroup\$ Humans tend to either go in a straight line randomly or wander around in circles until they die \$\endgroup\$ – Bálint May 18 '18 at 9:48
  • \$\begingroup\$ True to some extent, in real life your not guaranteed to find the item (exuaghst all the map) and a random approach to the problem is plausable but like mentioned doesn't take into account the ability to recognise walked path and doesn't guarantee or make it likely that item to be found \$\endgroup\$ – Raed Tabani May 18 '18 at 11:19
  • \$\begingroup\$ Which nessary for games purpose \$\endgroup\$ – Raed Tabani May 18 '18 at 11:19
1
\$\begingroup\$

If your humans are trained search and rescue people they would use one of the established search patterns.

This usually means going to the point most likely to contain the target and systemetically spiraling outwards. Or splitting up the search area into sectors and searching each one in turn.

This is not random but that is by design to avoid gaps and overlap.

\$\endgroup\$
  • \$\begingroup\$ For the game's purpose we are assuming they are not specialized in search and rescue. And therefore the BFS (systematic spiralling outwards) is not ideal. \$\endgroup\$ – Raed Tabani May 18 '18 at 11:13
  • \$\begingroup\$ What I'm thinking, what if you went exploring in a forest for an item and with minimal preparation , how would your behaviour be and what code and algorithm would best describe it? \$\endgroup\$ – Raed Tabani May 18 '18 at 11:15
0
\$\begingroup\$

Let's start with a simplified case and work up from there: Just one AI agent exploring the graph.

Calculating the perfect route to explore the whole graph in an acceptable time is an unsolved problem. So we shouldn't even try to find a perfect solution and instead aim for a simple solution which provides "good enough" results.

One such algorithm is the "greedy" algorithm: Always walk to the closest unexplored node.

This algorithm is very easy to implement and will cover a good amount of area in the short-term. But it has an unfortunate side-effect. It might lead the AI actor on a journey far away from the starting location before it fully explored its vicinity. You would usually expect them to look close to their starting location and then expand further when they don't find anything nearby.

A good way to account for that is to integrate this into the rating function for picking the next node. When you rate the nodes by priority, don't just take the distance to the current location of the agent into account, but also the distance to the starting location. How you weight these two criteria in relation to each other is more of an art than a science. Just experiment with this until you get a result you like.

Now how do we extend this to multiple cooperating agents? When they all perform the same algorithm, they will all walk to the same tile. They will likely stick close together and not make any use of their superior number.

In order to get them to divide and split, add a 3rd criteria to your rating function: proximity between the node and the next other agent. But assign a negative weight to this criteria. That means agents will avoid those tiles which are close to other agents and will instead focus on those areas of the graph no other agent currently attends to yet.

So final node rating formula:

node_rating = distance_agent * a + distance_origin * b - distance_closest_other_agent * c

Adjust the values of the constants a, b and c to taste. Lowest rating wins.

Now this algorithm might seem a bit too perfect. You said you wanted an "element of randomness and loss". To make the AI agents more fallible, you could screw with their list of visited nodes. While the AI agent wanders the forest, randomly mark previously visited nodes as unvisited, so the agents explore them again. Give each AI agent a separate list of forgotten nodes, so they wont all simultaneously run towards the same node. That way you will also observe the behaviour that they will occasionally not trust each other and check a node another agent checked previously.

How often to do this is another thing you might have to experiment with. Things I would experiment with is how frequently to forget nodes in which phase of the search and whether to prefer to forget nodes closer or further away from the agent.

\$\endgroup\$

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.