Has anyone found an algorithm for dividing a random map into different regions?

Question

Algorithms

I am looking for an algorithm or solutions for creating regions in a randomly generated map. I am looking for a similar solution to increase the productivity of pathfinding algorithms. Has anyone found a similar algorithm? Which, looking at a new map, divides it into regions of large spaces, within which it is possible to move in a straight line, and if you want to turn when moving from any points A and B, then a new region would be calculated ... I

apologize if it is unclear to read ... An example of how I want to divide the map:

R - This is a large region that is subdivided into sub-regions within itself
r - sub-regions within which it is possible to move in a straight line

Original map:

Answer 1

more about Clustering
https://habr.com/en/post/101338/

I am looking for a similar solution to increase the productivity of pathfinding algorithms.

you can do all your preliminary calculations offline (i.e. at the map generation stage, not during the "battle")
as an algorithm - enter any rule (heuristic) that gives good results you need (and no one will tell you think, try)
for example
- in the first pass - loop iterate all cells of the same type (blue on the map, for example, let's say it's "water"), check the type of their neighbors, choose borders, say green / yellow (let's say "land"), according to the result of the stage you have large areas of the same "color" with their borders (you can use bounding box or convex hull or whatever for description)
- the second pass - you can divide large areas into smaller ones, for example, get r1, r2, r3 from your screenshot, from the original one (not in your screenshot, but consider that it is the sum of r1 + r2 + r3) .. by determining the maximum distance , let's say you take any border randomly - and from it you continue along the border until the limit is exceeded, or in some other way, while iterating your points inside the region, check the length limit to the initially selected border
ps and for the same purpose of search optimization, read
https ://www.redblobgames.com/pathfinding/grids/alg...

Answer 2

This is done by clustering algorithms. There are a lot of them. Find the right one for you.