[Release] Dune 2000 Random Map Generator

[shai]

This is the current work-in-progress version of the Random Map Generator I have been working on. Please keep in mind I am by no means a professional at this so please report any problems you may encounter while running it here in this thread. A link to download it and the uncompiled code are below, Java is required to run it. Simply double click the 'run.bat' file to generate a map.

When a map is created, a total of three files are made. A log file, an ini file, and the map file. The log file contains the settings that were used to create the map. The ini file contains the name of the map, for use with the CnCNet launcher included in the GruntMods Edition of Dune 2000. And the map file, of course is the map itself. An optional fourth file, a .mis file, can be made as well. 

Updated: v170407

1. D2KMapGen-170407.zip
2. src-170407.zip

• Heavily reduced the time it takes to save the map and mis file
• Replaced the settings bellow with the following new settings:
  1. 'numberOfSandSpecialsToAdd', 'numberOfRockSpecialsToAdd', 'numberToAdd', 'numberOfSpiceSquares', numberOfDuneSquares', 'numberOfIslandSquares'
  2. 'sandSpecialFreq', 'rockSpecialFreq', 'rockFreq', 'spiceFreq', 'duneFreq', 'islandFreq'
  • These new settings are instead now a percentage. Ex. If 'rockFreq' is set to 0.2, then roughly 20% (0.2 * 100) of all blocks on the map will be a rock tile
• All areas have been properly altered to prevent it from getting stuck due to a value that is too high
• Improved the GUI
• Fixed the AI in the mis files being incorrect
• Partially fixed the placment of the dune edges
• Altered how the openings in the cliff faces are added, they can now be varied in size
• Sped up the placing of player spawns somewhat with 'autoSpaceSpawns' enabled, and the placement of spice blooms
• After a map is completed, the time it took to make it is displayed
• Prevented cliff faces and rock-to-sand edges from having two identical blocks right next to each other

Example of a map made with the default settings:

Spoiler

 

v170322

1. D2KMapGen-170322.zip
2. src-170322.zip

• Implemented safe guards to prevent the program from locking up; you may now set the settings as high as you want 
• All 7 original tilesets are now supported
• Now creates a .mis file to go with the map
• Added new setting: 'addMis'
  • Setting to true will create a .mis file, false will not
• Added new setting: 'autoSpaceSpawns'
  • Setting to true will use a new, better method to add the spawn points in a more evenly distributed layout. 'spaceBetweenPoints' is not used under it
• A 'README.txt' file is included which explains the settings and how to use the generator

 

v170317

1. D2KMapGen-170317.zip
2. src-170317.zip

• Added a new system where all you need to do is specify the map dimensions and tileset, and the remaining values will be estimated. Setting 'useSettings' to false will enable this. 
• Added a basic interface which utilizes the above feature. To use it, run the 'runGUI.bat' file. 'Load Defaults' will load the settings last saved and 'Quit and Save Defaults' will save the current settings 

Picture:

Spoiler

• Now uses the tileset ini files from Klofkac's Map Editor for the tile info
• Added new setting: 'numberOfEmptyBlooms'
  • Like how 'numberOfBlooms' would be the start of a spice field that has a spice bloom, 'numberOfEmptyBlooms' is the start of a spice field that does not have one
• Added new setting: 'addTimeStamp'
  • Setting this to false will disable the time stamp that is added to the end of a map's file name
• Reorganized the settings file to be more neat
• Spice blooms are now ensured to be spread across the map more evenly
• 'Islands' can now become merged with the rock-to-sand openings in the cliff walls 
• Altered the list of rock tiles in use

 

v170311

1. D2KMapGen-170311.zip
2. src-170311.zip

• Updated settings file; now uses ini4j to read ini formating
• Added small patches of rock to the generation
• Fixed spawns being put on inaccessible rock plains
• Updated the way extra spawns are added/removed to ensure there are always 8 in total

 

v170304

1. D2KMapGen-170304.zip
2. src-170304.zip

 

 

 

 

Edited April 7, 2017 by shai

[shai]

Updated: v170311

• Updated settings file; now uses ini4j to read ini formating
• Added small patches of rock to the generation
• Fixed spawns being put on inaccessible rock plains
• Updated the way extra spawns are added/removed to ensure there are always 8 in total

The new version can be downloaded above in the first post of this thread

[Klofkac]

Okay, so finally got some time to respond to this thread.

First of all: Well Done! Your random map generator really works, and it actually produces pretty reasonable results, which could be considered serious and playable, human-made maps. Pretty outstanding achievement you made.

Personally, I'm not going to utilize this program to produce my maps (simply because I do not create my own maps anyway), but I am pretty much interested in the technical solution/algorithm of the random map generation. I was even thinking about making a random generator myself and considering various algorithms to use, but never actually started.

I'm lacking some kind of description/explanation of the method/algorithm you used to generate the maps. But on the other hand, I was playing around a bit with the settings, and most importantly, I let export the individual results of all the steps, which gave me some insight to what's going on. Basically it starts up with placing square-shaped areas of rock (which will later become places for building up a player's base) and then it adds more rock tiles around them to form various shapes. Then it will form the access paths and cliff borders around the rock areas, and place proper cliff tiles (which is probably the most difficult part of the map generation at all). After that it will generate spice areas, dunes areas and small rock islands, using very similar methods. So far, I think I don't fully understand what exactly some settings do - for example numberAtATimeDivisor, squareTop/BottomRight/Left.

My question is - did you make everything from scratch (I mean the idea of the method of random generation) or you followed or got inspired by some articles about some random generation methods? If so, could you provide some referrences to those?

Here is some list of notices and ideas I'd like to say:

• By default you generate 48 spice blooms. But earlier I discovered that the game supports no more than 30 blooms in a map - if there are more, then those blooms above 30 will never spawn. So it has no sense to generate more than 30. Also the default number of worm spawns seems quite high for me.
• The program occasionally ended up in an infinite loop and needed to be killed forcefully. That happened mostly when I set very high numbers of numberOfSpawnsToAdd and numberToAdd, it seemed like it was trying to find a new free space to place a next rock tile, but there was no more room.
• It would be quite nice to break up the ini settings into multiple groups. I see that there are settings releted to rock area generation, and then very similar set of settings for generation of spice and dunes. Dividing these into separate categories would make ini file more readable. You could also match up the order of the settings with order of genreration of respective entities.
• It would be nice to add some randomization of the settings themselves. Now the final look of the map highly depends on the settings, which is still some sort of user input which needs to be supplied. If the settings were randomized too, the generator could make purely random maps with really great degree of variation and with minimal user input. My idea is that the users would be able to decide which settings they want to specify by themselves and which settings to let be random. The best way would be to specify the settings as ranges (minimum and maximum), the program would pick a random value within this range, and if the user wants a precise value he would set both min and max the same.
• I looked into the source code and the biggest problem I found is that everything (tile numbers) is just hardcoded into the code. When I was developing the map editor, I externalized almost everything into configuration files and made separate files with presets for each tilesets (ini files in Tilesets folder). You could actually utilize these tileset configuration files in your program - I already defined all tileset-specific blocks (sand specials, rock specials etc.) so it could save your work on defining all of these again.
• I was thinking about adding a new option to my Map editor, which would fire your random generator and then open up the resulting map just when the map is created.
• Edit: It would be good to add option to disable appending of the unix timestamp to the output file name. Sometimes I just wish to overwrite the output map instead of keeping history of all my attempts.

 

Edited March 14, 2017 by Klofkac

[shai]

7 hours ago, Klofkac said:

Okay, so finally got some time to respond to this thread.

First of all: Well Done! Your random map generator really works, and it actually produces pretty reasonable results, which could be considered serious and playable, human-made maps. Pretty outstanding achievement you made.

Thank you! I highly appreciate you taking the time to write up your thoughts on it

Quote

So far, I think I don't fully understand what exactly some settings do - for example numberAtATimeDivisor, squareTop/BottomRight/Left 

The 'divisor' variables are meant to help evenly distribute all the squares. Hopefully I can explain this well enough. So, the idea is that without this in place, all the squares will likely end up being placed very unevenly. This is because once an area starts to get big, it gets a higher chance of becoming even more bigger, compared to the smaller areas. When a rock square is being placed, the program looks for a rock tile that is next to a sand tile, so an edge point. The bigger an area is, the larger perimeter it has, further increasing it's chance to get bigger. 

So to counter this, the squares are placed in batches. The number of squares in a batch being found like this:

(numberToAdd / numberAtATimeDivisor) = numberAtATime

ex. (512 / 2) = 256

Here is a example showing how it works:

Spoiler

for(int i = 0; i != numberToAdd; i++){
    edges = findAnEdgeSquare(mainBoard, boardR, boardC, 1);
    counter++;

    valuesToUse[0] = values[rand.nextInt((3 - 0) + 1) + 0];
    valuesToUse[1] = values[rand.nextInt((3 - 0) + 1) + 0];
    valuesToUse[2] = values[rand.nextInt((3 - 0) + 1) + 0];
    valuesToUse[3] = values[rand.nextInt((3 - 0) + 1) + 0];

    for(int newC = (edges[1] - valuesToUse[0]); newC != (edges[1] + valuesToUse[1] + 1); newC++){
        for(int newR = (edges[0] - valuesToUse[2]); newR != (edges[0] + valuesToUse[3] + 1); newR++){
            try{
                if(mainBoardTemp[newR][newC] == 9){

                }else{
                    mainBoardTemp[newR][newC] = 1;

                }
            }catch(IndexOutOfBoundsException e){

            }
        }
    }

    if(counter >= numberAtATime){
        mainBoard = mainBoardTemp;
        counter = -1;

    }
}

mainBoard = mainBoardTemp;

The squares are being applied to the 'mainBoardTemp' array while the edges are being found in the 'mainBoard' array and the changes aren't being applied until the number of squares counted by 'counter' exceed the number of squares to be placed in a batch, which in the example above is 256. This effectively evens out the placement of the squares, making them more equally sized. But, I haven't had the time to properly test it with different numbers so I don't know just how effectively it can work.

 

As for the 'squareTop/Bottom/Right/Left', these simply are the dimensions of each square. 

From the blue centre square, this example has a 'Top' of 2, a 'Right' of 2, and 'Bottom' of 0, and a 'Left' of 1. Keep in mind that the four of these values are randomly interchanged with one another, to keep things looking less blocky. 

Quote

My question is - did you make everything from scratch (I mean the idea of the method of random generation) or you followed or got inspired by some articles about some random generation methods? If so, could you provide some referrences to those?

The methods that are used to generate everything are entirely my ideas, I didn't read any outside material to get any ideas. 

Quote

By default you generate 48 spice blooms. But earlier I discovered that the game supports no more than 30 blooms in a map - if there are more, then those blooms above 30 will never spawn. So it has no sense to generate more than 30. Also the default number of worm spawns seems quite high for me.

I hadn't known this, and I didn't notice any abnormal effects during gameplay, but I will keep note of this, thanks. Yes, the official maps, even ones 128x128, only seem to have 3 or 4, I will definitely turn them down some. 

Quote

The program occasionally ended up in an infinite loop and needed to be killed forcefully. That happened mostly when I set very high numbers of numberOfSpawnsToAdd and numberToAdd, it seemed like it was trying to find a new free space to place a next rock tile, but there was no more room.

This is something I will need to do in the future, making sure there safeguards in effect that prevent this sort of thing. I have already done so in, for example, the method 'addInfantryClimbs'. It will try a certain number of times to do what it does, and will stop after a number of times. Another possible way to get around this is have all the variables chosen by the program based on how big the map will be.

Quote

It would be quite nice to break up the ini settings into multiple groups. I see that there are settings releted to rock area generation, and then very similar set of settings for generation of spice and dunes. Dividing these into separate categories would make ini file more readable. You could also match up the order of the settings with order of genreration of respective entities.

I can do this too, I just wanted the ini file handling part in working order right away.

Quote

It would be nice to add some randomization of the settings themselves. Now the final look of the map highly depends on the settings, which is still some sort of user input which needs to be supplied. If the settings were randomized too, the generator could make purely random maps with really great degree of variation and with minimal user input. My idea is that the users would be able to decide which settings they want to specify by themselves and which settings to let be random. The best way would be to specify the settings as ranges (minimum and maximum), the program would pick a random value within this range, and if the user wants a precise value he would set both min and max the same.

Yes, like I mentioned above, this is something I will do in the future. I just need to find an acceptable range for all the variables based on the size of the map, or like you suggest, just a range supplied by the user.

Quote

I looked into the source code and the biggest problem I found is that everything (tile numbers) is just hardcoded into the code. When I was developing the map editor, I externalized almost everything into configuration files and made separate files with presets for each tilesets (ini files in Tilesets folder). You could actually utilize these tileset configuration files in your program - I already defined all tileset-specific blocks (sand specials, rock specials etc.) so it could save your work on defining all of these again.

Ah, I looked around in those folders but I did not notice those tileset ini files, I will definitely have a look at those, thanks. Doing it as it currently works, for all the tilesets would for sure take a vary long time, this would work a lot better, and work for custom tilesets even I think. To make all these changes would probably require rewriting almost everything, but I have no problem with doing that, and even somewhat planned to do so anyway. 

Quote

I was thinking about adding a new option to my Map editor, which would fire your random generator and then open up the resulting map just when the map is created.

That would be easily implementable, if you would like to do that you very well may do so. 

Quote

Edit: It would be good to add option to disable appending of the unix timestamp to the output file name. Sometimes I just wish to overwrite the output map instead of keeping history of all my attempts.

I will add this as well. 

[Klofkac]

Thank you for your reply and explanations. I got several more questions to ask:

• Right now it really often happens that two rock areas merge together into one big area. However, sometimes it may be undesired behavior, so are you thinking about implementing some sort of mechanism which would actively prevent two distinct rock areas from connecting together? For example enforcing minimum distance of rock tiles belonging to different areas. If set to 0, this check would be disabled and areas would be allowed to connect.
• As I understand, the spice always generates around a spice bloom which is placed first. But in original game there are patches of spice (sometimes really big) which do not have any spice bloom inside them and would not regenerate once exhausted. Are you going to add this as well?
• Generally, do you have some task list or "backlog" of what all are you going to implement? Would be interesting to share one and then strike through a task when it gets implemented.

 

[Nyerguds]

You should post about this on the cncnet forum

https://forums.cncnet.org/index.php?board=111.0

[shai]

9 hours ago, Klofkac said:

Right now it really often happens that two rock areas merge together into one big area. However, sometimes it may be undesired behavior, so are you thinking about implementing some sort of mechanism which would actively prevent two distinct rock areas from connecting together? For example enforcing minimum distance of rock tiles belonging to different areas. If set to 0, this check would be disabled and areas would be allowed to connect.

Right now, the only way to prevent two areas from connecting to each other would be to increase 'spaceBetweenPoints' so they are more separated, or decrease either 'numberToAdd' or 'numberOfSpawnsToAdd' to make them smaller or fewer. I'll see which settings work best to keep them apart. And like you suggest, I will also look into making a system that would make each area different from each other, so they don't connect at all and stay separated. 

Quote

As I understand, the spice always generates around a spice bloom which is placed first. But in original game there are patches of spice (sometimes really big) which do not have any spice bloom inside them and would not regenerate once exhausted. Are you going to add this as well?

Yup, I just added this yesterday, 'numberOfEmptyBlooms' will be the start of a spice field that does not have any spice bloom. There was a bit of a problem with some parts of the map not getting any spice at all so setting this much higher than 'numberOfBlooms' will ensure there are spice fields everywhere. 

Quote

Generally, do you have some task list or "backlog" of what all are you going to implement? Would be interesting to share one and then strike through a task when it gets implemented.

I do kind of have a list of things I will/need to do in my head, I'll write in down in the first post too. 

[shai]

2 hours ago, Nyerguds said:

You should post about this on the cncnet forum

https://forums.cncnet.org/index.php?board=111.0

Will do! 

[shai]

 

Updated: v170317

• Added a new system where all you need to do is specify the map dimensions and tileset, and the remaining values will be estimated. Setting 'useSettings' to false will enable this. 
• Added a basic interface which utilizes the above feature. To use it, run the 'runGUI.bat' file. 'Load Defaults' will load the settings last saved and 'Quit and Save Defaults' will save the current settings 

Picture:

Spoiler

• Now uses the tileset ini files from Klofkac's Map Editor for the tile info
• Added new setting: 'numberOfEmptyBlooms'
  • Like how 'numberOfBlooms' would be the start of a spice field that has a spice bloom, 'numberOfEmptyBlooms' is the start of a spice field that does not have one
• Added new setting: 'addTimeStamp'
  • Setting this to false will disable the time stamp that is added to the end of a map's file name
• Reorganized the settings file to be more neat
• Spice blooms are now ensured to be spread across the map more evenly
• 'Islands' can now become merged with the rock-to-sand openings in the cliff walls 
• Altered the list of rock tiles in use

The new version can be downloaded above in the first post of this thread

As well, here are things that still need to be done or fixed:

• Add support for all the other tilesets
• The auto creating of the values when 'useSettings' is false needs to be done better, the equation used needs to give a result more appropriate for the map size. It is in the method 'autoEq()'
• The edges of the dune patches are mostly incorrectly put on, they need to be redone to be perfect
• The rock-to-sand edges are sometimes incorrectly put on, especially on the edge of the map when touching a cliff face, they need to be worked on. Example: 

Spoiler

• Occasionally a cliff wall opening will have a detached end tile, this needs to be looked into and fixed. Example:

Spoiler

• Occasionally a cliff wall will not connect properly, this needs to be looked into and fixed. Example:

Spoiler

 

Edited March 18, 2017 by shai

[FunkyFr3sh]

Looks cool, very well done! Didn't thought it's possible to generate a random map that well

Will play around with the tool a bit the next days

 

good job

Edited March 20, 2017 by FunkyFr3sh

[shai]

Hey @Klofkac, I got a question about the other files with your map editor. Why is the 'default_ai.misai' file included only 7607 bytes when the template on the wiki and the game seems to require it to be 7608 bytes?  

Edit: I think I found out, the first byte is supposed to be the player number, oops 

Edited March 20, 2017 by shai

[Klofkac]

So I tried out your last version (v170317) and it does not work for me, because whenever I start the map generator, it runs forever and never finishes (like it gets stuck in an infinite loop). I tried to enable the exportAll option to see what's going on, and the last phase it exports is 23 addDunes, so it looks it gets stuck on phase 24 addSpice. So I tried to change the spice settings, first lower them, then set all numberOfBlooms, numberOfEmptyBlooms and numberOfSpiceSquares to 0, but without success. Could you please look where it might get stuck?
Also I got some idea. You could log the phases into console, so that user can see what the program is actually doing (and possibly also how long each step lasts) and where it gets stuck (if it happens), without need to enable exportAll option.

[shai]

35 minutes ago, Klofkac said:

So I tried out your last version (v170317) and it does not work for me, because whenever I start the map generator, it runs forever and never finishes (like it gets stuck in an infinite loop). I tried to enable the exportAll option to see what's going on, and the last phase it exports is 23 addDunes, so it looks it gets stuck on phase 24 addSpice. So I tried to change the spice settings, first lower them, then set all numberOfBlooms, numberOfEmptyBlooms and numberOfSpiceSquares to 0, but without success. Could you please look where it might get stuck?

I do recall running into this problem the other day, but I believe I have fixed it. In my case, it was because the other settings were not being resized correctly to account for the smaller map size, and by the time it got to that step there just was no more room left. I will go and add in some measures to prevent any step from getting stuck like that. 

Quote

Also I got some idea. You could log the phases into console, so that user can see what the program is actually doing (and possibly also how long each step lasts) and where it gets stuck (if it happens), without need to enable exportAll option.

That's a good idea, I will do that as well. 

[shai]

Updated: v170322

• Implemented safe guards to prevent the program from locking up; you may now set the settings as high as you want 
• All 7 original tilesets are now supported
• Now creates a .mis file to go with the map
• Added new setting: 'addMis'
  • Setting to true will create a .mis file, false will not
• Added new setting: 'autoSpaceSpawns'
  • Setting to true will use a new, better method to add the spawn points in a more evenly distributed layout. 'spaceBetweenPoints' is not used under it
• A 'README.txt' file is included which explains the settings and how to use the generator

The new version can be downloaded above in the first post of this thread

Edited March 23, 2017 by shai

[Klofkac]

Great! Nice to see another update so fast. I'll try it out once I get some time for it.

But in the meantime, I'd like to mention two other random generation methods I was thinking of, and still I am quite curious how well would they work if I really implemented them.

1. I got inspiration for the first method from an existing project somebody is working on. The project is called "Markeen" and it is random level generator for Commander Keen, a classic and legendary 2D platformer game from early 90s. In short, this is the key idea of the random generation algorithm:

Quote

I started a small project called Markeen. My goal is to be able to randomly generate levels for any Keen Galaxy-ish game. This will be accomplished by profiling an existing set of levels to determine the probabilities of each tile appearing next to every other possible tile, then using those probabilities to build a new level. It's kind of like Markov models for text, hence "Markeen".

You can find more information under this link. Scroll to the bottom, as the oldest posts starts at bottom and newer appear upwards. It's really interesting to read and there are good examples (screenshots) of the levels it produced. As you can see, the levels it generates are quite cluttered mess which are not playable at all and need lot of human modifications to become playable. However, it's actually improving during the time, and I'm really curious how well this method will work for Dune2000 maps, after creating probability profiles from all stock maps.

2. The second method is purely my own idea. It'd be easier to explain with visual examples, but I just try briefly describing it anyway.
The map generator first generates all rock-sand and sand-sand cliffs and rock borders. After this, it fills enclosed rock areas with rock, and then generates dues and spice patches and adds some special tiles in similar way as your generator does.
It starts up randomly placing several "seeds" in an empty map. A seed is any single rock-sand cliff, sand-sand cliff or rock border block. Imagine it places just one seed, which is a top-down cliff. Then it has two "connection points", one on the right side and one on the left side. The map generator randomly picks any appropriate block which can be connected to the either side of the block, then it places it, and the process repeats until no connection point is available. It is exactly same principle as how Domino game works. It can create really interesting and crazy shapes, but the biggest problem is to secure that it connects two distant connection points together, forming an enclosed area or cycle.

[shai]

3 hours ago, Klofkac said:

Great! Nice to see another update so fast. I'll try it out once I get some time for it.

Yes, I am quite glad it's coming all together so quickly now

Quote

But in the meantime, I'd like to mention two other random generation methods I was thinking of, and still I am quite curious how well would they work if I really implemented them.

1. I got inspiration for the first method from an existing project somebody is working on. The project is called "Markeen" and it is random level generator for Commander Keen, a classic and legendary 2D platformer game from early 90s. In short, this is the key idea of the random generation algorithm:

Quote

I started a small project called Markeen. My goal is to be able to randomly generate levels for any Keen Galaxy-ish game. This will be accomplished by profiling an existing set of levels to determine the probabilities of each tile appearing next to every other possible tile, then using those probabilities to build a new level. It's kind of like Markov models for text, hence "Markeen".

You can find more information under this link. Scroll to the bottom, as the oldest posts starts at bottom and newer appear upwards. It's really interesting to read and there are good examples (screenshots) of the levels it produced. As you can see, the levels it generates are quite cluttered mess which are not playable at all and need lot of human modifications to become playable. However, it's actually improving during the time, and I'm really curious how well this method will work for Dune2000 maps, after creating probability profiles from all stock maps.

Very interesting, I briefly thought of this kind of method the other week but I did not dig too far into the idea. I will definitely look more into it now though, but I'll need to first learn how that type of generator generally works 

Quote

2. The second method is purely my own idea. It'd be easier to explain with visual examples, but I just try briefly describing it anyway.
The map generator first generates all rock-sand and sand-sand cliffs and rock borders. After this, it fills enclosed rock areas with rock, and then generates dues and spice patches and adds some special tiles in similar way as your generator does.
It starts up randomly placing several "seeds" in an empty map. A seed is any single rock-sand cliff, sand-sand cliff or rock border block. Imagine it places just one seed, which is a top-down cliff. Then it has two "connection points", one on the right side and one on the left side. The map generator randomly picks any appropriate block which can be connected to the either side of the block, then it places it, and the process repeats until no connection point is available. It is exactly same principle as how Domino game works. It can create really interesting and crazy shapes, but the biggest problem is to secure that it connects two distant connection points together, forming an enclosed area or cycle.

The way I was planning on generating the sand-sand cliffs is similar to this, though all I have for it so far are the tiles drawn out on a piece of paper, no real code or anything made for it. Hopefully by the start of next week I will have actually started on it. But doing that for everything like you say would be rather interesting as well, but fairly difficult too. I don't think I'll be trying anything like that too soon, but I will hold onto the idea

[D2k Sardaukar]

Talking about algorithms, you could also try Perlin noise as a base for the height in the map. Use different levels of gray for the height.

I tried that here: https://forum.dune2k.com/topic/21583-r8-and-r16-graphics/?do=findComment&comment=390146

It did kinda work (edges very problematic), but it looks very "organic" in layout, your method has more "cubic" style which fits Dune 2000 better in my eyes.

Nice work, by the way , please keep going! And also please post more images  

Edited March 25, 2017 by D2k Sardaukar

[Klofkac]

On 23. 3. 2017 at 2:21 AM, shai said:

Updated: v170322

Ok, so now I tried it out. Again, I ran into the same problem as before, the program just runs forever and never finishes and needs to be killed. I realized that it freezes even during the very first phase (place spawn points) because it did not output "Player spawns added" message. So I turned off the setting "autoSpaceSpawns" and then it got past the phase "Dunes added" and froze on addSpice phase again, same as with the previous version. So I decided to look into the source code to see what's wrong here.

On 23. 3. 2017 at 2:21 AM, shai said:

Added new setting: 'autoSpaceSpawns'

• Setting to true will use a new, better method to add the spawn points in a more evenly distributed layout. 'spaceBetweenPoints' is not used under it

Well, the problem is, that this new method doesn't work. Apparently you use the exactly same method for placing spice blooms, that's why same problem is here. The problematic part is the double for-loop (one with "i" and one with "ii" variable), which just takes HUGE amount of time.
What I understand, your new method works this way: When it's attempting to place a spice bloom, it tries to place it as far as possible from any existing spice blooms. So it picks randomly some coordinates and checks the largest possible surrounding area around it, whether there is any existing spice bloom in it or not. For the same area diameter, It tries several different coordinates (ii-loop), and if no success, it decreases the diameter by 1 (i-loop) and tries the same again.
The worst is, that this method utilizes 4-level loop (2 levels for checking the surrounding area and 2 levels as I mentioned), leading to O(N^4) time complexity (where N is size of the map)!!!!!!! Which is really not usable in practice. Maybe your computer is faster than mine or you tried with smaller coordinates than 128*128, but for me, it would take forever to generate map using this method. So you definitely need to rework the method to be more optimal, or just use the "old" method for the time being.

Edited March 25, 2017 by Klofkac

[shai]

2 hours ago, Klofkac said:

Ok, so now I tried it out. Again, I ran into the same problem as before, the program just runs forever and never finishes and needs to be killed. I realized that it freezes even during the very first phase (place spawn points) because it did not output "Player spawns added" message. So I turned off the setting "autoSpaceSpawns" and then it got past the phase "Dunes added" and froze on addSpice phase again, same as with the previous version. So I decided to look into the source code to see what's wrong here.

Well, the problem is, that this new method doesn't work. Apparently you use the exactly same method for placing spice blooms, that's why same problem is here. The problematic part is the double for-loop (one with "i" and one with "ii" variable), which just takes HUGE amount of time.
What I understand, your new method works this way: When it's attempting to place a spice bloom, it tries to place it as far as possible from any existing spice blooms. So it picks randomly some coordinates and checks the largest possible surrounding area around it, whether there is any existing spice bloom in it or not. For the same area diameter, It tries several different coordinates (ii-loop), and if no success, it decreases the diameter by 1 (i-loop) and tries the same again.
The worst is, that this method utilizes 4-level loop (2 levels for checking the surrounding area and 2 levels as I mentioned), leading to O(N^4) time complexity (where N is size of the map)!!!!!!! Which is really not usable in practice. Maybe your computer is faster than mine or you tried with smaller coordinates than 128*128, but for me, it would take forever to generate map using this method. So you definitely need to rework the method to be more optimal, or just use the "old" method for the time being.

I realized after that there were still some parts where it could get stuck, but I should have fixed all of those occurrences by now. What settings are you running it on? I have not had it get frozen up on me when I tried values that were higher than the default, and certainly not when they were on the default. But I do notice that those parts do take a little bit longer than all the others, I will have a look at redoing them. For me, it takes roughly 1 minute and 30 seconds to make a map at 128*128, with a .mis file, which I now realize is probably much too long to wait for a map to be made. I suppose it's also worth mentioning that a decent amount of that time over all is spent writing the map and mis file to the disk, so it'd be a good idea to rework that area as well. 

I only have one computer to test this on, so I appreciate your feed back. Problems like this where it runs slowly on some systems are definitely a big issue

[shai]

15 hours ago, D2k Sardaukar said:

Talking about algorithms, you could also try Perlin noise as a base for the height in the map. Use different levels of gray for the height.

I tried that here: https://forum.dune2k.com/topic/21583-r8-and-r16-graphics/?do=findComment&comment=390146

It did kinda work (edges very problematic), but it looks very "organic" in layout, your method has more "cubic" style which fits Dune 2000 better in my eyes.

Nice work, by the way , please keep going! And also please post more images  

That looks like a pretty creative way to make a map, quite interesting. And thank you! 

[shai]

I've started work on the previously mentioned 'Markov' type idea, and to start I compiled a list of all tiles in the 36 stock maps. data.zip

Inside are 800 text files, one for each tile. Inside each text file are 8 sections called 'direc_', with '_' being a number from 0 - 7, This 0 - 7 number represents a direction from a particular tile, the directions go in a clock-wise circle starting from the top left. Under each section are all 800 tiles listed again with the number of times that they occurred in that direction, from that particular tile. In case you have no idea what the heck I'm talking about, here's a visible example: 

The empty square in the middle is any particular tile. Under the section [direc4] are the number of times any other tile appeared in the bottom right of that tile.

Looking at one of the text files for another example, in '48.log' under the section [direc4] is '52=561'. This means, with all the stock maps put together, tile 52 appeared a total of 561 times at the bottom right of a 48 tile. In '480.log' under [direc5] is '411=1', tile 411 only ever appeared once directly below the tile 480.

 

This probably isn't enough to make a good working generator of this type, but it's a start 

[Klofkac]

On 26. 3. 2017 at 1:47 AM, shai said:

What settings are you running it on?

Always when I download a new version of your map generator, for first I try it on the default settings (just run run.bat) and after that I try to modify the settings.

On 26. 3. 2017 at 1:47 AM, shai said:

But I do notice that those parts do take a little bit longer than all the others, I will have a look at redoing them. For me, it takes roughly 1 minute and 30 seconds to make a map at 128*128, with a .mis file, which I now realize is probably much too long to wait for a map to be made.

Yes. The parts where you use your "new" method of distribution (placing spawns with autoSpaceSpawns on, and placing the spice blooms) take excessively long time. Actually, as I previously complained that the program got stuck in infinite loop, that was probably not true, your algorithm was just taking time. In comparison, all other phases of the map generation took just fractions of a second, with one or few exceptions which took a few seconds.
I personally think that 1 minute and 30 seconds is way too long time. As I said, you might have a faster PC or something, but for me it was taking much more.
With the two first versions of the program you released, generating a 128*128 map took something between 5 and 10 seconds, which is reasonable time. So generating a map should really take no more than 10 seconds (maybe 15), so this should be your objective. You should take care about effectivity of your algorithms, so whenever you implement something new and generating a map takes significantly more, you need to rethink or remake it.

On 26. 3. 2017 at 6:03 AM, shai said:

I've started work on the previously mentioned 'Markov' type idea, and to start I compiled a list of all tiles in the 36 stock maps.

Good work, so I'm curious how well this method will go. If you get some first results, don't hesitate to post screenshots here.
I just have a few ideas. I looked at the files you generated and I personally think you really do not need to write values of 0 here (as 0 is really frequent value and should be default), which will lead to much smaller and better readable files. The second idea is that you could group all "clean sand" and "clean rock" tiles together and threat all of them as a single tile index. The idea is, there are like 10 different indexes of "clean sand" tiles and 15 "clean rock" tiles, which all look very similar and can be completely randomized. So I think this could optimize your algorithm.

And now some more notes.

• I see you removed the pictures with examples of a map generated with default settings from your first post. I don't think it was a good idea, because it's actually good practice to provide a quick demonstration of what your program can do, before anybody decides to download it.
• I recommend you to use some version control tool to track your development and changes in source code. The most used one is Git and you create a Git repository for free on github.com . I don't know whether you used anything like this in your life but this has actually many advantages. First, all states ("versions") of your code are tracked and archived, so you can look and compare what was changed between the previous and current version. Second, anybody is able to download your source code from github, so you do not need to always zip and upload it manually. And third, github allows collaboration of more people, so anyone else can make changes in your code and push (upload) them to your repository. Mine github repository for the map and mission editor is here: https://github.com/jkoncick/D2kEditor

Edited March 27, 2017 by Klofkac

[D2k Sardaukar]

I tried to make a 64x64 map (other settings kinda halved) and even after 5 minutes of running it was still not done... Don't want to sound rude, but your code, method or implementation needs some major overhaul for speed improvements. Or prevent while loops from getting stuck? Maybe try combining and minimizing for-loops.

I also tried to make a 16x16 map which seems to go a lot faster, but it crashes at:

Entrances edges reapplyed
Exception in thread "main" java.lang.NullPointerException
        at d2kmapgen.GenrateMap.checkSpacingDiagonally(GenrateMap.java:6820)
        at d2kmapgen.Main.createBoard(Main.java:982)
        at d2kmapgen.Main.main(Main.java:1179)

Any suggestions to what settings to use for a 16x16 or 32x32 map?

I would also suggest making the numberOfSpiceSquares and other squares variables dimensionless. Turn it into a percentage for example (like dune is max 20% of the map, rock 30%, etc). Lol, I read it as squared, hmm, perhaps still a percentage would make more sense, I have no idea how many squares there could fit in a 128x64 map for example.

Edited April 1, 2017 by D2k Sardaukar

[shai]

43 minutes ago, D2k Sardaukar said:

I tried to make a 64x64 map (other settings kinda halved) and even after 5 minutes of running it was still not done... Don't want to sound rude, but your code, method or implementation needs some major overhaul for speed improvements. Or prevent while loops from getting stuck? Maybe try combining and minimizing for-loops.

I also tried to make a 16x16 map which seems to go a lot faster, but it crashes at:

Entrances edges reapplyed
Exception in thread "main" java.lang.NullPointerException
        at d2kmapgen.GenrateMap.checkSpacingDiagonally(GenrateMap.java:6820)
        at d2kmapgen.Main.createBoard(Main.java:982)
        at d2kmapgen.Main.main(Main.java:1179)

Any suggestions to what settings to use for a 16x16 or 32x32 map?

I would also suggest making the numberOfSpiceSquares and other squares variables dimensionless. Turn it into a percentage for example (like dune is max 20% of the map, rock 30%, etc). Lol, I read it as squared, hmm, perhaps still a percentage would make more sense, I have no idea how many squares there could fit in a 128x64 map for example.

Oh yes, I know it still needs to be majorly improved, in the last version I posted there were still a few points left over where it could get stuck, but in the most current version I'm still working on it should be all good. Hmm, I'm not too sure what was the cause of that crash there, when I try a 16x16 map on that same version it runs fine, but I'll look into the cause of it. 

But a 16x16 map anyways is pretty much useless, since it's just too darn small. A 32x32 map is better, and mathematically the settings should be about 6.25% of the default values, although they would certainly need to be a little bigger than that, maybe about 10% or so. Now, it obviously would be annoying to manually change each value individually, and while there is the setting 'useSettings' which approximates most of the settings based on the size of the map, it would benefit from a large overhaul in general on that. It's starting to feel a little like all the settings are getting a bit disorganized, so I'll need to start rethinking a fair bit on bringing them all back together. 

I'm now using a percentage on the special tiles, for example the new setting 'sandSpecialFreq' set to 0.004 would have 0.4% of all sand tiles occupied by a sand special tile, I'll for sure see what I can do about making all settings work on a percentage system like that. 

[shai]

On 3/26/2017 at 4:12 PM, Klofkac said:

Always when I download a new version of your map generator, for first I try it on the default settings (just run run.bat) and after that I try to modify the settings.

Yes. The parts where you use your "new" method of distribution (placing spawns with autoSpaceSpawns on, and placing the spice blooms) take excessively long time. Actually, as I previously complained that the program got stuck in infinite loop, that was probably not true, your algorithm was just taking time. In comparison, all other phases of the map generation took just fractions of a second, with one or few exceptions which took a few seconds.
I personally think that 1 minute and 30 seconds is way too long time. As I said, you might have a faster PC or something, but for me it was taking much more.
With the two first versions of the program you released, generating a 128*128 map took something between 5 and 10 seconds, which is reasonable time. So generating a map should really take no more than 10 seconds (maybe 15), so this should be your objective. You should take care about effectivity of your algorithms, so whenever you implement something new and generating a map takes significantly more, you need to rethink or remake it.

Ok, I've made some quick changes to hopefully reduce the time it takes for now, later on I'll rework it completely. My PC is a Pentium E5300 @ 2.60 GHz with 4GB of RAM, I'm not sure if I'd consider that too fast, since it gets pretty slow sometimes, but I don't know what other people have. 

The only other spot where it takes a long time is "Entrances edges added" after the islands are added, it runs for about 8 seconds or so on just it, so I need to fix that too

Quote

Good work, so I'm curious how well this method will go. If you get some first results, don't hesitate to post screenshots here.
I just have a few ideas. I looked at the files you generated and I personally think you really do not need to write values of 0 here (as 0 is really frequent value and should be default), which will lead to much smaller and better readable files. The second idea is that you could group all "clean sand" and "clean rock" tiles together and threat all of them as a single tile index. The idea is, there are like 10 different indexes of "clean sand" tiles and 15 "clean rock" tiles, which all look very similar and can be completely randomized. So I think this could optimize your algorithm.

I'll work on that some more when I have the time, I wont make it much of a priority just yet. 

Quote

And now some more notes.

• I see you removed the pictures with examples of a map generated with default settings from your first post. I don't think it was a good idea, because it's actually good practice to provide a quick demonstration of what your program can do, before anybody decides to download it.
• I recommend you to use some version control tool to track your development and changes in source code. The most used one is Git and you create a Git repository for free on github.com . I don't know whether you used anything like this in your life but this has actually many advantages. First, all states ("versions") of your code are tracked and archived, so you can look and compare what was changed between the previous and current version. Second, anybody is able to download your source code from github, so you do not need to always zip and upload it manually. And third, github allows collaboration of more people, so anyone else can make changes in your code and push (upload) them to your repository. Mine github repository for the map and mission editor is here: https://github.com/jkoncick/D2kEditor

Ok, I'll add those pictures back in and continue adding them. 

Yes, I know about github and I've checked out the one for your map editor a few times before. Though to be honest, going into it without knowing too much was pretty confusing, and I only got as far as setting up an account before I didn't really know where to go. It didn't help that the program to manage it ran horribly slow on my system. When I'm finished with this version I'll go back and try at it again.