I am making ai for turn based game and I want it to choose good positions for its units.

Algorithm I come with looks like this:

For each tile in ai unit movement range I calculate a Djikstra map (distances with pathfinding to every other tile). Then I calculate heatmap based on distances from this tile to points of interests. Then ai just move its unit to tile with highest points.

The problem is, that result I getting is too slow. My map consist of a lot of tiles and unit movement range can be big. I can't precalculate heatmaps, because units have different pathfinding on different terrains.

Can you advice me some algorithms for this problem?

The A* algorithm is the defacto standard way to go. It's like Dijkstra but tries to only compute paths in the “right” direction. As it does only a fraction of the tiles at the map, in general, it's much faster.

An alternative can be not to have exact distances to your points of interest, but just a guess. A guess can be created in many ways. One way is to have fixed distances (perhaps with the terrain as parameter?). Running A* might work too.

You can also run a few Dijkstra computations every turn, instead of all of them.

All of this also depends on how many units you have. If they behave in formations, you could perhaps compute it for one of the group?

Oh, and this exists too: All distances between all tiles in one computation https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

No idea how it works.

BipBop17 said:
or each tile in ai unit movement range I calculate a Djikstra map (distances with pathfinding to every other tile). Then I calculate heatmap based on distances from this tile to points of interests. Then ai just move its unit to tile with highest points.

If you have visualizations of those steps, it would be good if you post images.
I speculate there might be a way to calculate the heat maps directly, avoiding the need for Dijkstra.

@JoeJ Thanks for answering! To be short I want to get path distance from each cyan tile to every other tile(or at least only tiles with objects on them). Brute forcing Djikstra works fine in this example, but thats only because map is small and unit has small movement range.

@Alberth Thanks for answering! Djikstra maps are calculated only once per each turn and only for tiles in movement range, but I suspect it will still be laggy on big maps or with units with a lot of possible movement tiles. Also I tried to calculate distance maps only from objects of interest, but it could be slow if there are many of these objects. Sadly I tried Floyd–Warshall algorithm and it was also quiet slow((. I think maybe I should use some kind of quadtree or an approximate distances?

BipBop17 said:
To be short I want to get path distance from each cyan tile to every other tile(or at least only tiles with objects on them).

Assuming the cyan tiles are always around a unit, you could run Dijkstra from the unit to find paths to the nearby objects.
Then, check the neighbourhood of a cyan tile if there is a path and connect to it if so. If the tile finds no paths you could process it later again, after it's neighbours have eventually created new paths.
Leaving out some details, but this should give a good approximation requiring path frinding only once from a single spot.

BipBop17 said:
Also I tried to calculate distance maps only from objects of interest, but it could be slow if there are many of these objects.

You could do this with an diffusion approach: Each frame, add energy to a map from each object, then blur the map and reduce energy globally, so it does not overflow from future frames. That's constant time per map cell. It takes some frames until distant changes become visible, so there is temporal lag.

@undefined Many thanks! I will try these out!