[SUGGESTION] Random Procedural Level Generation

This is somewhat drastic, but awesome.
Portions of the level(or the whole thing) would be generated procedurally from a random seed. This would provide an almost infinite number of variations of a single level. This could be completely independent of the normal levels/it's own objective based game type. Though, this might be suited to a different game, it could be enough to really boost Xonotic to the light of day. It's an idea I've been mulling for a while. It just needs to be incorporated seamlessly. Tell me what you think.

Sounds interesting. Could you explain it in more depth, please?

Sure! Here we go:
I will try to describe the process in steps:
1. Generate terrain: (Perlin->Gaussian Blur->Distort->Heightmap-to-Poly)
2. Generate terrain modifiers: (Cave->Bezier modifier->Poly Displacement[based on noise])
3. Generate minor objects: (Forest[noise based]->Distribute-by-terrain[place based upon terrain])
4. Generate major objects: (Building->House->1834->Window/Door/Hall/Room Count->Build from [generate]modules)
5. Test for bugs(walk entire map...requires a good GPU and OpenCL)
6. Pack procedural instructions.
7. Generate on client system.
8. Play.

Maps would be a couple hundred KB in size.

Hopefully that helps.

Oh you mean a random map generator basically?

Yup, but for each round. Generation and testing would be serverside. Testing involves walking the entire map and jumping as well? A modern GPU could accomplish this in minutes, i.e. while the current match is happening, but a suicide key would help with any un-catchable bugs.

Edit: I've considered this idea for a while, but don't have enough time/knowledge to implement it myself. I would be glad to help develop for Xonotic, whether it's with RPLG or not.

It sounds fantastic but would be really difficult to implement in a clean way.

There is a game based on this. All the textures in that game are generated from formulas before the map/level starts. It is a 3D FPS and it's archive measures 96KB (yes, that's right!). I forgot the name of this game.

Anyway, the idea is good, but this is more like something for future. At the moment, the developers are caught with the first release.

Aleator - you are thinking of KKrieger I think: http://www.theprodukkt.com/kkrieger

Another method is to simply create bits of maps and have them tile together randomly like in UFO:AI.

Yes, that was the one!

BTW, the idea with the connected map segments is really good. We can use it.

That was part of the spark. The procedural portion I stole from kkrieger. It's more or less the random portion that I was referring to. The procedural portion makes it simpler and easier to control(i.e. to prevent bugs) plus you wouldn't have to send a 50mb map file each game. It's a suggestion, but it would probable work better for it's own gametype(eg an objective based team game) It might show itself better in simple things, like the terrain outside a level, or the layout of a building. Making these random from round to round would provide a unique challenge for the players. Here would be a simple way to do this: Code the ability for modular construction(with the mapping software) - the hard part.
Mappers would create modular portions for specific areas(cubical sections of a building) The server would generate and test a random configureation of these modules on a GPU(with openCL) The client would assemble the modules and build the portion of the map. New content in each round!
This would be an easier method of this that would work for any type of level. The author could create a "normal" layout so you could disable this feature on a server.

How would we ensure balanced maps?

How would we ensure balanced maps?

Make them symmetrical?

Yup! The only unsymmetrical part would be the build/field/cave that was generated. It would be unsymmetrical on purpose(though it would be possible to make generation symmetric.)

Sounds like an interesting idea. My vote is definitely yes. I'd like to see it implemented in a future release. I don't see it being terribly hard to code. The hard part is going to be the algorithms.

Exactly. The hard part for me was the engine, but Darkplaces is ready to go. The only obstacle now is algorithms.

HELL yeah! this could be THE killer feature of Xonotic. I'm all for it and would love to see this implemented.

I'll start work on the algorithms. Maybe I can come up with some stuff and present it to the developers. =)

Well, okay, it's symmetrical. But what's stopping there from being an enormous wall in between the bases? How about unreachable pickups? Or optimal camping spots?
Even then, how do you make it look good? The machine has no sense of aesthetics.

That's the point of algorithms Roanoke. Also the point of computer walk throughs. You could use a simple priority queue or graph to traverse the map to make sure that there is a clean path between the bases. You can also create generic textures/basic maps to build upon so that aesthetics won't be a problem.

This is a good idea. You should really go for it. I think about Heroes 3 that has random map generation. We can have this on servers. It would be a unique feature for a 3D shooter.

Don't we need some base maps to start off with, though? I think it'd make it easier. Just some generic maps that could have layers built upon them.

Exactly Erusavion. The openCL library running on a good GPU could easily test every possible walking/running/jumping path in seconds, guaranteeing a quality level every time. The implementation of it is decently hard. The perfection of it is extremely hard. It would be totally worth it. It might, in fact bring in players we would never have before. Randomized levels would be a massive win point for Xonotic. It's just a challenge to implement.

---

Don't we need some base maps to start off with, though? I think it'd make it easier. Just some generic maps that could have layers built upon them.

That is the general idea. For example:
A desert city has two bases. The town in between the bases would be generated from cubed modules. The bases would be premade(as would the modules.) The author would create a basic layout of the modules. The Randomization would be a game modifier.

For something this big, we'd need an entire development team. I'd be happy to dedicate my time to this during the summer but right now I'm very busy with school and work.

But if we are to see this through we'd need several people working on this.

On one other note, I'm gonna take a whack at a simple algorithm that creates a 2d "maze" array. That should be a decent starting point...I think...if I can get an algorithm.

I've already got that. I had to do that for a programming assignment.