Optimal Pathfinding

Background

There is a square map with some obstacles on it. Obstacles are r开发者_JS百科epresented by polygons. I implemented following path finding algorithm:

1) Choose precision (it'll be denoted by k)

2) Divide map into k x k squares.

3) Make graph from those squares according to the following rules:

- Every node represents one square

- Two nodes are connected if and only if they are adjacent and none of them cosist any obstacle.

4) Find shortest path using A* algorithm (or Dijkstra or some other...)

This algorithm works quite well if map is not dynamic. It means that obstacles can't be moved.

Questions

1) Is that efficient approach?

2) What to do if obstacles can be moved?

3) How to treat other agents? Lets consider situation where there 100agents in the room. There are two exists. All agents are in one group, and that group near one of the exits. If all agents go to the nearest exit then it'll cause a bottleneck. Some of them should go to the other exit to minimize time needed to exit. How to get such result?

Use the A* path as a general guideline around static obstacles and perform local Obstacle Avoidance for dynamic (smaller) obstacles. Reynolds also has an algorithm for the bottleneck-problem. He calls it Queueing.