Map Generator Project
Hello,
Im a final year student who is undertaking the creation of an intelligent map generator for my final project.
i have to create a program in any language (ive chosen java so far), that creates a random terrain map, and places on this a random city (using ai rules) which can be used for a gaming society. Essentially it is a standalone program, in which a GUI appears at the start, allowing settings to be chosen, and the program will use this inputs to create the finished map, using simple 2d graphics. There is an Artifical Intelligence/simulation theme to the project. Something similar could be an AD&D map/city/dungeon generator eg www.mapmage.com, but better :-)
i have searched the web and found some information, but there isnt alot, especially on forums.
These are the things i would like some help on, if possible, and it would be very much appreciated. Please note, i am not trying to get somebody to do the project, i am after only help and ideas, so i can make progress :-)
1. Is java the best code to use for this? (im familiar with jbuilder 7.0 - What java program(s) would be best?)
2. Do u have any interesting links that would be relevant to my project ? e.g. a forum/a webpage/an article etc
3. Have you any information i could use?
Thanks for reading my (first post) and i hope you can help! :-)
[1384 byte] By [
uni2uni2] at [2007-9-30 19:46:19]
I would say use whatever language you are most comfotable using. It's easy to make GUIs and manipulate 2D images in Java if you know how to do it. The underlying generation algorithms don't sound language specific, so go with what you know best.
As for the generation algorithms, I can't find anything relevant, but I would say start by generating roads then add the buildings afterwards.
Generating the terrain is a solved problem.That is, it's a common problem with lots of interesting solutions out there.
Generating the buildings is interesting. I suspect you'd want to start with the normal of the polygon representing the current portion of terrain.For example on a sheer cliff, you're either not going to build a city, or you're going to build one by digging into the cliff face.
Part of the terrain, hopefully, would include rivers, lakes, oceans, etc. Plus possibly flora issues -- woods vs. fields vs. barren rock. A good AI program to generate settlements would take these into consideration, just as humans do in real life. If I were you I'd start in the library, looking up books on ancient urban planning and the like. (This kind of thing may not be online.)
For online searches, if you go to Google and limit your searches to the .PDF filetype, you're more likely to find technical articles, theses, and other academic research type papers.This may be helpful.
firstly, thanks for replying and offering your assistance.
The google searching is looking quick productive and im sure ill get solutions there.
As for creating the AI ill look into that in more depth after the basic terrain generator is made. A rough idea is to divide the map into squares, giving each square a value such as Rock, Plain etc, and using rules to distinguish what can go where, and in what density. The sponsor doesnt particularly want squares ((although they can be edited out), and i want to avoid the the maps looking like chessboards.
Denisity will be an issue for placing the buildings, as current generators on the web such as mapemage seems to place buildings randomly all over the place (ie it isnt dense in the city centre, becoming more spare towards the outskirts) Economics and Technology (ie medieval,industrial,present day) will also play a part.
thanks again for info and if u happen to come across anymore tips.. :-)
It does seem pretty vague so i shall narrow it down a bit for other people.
stage one of the project, which i am concentrating on at the moment, consists of creating a random terrain generator that will perhaps use a tile based system. Each tile will compose of a graphic which is dependant on the type of terrain e.g. Plains/Forest/Mountain/Deep Sea/Beach/Lake. In order to make a realistic map, i have to use AI via a set of rules composed in java. For example, The only tile type a "deep sea" tile can touch (or be beside) is another "deep sea" tile or a "beach tile".
The terrain is not the main issue of the generator ( the main issue is to use AI to create a realistic city on the random terrain using such issues as technology/ecomonics/whether its a village,town,city/tile type eg u cant build a harbour on a mountain etc ) but i cannot proceed until terrain can be randomly generated.
In my paper-based prototype its fairly straight foreward. The user inputs details into a GUI, such as terrain type eg plains/desert/artic. The terrain type will then allow access to another choice. eg. Plains has been chosen, so one option could be "forest coverage" or "mountain coverage", classified as a percentage of the maximum number of squares.
i would basically like help on creating a "blank template" of tiles (which appears in a new window), which can then be randomly filled with different types of terrain, so that a specific tile can be classified as a specific terrain type. At this early stage it does not have to be realistic (ie it doesnt matter that all the "deep sea" tiles are scattered all around the map - i just need to get it up and running - then i can create "rules" to make it more realist, and also to incorporate constraints. The graphical display of this is intended to be simple and 2d. At this stage i intend just to allocate colors to different tile types, although ill later need to add images.
I hope i have been more explanatory on what i am trying to achieve at the moment. If you are able to advise me, then please do :-)
thankyou for reading this.
Here are some ideas for world generation:
Try using perlin noise to generate your terrain. A web search will turn up some good resources on how to create it:
http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
http://www.robo-murito.net/code/perlin-noise-math-faq.html
In a nut shell, perlin noise is the blending together of several sheets of white noise at different resolutions. For example, if you have an 8x8 grid of tiles:
-Go through each square one at a time. For each square, assign each tile a random value between 0.0 and 1.0
-Now go through the tiles stepping by 2x2 squares. For each 2x2 square, pick a random value between 0.0 and 1.0 and add it to the values of each 1x1 square that make up the 2x2 square. An 8x8 grid should contain 16 2x2 squares.
-Now do the same for the four 4x4 squares. Pick a random value for each between 0.0 and 1.0 and add it to the existing values.
-Pick a random value from 0.0 to 1.0 for the last 8x8 square. Add this value to each square.
-Finally, divide the value of each square in your grid by 4. Each square should be a sum of four random numbers, so diving by 4 will scale all the tiles down to a range between 0.0 and 1.0
What you're left with is Perlin noise. (A rather blocky Perlin noise in this case; there are more elegant ways to generate it with sine waves) Perlin noise 'looks' like hazy clouds.If you create a large enough picture of it with 0.0 being black and 1.0 being white, you'll see a greyish shifting cloudy texture.
Perlin noise is also a great root to create terrain from. Look at your Perlin grid; let the value of each square be N. Then:
N < .4 - Sea square
N >= .4 < .5 - Sea shore square
N <= .5 > .8 - Grassland
N >= .8 - Mountain
Now that you've got your basic land, you can add features to it. Create forest squares by creating a second perlin noise grid. Then place forest squares on tiles that are designated 'land' that also have N >= .7 in your second perlin noise grid.
You can create your cities (and special resources) stochasticly - that is, pick a random square on the grid. Then evaluate the 'fitness' of the location. If it is in the middle of the sea, the middle of a mountain range or very close to another city, this is a bad spot for a city. If it's on land and near the coast and resources, this is a good spot for a city. Each time you attempt to place a city, roll a die (ie, choose a random number) to decide if you should place one. Weight the roll so fhat good places need lower numbers to win than bad places. Keep placing cities until you're happy.
Thanks Mark_McKay for your reply. It has been one of the most helpful posts i have read. I am going to have a look at your suggestions now, and have a look to see what i can do.
In another forum, a moderator explained to me that using tiles and various factors to generate a random terrain was not an AI problem but a Constraint-Satisfaction Problem (CSP) ie in my solution, the arrangement of tiles, is constrained by the properties of the tiles. I agree with this to an extent, but simple AI i intend to use consists of rules (e.g. they could be perhaps "True" or "false" in some situations). I believe that the terrain generator will need a little bit of AI, but the city generator will require much more. Have you any suggestions on how to keep an AI theme to the project? The project first creates a random map and then creates a realistic city using this map (I realise i am being vague in regards to the generation of the city, but i wish to do this one step at a time). The end result can then be printed at various scales.
The problem is this - It is not a game, such as tic-tac-toe where the system reacts accordingly to a players move. So how do i convince my sponsor and lecturers who will grade my work in 8 months that the system will use AI, and not CSP, as mentioned by another forums moderator?
Well, the best way to keep an AI feel is to write your code with the idea of AI agents doing your work for you.
Imagine that you had lots of little elves running about your world. Each elf has wants and needs (food, shelter), tactics they can use to enhance their survival (grow food, build fortifications, clear land, steal from another elf, form a partnership with another elf), resources they can find or build (hand tools, armor, rivers for travel, horses for riding), and a limited knowledge of the world (they only know their own little bit; they don't have super knowledge of everything in the world). Design your code not from the point of view of a 'classic' algorithm that looks at the whole world and crunches numbers to figure out where everything should go, but from the point of view of a lot of self interested elves that can help or hurt one another and build useful things like roads and cities in their quest to stay alive. Each day that passes will allow the elves to build more man made features.
Creating the terrain with the fractal method described above and the man made features by simulating this imaginary elf civilization will probably be a decent project your supervisors will be happy with.
