Auto Map Generation / Tile Filling

[Hooman]

Well I've been doing a little work on auto generating maps or filling regions with tiles. Hopefully it can evetually be used to make designing maps easier.

First off, I would like to point out that the code is in a very early test stage and probably needs some rewrite before it could be used in an editor.


Anyways, here's a link to some images of the initial Results. (I don't want to spam dialup users with large images).


The first set (marked initial results) was a simple algorithm that tried to fill each tile once. If it couldn't find a tile that "fit" then it just left it as blue and continued on. This created more problems than just unsightly blue tiles. It also caused areas of the images to be developed seperately and when they came together, there was no way to merge them properly. This resulted in more blue tiles and no real chance to let the user fix things up. (At least not without modifying large regions).


The second set of images (marked 2-x) used a backtracking algorithm to make sure all tiles were filled in. If there were no tiles that "fit" a certain location, nearby tiles could be deleted and it would try again. This lead to much better results as there wre no unsightly blue tiles, and the whole image was developed together so there wasn't the same problem with things not matching up.

There are still a few problems with the second version which I'll eventually be fixing. Those of you who are picky enough to notice, you'll see some of the edges where one terrain type transitions into another aren't quite right. Sometimes blocks that don't represent an edge transition get used. They tend to sort of blend in, so you might not notice so easily, but the flatness of the edge can sometimes be a bit detracting.

Another problem is diagonal banding along terrain transitions. This is fairly evident in all the images. It is a side effect of the weighting used in the random choosing and the order in which the tiles are placed. It is statistically favoured that a new tile is choosen from the terrain type of surounding tiles. However there is also a constraint of the tile having to "fit" with the surounding tiles. So once a transition starts, the seam tends to continue to ensure the fitness, but it lags by 1 tile on the line below since the transition tiles don't usually force the tile below to be a transition tile, but the new terrain after the transition will force the tile below to be a transition tile. Anyways, it's only really a problem because I built the images line by line, starting from the top left, moving down to the bottom right. I plan to mixup the growth in future versions so it can, say, start in the middle and grow in a blob around the starting point. Kinda like the blight.  


This initial version just generates a square of tiles. Really what it does, is it choose a starting seed tile, and grows things by lines from that starting tile (in the top left). Eventually in future implementations, the seed tile(s) can be placed anywhere, and it will grow around them. It will be most effective starting at some central point and growing outwards. That way there won't be any problems with two seperate parts growing together and creating a seam. However, it should (hopefully) also be useful to fill in a bounded region, creating large objects (like volcanoes, craters, wreckage), and (eventually) to fill in seams or ridges between two parts/terrain types. Oh, and it does the polar caps really nicely too.  (thumbsup)


Right now, the growth is fairly unrestricted. But I'm thinking of adding in controls to restrict growth to using tiles from a certain terrain only. I've also got some ideas about having it generate ridges properly, but no idea yet how well that will work out. Anyways, that sort of work seems like a ways off. For now, I'm aiming at something to help fill in flat terrain with matching tiles, but still have a bit of variance so it doesn't become an eye sore.

 

[zigzagjoe]

i have made a slideshow of these images(javascript dealie)

http://radio.punboy.com/slideshow1.html

and why is html disabled in the sapm forum and the forum games subsection? it is disabled that the time of this post.

[Leviathan]

Great work

Also what would be good for the mapper would be is a place tile type, so you can place sand and if your placeing it on flood plain then it lays the transtions around it to fit.

[CK9]

needs a little transition work, but it looks great

[BlackBox]

I think what he did is figured out transitions from the existing maps.vol maps (it recorded all the tiles touching other tiles) so the random map generator used that information to fill in the randomly generated map.
As well, some of the transitions are wrong in the official maps too (it's very hard to notice but you can see it).

Not bad for a beginning though. I wouldn't have had the time to write something like it, so it's nice to see someone doing stuff like this.

[Hooman]

There you go and spill all my secrets.    

And yeah, that was exactly what I did. I also counted the number of occurances of two tiles touching (in that direction) and used that as a weight for choosing the tiles.

Not bad for a beginning though. I wouldn't have had the time to write something like it, so it's nice to see someone doing stuff like this.

Here's the sick part. After a few false starts, it only took about a day for the first initial results, and then another day for the next set.

Oh, and the data used to generate the tiles can be edited to removed the unsightly transitions. I'm probably gonna get Baikon to do most of the dirty work for me.  
 

[zigzagjoe]

you could try having other people (trustworthy) with faster computers run it and then send you the result.

[Hooman]

I meant it took a day to write the code. It only takes about 10 seconds to generate each result. Preparing the data initially took maybe a minute or two (with the current code, the old code written in VB took 20 minutes, and the results weren't very good). But that data preparation is a one time thing. Once it's done, it doesn't have to be done again. Anyways, I'll eventually write more C++ code, which sould speed up the generation some more.

Also, the runtime growth rate in the number of tiles is expected to be linear, so it'd be feasible to generate a full world map with the VB code in about 20 minutes. Of course, that's provided it doesn't get stuck, and I expect the backtracking algorithm would get stuck generating something that large. And the non backtracking algorithm would suck. Anyways, I'm gonna hold off on that large of a project until I fix more things up. This is mostly aimed at getting some nice finishing touches in anyways. Like filling flat regions.

Oh, and future versions of the algorithm might not have such a pleasant linear growth. So don't be too surprised if I come up with something that would take 4 hours/days to generate a world map. Although, whatever I do write, it should be fairly fast for filling in small regions. The problem isn't really choosing the tiles, it's selecting the order in which tiles are filled in, and how backtracking is going to work that will probably slow it down the most.


I would also like to point out that this only selects the tiles. I've done nothing with things like cell type so the "maps" it generates aren't exactly useable. Setting proper cell types would be something left till later if it gets incorporated into the editor or something. Also, my current test app doesn't have any save option built in.
 

[zigzagjoe]

ahh....i thought you ment it took a day to generate a result.

[CK9]

lol, this would be soo great if it were in the editor, would have saved me soooooooooooooooooooo much time on my map

[zigzagjoe]

if you need any help w/ fixing the tile relationships, i would be glad to help too.

[Hooman]

I've extended my auto generation app to allow for editing of the data used in the generation. Basically it generates a map (32x32) and you can visually inspect it for errors (whatever fits on your screen, as there is no scrolling). If you see an error, you can click on it and "delete" the error. Well, you click a tile, and that tile is selected, and the four surrounding tiles are also displayed in a smaller picture box. You can then select the direction which is at fault (by either using the combo box, or clicking on the tile in the smaller picture box which will set the combo box when the tile is clicked on) and then click delete.

After you're done deleting all the errors, you can regenerate the map. Depending on the changes, you might just get local changes near fix, or you might get massive changes across the map. It depends on whether or not backtracking is needed. Although, even if backtracking isn't needed, you'll likely see change anywhere below the fixes. Also, the map generation has two parameters. A random number seed, and a seed tile. The seed tile is the tile placed in the upper left corner, and is used to start the algorithm off by selected tiles that "fit" next to that one. If you give someone else the same random number seed, the same seed tile (and the same generation data file) they will get the same map generated.

You can load and save the data file used to generate the maps, but not the maps themselves. This app was intended mainly for testing out the generation algorithm, and extended to edit the generation data. Don't expect much more. Although, the editing is kinda fun. =)


I posted a few more images of the new app in action. Note that one error being fixed might just reveal another error. So... keep fixing. Maybe I'll post the app soon. Probably a few more fixes before I submit myself to endless bug reports.   I might also want to write code to merge changes from multiple people so I don't have to worry about keeping the running copy in sync with all the changes.



 

[zigzagjoe]

gj hooman. may be you should have a private beta and save urself some pain :heh: .I can see where the map rules could get to be a bugger tho. perhaps use a database of some sort?

[Hooman]

I don't think it should be too hard to create merge code. The custom file format seems to be holding up just fine for me. I'm starting to think maybe have some kind of diff file for submitting changes. So you can keep track of what was removed (and eventually what was added once I get that part editable). Then just apply the diff to a master copy. As long as I don't get a ton of small diffs, hopefully it won't be too bad. I guess we'll see when/if the time comes.

For now, the results are much better from the edits I've done. I was so amused by my own program, I spent a few hours deleting bad fits today. The results look much better than before. Of course, since I'm only deleting the bad possiblilities, and not adding new possibilites, it's only half of the issue. Although, at least it doesn't tend to generate so much stuff that looks bad any more. I've since handed some of the work off to Baikon to continue with. As long as only one person works on it as a time, I won't have to worry about merging changes.
 

[zigzagjoe]

that would be what i would be thinking, except have it 'wieghted' ex, require 3-5 reports or so from diff clients, and then add it to the 'master'. a public beta would be very effective in a case like that.