Random Map Generation

I''ve have never done such a thing, but I can tell you how I would do it. First of all, linked lists would definitely not simplify the solution and would just complicate things. Leave it in a simple array. I don''t know exactly what you want on your map, but I''m assuming that you want something like trees, mountains, rocks and lakes (rivers would be too hard to implement). I''ll just use a mountain as an example (because its probably the most complicated). I''ll assume that you keep track of mountain tiles by storing their height. I would just choose a few random tiles and give them each a height of 1 or 2. Then I''d have a loop that executes a bunch of times (perhaps a certain predefined number of times, or until the map has reached a predefined average height), and each time all tiles that are adjacent to a mountain tile will have a random chance of increasing in height, the odds being better for tiles which are adjacent to heigher surrounding tiles.

I hope I explained well and that this was useful.

hmmmm....

Thanks alot, I actually didn''t give a height consideration to mountains. Actually, I''m starting out very simple. For the purposes of this thread, lets just say there are two tiles:

Water, and land.

I will consider the mountain thing thogh. It sounds like it could work! Hehehe

Any other suggestions for just, water and land tiles?

One option: Make subdivision plasma/multi-octave perlin noise, make every value above the halfway point water, and the rest land.

Another option, less realistic, but better than you might assume: Have an "ant" do a random walk on the water; wherever it goes turns into land.

make a random number (within set ranges) of ants with random starting locations (and they may or may not be allowed to start near each other), and then give them a random lifespan (number of steps).

So this algortihm has the following controllable areas:

- range for number of ants
- minimum distance for starting ant distance (can be 0)
- walking patterns, ie: completely random, or a disposition to either go in same direction or turn or whatever
- range of values for lifespan
- a bool deciding if "lifespan" is number of steps, or number of squares changed (so that walking over squares again doesn''t reduce total land)

I have no idea how this would turn out ... but I can see a very definate easy way to code it, which is a plus. After coded, play with a couple different sets of numbers, and see if any looks viable at all (BTW, print out the controlling parameters you test and at LEAST 5-10 maps of each type, to see how consitent or varied they are)

good luck.

Also, that perlin noise idea is cool ... basically, anything which works for cloud generation could be made to work for land generation, except remeber this, clouds form in a free 3d open space, where land form shapes due to techtonic shifts and fault lines ... and then errosion - so the perlin noise algorithms (and the random ones) will eventually want to be expanded and made more complicated in order to allow for more "grouping" of like tiles (also due to temperature), but still allow for abrupt shifts ... but that''s more advanced than you need right now.

I like the ants idea. I agree that perlin noise may be too complicated to get into. I mean, it''s just a 2d tile map for gods sake :D

In any case, I have done "ant" type algorithems before with some success. My major problem was lack of control. I got alot of "land-trails", these don''t look good on continents.

I belive I could perhapse confine the ants to a given region, like a large rect for one continent, etc. That would likely ensure more self contained land masses.

Perhapse, many ants with short life spans as you said will remediy the need for more coherent, self-contained land masses.

I think I will try and test this method first. Thanx for all the help!

If anyone else ahs suggestions, please let me know. I''ll keep you all updated.

if you like the ants idea, you'll love BlotchMaker, which is the map generator for my project:

http://www.project-axis.net/

feel free to download the current v0.1 demo to play with it, and download the entire source code for it if you want.

BlotchMaker has so many options, it's a science all to itself :-)

here's a screenshot:

http://www.project-axis.net/artbin/screens/snapshot22.png

the maps it makes aren't quite what you would get in a civ game, but you could easily get close with the right options (or very far away, alternatively). Basically, it relies on placing a certain number of one-after-the-other tiles in a series, with each tile's placement being randomly rolled for based on a series of "turn persuasion" which can make the "blotch" look like a straight line or continent depending on how you set it. It also supports "brush types", number of blotches, tiles per blotch, edge gravity, obstacle types (water, land, fort, whatever you program it for), deterioration, empty/filled reversal, and a slew of other options.

hope that helps a bit

[edited by - leiavoia on October 3, 2003 11:13:33 PM]

Well, I ended up takeing a rather novel aproach.

I randomly lay down a big square, this is the proto-continet. Then I scand the continent, any square that touches watter, has a 50/50 chance of beind ''deleted''. There is a sertain quota of tiles to delte, so the program scans back and fourth across the square untill the quota is met.

Make about 10 of these big blocks, repeat the steps above, and you got your self some nice looking land masses

Hope this aproach benifits anyone, who may dig up this thread in teh future. In the meantime, keep posting ideas. Im sure this will come up again.

It sounds like you''ve solved your problem- I like your erosion idea. Another possibility is fractal interpolation of class values (in your case, land and water). Subdivision of the grid would proceed as it normally does with the subdivide-and-perturb methods, but the interpolated values are random selections of the existing neighoboring classes. This method is described in "Real-World Fractals", by Mark Finlay, Keith A. Blanton and Keith Finlay (ISBN 1558513078).

One more height-map generator for all to consider is one presented in the July, 1994 issue of "Dr. Dobb''s Journal" (http://www.ddj.com/). The author''s Web page on the subject is here:

http://www.parse.com/~rk/fractal.html


This one uses repeated application of "fault lines".


-Predictor
http://will.dwinnell.com

You might want to invest into fractal noise generation. It may just be a "simple 2D tile landscape" but you ARE going for a rather broad approach. The best algorithm (and somewhat simplest) would be fractal clouds. With a few inital tiles (say, outlining a continent) you could come up with some very, very good results.

My advice is to have a 2D array of bytes (the screen works wonderfully, you can see it draw itself in real-time ;P) and generate a landscape based on pixels. Suppose you want a 50x50 map, create a 50x50 image. Then establish a range for every tile...

00-32 - Water
33-40 - Sand
41-90 - Grass
91-B0 - Forest
B1-FF - Mountain

You get the idea. The above would generate mountains only in the middle of forests but that''s just an example.

For reference''s sake, here''s a screenie of a rather quick and dirty landscape generated using a fractal cloud. You can get much more realistic results with perlin noise (the second picture) though. By the way, the second one is from an other program I coded to try out stereoscopic vision in 3D simulation; cross your eyes so the two landscapes overlap and you''ll see it in 3D :D But yeah, you get the idea.

Wow... those cloud generations look great!

Hmmm... I mean, they do produce rather nice map''s, I''ll give you that. But for the kind of game I''m building (an 2D isometric strategy/rpg) I think it may be a bit overkill.

Yet I do like it, and am interested in it, especially for later stages of development were height will be a bigger factor do define mountains, hills etc.

I especially like the idea that mountains, coastline, hills, lowlands, valleys etc. Are all logically placed by this algorithem. Do you have any suggested sources for someone beginning to look into this?

Thanks alot for your great suggestion.

Do a search in google for fractal cloud algorithms, should turn up a bunch of pages. It''s a rather simple algorithm that deals with subdividing a grid and tweaking the middle point a little. For instance... not sure how this is gonna turn out...

4...7
.....
.....
.....
7...9

These are your corner pixels. The number''s a color; let''s suppose from 0 to 9. Roughly, the algorithm takes all 4 "corner" pixels and averages them (4+6+7+7 / 4 = 6) then tweaks the result by a small value (say, ±2 here); the greater the value, the rougher the terrain will turn out. It then plots the middle pixel with that color.

4...7
.....
..6..
.....
7...9

The algorithm then recursively subdivides into smaller and smaller regions, always taking the 4 corner pixels in that region until it eventually fills the whole area. You can then do whatever you want with the result. I applied a palette over it to give it a landscape-like look, though you could just as easily make a heightfield out of it or use individual pixels to determine what tile to place on your map.

Here are a few links...

Java source to a fractal cloud applet
Not exactly it but close enough
Veritable storehouse of landscape-related stuff

I''m looking for information about a simmilar but different topic: How would I go about generating a ''base'' for a team game, where each base will consist of rooms, hallways, stairs, and lifts? Also, there are certain kinds of rooms that must exist {but in each base, the required rooms should be different sizes and arranged differently}, such as a spawn room, a store, a vehicle bay, a medical lab, etc. Not only do I need to generate the position and size of rooms and doors, but also the layout of everything in the room and make sure it meets certain requirements. For example, in the spawn room, there need to be at least 2 exits and 3-5 spawn tubes that can be clearly exited to either room exit {ie they won''t obstruct eachother so a person can get stuck in spawn}. In the store room, there are several types of terminals that can be both freestanding and against the wall and there should be a certain mixture of each type without blocking the required 2 exits (not all rooms require 2 exits, some must have only 1, some need several).

Any good hints on how I might go about this?

buy this book http://www.gamedev.net/columns/books/bookdetails.asp?productid=110

this has a chapter on ramdom map generation for 2d games..

Might help

Look into random maze generation alroithms that allow the creation of rooms. With a bit of tweaking you could probably make sure it always generates at least one room with 3 exits, etc, then select a random room out of all the created ones to be the lab, an other for the spawn room, etc...

Hope that helps

For future reference, this isn''t really a Game AI problem, but rather a Game Design or even Game Programming problem. Please try to keep things on topic for this forum.

Thanks,

Timkin

Try this.

Been looking for this link for a long time, in fact. You should be able to find a couple of useful links and suggestions to generate a realistic landscape from that site. Very, very good tutorial, easily understandable.

Hope this helps

This thread should be moved to the graphics section, though. I agree this doesn''t really have much to do with AI

a note on the idea of overkill ...

IF you can get a good map like rune made, then you can turn it into a 2d iso map simply by averaging on a grid ... so if he has float heights, simple partition the heights into ranges ... etc ... the key it to get the interesting coastline, heightmap, and additions, IN ANY FORMAT - and then convert them to your games specific needs ... of course an algorithm custom taylored to a game engine is WAY easier to make spit out balanced maps (maps where multiple starting locations are at least partially "fair" ... Civ3 has a great generation algortihm ... but FAIR is never even attempted - if you save the game early, look at locations, and save later, almost all of the players rankings is based on quality of starting location (for computer players that is) ...

good luck

Re: Random maps for FPS, capture the flag bases.

This is a continuation of the "Ant" idea. A while back I used the ant system to generate Quake 3 maps.

Imagine a big grid of cubes instead of a grid of 2d tiles.

The maps were 3d; I made them by having the ant walk in 3 dimensions, or by making my grid of blocks from multiple 2d maps laid atop one another.

The only change is you need to handle the special case of an ant moving up, in which case you need to add a predesigned "stair" or "ramp" object.

You can also detect corners fairly easily and replaced them with beveled corners, which improves the appearance.

"Rooms" appear as an emergent behavior from when the ant crosses its own path multiple times in a certain area.

The ant also occasionally placed lights of random colors throughout the map, and weapons/objects.


It''s not a terribly sophisticated system, but I think you''ll be surprised by the results you can get.

I once tried something akin to TerranFury''s method (not to long ago, in fact, for a college project for a VB class. Long story short, our end of semester project is anything we wish. I''m making a dungeon crawler à-la rogue) and got sizeably impressive results. No screenie right now though, I ditched the code in favor of something "better" for what I was working on.

What I did initially was generate, say, 10-20 randomly sized rectangles across a 2D grid, not caring if they overlapped. Of course, I kept a tab on the location of each rectangle. This is because I then went from every rectangle and drew a path going to the next one in the list. For instance...

A...C
.....
..B..

Would have paths like...

A./-C
|.|..
\-B..

I was lazy and made the paths go straight down/up to the next rectangle, then straight right/left. Sometimes I''d invert the directions (horizontal then vertical).

I''d end up with a very nice map (especially after placing tiles on it) that wasn''t very realistic but had large rooms and passages. Though right now I''m using a simple linked-room style dungeon.