# How can I procedurally find a wall that separates two or more points on a grid-based map?

I'm trying to generate walls that cut off a given point from other given points. The attached image shows the sort of thing I'm after:

1. Blue separated from Red.
2. Blue separated from Red and Yellow.
3. Blue separated from Red with tile obstructions.
4. Multiple Blue separated from multiple Red.

Any ideas how to do this?

• This is a bit too broad... do you want to minimize the are of blue, or perhaps you want equal area, or maybe area doesn't matter but you want to minimize the lenght of the wall, or perhaps all that is irrelevant and what really matters is to find a solution fast... etc. – Theraot Mar 14 '18 at 3:23
• To give you, or others, one possible direction this sounds related to a variant of "manhattan distance voronoi" depending on the look you're going for or just regular voronoi. – Sirisian Mar 14 '18 at 15:41
• Agreed with both other comments, my first thought was "there are an infinite number of solutions." Where "infinite" may not be infinite by arbitrarily large. There are no restrictions on what allows this and not this. – Draco18s no longer trusts SE Mar 14 '18 at 18:56
• Sorry for not getting more specific. Really, the only strict requirement was that the wall separate the given points, which i do realize has near-infinite solutions. The images I provided weren't really meant as anything more then a general idea of what I was trying to do, so your edit, Draco, would be a perfectly valid result for my purposes. I was just looking for the sort of methods that would produce those sort of results, even if there are a huge number of results. – IanLarson Mar 16 '18 at 2:09

I will present a general concept and three solutions using that concept.

Concept is an Influence map: For each location in the map, you are going to store a number that represent the distance to each color point. That way, for each position you can query how far it is from blue, red, green, etc. We call the result is the influence map.

For more detail on the motivation, creation and use of influence maps in games see: The Mechanics of Influence Mapping: Representation, Algorithm & Parameters.

I have no idea what this wall is for, my head canon is that we are talking about a strategy game, and the AI is deciding where to place the walls. To do that, there are plenty of approaches besides the presented here. A simple approach would be placing walls at a fix distance from the color points and combine the areas when they overlap – and, of course, do not build them over obstacles – the advantages of this method are that it guarantees that the walls are not too far away to send troops to defend them and it is very cheap computationally. I am assuming you want something more complex.

Solution 1:

To find a way to wrap blue, find the difference between the distance to blue and to any other thing, for each point. Addendum: The area where the diffrerence is positive is the domain of influence for blue. If you take the domains of influence for every color point, you can build a Voronoi Diagram. Thanks to Sirisian for mentioning them.

We can argue that for a point close to blue, the difference will be positive, and for a point close to another color point, the difference will be negative. Given that the distance is a continuous function, by the intermediate value theorem, we can argue that at least one point in the middle the difference will approach zero. A solution would be to trace a wall that minimizes the distance between all the tiles where the difference approaches zero.

Whatever or not that solution takes into account obstacles depends on the distance function. If you only use the Manhattan or Euclidean distances without considering possible paths, then the resulting wall will not take advantage of existing obstacles in the map.

Note: this solution approaches equal area for blue and the rest in a flat scenario.

Solution 2:

In abstract, you can find choke points between the area of influence of blue and the others, and then place the walls there. Doing this will place walls in places where the influence is not in equilibrium (the walls my end closer to one side) but will minimize the length of the walls.

A useful approach to find choke points is to break the scenario into convex nodes and create a network that represents the scenario. You will start assuming you will put walls around the nodes that directly have blue, and then start advancing over the network (always increasing the distance from blue) and considering the length of the wall if you placed it surrounding what you have advanced so far. Your solution is the position that had minimum length (and the locations of the walls are the choke points).

In practice, the algorithm is a bit more complicated than that because there might be ramifications in the scenario. You only need to consider each ramification once, and pick the best position for the wall for that ramification.

Solution 3:

The first solution has the problem that it might lead to wall that is too long. The second solution has the problem that it might lead to walls that are too far away from blue.

Notice that working with pixels, tiles, or working with a network the concept of the influence map, as a representation of the distance to the color points is valid and useful. Thus, it is possible to apply the solution 1 over the network of convex nodes.

My third solution is to combine the above approaches. Once you are working over the network, you can consider the length of the wall and the difference in influence – and any other metric you want – as a single indicator metric “cost” that you can optimize.

• This is super helpful. Using an influence map sounds exactly like what I need. Thanks for the links and detailed response. – IanLarson Mar 16 '18 at 2:15