Random Ufo Floorplans And Terrain

[stjones]

I wanted to start this thread to discuss Random UFO Floorplans. I have already implemented random floorplans in XcomUtil and have published the following synopsis of the algorithm in Research Disclosure. Using this algorithm we can either have totally random UFOs or just let the algorithm randomly fill the shapes created by designers. If the group is interested in using this as an option, I can port the code to Xenocide. Please note that this algorithm can be used equally well to create outdoor terrain.

 

Random Floorplan Generation:

 

Disclosed is an algorithm which can be used to extend the life of computer games by generating random floorplans for buildings or other areas of play. Most random maps in games are constructed by randomly placing a small set of fixed-sized, fixed-content tiles in a regular grid. Use of these tiles typically requires a fixed placement of entry and exit points on each tile to allow the tiles to be connected. This is a more robust algorithm which greatly enhances the randomness of the floorplans with a minimal increase of complexity for the game designer.

 

The algorithm uses a set of stretchable rectangular tiles, or rooms, which can be can be entered and exited from any location around the perimeter of each room that is not occupied by blocking terrain. The algorithm begins from a single room and expands by attaching tiles to randomly selected points on the perimeter of the current set of rooms.

 

Each new room is first stretched to a randomly selected size, possibly limited by available space, then moved to a randomly selected orientation relative to the selected attachment point. Stretching consists of adding empty rows or columns to a room definition. An example of a room orientation is that a 3x3 room attached to the north side of an existing room could be placed in any of the three positions where the attachment point is one of the 3 locations in the southern most row of the new room. Stretching of any room can be enabled or disabled for any direction to allow specific interior features to be generated along interior walls.

 

Connectivity to other rooms is guaranteed by simply requiring that all non-blocked locations within a room are accessible from all other non-blocked locations. Thus, the algorithm guarantees that all interior locations are accessible from all other interior locations by exactly one sequence of rooms.

 

The algorithm terminates when all available space has been filled with rooms. The boundaries of the area are most easily implemented by filling the perimeter of the available space with special blocking terrain that can be removed after the algorithm is complete. Irregular building shapes can be achieved by either filling some of the available space with more of the special bounding terrain before starting the algorithm or by simply terminating the algorithm before all available space has been used.

 

Additional floors can be generated by defining the tops elevators as new starting rooms. If no rooms containing elevators were generated, one may be randomly generated from any free location on the previous floor. If more than one starting room exists on a new floor, the rooms generated from each of those starting rooms will be accessible from each other only by a sequence of rooms that includes rooms on the previous floor.

 

Interior walls are automatically generated around each room as it is generated, exterior walls are automatically generated around the perimeter of each floor when interior generation of the floor is complete. A door is automatically generated at the attachment point of each new room. Exterior doors are randomly placed around the perimeter of the building when generation is complete.

 

The advantage of this algorithm is the level of randomness it achieves. A single room definition which contains a crate in the middle of a 3x3 room can be stretched to any size greater than 3x3 while still maintaining its connectivity to all other rooms. After stretching, the crate can reside anywhere within the room except for the first and last columns of locations within the room. This is much more random than floorplans produced by current algorithms.

[mamutas]

It looks like great algorithm to me. I would use it to generate alien bases and not for alien crafts. Crafts of certain type all should be the same in floor plans, like humans aircrafts are.

[Guest drewid]

I think I would agree with Mamutas about craft. At least I think the exterior shapes should be the shame, I guess this covers that. hmmm

 

I'm more interested in the idea of generating a random "town"

 

How would it work for exterior terrain definitions?

Define outside terrain as a special room type with floor but no walls I guess?

Then disable second floor creation above that room type?

Or would you define each building seperately, but somehow ensure that there is a minimum space between them?

I guess elevators could be replaced by stairs and the put in rules for the number and placement of stairs. Always next to wall, not too far from "front door"(if in UK).

 

Can you specify min/man dimensions for each room and each building?

[Deimos]

I agree with everyone else here it does sound verry cool but I'd be a bit worried about randomised craft from a tactical point of view.

 

Not knowing how a craft is designed is good for the first time a player comes up against it but for repeated attacks on the same size vehicle I don't know whether it'd be a good idea as the player would never be able to develop a strategy for dealing with a particular class of craft. For example everyone has their own way of dealing with say a medium scout. Personally I use between 4 and 6 guys in a pincer manuver to sweep the craft.

 

In multiplayer however it would be perfect as it could be used to generate craft from a pool of rooms so that neither player has an advantage in attacking or defending as neither know what the craft is like until they are both/all in the battle.

 

Battlescape missions, terror sites and alien bases would be perfect for the randomness factor as the player shouldn't know whats coming in them and therfore not be able to predict what's coming other than the most general of factors.

 

Like it's going to be daytime/nighttime and what kind of terrain they should expect depending on where in the world the mission is.

[[[Micah]]]

I agree with everybody here, and specifically with Deimos' opinion.

[red knight]

I do too.

[stjones]

I agree with everyone else here it does sound verry cool but I'd be a bit worried about randomised craft from a tactical point of view.

 

Not knowing how a craft is designed is good for the first time a player comes up against it but for repeated attacks on the same size vehicle I don't know whether it'd be a good idea as the player would never be able to develop a strategy for dealing with a particular class of craft.

I understand your concern. The same issue came up with XcomUtil, which is why you can have a random ship every time OR you can randomly redesign all of the UFOs then leave them that way until you ask to do it again.

[stjones]

I think I would agree with Mamutas about craft. At least I think the exterior shapes should be the shame, I guess this covers that. hmmm

If you provide the algorithm with a mask you can you can use it to fill any shape of ship. In XcomUtil, I only allowed the user to generate totally random shapes or fill cubical ships (a la Borg) because I didn't want to actually design the shapes.

I'm more interested in the idea of generating a random "town"

 

How would it work for exterior terrain definitions?

Define outside terrain as a special room type with floor but no walls I guess?

Then disable second floor creation above that room type?

Or would you define each building seperately, but somehow ensure that there  is a minimum space between them?

I guess elevators could be replaced by stairs and the put in rules for the number and placement of stairs. Always next  to wall, not too far from "front door"(if in UK).

 

Can you specify min/man dimensions for each room and each building?

In the current XcomUtil implementation, flags were allocated to denote multifloor rooms to support ships with stairs for TFTD, but they were never implemented. Currently, you can only specify the minimum dimensions of each room, but it would be extremely easy to add maximum dimensions. I didn't need it for XcomUtil, so I didn't implement it.

 

For towns, each building would sit in the middle of a stretchable tile so that you ensure minimum space around it. To create random floorplans for each building, the algorithm could be applied recursively, once to distribute the buildings, then again to create the interior of each building.

 

For more information on the algorithm, read the appropriate sections in the documentation on the XcomUtil Homepage that describe how to define your own rooms. The XcomUtil.rmx file in the package contains prototypes for about 40 rooms. To see what you get, you can select randomization of the ships, then use the VIS command to make the entire map visible each time after you enter combat, save, and reload. That was what I did to debug the algorithm.

[Guest stewart]

Okay, if we go random ships then it HAS to be from a fixed shell inward rather than totally random. The random ships produced by XcomUtil are TOO random. BTW Scott does XcomUtil have the "less" random shell-inward feature in it now?

 

Really though the ships should probably have a few designs. We can make designs similar enough that you don't know which floor plan you are in until the very end. But anyway.

 

Aliens bases should not be completely random. I'd like to see choke points in them for example, have some intelligence in their design.

 

Random for terrain sounds good.

[stjones]

Okay, if we go random ships then it HAS to be from a fixed shell inward rather than totally random.  The random ships produced by XcomUtil are TOO random.  BTW Scott does XcomUtil have the "less" random shell-inward feature in it now?

The ability to request regular shapes has been in XcomUtil for at least two years. The random shapes are the default, because they generate fewer small rooms. As the available space gets used up, the generated rooms tend to get smaller and smaller simply because larger ones will no longer fit. By creating a mask of bounding blocked terrain, you can force the outside shape to be anything you like. I use the same mask for both regular and random shapes, I just randomly reduce the total volume that I fill.

[Guest stewart]

REALLY!!! I'm gonna have to check this out!

 

Thank you sir!

[Maverick]

I think it would be pretty cool to random generate the shape of all UFO's at the beginning of the game and have them remain static for the remainder of the game. that way you can never "get used to" the alien ship orientation BETWEEN GAMES. In your single game it would appear that the ships were mass produced in that layout. Lemme know what you think.

[red knight]

That is a nice tradeoff...

 

Greetings

Red Knight

[GreatGold]

But it would absolutely kill any attempt have an X-Net entry for the UFOs...at least in terms of design. Also, it would kill any graphic put into X-Net to represent the UFO...

 

Gold

 

ps - sorry, I don't mean to come off like the devil of X-Net...

[Breunor]

I agree, it would definitely provide more strategic variety. When we get to the battlescape, this would be great to work with.

[Deimos]

But it would absolutely kill any attempt have an X-Net entry for the UFOs...at least in terms of design.  Also, it would kill any graphic put into X-Net to represent the UFO...

 

Gold

 

ps - sorry, I don't mean to come off like the devil of X-Net...

I don't know whether it would. I think somewhere in this thread someone (most likely The honourable Mr Jones ) that we can have a bounded limit for the ufo's. So we could have the outer shell remain static and the interior changeable.We'd be able to design cool looking shells and still have the randomness factor of the unknown but in between games. Talk about replay value

[Guest Jim69]

How specific is the algorithm? Could it, say, generate random parts of the ship, while having some set points?

 

That could easly be written into the story, afterall, think of 2 navy ships of the same size, most would have simular engine rooms etc. but specifics could be different.

 

That way it wouldn't completly kill off any comman strategy in certain types of ship, as the engine room and nav point would be in same places, but there could be other rooms that weren't in ships b4. Of cause, this wouldn't be much good in the smaller ships, but it would add a little suprise when dealing with the larger ships.

[revenant4]

I'm not exactly sure if the alien bases were random but if they weren't Jim69's idea would be good for alien bases as well...

[mikker]

In alien bases, x-com had some "areas", like your 2 start points, and the control point, with they took and placed together. This was completely random, but it was targeted to have 1 command center, and 2 enntrences.

 

btw, should the ammount of entrences be random?

[Anglachel]

I don't see why not. The number of entrances could be based on how long the base has been on earth. More entrances could mean they are still bringing in supplies and still constructing things, while one entrance could mean a finished base.

[stjones]

I think it would be pretty cool to random generate the shape of all UFO's at the beginning of the game and have them remain static for the remainder of the game.  that way you can never "get used to" the alien ship orientation BETWEEN GAMES.  In your single game it would appear that the ships were mass produced in that layout.  Lemme know what you think.

My random floorplan algorithm can be used to fill a ship with ANY external shape. This would allow the graphics buffs to design very good looking ships, but the interiors would be different every game or even every time you attack a ship. That way, you get the best of both worlds.

[GreatGold]

stjones -

 

Is it best to always have completely random UFO interiors...it seems like a strange and impractical system. Its not like the Avenger has a new interior every mission...why would a medium scout?

 

In another thread we are currently discussing this exact issue...are 10-20 well planned and tested UFO interiors better than an infinite random set of interiors? I think this really needs to be decided on soon, because it will have a huge impact on game design.

 

In terms of battlescape terrain, though, you are completely correct. It would be absolutely amazing if no two battlescape maps were ever the same!

 

Gold

[Fred the Goat]

I'll second that. Ships should be individually designed. It's easy to come up with designs, and we could get 10 or 20 per ship and have a good setup. If the ships look alike, you don't know what you're dealing with until you've gone in, and it'll take a while to get tired of. Remember that even if you randomize floorplans, a medium scout can only have so many variations within the parameters you specify anyway, so it's going to get predictable after a while, and it may as well be predictable and well planned. What if we had a single entry in the X-net for medium scout, and then the floorplans of each one will be added in as you encounter each type?

[GreatGold]

Freds on to something...

 

Gold

[Guest blaa]

FTG does have a point there. As is said in the other thread we can have several different hulls for each class of UFO too. Some can be based on races for example.

 

BTW Fred the Goat, hmmm? And what is RK's REAL name. Cooincidence?

Hmmmm?

 

Yes, I'm kidding!

[stjones]

stjones -

 

Is it best to always have completely random UFO interiors...it seems like a strange and impractical system.  Its not like the Avenger has a new interior every mission...why would a medium scout?

 

In another thread we are currently discussing this exact issue...are 10-20 well planned and tested UFO interiors better than an infinite random set of interiors?  I think this really needs to be decided on soon, because it will have a huge impact on game design.

 

In terms of battlescape terrain, though, you are completely correct.  It would be absolutely amazing if no two battlescape maps were ever the same!

 

Gold

I agree that the terrain should ALWAYS be different. The random ships are only important when people play the game MANY times, like I did with XCOM. If we make it easy to add new ship designs, the random interiors may not be needed.

[Fred the Goat]

Fred the Goat, hmmm?  And what is RK's REAL name.  Cooincidence?

Hehehe...yes! By day I am Fred the Goat, mild mannered newbie, but when disaster strikes, whoosh! Red Knight is here. Or something. Ah, well, may as well live it up. I'll leave it to Red Knight to disabuse you of the idea...in the meantime, feel free to treat me as a Senior Project Member.

[Meddik]

I do like the randomness idea, but have it available as an option.

 

Optionally, make it default to non-random at low difficulty, and make it default to random at a higher difficulty.

[decklen]

i waas just thinking maybe, to add some variety, the one thing i got really annoyed with in the orignal was the blandness of the ufo's.. everyone of them the same.. so i take it all the aliens bought at the same ufo dealership? ...

 

maybe some different types of interiors.. ?

[Breunor]

My impression for why there are different interiors was to address the different needs of the aliens. Sectoids need a different layout than mutons, etc. I think it would be cool to have the totally random floorplans as an option, but to make several interiors for each ship that are used under normal circumstances. I don't think we'd need to use the exact same floorplan to match up with each alien species however, just randomly pick from the designs created.

[Puasonen]

Now decklen has a point this time..

 

Why all alien races have the same interiors? You would think that for example sectoid needs a little smaller thingys than a muton?! Sectoids like to have one kind of ship-interior-type and muton another.. THAT would make SENSE and it would be cool cause then there would be more variety to ufo missions.

 

AND the hyperwavedecoder would be even more usefull than before because you need different weapons to different ufos.

 

Great Gold was worried about the x-net database, exterior same don't worry. And also you thought the stupidity because why would all ufos be different kind? I agree but this isn't a problem either in this case. All races like their own interiors and they would stay the same.

[Breunor]

It would be fun to go into a ufo where all the control panels and instruments are like 20 inches from the floor, it would be like assaulting a preschool.

[Puasonen]

It would be fun to go into a ufo where all the control panels and instruments are like 20 inches from the floor, it would be like assaulting a preschool. 

It would wouldn't it

[Cpt. Boxershorts]

Regarding the x-net concern about having different exteriors, would it be that difficult to keep track of the differnet hull designs yu encounter, and just update the x-net images?

 

After all, the overall size and crew should be about the same.

 

--The Captain

[GreatGold]

Hey -

 

No, I dont think that would be too difficult at all. Under each Category of UFO, such as Terror Ship, there would just be another list od designs seen. I suggest that each design should be researched before entered into the database though. Otherwise, how would you know it was a Terror Ship...

 

The same could happen with floor plans. I don't really think it would be much of a problem.

 

Gold

[Guest Jim69]

Heres something I think is worthy of discussion for the terrain side of things:

 

I've been playing Aftermath for the last couple of days and I have seen a pattern in the maps that we should at least think about. What they have done is create a mask layer with gaps of, for instance, 15mx15 and in that space a random model is chosen, house BB court etc. Then there are ( that I have seen ) about 5 different varients ( we should have more ) of this. So there is the plain map with trees and a small hut, a full street etc. If we create the maps in this way it will be easy to create random maps that take different strategies if we think of enough things to go in the gaps. This will also allow for more variation between countries and a host of other features, and allow the map masks to be created first and keep the buildings completely seperate thus saving on overall file space. What do you guys think?

[Deimos]

We shouldn't use Aftermath as source as it will show that we used them as a source. Which could lead us to trouble at the worst and the best it'll look like a cheap copy. Which is what we'll be doing if we use anythign from them. Think how you feel about clone games. They always feel cheap compared to the genre defining game they're copying. Think Doom, Quake and all the blatent copies that have been shoved out on us.

 

I'm sure everyone will agree we don't want to look like the cheap copy but be the genre defining game that everyone else wants to copy. Its probably best to keep aftermath as a game we play but not use it as a reference for our game.

 

Aftermath's mapping system is also prerendered with terrain and cover values pre caclulated. According to what I've read on their site it wasn't the easiest thing to acheive.

 

I don't understand how we'd save space as there will only be one model of each type and one texture and so on. These as I understand it will get called into th map by the engine as they are needed.

 

As for generating randome terrain features. Compter random is a little too random for most people's liking. there will be no doubt preset styles for the maps we use depening on where in the world the map is but the randomness factor will come up with more unplayable maps than it would good playable ones.

 

I'd personally don't know how best to solve the map issue but we could use a system similar to what my firends and I use when tabletop wargaming. In that from a set of terrain pieces each person takes one piece and places it on the board. In our case we have our map and each terrain piece could be assigned a size to where it could fit on the map and it get placed according to its size. That way similar sized features like houses (which would be the largest) would be put near each other on the map and smaller stuff would get grouped likewise. Ther could be markers on the map to say that certain terrain features have to go in certain places like bridges over streams and rivers and then everything fits around them.

 

That way we can widen the types of map we use and could fight up hills and over streams and things would look in place.

 

Of course another way to do it which would require more work is to have preset maps for each type of terrain pre playtested for the maximum fun and challenge. That would mean more work but it might be worth it if the benefits of preset terrain outweigh random generation.

[Guest Jim69]

We shouldn't use Aftermath as source as it will show that we used them as a source. Which could lead us to trouble at the worst and the best it'll look like a cheap copy. Which is what we'll be doing if we use anythign from them. Think how you feel about clone games. They always feel cheap compared to the genre defining game they're copying. Think Doom, Quake and all the blatent copies that have been shoved out on us.

 

I'm sure everyone will agree we don't want to look like the cheap copy but be the genre defining game that everyone else wants to copy. Its probably best to keep aftermath as a game we play but not use it as a reference for our game.

 

Aftermath's mapping system is also prerendered with terrain and cover values pre caclulated. According to what I've read on their site it wasn't the easiest thing to acheive.

 

I don't understand how we'd save space as there will only be one model of each type and one texture and so on. These as I understand it will get called into th map by the engine as they are needed.

 

As for generating randome terrain features. Compter random is a little too random for most people's liking. there will be no doubt preset styles for the maps we use depening on where in the world the map is but the randomness factor will come up with more unplayable maps than it would good playable ones.

 

I'd personally don't know how best to solve the map issue but we could use a system similar to what my firends and I use when tabletop wargaming. In that from a set of terrain pieces each person takes one piece and places it on the board. In our case we have our map and each terrain piece could be assigned a size to where it could fit on the map and it get placed according to its size. That way similar sized features like houses (which would be the largest) would be put near each other on the map and smaller stuff would get grouped likewise. Ther could be markers on the map to say that certain terrain features have to go in certain places like bridges over streams and rivers and then everything fits around them.

 

That way we can widen the types of map we use and could fight up hills and over streams and things would look in place.

 

Of course another way to do it which would require more work is to have preset maps for each type of terrain pre playtested for the maximum fun and challenge. That would mean more work but it might be worth it if the benefits of preset terrain outweigh random generation.

Yeah, that's what I was saying, it would save space in that building sizes can be reused for a lot of maps so we only need one outline of each house. I don't think this is an original way of doing things, noone can say anything about gleaning techniques from other games especially for art. It will still look different even if we use their interchangable system. I think Fux posted a while back a quote saying nothing good is ever written, only rewritten and I think this applies here. I agree we don't want to clone their game but if they have a good way of doing things then we shouldn't be afraid to use it too. The gameplay will be different from them and us anyway so I wouldn't worry about cloning it.

[Cpl. Facehugger]

I don't know, I think we should endevour to "borrow" as little as possible from other games in this genre (except xcom of course )

Sure if a game has an really useful feature, we should add it, but we shouldn't do it too often.

[[dipstick]]

To be honest, even with a 56k modem I don't care about how big the file is!! I just want the game!!

[Cpl. Facehugger]

I think we were talking about how we shouldn't blatently rip off other x-com like games.

[Guest Jim69]

Yes, but it isn't like I'm saying "Lets add X feature from Aftermath" I am just saying the way they have handled maps ( which, BTW, since I thought about it is pretty much the same way as X-Com just with a twist ) is good and we should use it, or at least improve upon it.

[Breunor]

For crash sites I think it would work to have a series of placement templates, where main features like buildings are given possible positions and then a random model is picked for each slot. Then the terrain generator would fill in the open areas and make sure to match the elevation of the buildings and all that. We had discussed terror sites and keeping them in a grid format for v1, that grid format could also be used for crash sites, where some grids are buildings and others are terrain. For determining tactical challenge and realistic looks, we can discuss it on the template layout just like a floorplan for a ufo IMO. We just come up with valid designs for farms and terror sites, and generate terrain for them. Regular crash sites without buildings would be a matter of making nice looking terrain, and leaving a flat spot for the landing craft and ufo, as if they were buildings. That template should just make sure they aren't right next to each other IMO.

[Guest Jim69]

That is exactly what I was thinking, it can make the maps look totally random assuming we have more than just buildings to go into those slots, the BB Court is one example but I think we need more for instance a park. You are right about the terrain parts as well, leave a space for the terrain generator and make sure that the edges are the same height as the space around it.

[Breunor]

Funny you mention the BB court, I played Vice City for the first time last night and ran past a court that looked very similar with a swat team on my heels... I think we can make several templates (say 5), and then make several different models or choices for each slot to get a decent variety the first time around

[Guest Jim69]

There is one in Aftermath as well They stealing our ideas ::

 

The more stuff we can think of to fill in these masked model parts, which BTW I think would be easily represented by a box that is replaced randomly from a list before the level starts, the more variety of levels that we will have. If there are, say, 5 different things for one area to fill in the gaps, in one area, and 5 gaps to fill in one level then there are 25 different combinations for that level in that area. See what I'm getting at?