2D Dynamic map generation

Obviously this is not the only approach, but it's a pretty simple way of doing this:

Start with the smallest logical unit. Assuming you want territory shapes like what we see in the video, the smallest unit might be the narrowest possible strip of land. The average territory might be about 50 of these units in a randomized shape. Let's call them "tiles".

Next, consider the smallest "chunk" of land you'd ever want. A chunk should be a square of tiles big enough to occupy a whole screen, and will probably contain parts of multiple territories.

Now instead of generating an infinite map, you only need to generate one chunk at a time. For each chunk, pick some semi-random tiles to be like the capital of the territory. Territories can grow out from the capital by selecting adjacent tiles in a semi-random way.

Chunks must also know about their neighbors, if only to allow territories to be "closed off" without boring straight edges. Ask your neighboring chunks if they have any territories with boring edges, and allow those territories to participate in this chunk's grow-out-from-capital algorithm.

You always want to store the minimum amount of data from each chunk. If you use a seed-based generation technique, theoretically all you need is the seed. However, in most cases this is not really enough, so you'll need a strategy for remembering information about each territory / capital so when you come back to it later, it will remember any changes that were made to it.

When you're moving around and getting close to the edge of the generated world, simply generate new chunks for the empty area you are about to enter.

There are more sophisticated ways to approach infinite map generation, but this will hopefully give you some idea of where to begin. Even if you don't like the rest of the strategy, the idea of splitting the world into chunks is probably a smart plan.