14
\$\begingroup\$

I am developing a game/simulation where agents are fighting for land. I have the situation shown in the picture below:

A green and red tiled area, with similarly coloured "creatures"

These creatures are walking around and occupying pieces of land they step on if they are free. To make this more interesting, I want to introduce "patrolling" behaviour, such that agents are actually walking around their land to patrol from any intruders who may want to take it.

On the technical side, each square is represented as a x,y position as well as a dimension representing its side length. It also contains information on who occupies the square. All squares are stored in an ArrayList.

How can I introduce patrolling behaviour? What I want is for each agent to patrol a certain portion of the area (they divide amongst themselves which areas they will patrol). The main issue I've found are as follows:

  • The area of land is very random, as seen in the picture. It is rather difficult to understand where the bounds are in each direction.
  • How they should agents split the regions to patrol?
  • Areas of land may be disjoint, since the opposing team may take territory from the middle.

I had an idea of taking the furthermost square in each direction, treating those as the boundaries of the area, and divide regions based on those boundaries, but this might include lots of irrelevant land.

How should I approach this problem?

|improve this question
\$\endgroup\$
  • 1
    \$\begingroup\$ Perhaps you could look at some image processing techniques for ideas? Various region growth algorithms running concurrently could emanate from each agent until all tiles belonging to their team have been assigned a patrolling agent. \$\endgroup\$ – Quetzalcoatl Feb 21 '13 at 18:11
  • \$\begingroup\$ @Quetzalcoatl: Nice idea, easy to implement, but this would lead to very unequal patrol regions. Consider the green agents in the image above. The top right agent would have ~15 squares to cover, the one in the center just 2. \$\endgroup\$ – Junuxx Feb 21 '13 at 18:51
  • \$\begingroup\$ Um is this more or less like picking the next closest block that belongs to their team from the current block. \$\endgroup\$ – Tohmas Feb 21 '13 at 18:57
  • 1
    \$\begingroup\$ Indeed, it is imperfect. Perhaps rather than using the agents as seeds for the region grow, seeds could be planted randomly initially (one per agent). Once the region grows have finished, maybe a balancing step could be performed, treating each region like a class cluster with tiles as nodes. KNearestNeighbour or KMean or similar could iterate until some form of convergence, whereupon the regions could be regarded as roughly balanced, with each agent then being assigned to the nearest seed (euclidean distance?). (I think I am probably overcomplicating this, there has to be a simpler way...) \$\endgroup\$ – Quetzalcoatl Feb 21 '13 at 19:06
  • 1
    \$\begingroup\$ Perhaps each agent could begin by repelling all other agents like magnets. That will force the agents to different corners of the region. When the agents come to a rest, then divide the land like Quetzalcoatl suggested. The regions should be roughly even. \$\endgroup\$ – tyjkenn Feb 22 '13 at 2:19
9
\$\begingroup\$

Fascinating question. I think one of the first issues you have to address is whether you want the patrolling behavior to be "optimum" patrolling or "lifelike" patrolling. I'm just making up these words, but what I mean is:

Optimum: The agents move about in a manner that perfectly distributes their coverage area for the system as a whole.

Lifelike: The agents move about and attempt to distribute themselves as equally as possible, but each only have access to data local to their perspective.

I'm going to focus on the second approach, which I think you can solve using weighted blending of various steering patterns from Craig Reynolds' Steering Behaviors For Autonomous Characters. The basic idea of steering behaviors is to use simple forces that combine to produce improvisational navigation around an environment. In your case I think you'd want to combine the following steering behaviors:

  • Avoidance (outside territory) - The agents attempt to stay within their territory and avoid moving outside it. For some realism though, the influence of "stepping outside" the territory needn't be 100% here. A little bit of "cutting corners" to go outside the area would probably make for more realistic movement.

  • Wandering - The agents attempts to keep moving around and exploring. This one you're going to want to weigh heavily otherwise the agents are going to try to find an optimal separation point from eachother and then "stay put".

  • Separation (other agents) - The agents attempt to keep a distance from other agents (so they cover maximum ground and don't clump up).

  • Seek (invaders) - The agents attempt to close in on any invaders they detect.

I think you'd want to play around with the relative weighting dynamically. For example, if an agent detects an invader, the separation weighting should drop down. (In other words, they only need to spread out when they're hunting, not when they find someone.) I think if you played around with the weights for the above four patterns, you'd have something pretty close to what you're looking for.

There are quite a few resources online about how to implement "boids" that follow the behavior patterns described. I recommend the open-source implementation opensteer.

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

One aproach is to record, for each cell, when it was last visited by a "guard", and have the guards continually move to whichever neighboring cell that has been unvisited the longest.

Of course, this assumes that the territory is connected.

This is not a perfect solution, but easy to code, adaptive to changing circumstances, and efficient. I have successfully used this algorithm for scouting and harassment attacks in an rts ai I wrote a while back.

|improve this answer
\$\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.