"Creativity is the ability to introduce order to the randomness of Nature" - Eric Hoffer
Foreword
So this is a bit random for my blog and is likely to be spread across multiple posts as it is fairly large. In the background, I am working on my AI project which is likely to never be over and I am reconstituting some test data after a bug in the code didn't save it properly (d'oh!). I was this week going to start a series I am calling "Defending Dilbert's Boss" about the effects that bad practices with data have on businesses but I found there is a huge amount of stuff going on there and wanted to spend some more time on it. So I am, the effects defaulting to a thing been working on quietly in the background.
Previously in the past, I have often suddenly had the feeling of I wish I could make this game idea, though it has always had the unfortunate problem that I didn't know how to build a randomized map, and usually after writing a few classes and creating a few betas I would give up. The problem was simply my ability to write effective procedural generation for such a mock-up was nonexistent and while I knew enough about object-oriented programming to generate a set of classes that would have the behaviors I wanted I did not have the knowledge base to build enough random variety to give it much interest.
Therefore I have been in between the other aforementioned projects running a series of tests to build a map generation program.
The product of which is below.
Features it has:
So I am planning on splitting it into parts of which I list the below steps (but this won't be a 12 part series) which I may later group back up into sections that make sense. This article will deal with part one generating noise and the different methods used. This way I can get through with this in weeks when I am still playing catch up with other projects and me. Regardless I think eventually there could be a game idea for this that can get written up in C++.
1 -Generates a map of noise using a pseudo-random number generator that I wrote myself. This is generated from seed, so I get the same map results if I set the same seed. The random number in this place is roughly equivalent to land level.
2 -Generates several land centers based on the highest values within the noise.
3 -Uses Lloyd's relaxation to shift the centers around so there is no clumping up.
4 -Creates tectonic plates by splitting up the map between the highest land points into sections.
5 -Adds seas to the side of the map and along the meeting points of the tectonic plates to create the seas in-between the continents.
6 -Groups the map into cells and builds a matrix of how the locations connect.
7- Apply erosion so tiles with less height and adjacent to a sea tile also become a sea tile and then use recursion.
8 -Take the top 20% of height generated from the noise and designate them as mountains
9 -use the matrix generated above and the sea list in step 5 and run an A-star algorithm to work out the fastest route from the mountains to a sea tile and therefore creates where rivers form.
10 - Use distance from the poles and the distance from rivers to estimate temperature and moisture and designate what type of biome it should be. The biomes are SNOW (less than 25% temperature and 50% wet), Mountains (Top 20% of height), Tundra (Cold and dry), Grasslands most places not at an extreme, If extreme hot and wet becomes a rainforest dark green and if hot and dry becomes a desert.
11 - Generate a randomized language weighting the consonants so that some are more common, assign finals, sibilants, choose a randomized syllable style and generate 8 monoheme's to form the basis of language. Generate consistent rules for handling silent vowels which happen when a letter appears twice in a row. Random languages are weighted so some use short words others very long words
12 - Assign random names using rules so each cell gets a random name.
13 - Display!
1 -Generates a map of noise
So I needed random numbers lots of random numbers and needed to think about how would I generate them. I had started knowing if I ever wanted to build games I probably would need to understand pseudo random numbers, and how to generate noise. I had written a pseudo random number generator before but never thought about it beyond that.
I started from the ignorant position of believing procedural generation was just pseudo random number generation. How hard could it be?
I Built A Dungeon
So It turns out you cannot make a land mass pf lakes, rivers, and seas from random number generation. They don't pool in the right places constituently. Though and If I ever did this again I wouldn't do it this way again I would probably use random numbers to generate room positions then door positions and the connect up the rooms like the original rogue. Though for reasons I cannot explain in hindsight I decided the whole map would be a grid based random number generation system that would rerun every time you took a step and be fast enough to do this in Python... Then equally strange I proceeded to do this...
I made a dungeon generator that generated the whole dungeon in time as you moved... Not rooms and connect the rooms like everything corridors and rooms where generated from a simple algorithm.
So my noise algorithm has a long gestation period which started with my piece on pseudo-random number generation but I had kept changing. At one point I thought I would have to give up and adopt a different approach. Below is the code I ended up with and it has changed a few times but you get the idea that it is intended to generate a noise field where the value at any point is primarily calculated from the X and Y coordinates that represents that point.
I had briefly tried to use this idea to build a roguelike game the prototype which is below. Every step would cause every square on the edge to move and be refreshed. This created a map that was essentially a large treadmill as you stepped forward more space was added in front by the random number generator and removed behind you. If you were to step back then the random number generator would take the same numbers and recreate the parts that it had only a second ago deleted and had ceased to exist.
The problem with this was when I started planning how enemy AI would act on this map as I realized the AI could not use planning as there would be the complexity of keeping track of that plan and the moving map that existed around them. I am sure I could have come up with a solution but I had originally envisioned an alien-like game with the alien tracking you and following scent trails which would become complicated if they also needed to be moved with every step, therefore the AI would probably have been much more simple.
Despite this, it is a concept that I am keen to return to, and building this map has furnished me with better skills to try this (I have a lot of those concepts I need to start delivering). Though I think this also shows why I do this now if I had gone I wanted to build a game where an alien stalks you in a ship I would have been able to think about building it as a series of maps though the below could be reutilized but didn't fit the cataclysm dark days ahead vibe I had in mind at the time due to the complexity of pseudo-random generating a whole map per step but would be easier if chunk up the map and plan the project out better.
Lesson learned sometimes the art is planning the project, not the algorithms themselves.
Spot the difference? What a difference a few steps make! It also uses line of sight algorithms for working out if can see a space on the map and whether it should be painted in. Hard walls are dark grey. Paths are light grey.
Perlin Noise
This had a surprisingly long genesis starting with this noise app that I built that was to generate random mazes using a grid based system to define the random number generation. You can see how I probably came up with this idea while staring at the earlier noise generator.
I think it was the Nietschze who wrote "stare long enough into the Noise and the Noise stares back at you". He could have said Void but you get the idea generating lots of different noise fields and thinking about how you might interpret them is what led me to create the above.
Making A Dungeon
This then led to the Rogue test which shows the below lit without the line of sight rules being applied so you cannot see the spaces out of view. It is interesting to me how an algorithm completely unrelated and unintelligent can stand in for something. The mind automatically associates straight lines and paths as being paths rather than random numbers.
The code for the function that draws the below is this: You can see that it takes the X and Y coordinates for the grid location and then generates a random number which indicates to the machine whether a position should be an open space or blocked off the wall. Because the X and Y coordinates are what generate the location the values can be retrieved when the character walks backward.
The raising to a power of 3 is important as changing this value drastically changes the map and most places results in something that doesn't look like a dungeon. I have created strange non-dungeon spaces using different powers.
def random(self,x,y):
self.m=1000
self.x=(((x)**3)+((y)**3))%self.m
self.x2=self.x/self.m
return self.x2
Visualising Noise
Noise looks like the static you get on old black and white TV. The picture below is a example. It is produced by below function which takes the X and Y grid coordinates and a value called funk which in this case is incremented with each new value.
I had chosen this because the aforementioned grid based method used for the dungeons was a bit unstable with the power method and I had hoped to create something where the values produced created pooled areas of green or blue in sections.
This type of noise is much more in line with traditional ways of doing procedural generation. We can generate noise for a whole area to assign random numbers for all the points and then interpret them afterwards. Usually; and this is what I did in my map generation was use the values to represent height or some other idea of what to centre important features on.
i.e. if I was to start again on the dungeon I would generate a map as a noise map, generate the centre (and perhaps sizes) using the larges points on the map. I might use the same noise or another one to decide various ideas about what that room was. I would then use a pathing system or some other rule based process or maze generation algorithm to join up the rooms and add corridors between them.
This is how I generated the below noise.
CODE:
def random(funk,x=10,y=20,m=200):
x=(x*y)%1024
y=(y*funk)%1024
funk=(funk*y)%1024
x=(x+y+funk)%m
return x/m
Tuning Channels
I used a value called I that multiplied the X and Y grid coordinates and gave them weight. The idea here was a small coefficient should open up the pooling in the noise so you would get blotches of blue or green. My idea was this could then be used to generate chasms in dungeons or islands in the sea.
The way I applied this was on calling the function: random(funk,x=(x1*i)+x_seed,y=(y1*i)+y_seed,m=m)
In this, I was semi-successful I could play with the dials on the screen and get different types of noise which I could then use for different setups the problem is a bit like the same noise on a TV you could tune it and get strange oscillating patterns like the below. I finally decided this was probably not something I would be happy letting players use so If I was to implement this in a game I would only provide an X or Y seed for players to manipulate the map generation.
Conclusion
So I would say my initial getting to know procedural generation from pseudo-random number generation was a bit of a rocky start. But I ended up making a map and a dungeon at the time I felt very frustrated but now think I could try randomly generating most things.
I also could have made the above map look prettier. I hadn't broken out the color wheel. I hadn't applied any noise to pixilated it. Though it more came about as my one frustration was whenever I had an idea if it was to do with games I would instantly go but Joe you cannot make a map and eventually, I would give up.
This at least ends that excuse...
This was confusing for me I expected Noise to be simply something that would just generate and play with. Instead, I found that there were lots of different parameters and I could get massively different maps from small changes in the maths. While I eventually managed to build a whole island map generation system using Veroni cells and I abandoned using Noise to generate everything I am glad that I spent the time to try writing a few different noise algorithms.
Noise is important but I learned the hard way that it is not enough to generate random numbers you need to do something with them and concede there is an art to interpreting them and connecting the dots. I had at the beginning been largely ignorant of Veroni Cells and the other algorithmic aspects and had kept assuming all I needed to do was understand noise better.
I realized procedural generation is more of an art than a science I had naively at the beginning thought would generate noise and it would come to me. Instead, I had many abortive attempts to write algorithms and see what would happen. The dungeon algorithm in particular was interesting as it came about by accident staring at random numbers and trying to interpret them in a layout.
I think if I did the map generation again I would use a pseudo-random number generator not the noise function I wrote. Though the dungeon generator is interesting as most of the guides I read in researching did not mention random number generation from grid coordinates. While it probably would be frustrating to code the agents who would populate such a game it might make an interesting game for an eternal scrolling map with no need to load.
I could imagine some sort of survival roguelike. That being said as already said the AI could not hold complex plans about pathing and you wouldn't be able to recreate the full matrix to implement an A star pathing algorithm every tick as the map changed. This I think is why most games that use procedural generation create worlds in chunks, maps, or rooms as it doesn't have the overhead of tearing it all down every step.
Though it might be something to come back to think about what AI could be implemented and I like the idea of no loading screens just traveling across a dungeon map and dealing with random encounters as they happen. I think it could be a challenge to think about what you could do to build emergent storytelling in such a liminal space. I think it is a flawed idea but flawed ideas sometimes lead to creative thinking.
I still have my map to finish and when it's done I have a trade and market system that will implement and hope to then scale into a game. If you read my blog post about the stock AI I am always interested in economics and always wanted to build a game concerned about economics.
I realize this isn't a full guide to building a map but hopefully, you will find it an interesting place to start with procedural generation as you can see there is a lot about using random numbers and noise that can get you thinking.
CODE:
This was the initial code I wrote I went through a lot of improving and simplifying so the below is not optimal.
def generate_map(x=950,y=650,i=0.1,x_seed=100,y_seed=3,m=10,funk_seed=10):
new_map=[]
funk=funk_seed
for x1 in range(x):
row=[]
for y1 in range(y):
funk+=i
row.append(random(funk,x=(x1*i)+x_seed,y=(y1*i)+y_seed,m=m))
new_map.append(row.copy())
return new_map
def random(funk,x=10,y=20,m=200):
x=(x*y)%1024
y=(y*funk)%1024
funk=(funk*y)%1024
x=(x+y+funk)%m
return x/m
Update On The Neural Network
So this is my AI test discussed here Hello World - Measures Of Language Skill | A Logic Called Joe (webador.co.uk).
So brief update on the neural network and to show why I am delaying. I have tested 7 different versions and the current versions I am looking at seem to be performing a few hundred times better at learning English than the original. The below scale shows one of the weaker versions but the one I have the most data for shows it is getting a score of 220 on my Bayesian Turing test.
To clarify the test is logarithmic by a factor of 10 and say a score value of 6 roughly equates to the AI saying something of which it had a chance of 1/1,000,000 chance it was a truly random number generator. 220 is not a bad score when considering it represents the random chance of this happening being 1/(10 ** 220) and which is itself a number getting towards causing an underflow error in python.
Given this is a form of entropy calculation it is both possible and valid to calculate the total information in the book that the AI is being tested on which is around 30,000,000. This is if you have ever asked about the chance of a monkey randomly typing out something like the complete works of Shakespeare it's probably after 10 ** 30,000,000 times they would randomly do it.
Though my idea here the output appears exponential and therefore theoretically even with what is written so far if that remains true I might be able to write an instance of an AI that understands English on my computer. I realize that seems somewhat crazy but put in perspective A) I have seen it now use words related to a person's "he", "I", and "him" which feels as if indicates an ability to understand agency. B) I recently and briefly saw my first connective words like "are". C) it is not rereading any book and is learning these things in a short training method. D) the likelihood this would happen randomly is extremely low. E) the network remains very small relative to other tests done and I could start scaling it up tomorrow but whatever I would try would probably require trying different sizes and so measure twice cut once...
But let's say it all continues to scale well and learns more and more from reading one book, as long as it leaps connecting meaning between words (a big if)
Add comment
Comments