Archived

This topic is now archived and is closed to further replies.

Automatic Level Design

This topic is 5585 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I can think of 2 ways.

One would be a randomized generator of different map pieces using good ol != and == == meaning that the basic rules say they can connect.

The other is making about 100 or so maps that it randomises for each type of map. The problem with this si I dont know how they get level 2 butcher and stuff like that in em with this method.

Share this post


Link to post
Share on other sites
places like the butcher´s are simply items which are only inserted in specific levels, the rest of the level is more or less built around it randomly.

Share this post


Link to post
Share on other sites
I once wrote a roguelike game that generated dungeon maps like this:

1) begin with an empty level (solid rock in this case)

2) attempt to add a room of a random size and type in a random location; if it overlaps an existing room, cancel the new one.

3) repeat stage 2 until there are the number of rooms you want (being careful that we don''t get stuck!)

4) pick a random point in a room, and try to add a passage N/S/E/W until it hits another room; if it doesn''t, or it scrapes against another passage in an undesired way, cancel it.

5) repeat stage 4 until there are the required number of passages.

The method will be different for different types of map (city, dungeon, forest, death star, whatever) and indeed in my roguelike game there were several variations for different levels. I hope this helps.

Share this post


Link to post
Share on other sites
If you can get your hands on a AD&D first edition Dungeon Master''s Guide (not sure if later versions have it), you''ll find a section detailing how to construct a random dungeon on the fly. It may not translate directly to your game, but I''m sure you could get some inspiration from it.

Share this post


Link to post
Share on other sites
Yes, g''s method is pretty good. My generator (which I wrote using the great ADOM as an inspiration) could combine random rooms with predefined rooms. It just made sure that the exits from the predefined room connected with the rest of the level.

The same principle of being able to balance between how much random you want and how much control you want can be applied to monster generation and item generation.

What I did was that, beside the usual attributes (value, damage, material etc.), each item could have some descriptive qualities that didn''t affect gameplay (classes preferring the object, magical object, ancient item, etc.) . So when defining a room, I could make an request for a random item as general as "costs less than 10 gold coins" or as specific as "golden ancient artifact, being a weapon or a defensive equipment preffered by knights with a value of more than 500 gold coins". Then the game would randomly generate objects until one of them fit the description.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
To look real, you need to have recognizable architecture. In Diablo and various roguelikes, the scheme is pretty simple. Rooms are recognizable. They have four walls, and door that connect to passages. Often, rooms are designated storage, in which case they are small and saturated with barrels. Or rooms just have items randomly strewn throughout. Humans tend to stockpile things to make organization and transportation easier, so just make sure that everything in the room is contiguous. Lights tend to be distributed evenly along walls for aesthetic reasons. If a room is large, lights tend to be present in the center, which is usually either a transport to the edges, or, if very large, the center of attention(as a dance floor or sports field). Either way, lights there are necessary. Entrances to large rooms tend to be large(factory pickup) or numerous(stadium) themselves to facilitate whatever activity for which the room is intended to be used.(numerous considered in Diablo, probably by accident, but not large)

Think about how humans would use it, then just link (an arbitrary) cause(room is big) and effect(so it must have large or numerous entrances). Developing a decent algorithm once you have that is pretty easy.

It would take some careful consideration to think of a logical reason to have 15+ basement levels to any facility, but that''s beside the point.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
g, how did you make it so only one doorway would lead to 1 room? Didn''t you ever experience like 6 doors on 1 wall to the next room?

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
g, how did you make it so only one doorway would lead to 1 room? Didn''t you ever experience like 6 doors on 1 wall to the next room?


I didn''t, no. This might have been something to do with the (large) size of my levels, or other complexities (my tunnels would join and bend and so forth).

If you want to prevent that, give each room a unique ID as you generate it; then store a table of which rooms are connected (bearing in mind that a tunnel from A to B connects B to A also). For a small level, the table shouldn''t be unmanagable, and of course you don''t need it once the level is finished (though it might help quite a lot for the AI).

The only danger here is that your passage adding routine could jam if it runs out of rooms to connect when the number of passages still hasn''t reached the quota. Rather like that guy in ''Wargames'', your computer needs to know when to give up.

Share this post


Link to post
Share on other sites
How would random map generation work in an MMORPG? Remember, there will be hundreds of players online in different areas. If you have a group of players in Dungeon Level 2, and a few players in Dungeon Level 1, and the DL1 players move down to DL2, would DL2 be randomly generated? Or would it be static?

There''s a problem right there. If maps are only generated randomly if there''s no existing players in the maps to be generated, then maps would be static in most parts of the game. Right?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
In the case of an MMORPG, when a tree falls in a forest and no one is around to hear it, a dungeon is created. With a large enough world, it will be difficult to tell if the dungeon was not there before, or if you simply hadn''t noticed it.

Changing an area that at least one player has already visited is a bad idea, IMHO.

The ideal, however, is to have visible causes for every action. Have a large caravan of baddies camp on a mountain and start digging. Have them raid caravans, etc.

Share this post


Link to post
Share on other sites
That sounds very nice. In other words, a large MMORPG''s ramdomness element should really be emulated by a virtual nature, where every action causes a reaction, as in reality?

Share this post


Link to post
Share on other sites
Well, a random map in an MMORPG sounds a bit tough to handle. Things like Diablo games are created when the game is created, but MMORPGs, as we all know are consistant... people don't create games to play with guild members, they log on and play with everybody.

Essentially, if you wanted a place to randomly rearrange itself on the fly, you would probably have to have a set interval- say 1 hour for simplicity's sake. At the end of the hour, first, you would have to check to see if anybody was in the said area (assuming a tile-based engine, we'll say an area of 50x50) then, you would have to find a way to make them leave... I'll make a quick example... uhh... The Liche's Maze- after some amount of time, you will recieve a message along the lines of suddenly being teleported out by an unknown force and suddenly, you're outside... then, when you re-enter (assuming the reshuffling of the tiles is done, otherwise, you'd probably have to have a way of preventing people from entering) the place is completely different... naughty liche...

Ok, another way to do it would be to rearrange areas on server startups (for example, after a scheduled downtime or even an unexpected downtime).

I'm just babbling, I'm in no way an expert on anything, really, but those ways are the only two ways I can think of to SAFELY randomize maps in an MMO environment.

Espionage is fun.

[edited by - zephreus on September 1, 2002 3:02:12 PM]

Share this post


Link to post
Share on other sites
Zeph, yea, the "when the server restarts" is one way to randomize the places marked for randomization, but AP is right.

It will require much more programming for the virtual nature AI, but in my opinion, it''s worth it. Say you''re a lumberjack and you start chopping down trees, a whole forest disappears, and then you have treehuggers protesting your actions, homeowners claiming they bought their house because of the forest, and the animal rights group wants to kill you because you destroyed animals'' homes.... see?

Share this post


Link to post
Share on other sites
Well, I personally like the natural AI deal (about each action actually having an effect on the environemtn around you) but that sort of architecture would really limit the capacity of a host server, considering the fact that each sector would have to have a multitude of variants as opposed to a set world or tile or polygon...

First off, let''s say you''ve got some exploding potion and you throw it into a forest, then it starts a fire... you then need sprites/models of burnt up trees and the like... not to mention the fact that with thousands of people to a server, the multitude of changes the server would have to process would be phenominal. Let''s just say for simplicity''s sake that there are 1000 characters logged in...
100 of them are lumberjacks and they''re all cutting down trees.
100 of them are miners, causing deep tunnels to form in the mines
100 of them are mages practicing magic of varying types
100 of them are alchemists who are running rampant with explosive postions
and the rest are just going about their business...

in one hour, assuming it takes 30 seconds to chop down a tree, that''s 12,000 trees gone which means that many times information has been updated and objects have been deleted for the world itself...

at the same time, miners are mining ore, assuming the same sort of expansion as experienced with the trees and lumberjacking in the mines, that''s 12,000 more updates and (assuming a 3d environment), I''d assume something like 4 units of ore could be harvested from one spot, so, that''s about 3,000 geometry changes

Mages practicing magic... one powerful mage begins practicing lightning magic in a forest (approximately 10 seconds of time, we''ll say) the lightning strikes a tree and sets it on fire, naturally, the fire spreads, so now you''ve got to take account of the fire, and its ai, and the changing of the trees to either disappearing or burning up to ash or something like that... Assuming an entire forest is consumed (we''ll say the forest was comprised of 3000 trees) that''s 3000 changes to objects or geometry deletions...

Finally, the crazy alchemists throwing potions just start blowing stuff up... mountainsides, buildings and the like... ok, so now, they blew a hole in the mountain, the server has to create a cave map, now, along with lots of geometry changes to buildings and the like because big gaping holes have been blown in them...

While this is a wonderful concept, it just doesn''t seem to be practical- especially considering the numbers would be much higher... Servers have a hard enough time with lag when there are a lot of users congregated in one place, now imagine when it''s having to process on-the-fly world changes along with that...

Don''t get me wrong, I like the idea and it could work- given you have smaller numbers of players on the servers at once- but if you implemented this into something like EQ or UO in which there are a great many users, the lag would be horrendous...

I''m just blabbering to try and save face... Geez, how pitiful am I?
-------------

Espionage is fun.

Share this post


Link to post
Share on other sites
There''s no reason to restrict your engine to a Quake like thing.
You can use blocks/tiles instead of raw terrain, that way, you change the terrain to another block/tile, and it''s not that much complicated.

The server change the block/tile @ location X,Y,Z (don''t even need a Z everywhere) type and that''s it.

A cave/whatever entrance might be put in a block/tile, in which case, either the Server generates the whole thing behind it, or the first level, or nothing at all, waiting for a player to come in to generate the levels/first level.

That way your geometry change but in a controlled and easy way.

As for the Terrain changing shape, you can do something basic like in populous (yep that old game). That works and is easy to control.

There''s no problem in computer science, only solutions.
The only problem remaining is to find the best solution

-* So many things to do, so little time to spend. *-

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The solution would be not to bite off more than you can chew. And outsource(to borrow a business term).

Okay, there''d be miners in some deep dark cavern. They hack away at the rock, never managing to actually damage the rock, just create some ore entities. Then, when all the players are home sleeping and not trying to catch the server modifying itself, it polls another server, which has access to the same database that the game uses to store its data. It grabs the region(the tunnel in this case. You did partition your world into logical segments so that you could transfer control of them to other servers for load balancing, didn''t you?), and calculates what the miners would do. This server is dedicated to making changes, mind you. It doesn''t manifest player actions at all, and it has only one region, whereas other servers have several. How is this different from simply manifesting changes behind the back of the player? Well, it''s progressive(instead of creating one big tunnel, it makes it 2 or 3 feet at a time, or instead of building a building, it goes up a wall at a time), but this makes a good starting place for a more advanced system.

The more advanced version could check line of sight and future line of sight, and change as soon as players can no longer see whatever needs to change. In other words, circling around a huge castle under construction, you could find the moat four feet longer on your return, but as you watch, they don''t make any progress. It wouldn''t calculate field of view because there''s no way to communicate this fast enough. It''s easier to tell the client all the things the player can see and let the client program rotate. I''m sure you all knew that, but just clarifying what I mean(circular or spherical field of view is assumed instead of conical).

Come to think of it, the server could change it while the player''s still looking at it, but just not notify it of the change until it falls out of sight and then moves back in, which might reduce lag anyway(only those objects in sight are loaded).

Share this post


Link to post
Share on other sites