Background
There is a square map with some obstacles on it. Obstacles are represented by polygons. I implemented the following path search algorithm:
1) Select the accuracy (it will be denoted by k)
2) Divide the mapping into squares kx k.
3) Make a graph of these squares in accordance with the following rules:
- Each node represents one square
- Two nodes are connected if and only if they are adjacent, and none of them is an obstacle. 4) Find the shortest path using the A * algorithm (or Dijkstra or some others ...)
This algorithm works well enough if the card is not dynamic. This means that obstacles cannot be moved.
Questions
1) Is this an effective approach?
2) What if obstacles can be moved?
3) How to treat other agents? Let's look at a situation where there are 100 agents in a room. There are two options. All agents are in one group, and this group is located next to one of the exits. If all agents go to the nearest exit, this will cause a bottleneck. Some of them should switch to another exit in order to minimize the time required to exit. How to get such a result?
source
share