The game Noita has a relatively low effective complexity. The game is a single physical map but it is separated into different areas that follow different sets of rules. Though every pixel in the game is simulated and can have an enormous quantity of physical effects applied to it, little of that can happen without some sort of direct or indirect action from the player. Therefore the environment itself, while topographically randomized is still relatively consistent from one generation to the next.
The Problem of Creativity:
I think that generative art pieces are absolutely creative. Far more so than much of photography in my opinion. With generative art pieces, you have to start with a completely blank slate and come up with something entirely new, while with much of photography you are already given the infinity varied masterpiece that is the world at large. Even if you are not drawing the art itself, you are still responsible for the machine, the virtual robot, that creates that art and you have an intent for what that art should look like. Therefore, generative art pieces are creative as without someone with vision to create the piece, there would be nothing to look at.