Creating a maze to protect the tower (the longest maze with limited walls) - an almost optimal heuristic?

Question

In the tower defense game, you have an NxM grid with a start, finish and a number of walls.

Enemies take the shortest path from start to finish without going through any walls (they are usually not tied to a grid, but, for the sake of simplicity, let's say they are. In any case, they cannot move along diagonal “holes”)

The task (at least for this question) is to place additional walls up to K in order to maximize the path that the enemies must take. For example, for K = 14

My intuition tells me that this problem is NP-hard, if (as I hope) we generalize this to include waypoints that must be visited before going to the finish line and, possibly, also without waypoints.

But, are there decent heuristics there for almost optimal solutions?

---

[Edit] I posted a related question here .

Answer 1

I present a greedy approach and perhaps close to optimal (but I can not find the approximation coefficient). The idea is simple, we must block the cells that are in critical places of the Labyrinth. These places can help measure the connectivity of the maze. We can consider the connectedness of the vertices and find the minimum cut that disables the beginning and end: (s, f). After that we delete some critical cells.

To turn it into a graph, take the double labyrinth. Find the minimum (s, f) vertex cut out on this graph. Then we examine each vertex in this section. We delete a vertex; deleting it increases the length of all paths s, f or if it is in a path of minimum length from s to f. After removing the vertex, recursively repeat the process described above for k time.

But there is a problem with this, when we remove a vertex that cuts any path from s to f. To prevent this, we can reduce the weight of the node as much as possible, this means that the minimum (s, f) slice is calculated first, if the result of the cut is just one node, make it weighted and set a large weight, like n ^ 3, vertex, now again we calculate the minimum s, f cut, the only cutting vertex in the previous calculation does not belong to the new cut because of the wait.

But if there is only one path between s, f (after some iterations), we cannot improve it. In this case, we can use ordinary greedy algorithms, such as removing a node from one of the shortest path from s to f, which does not belong to any section. after that we can cope with the minimum cut of the vertex.

The algorithm running time at each step:

min-cut + path finding for all nodes in min-cut O(min cut) + O(n^2)*O(number of nodes in min-cut) 

And since the number of nodes in min cut cannot be greater than O (n ^ 2) in a very pessimistic situation, the algorithm is O (kn ^ 4), but usually it should not take more than O (kn ^ 3), since usually the minimum cut algorithm dominates the path search, also usually the path search does not accept O (n ^ 2).

I think the greedy choice is a good starting point for modeling annealing type algorithms.

---

PS: the minimum section of a vertex is similar to the minimum section of an edge, and a similar approach, such as max-flow / min-cut, can be applied to the minimum section of a vertex, just assume that each vertex has two vertices, one V _i , one V _o , means input and output, also converting an undirected graph into a directional one is not difficult.

Answer 2

one can easily show (let’s prove it as an exercise for the reader) that it’s enough to find a solution so that each of the K-blocks is placed on the current route of minimum length. Please note that if there are several routes with a minimum length, then all of them should be considered. The reason is that if you do not put any of the remaining blocks on the current route of minimum length, this will not change; therefore, you can immediately set the first available blockade during the search. This speeds up even the search for brute force.

But there are more optimizations. You can also always decide that you will place the next blockade so that it becomes the FIRST block on the current route of minimum length, i.e. You work so that if you place a blockade on the 10th square on the route, then you will mark squares 1..9 as “constantly open” until you back off. This again saves the exponential number of squares to search while searching in the opposite direction.

Then you can apply heuristics to reduce the search space or change its order, for example. first try the blockade locations that increase the length of the current minimum-length route the most. Then you can run the reverse tracking algorithm for a limited amount in real time and choose the best solution found so far.

Answer 3

I believe that we can reduce the contained problem of maximal variety to boolean satisifability and show NP-completeness through any dependence on this subtask. Because of this, the spinning_plate algorithms provided are reasonable, since heuristics, computer pre-processing, and machine learning are reasonable , and the trick is finding the best heuristic solution if we want to miss here.

Consider the following board:

 ..S........ #.#..#..### ........... ........... ..........F 

This has many problems that make greedy and gate-related solutions fail. If we look at this second line:

 #.#..#..### 

Our logic is in a 0-based 2D array, ordered as [row][column] :

 [1][4], [1][5], [1][6], [1][7], [1][8] 

We can re-imagine this as an equation to satisfy a block:

 if ([1][9] AND ([1][10] AND [1][11]) AND ([1][12] AND [1][13]): traversal_cost = INFINITY; longest = False # Infinity does not qualify 

Except for infinity as an unsatisfactory case, we go back and relay this as:

 if ([1][14] AND ([1][15] AND [1][16]) AND [1][17]: traversal_cost = 6; longest = True 

And our hidden logical relationships fall among all these gates. You can also show that geometric proofs cannot be fractionalized recursively, because we can always create a wall that has exactly N-1 width or height, and this is an important part of the solution in all cases (therefore, divide and conquer will not help you).

In addition, since the perturbations in different lines are significant:

 ..S........ #.#........ ...#..#.... .......#..# ..........F 

We can show that without a complete set of computable geometric identities, the full search space reduces to N-SAT.

In addition to this, we can also show that it is trivial to check and non-polynomially solve, since the number of gates is approaching infinity. It is not surprising that therefore tower defense games remain so fun for people to play. Obviously a more rigorous proof is desirable, but this is a skeletal beginning.

Note that you can significantly reduce the n-term with respect to n-select-k. Since we can recursively show that each perturbation must lie on the critical path and because the critical path is always calculated in O (V + E) time (with several optimizations to speed up the process for each perturbation), you can significantly reduce your space search in a breadth-first search score of each additional tower added to the board.

---

Since we can very likely take O (n ^ k) for a deterministic solution, a heuristic approach is reasonable. My advice, therefore, lies somewhere between the spinning_plate answer and Soravux , with an eye on machine learning methods applicable to the problem.

Solution 0: use a valid but suboptimal AI in which spinning_plate provided two applicable algorithms. Indeed, these approximate numbers of naive players are approaching the game, and this should be enough for a simple game, albeit with a high degree of exploitation.

1st order solution: use a database. Given the formulation of the problem, you have not quite proved the need to calculate the optimal solution on the fly. Therefore, if we relax the restriction of approaching a random board without information, we can simply precommute the optimal for all K admissible for each board. Obviously, this only works for a small number of boards: with V! potential states of the board for each configuration, we cannot highly compromise all the optima, since V becomes very large.

2nd order solution: use the machine learning step. Facilitate every step as you close the gap, which leads to a very high cost of crawling, until your algorithm converges or a more optimal solution is found than greedy ones. Many algorithms are applicable here, so I recommend following the classics and literature to choose the right one that works within the limits of your program.

The best heuristic can be a simple heatmap created by a local state recursive depth traversal, sorting the results by most of them, as a rule, intersect after traversing O (V ^ 2). Fulfilling this conclusion, he eagerly identifies all bottlenecks, and to do this without making impossible paths is quite possible (checking this is O (V + E)).

Combining all this, I would try to intersect with these approaches by combining the heatmap and critical path identifiers. I would suggest that here is enough to come up with a good functional geometric proof that satisfies all the limitations of the problem.

Answer 4

At the risk of declaring the obvious, here is one algorithm

 1) Find the shortest path 2) Test blocking everything node on that path and see which one results in the longest path 3) Repeat K times 

Naively, this will take O (K * (V + E log E) ^ 2), but you could improve 2 with some little work, only by recounting the partial paths.

As you say, simply trying to break the path is difficult, because if most breaks just add a length of 1 (or 2), it is hard to find narrow points that lead to big wins.

If you take the minimum vertex length between the beginning and the end, you will find the shutter points for the entire graph. One possible algorithm is

 1) Find the shortest path 2) Find the min-cut of the whole graph 3) Find the maximal contiguous node set that intersects one point on the path, block those. 4) Wash, rinse, repeat 

3) - a large part, and why this algorithm may also work poorly. You can also try

• The smallest node set that connects to other existing blocks.
• finding all groups of adjacent vertices at the top of the section, testing each of them for the longest path a la of the first algorithm

The last thing that may be the most promising

If you find the minimum vertex cut to the entire graph, you will find blowing points for the entire graph.

Answer 5

Here is a thought. In your grid, group adjacent walls into islands and process each island in a node graph. The distance between the nodes is the minimum number of walls that are needed to connect them (to block the enemy).

In this case, you can start maximizing the path length by blocking the cheapest arcs.

Answer 6

I have no idea if this will work, because you can create new islands using your points. but it can help decide where to place the walls.

I suggest using a modified width search first with a K-length priority queue, tracking the best K paths between each island.

I would like every island of the connected walls to pretend it's light. (special light that can only send horizontal and vertical rays of light)

Use ray tracing to see which other islands might come into light.

say Island1 (i1) falls into i2, i3, i4, i5, but does not fall into i6, i7 ..

then you will have row (i1, i2), row (i1, i3), row (i1, i4) and row (i1, i5)

Mark the distance of all grid points to infinity. Set the start point as 0.

Now use the first width search from the very beginning. Each grid point, mark the distance of this grid point with the minimum distance from its neighbors.

But here's the trick.

every time you get to a grid point that is on a line () between two islands, instead of recording the distance of at least your neighbors, you need to make it a priority queue of length K. And write K the shortest paths to this line () from any other line () s

This priority of the queue remains the same until you go to the next line (), where it combines all the priority requests going to this point.

Answer 7

You did not indicate that this algorithm should be in real time, but I could be wrong about this premise. Then you can pre-calculate the position of the block.

If you can do this in advance, and then just do AI, create a labyrinth stone with a rock, as if it were some kind of tree, you could use genetic algorithms to ease your need for heuristics. You will need to load any structure of the genetic algorithm, start with a combination of non-moving blocks (your map) and random moving blocks (blocks that the AI ​​will place). Then you develop the population by making transitions and transmutations over the moving blocks, and then evaluate the individuals, giving more rewards for the calculated longest path. Then you just need to write a resource-efficient path calculator without requiring heuristics in your code. In your last generation of your evolution, you would take the person of the highest rank that would be your decision, so your desired block template for this card.

Genetic algorithms have proven that in an ideal situation you get to local maximums (or minimums) in a reasonable amount of time, which is impossible to achieve using analytical solutions on a sufficiently large data set (i.e., a sufficiently large map in your situation).

You did not specify the language in which you intend to develop this algorithm, so I can not offer a framework that may well satisfy your needs.

Please note that if your map is dynamic, it means that the map can change according to iterations of tower defense, you can avoid this technique, as it can be too intense to re-develop the whole new population on each wave.

Answer 8

I'm not an expert on algorithms at all, but looking at the grid, I wonder if the game in Conway’s life can somehow be useful for this. With reasonable initial seeds and well-chosen rules for the birth and death of towers, you can try many seeds and subsequent generations in a short period of time.

You already have a creep suitability score, so you can choose the best one accordingly. I don’t know how well (if at all) it will bring the best way, but it would be interesting to use in the solution.