gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Random level generation

#14623 - poslundc - Sat Jan 10, 2004 12:40 am

I'm toying the idea of randomly generating the battle arenas for my RPG instead of using pre-made ones.

I've done some net research on random terrain generation, but most of what's out there does not suit my needs, as they are trying to create landscapes based on height whereas I am trying just to place random elements on a field in an aesthetic way.

For example, there could be a dirt path, or some cobblestone, or a big patch of grass, or a pool of water, but they must not intersect each other and they don't relate in terms of altitude (ie. dirt has as good a chance of being next to water as grass or cobblestone does).

So far the most promising idea I've found is a province/spoke based system that creates distinct regions and paths between them. I think this could work, but I thought I would see if anyone had some other suggestions.

Thanks,

Dan.

#14639 - sajiimori - Sat Jan 10, 2004 2:10 am

The reason the province/spoke idea works well is because it starts by arranging the space in terms of its most important aspects (provinces). More generally, the aspects of a level can be arranged into a hierarchy based on their 'authority' to allocate space in the level.

Aspects that affect gameplay would be given the most authority, while decorations would have the least. Also, aspects that involve many side-effects should be given greater authority than those which require no additional support. For instance, a house might require a garden and a path that leads to the door, but it is ok to have a rock with nothing around it.

An aspect can be represented as an array of component aspects, each having a range of desired quantities and a list of interactions with other existing aspects (for instance, MonsterGroups could repel each other, while being attracted to TreasureStashes).

The root aspect would presumably be the Level. The lowest level aspects (leaves) would have no components, and would immediately try to allocate space and draw themselves on the map.

You would need an array that corresponds to the level of authority required to overwrite each part of the level. When an aspect wants to use some space, it can only do it if it has the authority. If it succeeds, the authority required would be set to that of the aspect itself.

With a detailed hierarchy of aspects, this sort of system could result in more organic, flowing levels that aren't divided up in any obvious way.

#14640 - jma - Sat Jan 10, 2004 2:12 am

Actually, using fractal terrain height maps is an excellent method of doing what you want. Water, trees, etc. all relate to various height levels on the map.

Once done, randomly place various objects at locations that are at least a specific distance from one another. You can use the height map as a tile/cost based system, and use this and A* to generate paths between objects (like roads between towns).

There are other methods, but in my experience, starting with a good heightmap makes life a whole lot easier...

Jeff
_________________
massung@gmail.com
http://www.retrobyte.org

#14642 - tepples - Sat Jan 10, 2004 2:28 am

Jma's advice is sound. How did real societies on Earth decide where to put their towns? They looked at a height map and a drainage map.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#14643 - poslundc - Sat Jan 10, 2004 3:13 am

jma wrote:
Actually, using fractal terrain height maps is an excellent method of doing what you want. Water, trees, etc. all relate to various height levels on the map.


Water and trees do, but what about dirt and grass and flowers and stones and cobblestone paths? These are many of the things I'm looking to place, and they need to be placed next to each other in a pseudo-random fashion. Height maps won't accomplish this, because with a height map it would mean that all of the dirt is next to all of the flowers and stones, but never next to the grass.

I should perhaps clarify: my engine is Mode 7, and because of that the terrain is mostly flat, except for a few "tricks" (eg. pools of water). This will also be used for other situations: caves, mountain trails, etc. mostly to add decoration and simple obstacles.

Meanwhile, it looks like I'm back to figuring out the best way to do a Delaunay Triangulation on the GBA... :P

Dan.

#14649 - sajiimori - Sat Jan 10, 2004 4:40 am

I just got back from dinner and read my post again -- man, I can hardly understand it myself! hahah

#14652 - Miked0801 - Sat Jan 10, 2004 5:52 am

Wow. This is an interesting problem. I'm gonna sleep on it and see if I can come up with something insightful. I have a few ideas, but want to let them stew for a bit.

Mike

#14657 - sgeos - Sat Jan 10, 2004 7:46 am

poslundc wrote:
I should perhaps clarify: my engine is Mode 7, and because of that the terrain is mostly flat, except for a few "tricks" (eg. pools of water). This will also be used for other situations: caves, mountain trails, etc. mostly to add decoration and simple obstacles.


It seems that you may be confusing display with internal representation. You can generate a height map and represent a map as such internally even if you display a flat mode 7 map.

You could generate a height map and a vegetaion map. Depeneding on the heigt and vegetation level you can decide what the chances of a tree or flower or dirt are.

After the height map has been generated, and before you do anything based on on the vegetation map, you'll have to have code that looks at what you have and places man made objects accordingly.

After the high priority man made objects- including paths, are out of the way, then you bother with figuring out what vegetation is present.

Your cobblestone will be a man made feature. A dirt path could also be a man made feature. Dirt on its own could show up in low vegetation areas.

I've looked into random map generation in the past. Here are some articles I have read:
http://www.geocities.com/SiliconValley/Bay/2535/randommap.html
http://www.hut.fi/~vesanto/link.useful/maps/mapping.algorithms.html
http://roguelikedevelopment.org/development/FAQ.php - read from 6.2
http://kuoi.asui.uidaho.edu/~kamikaze/GameDesign/art07_rogue_dungeon.php

-Brendan

#14669 - poslundc - Sat Jan 10, 2004 5:10 pm

My problem isn't with the conflict between internal/visual representation. It's with the way that fractal heightmaps work on a gradient.

I basically want to put things in "clusters", and it's vitally important that those clusters don't touch. A fractal heightmap generates those clusters for me (by taking high and low altitude regions), but it doesn't help me to distinguish between those clusters (ie. tell where one starts and one ends) or determine what kind of thing goes where.

That's what the province/spoke system does, although trying to compute these Voronoi diagrams internally is not fun.

Also, with the province/spoke system I can easily combine two adjacent provinces to make more interestingly-shaped clusters, and I'm not certain that I can do that with fractals.

Dan.

#14671 - tepples - Sat Jan 10, 2004 6:10 pm

It appears the fastest Delaunay triangulation algorithm is Dwyer's algorithm. It's too bad that CiteSeer doesn't carry Algorithmica, the journal that first published Dwyer's explanation of the algorithm.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#14673 - Miked0801 - Sat Jan 10, 2004 6:34 pm

Clusters huh. Ok. Make your vegatation map with one of the listed ideas, then randomly pick a few good (non mountain/rock/water) areas that are far aprt and seed a town. From this seed, throw a bunch of small seeds randomly from the center - but within a very small distance. Repeat until you have a good civilization area. SHould make for nice clusters of town that grow out nicely.

Mike

#16591 - poslundc - Fri Feb 20, 2004 2:59 am

Well, for those interested in what I ended up doing, I used Perlin Noise (thanks DekuTree64 for the idea) as my basis for terrain generation. Using this, I can represent a 256x256 tile map by a random 32x32 heightmap in IWRAM.

Then in order to separate the "islands" (so I can distinguish where one terrain type starts and another ends) I use a recursive paint-fill algorithm to assign different identifiers to another 32x32 matrix based on the heights in the first one. (This is where the Perlin Noise technique really shines; a recursive algorithm on an entire 256x256 map would be a non-starter, but it works just fine with a 32x32 array in fast RAM.)

Next the 32x32 island data is rendered to a 256x256 map in EWRAM with linear interpolation. Finally, the data from the 256x256 map is transferred to another 256x256 map in EWRAM, with the terrain identifier keys replaced with the actual map tile numbers and an additional algorithm used to determine the border pieces around the edges of all geometries.

As a final bonus, I use some of the heightmap data to construct "paths" of a random terrain type just for the portion of the map lying within a random circle. (I could fill the paths everywhere, but it looks a lot more congested and artificial when I do.)

Here are some images (zoomed out to reveal a larger portion of the terrain, so it doesn't look as good as when scaled to 100%):

[Images not permitted - Click here to view it]
[Images not permitted - Click here to view it]
[Images not permitted - Click here to view it]

Eventually I will add a mode for islands that aren't just "filled" (with grass or water) but can instead have randomly-strewn tiles (eg. stones or flowers) at a certain density.

I'm pretty happy with the results overall. A 256x256 map takes about a second to generate on hardware, which shouldn't be too bad when combined with some battle-entry transition effects. (All of the code is currently in plain C running in Thumb/ROM, so I can do plenty of optimization if needed.)

Thanks for the various suggestions,

Dan.

#16598 - yaustar - Fri Feb 20, 2004 9:15 am

Very very nice :)
_________________
[Blog] [Portfolio]