Optimize the algorithm for finding the shortest path

Question

Programming

Good afternoon.

There was a problem with the pathfinding algorithm. Implemented the Lee algorithm and many others. There were no problems before due to the fact that the game cards are small.
Now there is a need to calculate the shortest path for the npc on a fairly large map.

And two problems arose:
1) Since the map is large, running the wave algorithm for each npc is in itself quite expensive.
2) So far, the path is calculated at each step using a new one .

Therefore, I want to ask for help in optimizing the algorithm in order to somehow eliminate these problems. Or at least minimize the computation time somehow.

ps There is no need for ready-made sources, etc., I'm interested in the theoretical part.

Answer 1

I don't know if you tried this option based on the statements:
1. the entire map of the game world does not change much
2. usually you can try to divide the map into zones or in a blunt version of the cell (or rather, options for moving between them), which are also change very rarely and not much
. The simplest example: let the zones be just square cells inside a simple grid, the size of the cell is comparable to the average size of the obstacle on the map.
A more complex example: a polygonal area is divided into zones along the boundaries of large obstacles, and perpendicularly crossing the typical paths of movement of units (roughly speaking, the highways of their movement), it is not difficult to collect such statistics during the game, it is more difficult to choose the size of the zone, as an option - to fix the number of such zones from the average number of units in the game ...
Then from neighboring cells, the paths of movement are usually either bypassing through neighboring cells or through a connecting edge between these two.
Cell sizes should be chosen to accommodate some (not very large) number of obstacles... dozens or hundreds.
We calculate in advance (and gradually update as the world changes, this is not necessary to do in real time, although then funny artifacts in movements will be possible) possible ways of moving between such zones (each face is a list of zones crossed by possible paths), and at the moment when an exact path is needed, we calculate it only within these cells, adding to the algorithm the search for a point on the edge between the cells closest to the path (that is still a problem).
It is not relevant to count the whole way, it is enough to count within 1-2 cells forward (according to the algorithms already known to you) and get an answer if there is even a possibility to hit the target. Add to the algorithm recalculation of the path depending on the game objects that are relevant for calculating collisions (here the problem is whether traffic jams are possible).
Such cells arean analogue of the unit's memory of how it would be possible to approximately pass into the corresponding zone.
It will add even more realism, for example, behavior during traffic jams, as if the unit does not yet see that the path ahead is closed, but obediently stomps until it gets into a cell with this traffic jam… then an event will occur that the path cannot be reached… since there are always several options for moving between cells , this creates more than one path to move through the cells, several, respectively, temporarily mark that the path is closed and select the next one.

Answer 2

Look at this article: habrahabr.ru/post/162915/ . And this one: habrahabr.ru/post/166713/ . Together, like, what you need.

Answer 3

Try to read this note, it may lead to the right thoughts.