Video

Glad the video helped :)

Thanks for the feedback. I tend to agree that there are a lot of things that could be done to make the terrain more interesting/realistic. I particularly like the idea of applying the algorithm at multiple scales. The purpose of the is video of course was just to be a relatively quick introduction to the approach, and a brief discussion of other application areas.

Great suggestion! I think Processing has a some interface libraries that include easy to use sliders. Part of my goal is definitely just to present a 'starter' project for people to build on. If you do extend it post a comment, I'd love to hear how it worked. I've seen projects that used more complex starting shapes, like letters, for the growth. Maybe starting with a simple maze and having this add twists and dead-ends?

I did it using recursion, draw a triangle, have it draw smaller triangles, etc. But I do vaguely remember seeing versions where the program places random points following some formula that leads to the same shape.

Thank you! I'm glad you enjoyed.

Thank you! I leave the errors in (and point them out) for a couple of reasons. I think it's a better representation of 'real' programming where we make mistakes, types, etc. I'm afraid that showing perfect coding is a little demoralizing, especially for newer programmers. And this way I don't have to rerecord over and over until its perfect :) I'm glad you appreciate the pointers to the errors. If you add this to your frame work, feel free to post another comment, I'd love to see it running.

Great comments and suggestions! The exponential function sounds very similar to simulated annealing. With simulated annealing the probability of acceptance of a worse solution decreases over time as the 'temperature' decreases. One question it raises is how to measure 'ugly' maps? They are obvious to the eye, but can we characterize them mathematically? Presumably the 'count' of terrain matters: only plains and forest isn't good. But what is the right amount of mountains (and high mountains) and water (and deep water). And the distribution also matters, maybe a specific distribution of clump sizes? If it were possible to measure that then you could do meta-optimization on the algorithm to tweak it to give the best terrain types. One question, as a I mentioned in the video, I found using high mountains and deep water as 'anchoring' terrain seemed to help. Have you experimented with that approach at all?

@@programmingchaos8957 the way I am initializing the terrain is kind of inspired by this anchoring approach. Since I use larger squares of a uniform type, so I am basically anchoring or biasing the algorithm such that it won't just end up in one of these very uniform solutions. This could of course be combined with what you showed in the video and I think it could be further improved. For example, if you make the squares quite big, the converged solution can have some straight long edges. So one thing that would make sense is to randomly blend over to the surrounding terrain types in this initialization to remove these patterns. I definitely remember watching videos on simulated annealing before. That might be where this idea came from, I felt like I knew about something similar where the exponential function was used and now that you mention it I think it was simulated annealing. Although I feel like I have seen these concepts in some Monte Carlo sampling strategies as well. The exponential function really is quite useful across many applications, recently I learned about how to use what is basically exponential decay for interpolating animations smoothly.

@@maxmustermann3938 I also saw some suggestions to try multi scale systems, a larger cell of forest that when zoomed in has more varied terrain. Which is quite a bit like anchoring terrain regions.

I'm glad you enjoyed it. Making the coding clear is one of my main goals so I'm glad to hear that you found it clear. The language is Java, not C, but at this level they are almost identical. The major difference is the arrays are declared as: int[][] map; // Java not int map[][] // C Global constraints are a great idea. I think the answer depends in part on the type of constraint. For example, if the constraint was no more than 20% forest then it would be easy to update a global counter as part of the constraint satisfaction algorithm. Every time you added a forest, add one to the counter, every time you removed a forest subtract one. But that's the simple case. For your group sizes constraint I think the only solution would be a separate pass over the whole map calculating the required statistics. But for a game this would only need to be done once at the beginning, so even if it took a while (tens of seconds) it could be hid behind a loading screen, tutorial, character selection screen, etc. Another interesting question is does this (at least for the power law) happen automatically with this algorithm? I could see where very large sets of terrain are increasingly unlikely. Or is there a way to seed the initial map to get a desired distribution? E.g. by placing random circles of forest that follow a power law.

@@programmingchaos8957 For the afforementioned algo.s, it's an emergent feature. Both of them are essentially cellular automata that update based on a local kernel passing over the grid element-wise with random fluctuations in cells, which would probably be more efficient than passing over the whole thing, checking the statistics and then making an adjustment and checking to see if the statistics are closer, etc. (plus I imagine that'd look more unatural), but scaling these things up is still a nightmare. I tried a while ago getting them to a good enough looking resolution, and it got to taking tens of minutes in Python (albeit using a less-efficient algorithm for it; but I kinda had to since I wanted to also track the correlation-length over time). The thing about the power law distribution is that it's scale-free, so you can zoom into any part of the distribution and it should be similar. This is really the property I'm interested in, because _in principle,_ if you have local information around some region in your grid, then that should also give you global information - but it only givees you the information about the distribution, not about how that distribution is realised. I just thought that it would be nice if I could exploit that fact to allow it to scale faster.

@@programmingchaos8957 Sorry, I typed a response to you, but it disappeared. The aforementioned algorithms are essentially cellular automata that check some local kernel around a cell and transform it depending on that calculated value. The power-law distribution is emergent from these rules. As they are, these algorithms scale pretty poorly both in space and (particularly of interest) time. There are more efficient algorithms that one can use (say for the Ising model), but you end up sacrificing some other things. It might be fine for the purposes of terrain generation, but I wanted to track the correlation-length of the whole system in real-time, which it looks like only the Metropolis algorithm was capable of doing. Nonetheless, I'm still unconvinced about the traditional approaches. I tried scaling these guys up before, and they took me tens of minutes on my machine with Python (I couldn't quite get what I wanted out of Numba; it threw a fit at me when trying to parse multidimensional arrays, so I shelved it. I know some C now, so I might revisit it in Cython). The thing about power-law distributions, is that they're self-similar at different scales - if you zoom in or out of the distribution, you end up seeing the selfsame distribution. Think: the Pareto 80/20 rule in economics: 80% of the wealth is in 20% of the population; 80% of _that_ wealth is in 20% of that population, etc. etc. Similarly, with these phenomena, if you zoom in or out of these grid-arrays, the group-size distribution is the same. This property is what's known as being "scale-free". This means that _in principle,_ we should have information about the global distribution of group-sizes from local information in some region. I'd hoped I could use that fact to kind of 'compress' the grid in some way, maybe to speed things up. I would say that with these algorithms, seeding can be difficult. What tends to occur is that the major groups end up moving around in non-trivial ways, making them unrecognisable from the initial seed. You can probably obtain utility out of seeding if you don't run them for a very long time, but you want to run these things for a very long time to obtain power-law results.

This sounds like a great idea. If you implement it I would be very interested in seeing the results.

Edit: sorry, my previous reply was thinking about another video I commented on. I haven't implemented this one yet, I was thinking of the procedural generation with constraints when I typed this reply out earlier.

That's great! I'm glad you're enjoying the content. I really need to find the time to try out GeoGebra.

Thank you! Your comment is on the differential growth video, have you checked out the diffusion reaction video: czcams.com/video/COMvgTLTw6g/video.html I think that is a model of chemical morphogenesis, although that's not the term I'm familiar with.

@@programmingchaos8957 ahhh! The equations are similar to the chemical morphogenesis! Fun fact this is prolly one of Turing's less known contributions but one of my favorite!

Thank you! Making sure the explanations are clear is one of my main goals, so I'm glad that's working. Keep in mind that dx can be negative (it starts as negative of the range), if x is small (e.g. less than range) then dx + x is negative and, at least in Processing/Java % of a negative is that negative value. E.g. -2 % worldWidth = -2, which will cause an array out of bounds error. So, the +worldWidth is to wrap the negative cases.

@@programmingchaos8957 Ah i understand, thank you The actual Modulo operator in maths is defined differently then, and i'm honestly not sure why it's done this way in javascript...

I'm not sure either. But I double-checked that -4 modulo 100 does return -4, not 96, which would make your approach work.

@@programmingchaos8957 Unfortunate :( But if Javascript does not follow the normal modulo definition + worldWidth is a clean fix for it

@@zitronenwasser Me neither. It's why I've gotten in the habit of testing the behavior of functions to make sure they act they way I expect. It's rare, but there's nothing worse than spending hours trying to fix a bug that caused by unexpected behaviors rather than a mistake.

Thank you! I'm really glad that it was clear and straightforward, as making the explanation clear and easy to follow is one of my main goals.

I'm glad you enjoyed the video. It's been a long time since I've use mpi, so probably can't help you there. But I would love to hear how it turns out.

Thanks! I'm glad to hear that the explanations are working - that's one of my major goals.

Hi! It's great to hear the degree is serving you well. I hope you're enjoying the work. As you can probably tell I'm still enjoying teaching :) And thought I should help a larger audience.

@@programmingchaos8957 You’re a great teacher and professor. Your research has always had my attention. I’m treating SE as a career, which has served me well, but I miss the science side of CS. I have a library of rigorous math, CS, and physics books and I’m trying to figure out how to be valuable in those fields. Your work is endlessly inspiring and accessible to so many. Thanks for responding, I’ll be watching all your videos on this channel this weekend. Thanks again for not only being a great teacher but also sharing your fascinating research and creative projects with students at every level, cheers!

oh this is an incredibly wholesome reunion

You're very welcome! I have to say that one of the huge advantages of being a professor (besides getting to teach) is the flexibility to try the random projects that seem interesting.

Thank you! I'm glad you're enjoying the content. If there's any topics you'd like to see covered let me know, I'm always looking for new ideas.

Thank you! 😃

Interesting idea. If the constraints necessary to make the algorithm work properly were well defined this could be doable. There is a field, genetic programming, that evolves programs to solve problems. Some of the ideas of fitness from that field might translate into constraints.

Thanks! I'm really glad you found it useful. Good point about flipping the camera. I should have noticed that during editing. Thanks for the suggestion.

Not exactly. In WFC values are only assigned if they don't violate any constraints. If the WFC algorithm finds a variable (cell) with no assignable values (e.g. mountains on one side and deep water on the other) it either backtracks, undoing and retrying some previous assignments to avoid the issue, or starts over from scratch. In contrast the minimum conflicts algorithms just assigns the value that leads to the fewest conflicts and hopes it gets fixed on a later pass, by changing some of the neighboring values. The least conflicts algorithm is simpler to code and runs faster, but if there aren't very many solutions it may fail to find a solution with no conflicts. WFC is harder to code and may take longer to run, but is more likely to find a solution when they are rare.

I hadn't thought about the relationship to Stable Diffusion, there is an interesting similarity. And yes a shader would definitely be the way to do this if you wanted it to be super quick or had a much bigger map. As you noted, my focus is really on teaching the algorithm. But it does make me think that I should put together a video or two on basic shader programming and its applications. Thanks for the suggestion.

You're very welcome! I'm glad you enjoyed it.

Great idea! I think it's been done on a smaller scale without machine learning using small, sample maps. E.g. take a small sample map, record what terrains are next to each other and which aren't, and use that to generate the rules. It can be done with any pattern, not just maps. But the idea of using ML and real maps is really good.

@@programmingchaos8957 That would be cool, generate the model and the constraints from real world data. But I imagine the hardest part is getting detailed maps and how to map real data to a constraint model, what features you care about etc.. It would be cool to do all this with hyperspectral satellite images, not just RGB. So you can accurately distinguish different types of terrain, vegetation and man made structures. And all that in 4D would be even cooler. Then learn to model the evolution of a river with constraint satisfaction 😄 Realistic world generation has always been my favorite computational problem to daydream about. I love to see all these different approaches on CZcams.

I think getting detailed images of real terrain isn't too hard these days. But if they need to be annotated for the ML algorithm to work that may be harder - although I'm constantly surprised at the amount of annotated data that's out there for free. 4D would be fantastic, not sure if the high quality data goes far enough backwards in time though. World generation is definitely fun. I particularly like the versions that add cities with random 'facts' or descriptions (much easier these days with LLMs), so you can image visiting them.

Writing the tests for the function is a great application area for an AI. I'm a little skeptical of the claims that it will take over programming. LLMs are great at problems that have been solved hundreds of times already, writing a resume, legal brief, or a quick sort algorithm, which makes them seem really impressive. But most programming projects should include some new aspects, requiring new solutions, which LMMs are not so good at. But generating tests for human written code seems like a space they would perform well in.

Good catch! It's very similar, but in minimum constraints the algorithm will assign values that violate the constraints with the hope of fixing them later. WFC traditionally will backtrack and undo some of its previous assignments (or start over) if it finds a variable (cell) with no acceptable values (e.g. no terrains that can be assigned without violating constraints). It means the WFC is more likely to find rare solutions, when minimum conflicts will just keep trying invalid values, but it also means that WFC is slower - and more complex to code. As a side note WFC is even more similar to (maybe identical) to the forward checking algorithm for constraint satisfaction.

Don't be hard on yourself. I've been coding for literally decades. And it still took me probably 6 or 8 different projects that used similar range checks to come up with that approach. I remember starting with 8 separate if statements, one for each neighbor, and each with it's own boundary checking conditionals, something like 24 if's altogether :)

@@programmingchaos8957 That is a bit relieving! Thank you for the Video :=)

Your welcome! I'm glad to hear that the explanation was clear, that one of my major goals in these videos.

This minimum conflicts algorithm is willing to assign values that violate constraints with the hope of fixing it on a later pass. My understanding is that WFC won't assign a value that creates conflicts. If it reaches a variable that has no valid assignments it backtracks and undoes recent variable assignments and tries different values for those variables hoping to avoid the conflict (or it starts over). This makes WFC much better at solving problems with very few solutions (like sudoku) and it potentially can report that a problem is unsolvable (there is no valid set of assignments). However, the backtracking is trickier to code and it's potentially much slower. So, if you know there's a lot of solutions available, which is typical for procedural generation, this minimum conflicts algorithm is simpler and faster. But if there are relatively few solutions available WFC or other exhaustive search algorithms may be necessary to find one of the solutions. As far as I can tell WFC is very similar (identical?) to the forward checking algorithm for constraint satisfaction.

Thank you! And that's a great idea! Painting in the rough map to start with, 'I want a mountain range here, a deep lake there, a massive forest in the North' and then letting the algorithm fill in the details, and then being able to go in and re-edit, clean up shorelines, merge mountain ranges, add mountain passes, etc. would be fantastic.

Thanks! I agree that that makes it much more interesting. I think its sometimes referred to as a falloff map if you want to learn more about how it can me done.

So, the map isn't decided at all until the player moves into the new areas? That would be interesting, especially if the player's actions influence what appeared next. So, the terrain would have to follow the rules, but if a given cell could be either plans or forest which one it became depended (in part) on the player. For example, if they traveled from forest it was more likely to continue as forest, or they had some ability to influence the probabilities. If you make it Ill play it! :)

@@programmingchaos8957 I didnt' think that far ahead :) I had an idea of the maps generating in a 2D platformer style. Having some gameplay elements advance the generation sounds more viable. Making a game out of that would require some serious deep thinking....

Your very welcome! I'm glad you enjoyed it.

Thanks! I'm thrilled that you enjoyed it. Hopefully the other videos will be useful as well.

Thanks! I'm very glad your enjoying the videos. If you have an ideas for projects you'd like to see video on, please feel free to let me know.

Exactly my thoughts!

Thank you! I'm really glad the explanation was helpful.

Thank you! I hope some of the other videos are also useful. And if you have suggestions for topics, please feel free to share them.

Very cool application! It is surprising how many problems can be reformulated as constraint satisfaction and then there's well defined solution approaches.

@@programmingchaos8957 Indeed. I believe that they sound too formal to be used out there. That's why we don't see more of it. In more important projects or fields, I believe this method is treated with more importance. I wish I could work with it.

Glad you liked it! Procedural generation and artificial life (especially evolutionary alife) are my two favorite programming areas.

Definitely! I was thinking my approach was a bit easier to code, and was trying to keep things simple. But removing items in a random order from and ArrayList would be pretty simple. Languages with a built in shuffle function would also work well of course.

Thank you! I'm glad you're enjoying it. If you have any favorite projects you'd like to see coded let me know.

People used Rule 30 as a pseudo-random number generator for a long time after it was developed. pRNGs are all like this, so there isn't really a material distinction between Rule 30 and other methods like it. Also it's not correct to say pRNGs are biased. If they were, we could detect it by running it a whole heap of times, and generating the empirical distribution for the frequency of numbers it generates, and test to see if it's significantly different from a uniform distribution. We use pRNGs _because_ there is no test we have yet developed that can distinguish them from true RNGs. All we know is that they will eventually cycle, because they are determinate.

Very interesting idea! It would be possible to go through and calculate the 'next' value, but not update it until all of the next values were calculated. This is the standard approach for cellular automata like Conway's Game of Life czcams.com/video/SgrenppLn8c/video.html. Of course, it could lead to the problem of picking conflicting choices for neighboring cells and having to fix it on the next iteration. It might give interesting results for the plants, not sure if it matters for the maps or textures. I understand wanting everything to follow solid, deterministic rules. The issue with purely deterministic rules is that they will always lead to the same outcome and I want different outcomes each time. I could use deterministic rules with (pseudo)random starting conditions, but that might give a smaller range of outcomes (and doesn't completely do away with randomness). I prefer to think of the (pseudo)randomness as representing unknown hidden variables. For example, coin flips are not truly random - in the sense that if you knew the exact forces being applied at the beginning of a flip then a physics simulator could tell you whether it would be heads or tails (and I believe that accomplished slight of hand artists can flip a coin exactly N times to control whether its heads or tails). But if I want a coin flip in a game I'm just going to randomly determine heads or tails, not build a physics simulator for coin flips. This is the same idea, for plants I'm not going to try to simulate all of the factors that cause a plant to branch or not, I'm just going to choose to randomly branch. However, that's because of my relatively simple goals. There's probably a good use for a program that does simulate all of those factors. (And a mini-game where you try to apply the forces to get a coin to flip exactly N times might be fun.)

Few, if any, pseudo-random number generators are biased in the sense of generating more 8's than 9's. But all(?) have artifacts that can be detected with subtle statistical tests. The Wikipedia article on pseudo-number generators has a nice overview of some of the issues. My understanding is that because of this for super high risk areas, like generating encryption keys for launch codes, they use hardware random number generators that use physical phenomena, like radio static, to generate random values.

I'm not sure. I think it's very unlikely for this algorithm to get stuck in a literal loop because it's making random selections to resolve conflicts. So, to get stuck in a loop it would have to be a condition where there are only a few options that it cycles through. On the other hand its very possible for it to search endlessly through different terrain assignments without every finding a conflict free solution - it's just unlikely to loop. There are other systematic conflict resolution algorithms that never get stuck and can say whether or not a solution exists, but they are much slower and because they are systematic, don't lead to interesting terrains. They are useful for problems like sudoku, where there are very few solutions, or if you want to know if any solution exists.

Nice idea! I think that would be a bit simpler.

That's sounds really cool! I'd be interested in hearing about how it turns out if you want to share the results.

A faster solution using multiverse theory would be: generate_random_map(); if (!is_map_valid()) destroy_universe();

@@Erkle64 True, but my computer can't destroy the Universe yet :(.

I'm not sure about perfect, but one formal term is 'complete'. A complete algorithm is guaranteed to find a solution if one exists and return false if no solution is possible. The minimum conflicts algorithm I presented is definitely not complete. It is only find likely to find a solution if lots of solutions exist - which should be the case for procedural generation. WFC can be complete if every time it reaches a variable the no longer has a valid assignment (e.g. a cell between forest and deep water) it backtracks, undoing previous assignments and trying new ones until it solves the conflict. But that type of exhaustive search tends to be a lot slower. With regards to probabilities I suspect, but don't know for sure, that both minimum conflicts and WFC collapse create terrain that's 'clumpier' than your algorithm would produce. Because the easier to find solutions have large clumps of the same terrains. In fact, if a map problem is hard (for example if the range where the cells can't conflict is large) the minimum conflicts tends to 'give up' and just push everything towards a middle terrain like plains.

I want to live in the universe where all of my code compiles and runs correctly the first time. But I suspect that even in an infinite multiverse that one doesn't exist :)

@@programmingchaos8957 By "perfect" I don't mean a program that finds a solution, but it also needs to have the same probability distibution as the orginal algorithm

yup

Very similar, but not quite the same (I'm pretty sure). With minimum conflicts the algorithm will assign a value (terrain) even if it violates constraints. With WFC it will only assign conflict free values, if there's a variable/cell has no acceptable values left, WFC will backtrack, undoing past assignments, and try again (or will start over from scratch). This means that WFC is more likely to find a solution if they are rare, but can be much slower. WFC is, as far as I can tell, identical to the forward checking algorithm that is used for constraint satisfaction.

Right! But this is the drawback to local search, because it's fairly random there's no guarantee that it will find a solution even if one exists (technically its an 'incomplete' search). So, the best you can for termination is stop after a lot of tries. The assumption is that if you are doing procedural generation there should be a lot of possible solutions and so the algorithm will find one. If there's only one (or possibly no) solutions it's better to use a complete search algorithm, but they can be harder to code and a lot slower to run.

I'm glad you enjoyed it. The dying and respawning is clever idea, I'll have to give it a try. Thanks for the comment about N*Max. I tend to fall into the habit of using the same tools even when they are not ideal. In this case I had been using map() a lot and didn't stop to think about the simpler approach.

Thank you! I'm glad you're enjoying it.