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:
There is a concept of graph theory called Strongly_connected_component(AKA
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)).
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:
- The point is a strongly connected component.
- 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.
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:
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.