[ijdykeman]

> Is it possible that the algorithm will fail to find a suitable tile and needs to restart?

Yes, the algorithm can fail. Since it considers only local areas when making decisions, it can easily make a placement that dooms progress later on. The best way to guarantee success in a given amount of compute time is to make tile sets easier to solve, for example by making it possible to transition from any tile to any other in a few hops. But this limits the amount of structure in the output.

> I don't understand, why or how you get those rectangular ponds and lava areas in the first youtube video. I expected them to be far more organic or am I missing something?

It's possible to restrict the tile set so that only rectangular regions are allowed. You do this by creating only convex corners. Here's an example:

Imagine you only have 10 tiles. They are made up of Ground (#) and water (~), and you want rectangular areas of water.

your six tiles are

  ###   ~~~
  ###   ~~~
  ###   ~~~

  #~~  ~~#
  #~~  ~~#
  #~~  ~~#

  ~~~  ###
  ~~~  ~~~
  ###  ~~~

  ### ###
  #~~ ~~#
  #~~ ~~#

  #~~ ~~#
  #~~ ~~#
  ### ###

A valid tiling might be

  #########
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #~~~~~~~#
  #########

The above uses all tiles except the all ground tile.

I can extend that water rectangle in either direction, but I can't add a feature like

  #~~~~#####
  #~~~~#####
  #~~~~#####
  #~~~~#####
  #~~~~~~~~~
  #~~~~~~~~~

Because that bottom center tile that allows the bend in the water does not exist in your tile set. Adding more tiles like

> How would do you ensure connectivity of areas or points of interest? Any ideas? Would you path a way before or after running the algorithm?

Great question! Let's say you have points of interest A and B, sitting on the ground

  ### ###
  #A# #B#
  ### ###

You'll get a world with As and Bs scattered randomly. So let's connect them with a road (+)

  #+# ###
  #A# #B#
  ### #+#

Now you get worlds like

  ##########+#
  #B##B##B##A#
  #+##+##+####
  #+##+##+#### 
  #A##A##A##B# 
  ##########+# 

Repeating forever. But now add more road pieces

  #+# ###
  #A# #B#
  ### #+#

  #+# ###
  #+# +++
  #+# ###

  ### #+#
  #++ ++#
  #+# ###

Now you have roads that slope up and to the right, always starting at A and ending at B.

  ######
  ####B#
  ####+#
  ####+#
  #++++#
  #+####
  #+####
  #+####
  #+####
  #+####
  #A####
  ######

There are no dead ends because no road dead end tiles exist. Eliminating loops in the road while allowing any direction of travel is more complicated but possible.

[tmiahm]

This looks like a preview of Advent of Code 2022