Announcement

Collapse
No announcement yet.

Map Generator- Please Critique!

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

    Map Generator- Please Critique!



    I am creating a rather vast and complicated map generator and I am looking for some constructive feedback regarding my methods. If you can provide any help or insight I would greatly appreciate it!

    Disclaimer: I am not a programmer but I will eventually get this into the source one way or another(for performance). At this time I am trying to prototype the generator while simultaneously learning how to use blueprint. This generator will be greatly expanded over time as tile types are ~doubled/tripled, functionality is added, and generation becomes more complex/intelligent in general.

    Image 1 is basically the entire generator in it's current state. Here is a general order of operation and explanation of each general area:
    1. Meshes are applied to my terrain variables for later use.
    2. (Image 2) The Vector Field Generator determines the vector for each hexagon in the map, and inserts the vectors into an array that I have visually represented.
    3. (Image 3 & 4) Immediately after the Vector Field Generator, Sequence 1 leads to the Biome Generators which generate vectors based on latitude and longitude principles such as continent, climate band, etc. The vectors are fed into Arrays based on tile type(Desert, Jungle, etc) for use in the Biome Locators.
    4. (Image 5) Once the Biome Seeds have been generated, the Vector Retriever retrieves the vectors previously generated and store in Vector Field, loops each individual tile through the Biome Locators, and finally on to the Biome Placer.
    5. Before the Biome Locator is a function that sets the Climate Booleans and a set of branch macros that determines what climate band the tile about to be placed in, thereby reducing unneeded loops. Tropical, Termperate, Arctic, etc. This makes it so that loops aren't called on Desert tiles when the tile is being placed in the Arctic.
    5. (Image 6) Once in the Biome Locator, it is determined which tile type is closest to the tile currently being created. If the tile is closest, it sets the "Nearest" variable to be that tile type, and then it sets the Dist variable to equal that shortest distance so the next biome locator can reference against it. There is 1 Biome Locator per tile type. Currently each iteration is only filtered based on climate band. My next objective is to filter by longitude and overall sector so that it only looks for Seeds that are within say 3-5 tiles when generating instead of across the map.
    6. Finally, the tile is generated based on whatever Biome Seed was Nearest after all the relevant loops were run.

    Image 1 - The Generator


    Image 2 - A visual representation that shows how the Indexes in my Vector Field variable correspond to the Vectors. This was absolutely invaluable for the math!


    Image 3 - East Continent Biome Generator


    Image 4 - Grassland Biome Generator for East Continent


    Image 5 - The Vector Retriever (First loop for the actual map generation.)


    Image 6 - Biome Locator for all Grasslands. Checks each tile to be generated against all Grassland Biome Seeds(if they are in the right climate band).



    Note 1: Map Size is 10, and scales in increments of 10. Each time the Map Size doubles, the number of tiles quadruples. All math takes into account the scalable Map Size Variable.
    Note 2: More variables for Temperature, Humidity, Tectonic Age, etc will be added and everything will have to scale accordingly.
    Note 3: I currently have 6 tile types. Plans are for ~8 base types, multiplied by vegetation, multiplied by hills, and later further multiplied by resources. Each additional Biome Tile increases the complexity and number of iterations significantly.
    Note 4: Once I filter for Longitude or sectors, the number of iterations will decrease significantly, but not enough to drop below the iteration limit for medium and larger maps. Currently, Iteration Limit of 1,000,000 iterations is being hit on the Map Size 20, or 800 tiles.
    Note 5: All Index related math is run against the Vector Field index(Image 2) and scales to map size.
    Last edited by Zeustiak; 06-08-2014, 08:26 AM.
    Map Generator 1.0
    Map Generator 2.0
    Map Generator 3.0

    #2
    Here is a zoomed out view of my Climate Flow Enum Abomination:

    Precipitation = Arid, Semi-Arid, Moderate, and Wet

    Vegetation ranges from Desert to Jungle, Ice to Boreal Forest, and everything in between. There are ~10 basic vegetation types.

    Right now it is just high level thinking, but I will implement it when I have solidified a few other systems.
    Last edited by Zeustiak; 06-08-2014, 08:26 AM.
    Map Generator 1.0
    Map Generator 2.0
    Map Generator 3.0

    Comment


      #3
      This is really impressive I must say thats why I thought I might try to help with some input on this base system, so firstly great work

      Now the first issue that I saw was the fact that there are fixed east/west type biomes, now if I were to do something like this myself I would try to make it more procedural and randomized in that it could support different types of land masses and not just continents but ofcoarse its possible this base system could be expanded upon.

      Which leads me into the next point, whilst this system might work well currently I do think it could be made more adaptable, a primary example is how the entire pole sections are pretty much solid with no actual depth to their shapes.

      The way I would have approached this is probably similar but I would have generated an entire set of blank tiles first, these tiles would have held an enumerator to their location in comparison to the equator, this would have been assigned mathematically when the initial two dimensional array (grid) was generated. As you can see on your generated table you can see the pattern it makes so you dont actually need to generate that because you know 5/15/25 etc are close to the equator at a height of 10.

      In terms of the tiles and what type of tile they are I would do that within the tile itself and do something of a growth algorithm by checking the nearest neighbors to a select depth, this allows creation of land masses, peaks and beaches where you would expect. Ofcoarse there is always rivers and inland lakes but these can be taken care of as well, I would give tiles a height so Id know that taller peaks would also be snow like the poles so it might even lead to a more three dimensional array.

      Im really curious about these biome placers, do you really place each tile in random order rather than just switching their "theme"?

      Comment


        #4
        Originally posted by MonsOlympus View Post
        This is really impressive I must say thats why I thought I might try to help with some input on this base system, so firstly great work

        Now the first issue that I saw was the fact that there are fixed east/west type biomes, now if I were to do something like this myself I would try to make it more procedural and randomized in that it could support different types of land masses and not just continents but ofcoarse its possible this base system could be expanded upon.
        Thanks!

        Actually, my first iteration of the biome placement was random, and it was fairly decent, but I chose a more tailored setup so I could test map control as I iterate.

        Realize though, that in a Civilization type game, you will have many map types to choose from. The version you see is a map with 2 generally equal continents. To do a Pangea, I could switch out the Biome Generator and do a Pangea setup. I can have a hundred generator types, and the user chooses from them. I could even make a randomized earth map replica just by fine tuning the biome generator.

        Originally posted by MonsOlympus View Post
        Which leads me into the next point, whilst this system might work well currently I do think it could be made more adaptable, a primary example is how the entire pole sections are pretty much solid with no actual depth to their shapes.
        It is actually very adaptable. In order to grow the poles out, all I have to do is reduce the number of water seeds that generate between the pole and the continent. It is as simple as that. For instance, I could reduce water in the north tundra while leaving it the same in the south. This would create something more akin to the Earth, which has open ocean in the south, and vast tundra in the north.

        Originally posted by MonsOlympus View Post
        The way I would have approached this is probably similar but I would have generated an entire set of blank tiles first, these tiles would have held an enumerator to their location in comparison to the equator, this would have been assigned mathematically when the initial two dimensional array (grid) was generated. As you can see on your generated table you can see the pattern it makes so you dont actually need to generate that because you know 5/15/25 etc are close to the equator at a height of 10.
        Generating the blank tiles has been on my mind for a bit now. I would then go behind and instead of placing tiles, it would be instancing materials.

        My array already keeps the vector information, and I was planning on having other arrays in the future to place actors into another array so I can reference what tile type is in each location.

        Can you show an example of how you would use an enumerator in this case? When I looked into enumerators prior to arrays they didn't really do what I needed them to but I may not have fully understood how to use them.

        Originally posted by MonsOlympus View Post
        In terms of the tiles and what type of tile they are I would do that within the tile itself and do something of a growth algorithm by checking the nearest neighbors to a select depth, this allows creation of land masses, peaks and beaches where you would expect. Ofcoarse there is always rivers and inland lakes but these can be taken care of as well, I would give tiles a height so Id know that taller peaks would also be snow like the poles so it might even lead to a more three dimensional array.
        Do you have a link to any code examples of this kind of generation?

        My general idea for coast generation and other similar tasks was to do a neighbor check to determine which mesh/material and what rotation it should use for proper placement. In the current setup my tiles are not referencable and it is something I will have to address sooner or later. By placing tiles first, and then changing them later this also allows me to do such checks and mesh swaps after every other tile type has been decided. Once the generator knows water will be placed in a certain hex, and land around it, then it can say use WaterMesh17 or whatever with Rotation Z in order to align the coasts.

        Rivers are another thing on my mind. It seems like splines are the normal method of river type placement in games like these, but from what I understand splines are somewhat under-developed in the current engine, for things other than landscapes. I am not in a rush to implement rivers, but I see a good method for generating and referencing them I will certainly see if I can use it.

        Originally posted by MonsOlympus View Post
        Im really curious about these biome placers, do you really place each tile in random order rather than just switching their "theme"?
        This was just how I got it to work in the first place and I have spent more time on fleshing out the random generation than I have into looking at upgrading the actual placement process.

        If you have a good method I can use to reference the field of blank tiles, I am all ears.
        Map Generator 1.0
        Map Generator 2.0
        Map Generator 3.0

        Comment


          #5
          Originally posted by Zeustiak View Post
          Thanks!

          Actually, my first iteration of the biome placement was random, and it was fairly decent, but I chose a more tailored setup so I could test map control as I iterate.

          Realize though, that in a Civilization type game, you will have many map types to choose from. The version you see is a map with 2 generally equal continents. To do a Pangea, I could switch out the Biome Generator and do a Pangea setup. I can have a hundred generator types, and the user chooses from them. I could even make a randomized earth map replica just by fine tuning the biome generator.

          It is actually very adaptable. In order to grow the poles out, all I have to do is reduce the number of water seeds that generate between the pole and the continent. It is as simple as that. For instance, I could reduce water in the north tundra while leaving it the same in the south. This would create something more akin to the Earth, which has open ocean in the south, and vast tundra in the north.
          Im still having alot of trouble knowing what youre doing here because each piece is being sliced up and its hard to see the flow of execution which was my main reason for wanting to see, to help minimize the number of iterations because they will largely determine how long it takes to generate a map.

          I guess I just look at things alittle differently in that I start with this vision of water everywhere, then I have visions of deep water cracking and pushing the shallow sands up through the water to form continents then on the islands and continents formed you get mountains and peaks, hills and rivers.

          Originally posted by Zeustiak View Post
          Generating the blank tiles has been on my mind for a bit now. I would then go behind and instead of placing tiles, it would be instancing materials.

          My array already keeps the vector information, and I was planning on having other arrays in the future to place actors into another array so I can reference what tile type is in each location.

          Can you show an example of how you would use an enumerator in this case? When I looked into enumerators prior to arrays they didn't really do what I needed them to but I may not have fully understood how to use them.
          I guess what Im trying to say is that a 2D Array is a 2D vector already so you dont need to generated that information, its one of the best bits to make entirely procedural. I know from your table that any index ending in 4 or 5 will be tropical and I can put that into a relatively simple formula for any height so you dont really need to store that data you are much better off storing the formula and being able to delegate that formula out.

          Basically an enumator like for, we'll call it temperature but you might have a better name:

          Code:
          enum EClimate
          {
          	EC_Arctic, //1
          	EC_Tundra, //2
          	EC_Temperate, //3
          	EC_SubTropical, //4
          	EC_Tropical; //5
          };
          This would be stored in the tile itself and you can store its position in the array in the tile itself also, that tile can also know based on on the fixed 2D array what tiles are directly adjacent to it which can also be stored for quicker lookup and you can do this for every tile when creating the vector field.

          From previously you dont need to search all tiles to know which are Tropical for instance you simply do height-5 or height-6 which is the midpoint of the height so having the enumerator could be purely for the visuals and the biome generation portion.

          Originally posted by Zeustiak View Post
          Do you have a link to any code examples of this kind of generation?
          Im not sure if there are any examples considering I came up with it on my own just looking at what you had and using my experience to think about where I would do things differently or make improvements. Im not sure exactly how close you are sticking to the Civ 5 methodologies but Im sure they are well documented so if there are references you are using I could look over to provide more detailed feedback on how my thinking differs that would be appreciated.

          Originally posted by Zeustiak View Post
          My general idea for coast generation and other similar tasks was to do a neighbor check to determine which mesh/material and what rotation it should use for proper placement. In the current setup my tiles are not referencable and it is something I will have to address sooner or later. By placing tiles first, and then changing them later this also allows me to do such checks and mesh swaps after every other tile type has been decided. Once the generator knows water will be placed in a certain hex, and land around it, then it can say use WaterMesh17 or whatever with Rotation Z in order to align the coasts.
          Yup this is where the idea of generating land masses from the center outwards has its benefits, you can have an array of outmost tiles only and iterate coastlines extremely rapidly. You could also generate ocean depth in much the same manner but it does depend if youre just wanting to go the Civ route with acouple of depths where the most deep can simply be X units from the beaches roughly.

          Originally posted by Zeustiak View Post
          Rivers are another thing on my mind. It seems like splines are the normal method of river type placement in games like these, but from what I understand splines are somewhat under-developed in the current engine, for things other than landscapes. I am not in a rush to implement rivers, but I see a good method for generating and referencing them I will certainly see if I can use it.
          Probably the most complex part of the generation and splines will certainly be beneficial but there is still alot of data to consider when generating them. Civ cheats in regards to mountains and mountain ranges in some regards and typically does rives on more hills or flats with flood plains, so matching that wouldnt be overly difficult but if youre looking to do better and have water that actually has some semblance to real rivers and lakes it'll be alot more difficult and the height of the surrounds will play an extremely important role.

          Originally posted by Zeustiak View Post
          This was just how I got it to work in the first place and I have spent more time on fleshing out the random generation than I have into looking at upgrading the actual placement process.

          If you have a good method I can use to reference the field of blank tiles, I am all ears.
          Main reason I wanted to give some critiques is to perhaps save you some time, it can be easy to get hung up on extra details in the implementation rather than improving on the core implementation itself. As I said I still dont understand entirely how what you have works but I think youre using sub-arrays for each biome to create smaller fast iteration lists, this is a good way to use memory for this kind of thing especially if you only need to do the generation once off and save the end result clearing all the memory when youre done.
          Last edited by MonsOlympus; 04-25-2014, 12:23 AM.

          Comment


            #6
            Originally posted by MonsOlympus View Post
            Im still having alot of trouble knowing what youre doing here because each piece is being sliced up and its hard to see the flow of execution which was my main reason for wanting to see, to help minimize the number of iterations because they will largely determine how long it takes to generate a map.
            I have shown you the complete flow of execution. The only thing missing is the Vector Field Generator which is self contained, and some stuff for my execution counting print string. Also, I have some ClearArrays right before my Biome Generators because I was seeing some odd tile placements even though the arrays were empty.

            Vector Field Generator(Self Contained) to Sequence
            > Sequence 1 >
            Biome Generators(Self Contained)
            > Sequence 2 >
            Vector Retriever(Executes Biome Locators, Boolean Setter, and Biome Placer for each tile in the map)
            Climate Boolean Setter sets climate booleans.
            Climate Branch Macros only allow loops through if the tile is to be placed in their Climate Band.
            Biome Locators, 1 per tile type.
            Biome Placer places a tile at the end of the loop.



            Originally posted by MonsOlympus View Post
            I guess I just look at things alittle differently in that I start with this vision of water everywhere, then I have visions of deep water cracking and pushing the shallow sands up through the water to form continents then on the islands and continents formed you get mountains and peaks, hills and rivers.
            My order of thought is generally: water, landmass, coasts, underwater terrain, mountains, hills, plains, rivers, vegetation, resources.

            Originally posted by MonsOlympus View Post
            I guess what Im trying to say is that a 2D Array is a 2D vector already so you dont need to generated that information, its one of the best bits to make entirely procedural. I know from your table that any index ending in 4 or 5 will be tropical and I can put that into a relatively simple formula for any height so you dont really need to store that data you are much better off storing the formula and being able to delegate that formula out.
            I think I need to see an example of this before I full understand how that is supposed to look/work.

            Originally posted by MonsOlympus View Post
            Basically an enumator like for, we'll call it temperature but you might have a better name:

            Code:
            enum EClimate
            {
            	EC_Arctic, //1
            	EC_Tundra, //2
            	EC_Temperate, //3
            	EC_SubTropical, //4
            	EC_Tropical; //5
            };
            This would be stored in the tile itself and you can store its position in the array in the tile itself also, that tile can also know based on on the fixed 2D array what tiles are directly adjacent to it which can also be stored for quicker lookup and you can do this for every tile when creating the vector field.

            From previously you dont need to search all tiles to know which are Tropical for instance you simply do height-5 or height-6 which is the midpoint of the height so having the enumerator could be purely for the visuals and the biome generation portion.
            Again, I think I am going to need some kind of example for how this works.

            What I think I get:

            Tile stores Enum_Tropical; // 5, it's vector, and the vector of it's neighbors(perhaps ordered starting at 12 o'clock and moving clockwise).

            I would simply add blank tiles to my Vector Field Generator so it can lay down the tiles and apply this information to them.

            Then, when I Generate Biome Seeds, and locate them, I can use the information already in the tiles as a reference.

            What I am not sure about:

            How to store and also retrieve that information in an instanced static mesh? Especially the Enum.

            Originally posted by MonsOlympus View Post
            Im not sure if there are any examples considering I came up with it on my own just looking at what you had and using my experience to think about where I would do things differently or make improvements. Im not sure exactly how close you are sticking to the Civ 5 methodologies but Im sure they are well documented so if there are references you are using I could look over to provide more detailed feedback on how my thinking differs that would be appreciated.
            I use Civ 5 as a general guidepost since I spent a good deal of time modding it and it generally has the minimum of what I want to accomplish, at least in terms of map generation. Civ 5's map generator has been criticized as too random though, so obviously if I can improve upon the generation that would be a plus.

            One idea I have involving my biome generator, is to figure out a way to randomly place tectonic lines throughout the globe, and have water/land seeds generate on either side of the lines. The really complicated stuff will come much later though.

            Originally posted by MonsOlympus View Post
            Yup this is where the idea of generating land masses from the center outwards has its benefits, you can have an array of outmost tiles only and iterate coastlines extremely rapidly. You could also generate ocean depth in much the same manner but it does depend if youre just wanting to go the Civ route with acouple of depths where the most deep can simply be X units from the beaches roughly.
            This would follow along with my idea for tectonics.

            Actually, Civ 5 isn't my favorite Civ game. That would be Call to Power, and CtP had underwater cities, underwater ridge lines, volcanos, etc. I don't want that much terrain down there, but more than simple Coast/Ocean for sure.

            Originally posted by MonsOlympus View Post
            Probably the most complex part of the generation and splines will certainly be beneficial but there is still alot of data to consider when generating them. Civ cheats in regards to mountains and mountain ranges in some regards and typically does rives on more hills or flats with flood plains, so matching that wouldnt be overly difficult but if youre looking to do better and have water that actually has some semblance to real rivers and lakes it'll be alot more difficult and the height of the surrounds will play an extremely important role.
            I definitely want rivers to flow from mountains to the ocean. Also, rivers that like to feed into each other as they travel that distance.

            My general idea is to generate the landmass with it's mountains, hills, and plains, and use those heights to guide the river as it's starting point is in the mountains and it's ending point is in the ocean. Then, other rivers do the same thing until they hit another river and they merge. I might have 1-2 major rivers that traverse the continent and then all other rivers feed into it from the mountains.

            Originally posted by MonsOlympus View Post
            Main reason I wanted to give some critiques is to perhaps save you some time, it can be easy to get hung up on extra details in the implementation rather than improving on the core implementation itself. As I said I still dont understand entirely how what you have works but I think youre using sub-arrays for each biome to create smaller fast iteration lists, this is a good way to use memory for this kind of thing especially if you only need to do the generation once off and save the end result clearing all the memory when youre done.
            I definitely appreciate it. The main reason I am doing what I am doing is because I am learning from scratch. So I will generally stick with something I have figured out and try and make it better and better so I retain the knowledge and really understand what I am doing. If I jump around too much I could forget how I have done what I have done, especially on the math side.

            Everything is modular enough that I could just switch out one chunk for something better and the rest of the blueprint could stay the same until it's upgrade comes. For instance, the Vector Field Generator could easily place the blank tiles and fill them with information while still keeping the generator intact. Then I can upgrade the rest to look to the new system.
            Map Generator 1.0
            Map Generator 2.0
            Map Generator 3.0

            Comment


              #7
              Okay so hmm this is hard to explain, if I show you I might as well just be doing it myself and thats really not my goal my goal is to help you.

              Lets take a basic 3x3 table:

              Code:
              --------------
              | 0 | 3 | 6 |
              -------------
              | 1 | 4 | 7 |
              --------------
              | 2 | 5 | 8 |
              --------------
              Lets say X is the axis running down (columns) and Y is the axis running across (rows).

              Code:
              0 is at X=1, Y=1
              1 is at X=1, Y=2
              2 is at X=1, Y=3
              3 is at X=2, Y=1
              and so on.

              Now we know that half of 3 is 1.5, rounded up gives us 2. The centre point is X=2, Y=2 so we can find the tile at that location and for any tile along X=2 for our tropical climate for example.

              Alittle bit about the tiles before continuing, you could use instances but Im not sure if your performance will be much of an issue since you have such a limited FOV and draw distance. Granted there might be alot going on, on the screen but I dont see a reason not to make the tiles their own actor/blueprint at this stage, maybe there is something Im missing but if you have memory you might as well use it. You can certainly use instances and create a subclass of a component and use those instead of actors if you wish to go that way, including putting the enumerator in there but thats accessible through C++ not blueprint.

              In our Tile at the midpoint, the Tile being at X=2, Y=2 we can then get all the indices immediately surrounding that Tile and in this case since its square we'll just include the corners but you'll only need 6 instead of 9 in a static array. Infact we can work it out programmatically which tiles are nearest too but that is alittle more complex mathematically so it can be faster to cache them especially if you want to say, do a move through numerous tiles you can actually plot a path using those arrays.



              Okay so in terms of your tectonic idea you can see here that a new 2D array starts to emerge, the line between [Tile 3, Tile 6] for instance.

              The reason why I suggested doing things this way though is you can do each step as you go, you generate the blank tiles and assign the climates in one swoop. Then you pause for a short period, perhaps to display loading progress. Then you continue and start making the biomes, you can pause at each biome and again display the progress even some kind of debug statistics screen to yourself to make sure everything is going according to plan and so on...

              Im not sure if Im being alittle too basic, you seem to understand where Im coming from and perhaps I could start something similar in blueprint to show. We'll see how it goes from here

              Edit: Oops ignore that 4 in tile 6, it should be a 3.
              Last edited by MonsOlympus; 04-25-2014, 07:39 AM.

              Comment


                #8
                Alittle bit about the tiles before continuing, you could use instances but Im not sure if your performance will be much of an issue since you have such a limited FOV and draw distance. Granted there might be alot going on, on the screen but I dont see a reason not to make the tiles their own actor/blueprint at this stage, maybe there is something Im missing but if you have memory you might as well use it. You can certainly use instances and create a subclass of a component and use those instead of actors if you wish to go that way, including putting the enumerator in there but thats accessible through C++ not blueprint.
                I noticed a very significant difference in both generation and runtime performance when using static meshes compared to instanced meshes. It was the first thing I had to change once I had my first generator working. Now, my video card is on it's last leg, so that may contribute, but I can play around with that some more when my new card arrives.

                The slowdown I experienced was with 800-3K meshes and very few features, and my maps will get up to 20K+ meshes with many features. Additionally, that was with my old random generator which took much less power than the more complicated biome generator.

                Also, I should mention that when I fixed this problem, it was with the help of an Epic Dev and he suggested using instanced meshes for visual representation and using volume actors to hold my information. I think this would be acceptable, except I am not sure how dynamically finding and changing an instanced mesh works, if at all, after the generation.

                Can you "FindActor" or whatever on an instanced mesh, and get at least a minimal amount of information such as a TileVariable? Also, can you change the material of an instancedmesh after it has been spawned? If that works, then I could probably continue to use that and run everything else through volumes.

                Now we know that half of 3 is 1.5, rounded up gives us 2. The centre point is X=2, Y=2 so we can find the tile at that location and for any tile along X=2 for our tropical climate for example.
                Why did you cut 3 in half? And then round it up? Also, calling X the axis that is up and down is confusing...

                I think I would prefer to use the indexes already established if possible. I could create the array and store the Index for each neighbor tile and either convert to true vector as required, or run a formula on the index itself to determine what the neighbor index should be. I am already doing a lot of that with map scaling and using the index would allow for the same process that would talk to tiles further away than just the nearest neighbor.

                This is the Array Index table for Map Size 20. As you can see, the Indexes increment X by 20 instead of 10, which I have to account for when scaling.

                If Center = 44, then:
                North = 45; NorthEast = 24; SouthEast = 23; South = 43; SouthWest = 63; NorthWest = 64

                So, the Array, starting at North and moving Clockwise, could be filled with integers as such:
                C = Core Tile Index (44 for instance)
                M = Map Size

                N = C + 1
                NE = C - M
                SE = (C - 1) - M
                S = C - 1
                SW = (C - 1) + M
                NW = C + M

                I already have formulas to convert Index to True Vector, and it wouldn't be very hard to run any given formula on those indexes or their vectors.

                Additionally, since I am already doing math on the indexes for neighbors, it wouldn't be much of a stretch to reach out and grab tiles further away for whatever purpose.

                Okay so in terms of your tectonic idea you can see here that a new 2D array starts to emerge, the line between [Tile 3, Tile 6] for instance.
                I can see how you could form the basis of just about any map generation type when you can reference surrounding tiles. The problem is going to be creating an algorithm that does this across a giant map in shapes that look like they could have occurred in nature.

                The reason why I suggested doing things this way though is you can do each step as you go, you generate the blank tiles and assign the climates in one swoop. Then you pause for a short period, perhaps to display loading progress. Then you continue and start making the biomes, you can pause at each biome and again display the progress even some kind of debug statistics screen to yourself to make sure everything is going according to plan and so on...
                I agree, and I it is how I have handled everything so far. You are definitely helping me visualize how I can implement a tile reference system which much of the map generator will come to rely on.
                Last edited by Zeustiak; 05-06-2014, 05:29 AM.
                Map Generator 1.0
                Map Generator 2.0
                Map Generator 3.0

                Comment


                  #9
                  Originally posted by Zeustiak View Post
                  I noticed a very significant difference in both generation and runtime performance when using static meshes compared to instanced meshes. It was the first thing I had to change once I had my first generator working. Now, my video card is on it's last leg, so that may contribute, but I can play around with that some more when my new card arrives.

                  The slowdown I experienced was with 800-3K meshes and very few features, and my maps will get up to 20K+ meshes with many features. Additionally, that was with my old random generator which took much less power than the more complicated biome generator.

                  Also, I should mention that when I fixed this problem, it was with the help of an Epic Dev and he suggested using instanced meshes for visual representation and using volume actors to hold my information. I think this would be acceptable, except I am not sure how dynamically finding and changing an instanced mesh works, if at all, after the generation.
                  Okay so if that works for you we'll stick with that since I actually found something similar with spawning alot of meshes, I actually didnt remember till you mentioned it but I did have some camera frustrum culling issues with instances when I was panning really quickly but Im sure the performance outweighs the drawbacks. I think it goes to the amount of drawcalls and instances have draw call batching which could be why it was suggested to use volumes.

                  Originally posted by Zeustiak View Post
                  Can you "FindActor" or whatever on an instanced mesh, and get at least a minimal amount of information such as a TileVariable? Also, can you change the material of an instancedmesh after it has been spawned? If that works, then I could probably continue to use that and run everything else through volumes.
                  There are a few ways to speed up searches, first would be narrowing the search field. If you know youre searching for a water tile, or tundra etc there are ways you could narrow the field and search only the required indices. Keeping a list of boundaries for continents would certainly help, if youre searching water you would avoid any index within the bounds of a continent, C++ does have some handy things like checking sets if one contains another and so forth. Sublists are extremely handy and if you really need them I highly recommend a concept called skiplists, its like a weighted array that can speed up searches quite alot in the right conditions.

                  Originally posted by Zeustiak View Post
                  Why did you cut 3 in half? And then round it up? Also, calling X the axis that is up and down is confusing...
                  I did it to find the tropical climate, you know based on the enum how to slice each section of the columns. Basically I had to round to make it a valid array index because they are integers not floats.

                  Originally posted by Zeustiak View Post
                  I think I would prefer to use the indexes already established if possible. I could create the array and store the Index for each neighbor tile and either convert to true vector as required, or run a formula on the index itself to determine what the neighbor index should be. I am already doing a lot of that with map scaling and using the index would allow for the same process that would talk to tiles further away than just the nearest neighbor.
                  Yes ofcoarse and this neighbour data is useful in the actual gameplay too. Like I said for generating routes over tiles. In terms of generating islands though its pretty easy to just choose a random neighbour and give it some land with preference to neighbours already with land adjacent but thats just another example.

                  Originally posted by Zeustiak View Post
                  This is the Array Index table for Map Size 20. As you can see, the Indexes increment X by 20 instead of 10, which I have to account for when scaling.

                  If Center = 44, then:
                  North = 45; NorthEast = 24; SouthEast = 23; South = 43; SouthWest = 63; NorthWest = 64

                  So, the Array, starting at North and moving Clockwise, could be filled with integers as such:
                  C = Core Tile Index (44 for instance)
                  M = Map Size

                  N = C + 1
                  NE = C - M
                  SE = (C - 1) - M
                  S = C - 1
                  SW = (C - 1) + M
                  NW = C + M
                  Yup those seem straight forward enough, its much the same with grabbing all tiles along the equator for instance, you just have to account for both odd and even numbers, odd meaning there will only be a single strip of equatorial tiles and even meaning there will be 2. You obviously even have some kind of algorithm for knowing how wide each climate should be at a certain map size, if its customizable or what not.

                  Originally posted by Zeustiak View Post
                  I can see how you could form the basis of just about any map generation type when you can reference surrounding tiles. The problem is going to be creating an algorithm that does this across a giant map in shapes that look like they could have occurred in nature.
                  Its not as hard as you might think, if you are drawing single lines all you have to make sure is that it doesnt back over or cross over itself kinda like snake, the odds on it winding itself into a spiral though are next to none (it is possible though). Using the same example as before [Tile 3, Tile 6] we know the line has to go along either of those two and we know they both share Tile 5 adjacent so there is actually only 2 possibilities to start the path [Tile 3, Tile 5) or [Tile 6, Tile 5] if you actually make it so it can only move forward choosing 2 or 3 of the most forward directions then the line should slice the map vertically eventually.

                  Originally posted by Zeustiak View Post
                  I agree, and I it is how I have handled everything so far. You are definitely helping me visualize how I can implement a tile reference system which much of the map generator will come to rely on.
                  Ahh Im glad I am being helpful, this is actually interesting for me too since Ive not actually studied much so its abit of a test to see if I can understand how to do this. Set theory and probabilities are my two kinda pet subjects lol

                  Comment


                    #10
                    Lets hope my SSD doesn't cause another bluescreen of death as I write this...

                    There are a few ways to speed up searches, first would be narrowing the search field. If you know youre searching for a water tile, or tundra etc there are ways you could narrow the field and search only the required indices. Keeping a list of boundaries for continents would certainly help, if youre searching water you would avoid any index within the bounds of a continent, C++ does have some handy things like checking sets if one contains another and so forth. Sublists are extremely handy and if you really need them I highly recommend a concept called skiplists, its like a weighted array that can speed up searches quite alot in the right conditions.
                    What I meant was, can you grab an instanced actor and change it's properties? Really if I can just delete it, then I can replace it with what I need. That would both be in map generation, and later on when players are terraforming the countryside. What nodes are used to find and select an actor in the world?

                    By sublist, you mean an Array or an Enum or something else?

                    I did it to find the tropical climate, you know based on the enum how to slice each section of the columns. Basically I had to round to make it a valid array index because they are integers not floats.
                    Ah. So let me see if I understand how to use an Enum in this case:

                    I have an Enum that contains all my tile types and each tile type is assigned an integer.

                    Then, I have an array, say Climate Array, that is loaded with integers based on the Climate Enum and is generated along with my Vector Field. The index of the Vector Field Array and the Climate Array would line up so that they could both be addressed using the same integer/math.

                    That seems different than when you say to store it in the tile itself. How would I do that, and would it be better than keeping a Climate Array instead?

                    Its not as hard as you might think, if you are drawing single lines all you have to make sure is that it doesnt back over or cross over itself kinda like snake, the odds on it winding itself into a spiral though are next to none (it is possible though). Using the same example as before [Tile 3, Tile 6] we know the line has to go along either of those two and we know they both share Tile 5 adjacent so there is actually only 2 possibilities to start the path [Tile 3, Tile 5) or [Tile 6, Tile 5] if you actually make it so it can only move forward choosing 2 or 3 of the most forward directions then the line should slice the map vertically eventually.
                    Is it randomly going to choose between Tile 3 and Tile 6? The problem is, how does it know when to turn in order to make natural seeming landmass shapes? How do you inject a purpose behind that system? Would you seed in guide tiles that it heads toward, kind of like connect the dots?
                    Map Generator 1.0
                    Map Generator 2.0
                    Map Generator 3.0

                    Comment


                      #11
                      What I meant was, can you grab an instanced actor and change it's properties? Really if I can just delete it, then I can replace it with what I need. That would both be in map generation, and later on when players are terraforming the countryside. What nodes are used to find and select an actor in the world?
                      Oh okay I think Im understanding the dilemma, you can turn a material instance to dynamic to adjust its parameters and you can create global sets of material parameters as well. The idea might be to piggy back extra data onto the instance so you dont have to modify them directly, should be able to do this with structs.

                      By sublist, you mean an Array or an Enum or something else?
                      Ahh sorry yes I tend to refer to single dimensional ordered arrays as lists, for example on a 2D array as in your vector field you can describe any solid rectangle just by its corners and I would call that a sub field. Where a list is just every item taken from the vector field that fits a certain criteria. For example if you wanted to search just temperate tiles you could have a shorter list, I think you might be doing this already but another set of lists could be continent boundries like we've discussed or any other type of data we could use to seperate our random tiles.

                      Ah. So let me see if I understand how to use an Enum in this case:

                      I have an Enum that contains all my tile types and each tile type is assigned an integer.

                      Then, I have an array, say Climate Array, that is loaded with integers based on the Climate Enum and is generated along with my Vector Field. The index of the Vector Field Array and the Climate Array would line up so that they could both be addressed using the same integer/math.

                      That seems different than when you say to store it in the tile itself. How would I do that, and would it be better than keeping a Climate Array instead?
                      I tend to work via object references, structures and the like so I think its just a difference in thinking. Im seeing alot more flat process from how you work and thats okay, I think we are going back and forward talking about the exact same thing, I think I understand why you need the vector field and I think it might be hurting your maths to some degree or causing you to do more complex calculations on lookups then again...

                      CurrentIndex+Height gives the next tile right? With a 2D array you can work on each index independently so itd be good to have Macros for those.

                      I think whats most confusing is perhaps the way I used Climate since it relates to what the tile will be assigned but not the tiles type directly. I might have mixed it up so when you have jungle, desert or water those are the possible tile types based on the climate, the climate though can be got through math you dont actually require the table as you can check if a tile is less than or greater than the index of a Climate.

                      Is it randomly going to choose between Tile 3 and Tile 6? The problem is, how does it know when to turn in order to make natural seeming landmass shapes? How do you inject a purpose behind that system? Would you seed in guide tiles that it heads toward, kind of like connect the dots?
                      There is nature in chaos or chaos to nature, one of those, your land masses are kind of limited either way because of the fact its tiles, you can only turn a tile 6 different ways and while you could have a number of different patterns you can turn around not all of them will line up with adjacent tiles. Unless perhaps you make it so you can slice certain tiles and break them down to a smaller tile:



                      This would allow more complex slices and details on tiles by procedurally generating each of the smaller portions and could allow for rivers without using splines. This is just an idea though there is alot of ground to cover, figuratively speaking, in regards to possibilities. There are rules which tectonics follow which includes the plates overlapping and shifting so you could go into alot of organic details but the generation time would increase with the amount of depth.

                      Anyway Im getting alittle bit side tracked, Im not exactly up on tectonics but Im pretty sure that they are independent from land mass, they slice through both oceans and land masses. If we ignore that and use a slice method for generating land masses, if you have a start and an end point then you will end up with only a set amount of probabilities each time, which means your map isnt actually random so maybe my question would be do you want a randomized map or are you trying to specify what you want to create?

                      In terms of completely random outcomes you have no end goal, you have a start position and a set of rules and you just iterate for as long as required, its a similar concept to time based rendering where you specify the amount of time it should iterate for and regardless of the quality of the image it will stop when its told where the opposite is knowing what the image should look like and rendering till you hit that point. I guess the issue is that you could run into a situation where a slice never ends but you could limit it based on the map size, for instance if your map size is 10 then your maximum slice distance could be 30 and you could even take into account branches where it chose to go both ways and create a split. The rules for not overlapping is relatively simple but it can cause problems after a certain length like having to check back over the slice and make sure the current slice wont break any of the others.

                      I hope youre considering a more layered approach by now atleast, that each part of the generation is important as the next, that using maths for the parts you dont need to cache is the way to go and caching small datasets to improve lookups rather than trying to cache the entire field each time.

                      Comment


                        #12
                        Oh okay I think Im understanding the dilemma, you can turn a material instance to dynamic to adjust its parameters and you can create global sets of material parameters as well. The idea might be to piggy back extra data onto the instance so you dont have to modify them directly, should be able to do this with structs.
                        I am going to need to change more than just the material. I will have to swap out meshes as well. Plains to Mountains and whatnot.

                        Is the best way to do this to destroy the actor at the vector and replace it with a new mesh? Do you know how that might be done in blueprint?

                        I tend to work via object references, structures and the like so I think its just a difference in thinking. Im seeing alot more flat process from how you work and thats okay, I think we are going back and forward talking about the exact same thing, I think I understand why you need the vector field and I think it might be hurting your maths to some degree or causing you to do more complex calculations on lookups then again...
                        I think the miscommunication we are having is that I don't know as much as you think I know. Like I said, I picked up UE4 ~3 weeks ago and am learning from almost 0 knowledge. I have an idea what an Enum is, but no idea how to effectively use it in blueprint. Have seen structs in the editor but don't know what to do with them or even what they do.

                        You keep saying store the information in the tile but I haven't even yet begun to figure out how that is supposed to happen.

                        So anything you see me doing, it is because that is how I learning how to do it(or how I got it to work). Everything is getting upgraded as I learn new things.

                        I think whats most confusing is perhaps the way I used Climate since it relates to what the tile will be assigned but not the tiles type directly. I might have mixed it up so when you have jungle, desert or water those are the possible tile types based on the climate, the climate though can be got through math you dont actually require the table as you can check if a tile is less than or greater than the index of a Climate.
                        Yeah that is basically how my range checks work right now.

                        There is nature in chaos or chaos to nature, one of those, your land masses are kind of limited either way because of the fact its tiles, you can only turn a tile 6 different ways and while you could have a number of different patterns you can turn around not all of them will line up with adjacent tiles. Unless perhaps you make it so you can slice certain tiles and break them down to a smaller tile:
                        Yeah I wouldn't even know where to start using that crazy hexagon to do things. Just imagining the number of vectors required to account for all the mini hexes....

                        Anyway Im getting alittle bit side tracked, Im not exactly up on tectonics but Im pretty sure that they are independent from land mass, they slice through both oceans and land masses. If we ignore that and use a slice method for generating land masses, if you have a start and an end point then you will end up with only a set amount of probabilities each time, which means your map isnt actually random so maybe my question would be do you want a randomized map or are you trying to specify what you want to create?
                        Both. I am not too worried about the many ways to actually generate the map at this point. More focused on proof of concept with 1 type of map, flesh out the rest of the tile types and other features, and then come back to the fine details of procedural generation.

                        My mention of tectonics was just a thought on how future generation might work, and how it should be considered as I build the system up. I believe being able to reference and change neighbor tiles will be key to such generations and it would be good to get that working sooner rather than later.

                        I hope youre considering a more layered approach by now atleast, that each part of the generation is important as the next, that using maths for the parts you dont need to cache is the way to go and caching small datasets to improve lookups rather than trying to cache the entire field each time.
                        I hope I haven't given you the impression that I am not taking a layered approach. Like I said, I am learning how to use UE4 and various programming concepts as I go. The question isn't WILL, but HOW.
                        Map Generator 1.0
                        Map Generator 2.0
                        Map Generator 3.0

                        Comment


                          #13
                          Well I really dont want to give you everything straight up because the best way to learn is by doing but I do think I may have to show you a few things so Im going to make a start on a quick little thinggy of my own but what I'll do is I'll use what I know and we'll see what I end up with in comparison. This should help you cover abit more ground but the thing of it is Im starting with the head start youve provided in discussing this with me so I should be able to incorporate parts of what you have going. I dont want to spend too much time on it though as I have other things to do but I'll certainly show how to piggyback the enum's and other data in a struct, perhaps try to refine your iterations as well but its possible I'll hit the limit.

                          Im happy to provide what I do to the community, I do think though we could use a robust multidimensional array implementation but we'll see what I can do. Im going to start with a simple shuffle algorithm and then work on the tiles, I'll spend alittle time on it tonite whilst Im doing some player physics on my project. Please keep me updated on your findings and I'll certainly get back to you with what I have over the coming days

                          Comment


                            #14
                            Cool, I look forward to seeing what you come up with!

                            I will research structs, enums, and how to reference instanced tiles in the meantime.
                            Map Generator 1.0
                            Map Generator 2.0
                            Map Generator 3.0

                            Comment


                              #15
                              I came up with 4 Enums should help with the generation, especially as I add more terrains, vegetation, etc.

                              Each Elevation can lead to a set of Terrains based on climate band. Each Terrain can lead to a set of Vegetations based on climate band.

                              Climate - Arctic, Temperate, Tropical, etc
                              Elevation - Plains, Hill, Mountain, etc
                              Terrain - Tundra, Grassland, Desert, etc
                              Vegetation - Boreal, Deciduous, Jungle, etc

                              Each tile should be able to store it's enum value for each enum type for later reference.
                              Map Generator 1.0
                              Map Generator 2.0
                              Map Generator 3.0

                              Comment

                              Working...
                              X