0
\$\begingroup\$

I am new to Unity and want to create a tower defence game like Fieldrunners.

Screenshot of Fieldrunners

I need help to create the grid placement area for the towers so that there is always a path for enemies to travel. I mean the game shouldn't let the player to completely block the path of enemies by placing towers in that grid area.

\$\endgroup\$
0

3 Answers 3

1
\$\begingroup\$

If I understand correctly, you're asking how to check that units are able to make it from the start to finish. The normal method would be to run a pathfinding algorithm and see whether it finds a path or flood-fills the arena.

However, for the special case that your start/finish are at the top/bottom of the arena, with walls on the left/right side, there is a trick that is utilized by many tower defense games. The only way the path can be blocked is if there is an unbroken chain of towers stretching from the left-wall to the right-wall. So you just check all the towers to see if any such chain exists.

The valid-tower check can be optimized to be O(1) (!!) by noticing that an invalid tower always connects a left-wall chain to a right-wall chain. So, just keep track of which type of chain each tower is, and disallow towers that connect the two.

\$\endgroup\$
5
  • \$\begingroup\$ Don't forget to check if there is a tower diagonal placed as well else there could be no possible walking way even if there is no unbroken chain of towers \$\endgroup\$
    – Zibelas
    Feb 1, 2023 at 8:10
  • \$\begingroup\$ @Zibelas: It depends if units are able to walk diagonally or not. If so, then only the 4 cardinal directions need to be checked for chains, but if not, all 8 directions need to be checked. \$\endgroup\$ Feb 1, 2023 at 9:56
  • \$\begingroup\$ That is true. I just mentioned it since OP gave the example of Fieldrunner which has diagonal movement \$\endgroup\$
    – Zibelas
    Feb 1, 2023 at 11:17
  • 1
    \$\begingroup\$ I think you can generalize this special case to handle even more scenarios. Treat the map boundary on each side of an entrance/exit as a separate "source" cluster (wrapping around adjacent boundaries until you reach the next entrance/exit), and forbid any move that connects two different source clusters. This scales to any number of entrances/exits located anywhere around the perimeter. You can use a disjoint set data structure to keep these checks fast. \$\endgroup\$
    – DMGregory
    Feb 1, 2023 at 14:29
  • \$\begingroup\$ Note though that if you have at least two entrances and two exits, then the version I described above would forbid dividing the map into two lanes, each with one entrance leading to one exit, which might actually be a legal move you want to allow. \$\endgroup\$
    – DMGregory
    Feb 1, 2023 at 14:30
2
\$\begingroup\$

While Unity does have built-in path finding, it only works for 3d environments, not for 2d. I have seen some attempts to bend it to work in a 2d scenario, but I really can not recommend those flimsy hacks.

However, stock pathfinding algorithms like A* or the even simpler (but less performant) Dijkstra's Algorithm are relatively simple to implement yourself with some intermediate programming knowledge. I am not going to write yet another explanation how to implement those algorithms yourself, because the Internet is already full of those which are easy to find with your favorite search engine.

When the player makes a change to their tower layout, calculate a new path from start to finish. This is the new path for the enemies to take. When the pathfinding algorithm fails, then there is no path anymore and you should deny the layout change.

\$\endgroup\$
0
\$\begingroup\$

Trying to find path from start to end every time the layout changes is the most straightforward and the first thing you should try. If tested with no serious performance issues, maybe this is the final solution.

Considering that the operation of "try to place" is much more frequent than "place"(It depends on the type of game/target platform. For example, in PC, players often move the mouse quickly when choosing a place to place, resulting in multiple detections in a short period of time), If Detecting every time the mouse is moved, or the coordinates of the grid pointed by the mouse changes, may cause the frame rate to drop. We can try a way to calculate which positions cannot be placed when the layout changes, so that we can directly get the result when trying to place.

Grids can be viewed as undirected graphs, When a point is set as blocking, it is equivalent to deleting a node and its connected edges in the undirected graph:

enter image description here -> enter image description here -> enter image description here

There is a concept of graph theory called Strongly_connected_component(AKA cut vertex):

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)).

enter image description here

In a (normal) game state, the start point has a path to the end point, and all reachable locations form a strongly connected graph. Now we want to find all the points that can separate the start and end points, ie:

  1. The point is a strongly connected component.
  2. After removing this point, the starting point and ending point are in different subgraphs.

So we first need to find the strongly connected components of this graph. We can execute the Tarjan's strongly connected components algorithm with the starting point in the game as the starting point of the algorithm. The specific algorithm can be found in many places for reference.

However, we need to make some improvements, because only determining a certain point as a connected point does not ensure that the starting point and the ending point are not in the same subgraph. The core idea of the Tarjan's algorithm is to find a node, at least a child node of this node cannot bypass it to reach the root node(named broken child). We need to find this node, and all broken child. In addition, we need to record the path from the start point (root node) to the end point during the dfs process. These are all done in the same dfs, so there is no much more overhead compared to the original algorithm.

For each cut vertex, test whether it’s broken child is included in the path. If it does, it means that the start point and end point are not in the same subgraph after splitting, then the cut vertex is valid, and the fort cannot be placed here: enter image description here

I know these are rather obscure, but if you understand Tarjan's algorithm this is easy to understand. This method only calculates unusable positions when the layout changes, which is very fast when trying to place turrets.

\$\endgroup\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .