[Project] Random map generator

Evil_bOb1Evil_bOb1 Join Date: 2002-07-13 Member: 938Members, Squad Five Blue
<div class="IPBDescription">Similar to what Diablo does.</div>Wouldn't it be fun to have maps generated on the moment? They would provide unique experiences and would also allow many community members to get involved.

In brief. This would need a programmer and mappers. The programmer would develop the mod which generates the maps from a tile database developed by the mappers. This would need a new set of entities set in each piece to ensure they connect appropriately together. Typical tiles would be spawn locations, rt locations, maybe an occasional double rt, and connecting corridors. Each pieced up randomly, according to distance rules, path rules, connecting rules, number of spawns, rts and so on.

Once the mod is in place. It will also allow any mapper to add to an existing tile set or create new themed tile sets, creating a rich database of tiles to generate the maps.

Of course, these maps would be much more generic looking than a unique map, but it could result in an infinite amount of maps, which can find many forms and could scale for different sizes of players. An id system to save a certain layouts could also be used for competitive games for a version that is already known and favored.
<!--coloro:#00FF00--><span style="color:#00FF00"><!--/coloro-->
I would love to work on the tiles, and if any other mapper would also, would gladly accept any contribution. But I do not have the programming knowledge to develop the base system. Is anyone up for that?<!--colorc--></span><!--/colorc-->

At first we should develop a prototype to see how this can work, with basic 'greybox' tiles, and as the project develops, develop for a release with a base tile set and documentation for anyone to develop a tile set.
«1

Comments

  • ArgathorArgathor Join Date: 2011-07-18 Member: 110942Members, Squad Five Blue
    I love it and it makes me very sad that I have no skills that can help support this project!

    I really hope this becomes reality, it would be...gorge-tastic!
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
    I though of this as well, the problem is that the maps are in binary format so you can't write one with a different software.
    It would be awesome to be able to import a text format.

    Maybe there is a way to hack it that I missed.
  • playerplayer Join Date: 2010-09-12 Member: 73982Members
    Immediately had to think of <a href="http://www.youtube.com/watch?v=3g13xaxEgv8" target="_blank">this @ 8:33</a>.
  • FloodinatorFloodinator [HBZ] Member Join Date: 2005-02-22 Member: 42087Members, Reinforced - Shadow
    edited May 2012
    You mean something like Hellgate London did?
    Sounds interesting and it would be extremly dynamic.
    But it still possible to "know" the maps because it uses different rooms of a set, so that you can learn atleast the rooms.

    I hope you can get this running and find some PPL to help. Too bad I can't map nor prog. .
  • scottyscotty Join Date: 2011-07-01 Member: 107400Members
    Please change title to [Idea]
  • MartinetMartinet Join Date: 2012-05-01 Member: 151385Members
    edited May 2012
    I'm in.

    I can contribute concept art, textures, some rough mapping etc.

    ***

    What may help is to limit each map to a single tile set of one environment at a time; for example, creating a orbital platform tile-set which only deals with the environment of a orbital human habitation: tubes, chambers, glass windows etc.

    This way, when the map changes to a "Random" map, all the tiles will work together both physically and setting-wise.
  • Champlo0Champlo0 Join Date: 2012-04-17 Member: 150617Members
    Sorry but something really makes me feel like this will end up making horribly imbalanced maps.
  • ScardyBobScardyBob ScardyBob Join Date: 2009-11-25 Member: 69528Forum Admins, Forum Moderators, NS2 Playtester, Squad Five Blue, Reinforced - Shadow, WC 2013 - Shadow
    <!--quoteo(post=1935181:date=May 10 2012, 11:34 AM:name=Champlo0)--><div class='quotetop'>QUOTE (Champlo0 @ May 10 2012, 11:34 AM) <a href="index.php?act=findpost&pid=1935181"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Sorry but something really makes me feel like this will end up making horribly imbalanced maps.<!--QuoteEnd--></div><!--QuoteEEnd-->
    As long as you have the logic correct, it shouldn't make maps any more imbalanced than what we currently have.
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
    Just saw you can import VMF files, so it should be possible to generate geometry at least.

    <a href="https://developer.valvesoftware.com/wiki/VMF" target="_blank">https://developer.valvesoftware.com/wiki/VMF</a>
  • Evil_bOb1Evil_bOb1 Join Date: 2002-07-13 Member: 938Members, Squad Five Blue
    edited May 2012
    I have been looking around how to get this working, mainly what other people have done to procedurally generate maps. I still have some questions about it, but I am starting to get a vision of the algorithms involved, and the variables. I do hope it is a project and not just an idea :p Of course this all depends on the people who get involved on this with me as I will not be able to do this alone. But I have faith this project will call the right people for it ;) I will probably design how most of it works, at least the basic logic of it, I would then definitely need someone with the proper understanding of code to translate the logic and bring his own understandings and ideas about it.

    I am pretty confident about the balance of the maps. It all comes down to the algorithm that constructs them, and I already have some answers to that.

    Of course the 'first' tile set will be very simple, nearly unthemed, space hulk sort of thing, stemming from the prototype tiles. But once the system is there it should be simple enough for anyone to develop a database of tiles, according to a theme/environment of their wish.

    @Yuuki. I am thinking of a different method to achieve it. In which the engine loads multiple .level files, each one a tile, named according to its form and connectivity and places them together. A seed number/id would be parsed to the clients and they do the same process as the server. If a whole .level file has to be generated, generating it and distributing it for the game would be cumbersome.
  • 1dominator11dominator1 Join Date: 2010-11-19 Member: 75011Members
    edited May 2012
    Would be famous if you can get it to generate random tiles as well.
  • HuzeHuze Insightful Join Date: 2003-11-12 Member: 22724Members, NS1 Playtester, NS2 Playtester, Squad Five Blue, Reinforced - Shadow
    <!--quoteo(post=1935265:date=May 10 2012, 04:54 PM:name=Evil_bOb1)--><div class='quotetop'>QUOTE (Evil_bOb1 @ May 10 2012, 04:54 PM) <a href="index.php?act=findpost&pid=1935265"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->@Yuuki. I am thinking of a different method to achieve it. In which the engine loads multiple .level files, each one a tile, named according to its form and connectivity and places them together. A seed number/id would be parsed to the clients and they do the same process as the server. If a whole .level file has to be generated, generating it and distributing it for the game would be cumbersome.<!--QuoteEnd--></div><!--QuoteEEnd-->

    You could just have all the tiles in a single .level file, and then move the pieces around using the program. That way they only have to download a single map. However, you would have to figure out a way to move level geometry with lua, which may not be possible as of right now.
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
    Yeah, as I understand Radiance does manipulate the level directly, it's coded in c Sharp and it's quite complicated. I'm not sure it can manipulate geometry also.
  • EvilKoaLaEvilKoaLa Join Date: 2012-03-24 Member: 149331Members
    [Personnal Opinion]"Mais il est fou !?"[/Personnal Opinion]

    I've been doing some mapping on the old Hammer. I wasn't great, but I could understand how it barely works. I don't know yet how has evolved the NS2 mapping from that.
    But, I am a developper ( not available due to tons of works ) and I can give you some hints.

    First be advised, this is an external viewer thought about this. I do not map, and I do not know what you can do with the actual code of the game.


    Actually, for the game design, the environnement idea from Martinet is the best way to follow I think.
    For the generation, it can be hard, but not impossible. Talking with the UWE guys would greatly help. They might just tell you what to use and what part to use from the code, you modify it and you're ok. The question is more : "how and when would you generate ?"
    How much time would it take to render the lights, etc etc. ( You know more than I on this )


    But for the system of "random" association of existing rooms, it's quite easy :

    Take a look at the level editor from Trackmania :

    <img src="http://www.katsbits.com/images/tutorials/trackmania_forever/trackmania_valid_track_sml.jpg" border="0" class="linked-image" />

    - Just think in the same way. On TM, it's not random, because the fun is where you create your own map track to play it instantly.
    -Simply admit an area which depends on the size of the map you want ( might be dependent from the number of players ) : let's say 100x100x30 blocks ( 30 is the height )
    - Choose the block your need from the base with a random salt : 5 spawn blocks, 3 only res blocks
    - Place it on the aera ( with random salt again ) with "x" ( x is random between "y" and "z" which are defined by you, or by map size ) free space between each blocks. ( I take this opportunity to say I'd love to see some more heights, more 3d on NS2 maps, I too often think the game lacks some stairs / elevators. So do it on the 6 directions )
    - Then, you got your parts, randomly placed on your map, you just have to put some "little" tiles to connect them. Those tiles must have the "x" block size from before. These can be corridors, stairs, elevators, ramps, etc. They also must fix with the "oppenings" of the big tiles of course.
    - And there you go, it's almost random.
    - You now just need to connect your entities ( if it still exists ) and then generate the whole thing.


    I would go this way, not just putting all the blocks in one pass, but by 2 : first the bigs, then the little ones to connect them. Having it done randomly is quite a challenge by the way. Not because of the code, it's quite easy, but because if you want it to be really random, and respecting an environnement, there are a lot of tiles to build, to study, etc etc.
    You might want to take care of the size of each of them, just to get the connections correctly.
    Openned aera may be quite hard to get connected also.


    Again, I do not know a lot about the mechanics of the internal game, but as a developper, here is my first thought about "how would I do this"

    Hope it helps ! If it doesnt, throw me potatoes.
  • Evil_bOb1Evil_bOb1 Join Date: 2002-07-13 Member: 938Members, Squad Five Blue
    edited May 2012
    Yeah I have thought about that. It has to stay an NS2 map and NS2 involves two teams. The two spawns would be the roots of the rest. It wouldn't be completely random, but produce different layouts, according to distance rules, density rules of what exists between these two spawns.

    I should probably get started and produce the tiles at least in a .level file so I could manually create these different layouts, and in good time find out how to set up the generator to work in the most effective way.
  • menohackmenohack Join Date: 2004-02-29 Member: 26995Members
    I am a programmer and I like this idea. The problem I see is that it may not be that useful for gameplay. Why would you want to play a randomly generated map which couldn't possibly have the thematic tone of a map made by a single artist?

    If we did make this mod people would probably still stick with custom maps.

    But all of that aside, here is what I think we should do and the challenges we would face. Mappers would have to design the architecture of rooms and hallways. Each room would have to have either a door or some time of portal (like a door frame). Then, rooms would piece together at these points. For the map to be balanced we would probably start with one of the layouts specified in the mapping manual. Then the program would fit pieces to the layout. This is essentially a graph theory problem. Nodes, such as resource nodes and hives, are connected by edges. The edges are where we get to customize the layout--a straight line between two resource nodes could be several L-corridors.

    Mappers would need to make many of these pieces fitting certain guidelines. We could customize the rooms when the map is generated by changing whether they contain resource nodes or hives and where they are located within the room.

    We would also need to reverse-engineer (or ask UW) the binary layout of .level files. Apparently the person who made Radiance did this somewhat, so this would not be impossible. The map editor to my knowledge does zero pre-processing on the level--all of the pre-processing is done by the engine when the map loads (by the way UW, why do you do this? You could have precomputed shadowmaps and lightmaps for static lights). This makes our life a lot easier. All we need is a .level file containing all of the pieces, then we copy, rotate and translate them into a new file which is sent to the players. I do not know whether the server can upload files like maps to the client, but it shouldn't be impossible.

    This shouldn't be impossible, but it is a large amount of work and it is unclear how useful it would be to players. If you guys are really interested in this then I might be able to do the programming. Let me know what you think.
  • Laosh'RaLaosh'Ra Join Date: 2011-12-09 Member: 137232Members
    awesome idea, although debugging is probably a bit tricky for something like this.
    one keyword you can look for is "roguelike". this genre is basically diablo on hardcore mode (1 life for your character) and lack of good graphics (many are ascii-based) but deep and complex game mechanics in return. i've been creating one for warcraft 3 and i'd say there are indeed countless possible approaches to implement something like this and it is probably a good idea to create your own method after looking at some examples (because there are resnodes, techpoints, doors and vents to take into account).
    apart from that, here is a personal suggestion for a high-level-layer:
    for each generated map, you could randomize a certain set of "architecture style" variables (just tendencies, no dogmatic limits!). e.g. one map might have long corridors and only few medium sized rooms, another map might have very short corridors (acting more as a door instead of an actual corridor) and a lot of larger rooms.
    having multiple different styles per map seems even better, as long as the area for each style is not too small (e.g. one area for each side's starting locations and 1-3 more for some areas inbetween, each area containing multiple rooms and/or corridors).
    the motivation behind this is the following: if you have arbitrary tile-combinations in EVERY generated map, this "style" as a whole might be perceived by the player as a consistent architectural style, as all generated maps look somehow similar to a certain degree (the pattern being a lack of patterns). if you have a certain style for a larger area, then the style in the next area (and in the next map) is likely to be quite different and thus more distinct/memorable. you can amplify this by including texture/lightning/whatever to make the area more unique.
    you can even set the parameters for the amount&size of those areas (replacing the "1-3" i mentioned above) for each new map in order to create another layer of map-specific style: one map might have many distinct places (e.g. outdoor, installation, natural cave, cave with lots of neutral alien plants) whereas another map might look more monotone (e.g. a sewer). i'm not saying that this is necessarily a good parameter to randomize, but you can easily find parameters of that kind in order to come up with many possible styles for the generated maps.
    sorry if my post is a bit complicated, i hope you get the idea though.
  • playerplayer Join Date: 2010-09-12 Member: 73982Members
    <!--quoteo(post=1935538:date=May 12 2012, 12:06 AM:name=menohack)--><div class='quotetop'>QUOTE (menohack @ May 12 2012, 12:06 AM) <a href="index.php?act=findpost&pid=1935538"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->We would also need to reverse-engineer (or ask UW) the binary layout of .level files. Apparently the person who made Radiance did this somewhat, so this would not be impossible. The map editor to my knowledge does zero pre-processing on the level--all of the pre-processing is done by the engine when the map loads (by the way UW, why do you do this? You could have precomputed shadowmaps and lightmaps for static lights). This makes our life a lot easier. All we need is a .level file containing all of the pieces, then we copy, rotate and translate them into a new file which is sent to the players. I do not know whether the server can upload files like maps to the client, but it shouldn't be impossible.<!--QuoteEnd--></div><!--QuoteEEnd-->
    In the best-case scenario you would be able to succesfully reverse-engineer how geometry is structured in the .level-file, though it may be quite a bit harder than the entities, as geometry is stored in a more obfuscated way. Of course this method of level-generation demands auto-downloading. Also, it is important to note that proper occlusion-geometry needs to be generated to go along with the newly structured map (as NS2 no longer auto-generates this for maps upon a map-load). Technically there is a lot possible in this area, but it'll be a real pain in the arse.

    Personally I was thinking more along the lines of brush-anchored entities (entities that represent physical geometry in the map). We don't really have those yet (apart from triggers), and I've been whining to get them in, but so far no luck. This does not require any reverse-engineering or auto-downloading, would allow for actual realtime generated maps (in mid-round even), and could be easily interfaced with using the entity-methods currently available in the engine. The only real downside to this is that there cannot be any occlusion happening (as the game does not know the layout when the map is being loaded). When NS2 was originally announced I hoped it's occlusion-culler allowed for realtime geometry-manipulation, and the culler would just pick up on it (realtime lighting would've allowed for this also), but as it stands we're stuck with basically the good ol' pre-computed stuff. That sucks a little bit. So when you're building a map with entities, you have to keep in mind clients should be able to render the map whole (as that is what they'll most likely be doing without any proper occlusion). Of course entities also generated additional strain on the server, client and especially the netcode, so you need to work with large chunks of geometry per entity, to keep the total amount down as much as possible.

    TD:DR:
    <ul><li>Modifying .level-files can be very tricky, demands auto-downloading, is static during the map play-through, but allows for complex maps with good performance.</li><li>Using brush-anchored entities is very easy, does not require auto-downloading, allows for map-changes while ingame, but must be kept in more simple geometric-shapes to keep the performance acceptable.</li></ul>
    End-result would be a request to UWE to release the .level-structures and\or implement brush-anchored entities. Or both. That would be preferable. Both.
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
    Cracking the binary files looks like too much job to me.

    A different approach would be to generate all the geometry from scratch with some heavy computations (in python/blender, matlab, ...) and to import it in the editor using vmf. I don't know if you can import texture and entities using vfm files though.

    Then you can generate hundreds of maps and just browse through them looking for interesting ones and finally polish them by hand.

    A kind of generative architecture :

    <img src="http://farm3.static.flickr.com/2064/2109605218_15c158a82c.jpg" border="0" class="linked-image" />
  • Evil_bOb1Evil_bOb1 Join Date: 2002-07-13 Member: 938Members, Squad Five Blue
    Thank player for that info. I have also thought about the occlusion issue, and just imagined that each piece could have the occlusion geometry attached.
  • menohackmenohack Join Date: 2004-02-29 Member: 26995Members
    I was under the impression that the game computed the potentially visible set during map load each time and that it was not part of the .level file. Am I wrong? The level file is generated extremely quickly by the map editor and after the game runs it's size does not change. How could generating the geometry have any effect on the culling?
  • playerplayer Join Date: 2010-09-12 Member: 73982Members
    It was early on, but that has been replaced by manual visibility-(hints\geometry) that are placed by the mapper.
  • menohackmenohack Join Date: 2004-02-29 Member: 26995Members
    I didn't know that. Is it a prop?
  • Evil_bOb1Evil_bOb1 Join Date: 2002-07-13 Member: 938Members, Squad Five Blue
    Its geometry with an attribute to it.
  • menohackmenohack Join Date: 2004-02-29 Member: 26995Members
    So I looked at mineshaft to see how this is done (it's so nice that level files aren't compiled and we can look at them). The entire map needs to be enclosed in a shell of geometry. For some reason this needs to wrap as tightly as possible to the level geometry, so it is more complicated than just a giant box.

    Either way this does not really present us with a challenge. We would have to solve this same problem anyway. Each component that needs to be able to connect to another component (i.e. room to hallway) needs to have a common interface (i.e. a door) that matches on each type of component. It would be exactly the same for the OcclusionGeometry layer: it would wrap the room as closely as possible but at the interface between it and another component it would have a similar structure so that two components can lock together. I made an image to demonstrate.

    <img src="http://menohack.acm.jhu.edu/RoomInterface.png" border="0" class="linked-image" />
  • c0kec0ke Join Date: 2004-07-02 Member: 29676Members
    i don't think the world is ready for that yet ... :P
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
    I tried some stuff in matlab, just for fun.

    I give two profiles, one for hallways and one for rooms, and then the thing just extrude the profile and switch from room to hallway randomly (after a minimal length is reached):

    <img src="http://i.imgur.com/wspgZ.png" border="0" class="linked-image" />

    <img src="http://i.imgur.com/WxffL.png" border="0" class="linked-image" />

    Now one should add some kind of splitting behavior to add new hallways to the rooms, and close up the whole thing together, but it's not so easy to do I guess.

    That's a really fun problem to play with, but I'm not sure I have the time to, I also need to work ;)
  • HackepeterHackepeter Join Date: 2003-06-08 Member: 17107Members, Constellation
    Like some people already mentioned before I also think that working against the binary level format would be a pain, especially because there is no automatic map download.

    I'm more into the idea to make some props of the different tiles because they could be manipulated as every other entity in the world. Each map would represent a specific theme (so no weird combination of themes) i.e. ns2_RandomMine and when the map is loaded the mod detects the tiles and builds a nice random mine layout.

    One downside would be that there would be no mini map because that is currently pre-generated. But still I think that approach would be -currently- the best but not the perfect one, though.

    If someone could make me two basic tiles of a quadratic room and a corridor as .model file I would write a proof of concept to test this idea and gather some information.

    <img src="http://dl.dropbox.com/u/8054606/roomtiles.jpg" border="0" class="linked-image" />

    It would be great if the room could be placed 1:1 in the world (without the need of scaling) and would be large enough to keep a team spawn with hive etc. Furthermore, exactly defined connection points would be helpful like after 5m a 2m wide entrance etc. so the connection can be as exact as possible. Maybe later a solution with bone joints as connection points would be better.
  • ZeikkoZeikko Join Date: 2007-12-16 Member: 63179Members, Squad Five Blue, NS2 Map Tester
    <!--quoteo(post=1936526:date=May 16 2012, 01:29 PM:name=Hackepeter)--><div class='quotetop'>QUOTE (Hackepeter @ May 16 2012, 01:29 PM) <a href="index.php?act=findpost&pid=1936526"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Like some people already mentioned before I also think that working against the binary level format would be a pain, especially because there is no automatic map download.<!--QuoteEnd--></div><!--QuoteEEnd-->
    I don't understand how this could work without reverse engineering the map format. You need to generate a map file after all.
    You don't need map download though if the clients have the mod installed too. The server only needs to give the seed number to the clients and their map generation scripts will generate the same result as the server with the same seed number.
  • HackepeterHackepeter Join Date: 2003-06-08 Member: 17107Members, Constellation
    edited May 2012
    <!--quoteo(post=1936537:date=May 16 2012, 03:27 PM:name=Zeikko)--><div class='quotetop'>QUOTE (Zeikko @ May 16 2012, 03:27 PM) <a href="index.php?act=findpost&pid=1936537"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->I don't understand how this could work without reverse engineering the map format. You need to generate a map file after all.
    You don't need map download though if the clients have the mod installed too. The server only needs to give the seed number to the clients and their map generation scripts will generate the same result as the server with the same seed number.<!--QuoteEnd--></div><!--QuoteEEnd-->

    I think you miss understood me, the idea is NOT to build a map like the editor does with brushes. It's about dynamically building the rooms only with props because they can be treated like entities. You can move them, copy them and so on. The map won't be saved and all calculations are server sided. Actually, that is already in the game with the alien and marine structures. They have correct lighting, correct collision detection and placed dynamically. If that is possible with single structures it should also be possible for an entire room.

    But I like the idea with the seed so you could recreate cool maps, good point!

    Maybe the dynamically building with props does not work at all; that's why I would like to make a proof of concept to gather some information about that approach.
Sign In or Register to comment.