Maze algorithm for dynamic buildings and RUBE_BuildingElements

(for the rather visual folks out there: scroll down, pictures are linked below!)

The idea: basic building elements, arranged and spawned per script to form/build random, yet somehow authentic/believable - functional - buildings (inclusiv interiors!), where

• the basic building elements consist:
  
  • wall-elements (we do not need corner elements)
    
  • door-wall-elements (single-/double-doors, garage-doors, gangways, ...)
    
  • roof-elements (incl. variations with hatches and ladders, solid/concrete roofs or camouflaged/overgrown and special egde/corner-elements with guard railing, little walls or sandbags)
    .
    

  [*]a pretty simple, recursive maze algorithm/script divides a rectangle into smaller ones (chambers) and return's the needed data to:

  • spawn the maze/building itself (wall-, door-, roof-elements)
    
  • design/spawn the interior of the building (we get an array of created chambers)
    
  • also we may regard the roof as another (special-)chamber
    .
    

  The script itself should be highly customizeable to define min. and max. room/chamber-sizes, etc. And maybe we need a meta-maze/building-script to build non-rectangular or more complex buildings out of several such simple mazes, cleverly connected together. Maybe even multiple floors on resulting roofs?

  .

  [*]a "fill-the-chamber's" script, which `designs` the interior of the mazes/buildings chambers.

  This need's to be themed (military buildings like armory or bunkers, civilian buildings like offices, industrial buildings, ...), depended on factions, highly customizable and also a bit clever (some chamber-types should occur more often than others, some should occur only once, some work only for small chambers, some only for greater ones, etc..).

  Also this script should be able to spawn random specialized AI with their own tasks (be it office-work, patrol, sleeping, research, ...), based on the chamber's theme/function. We probably need to have AI-tasks that work on the whole maze/building (e.g. to walk through all chambers or around the building, ...) and such that work on/in a single chamber and it's interior-objects...

  And, to be absolutely sure, that one defined chamber exists (mission critical?), you may aswell filter the chamber-list, do something with a certain chamber with your custom script and pass the other chambers along to this one here...

The goals of this are thus:

• fun and interessting CQC in a fresh dynamic generated world/building. (static Hexenkessel my ass! hrhr How about some CQC in an always newly created, really big maze? - with no exit!? ArmA2 - The Cube anyone? hehe)
  
• a random/dynamically created building for missions where this building is central: hijack some engineers, spy stuff, steal documents... where the goal is always to newly explore/search that building.
  
• maybe even a small city with such buildings, maybe complex buildings consisting of such rectangle-mazes, ...
  
• a small piece to use in "dynamic spawn base"-scripts.
  

btw. the AI (in my current prototype) performs pretty well in such a maze environment, though pathfinding (on go there commands) is a bit confusing at times. That is, they don't always choose the quickest path, maybe the safest?! Well, my spawned buildings are mazes afterall, so if you consider this a hardness test for pathfinding, AI does actually pretty well. Also the advancing, cross fire and leaning and stuff is totally titts! (at least most of the time)

The maze algorithm

The maze algorithm is really the most simple one there is, (we may experiment with other ones):

Given a rectangle, (we build walls around that container-rectangle and place at least one entry/door which constitutes our maze/building). Thus we start with one big chamber.

As long as a chamber is greater than a given max. OR by chance, but never, if the chamber is under a given min. size, we divide the chamber at hand by a randomly placed wall - either horizontal or vertical - and we place exactly one door. Recursively repeat on the resulting child-chambers, and thats it.

If the defined min. size of a chamber would be atomic, we would indeed end up with those crazy mazes, but if we define a reasonable min.size, we will end up with a pretty nice "level"-layout, where it's guaranteed, that all chambers are accessible.

The most difficult problem here is the placement of the walls. We need to be able to make the maze with one single wall-element. One single wall-size which defines the atomic chamber-size or a maze-cell if you will. If you think about it, you will need to get around the following problem: as we divide a chamber further into child-chambers, the cell-size would diminish if we consider the width of the wall itself. Thus such an approach is doomed, if you don't wanna use a zillion of differrent sized wall-elements.

Instead, we imagine the wall uses no width (or depth) at all so we can place the wall elements (in though) exactly on the edges of a maze-cell, thus keeping the cell-size constant. What we really do is: we place the wall's according to the following sketch into the next cell, so we will end up with nice corners (from inside and outside), since two wall elements will overlapp a bit. (yeah z-/depth-fighting,.. see below). Thus, the thiner the wall-element, the better, though it works quite nice with my concrete-wall already (0.25m in depth).

Example/Sketch:

   `Maze` with 3 divisions/walls and 4 chambers:

                      C
      ________________|___________                 A
      |        |      |           |              /   \
      |        |   3   <    4     |             1     B
      |        |      |           |                  /  \
      |        |______|_____   ____ B               2    C
      |   1    |             ^    |                     / \
      |        |                  |                    3   4            
      |         <      2          |
      |        |                  |
      |________|________   _______|
               |         ^
               A      single bottom entry/exit

  We place the wall-objects not inside the cell, but outside (into the next cell)
  to get nice corners:

         _____
       _|_____|_  
      | |     |w|   
      | |cell |o|  <- wall object placement into next cell
      |_|_____|_|     to get nice corners from inside and outside.
        |_____|  


      _________________________________
      |       |       |       |       |  
      |       |       |       |       | <- cell
      |       |       |       |       | 
      |_______|_______|_______|_______|
      |       |_|_____|_______|_______| <- wall object, overlapping at the corner
      |       | |     |
      |       | |     |
      |_______|_|_____|
         ^     ^
       cell    |
             wall object

^^ Btw. I have a little flaw with this, since some inner wall-objects need to be put in the "self" cell and not the one next to it to build a nice corner (I need to consider already placed walls are for this). Thus, we may currently end up with a "double-corner", as in the sketch below. The "wrong" wall get's place from cell 2 into cell 1 where it builds the topleft double-corner, instead of beeing placed in cell 1 to form a nice corner.

  possible flaw: double-corner:

              ________
      ________|___w___|  
      |     | |       |
      |  1  |w|   2   | 
      |     | |       |
      |_____|_|_______|
             ^

  instead of: 

              ________
      ________|___w___|  
      |       | |     |
      |   1   |w|  2  |
      |       | |     |
      |_______|_|_____|
               ^

Well, it's not too bad, but I might wanna address this issue...

RUBE_BuildingElements (the addon)

Now, I never really was a great fan of addons. I love the great modifications, but I hate to collect lots of small ones... etc, and personally was never interested in actually creating something by myself.

Well, as you can see here: alphaMaze091101.html, I soon realized that I woudn't come far with vanilla ArmA2 objects - heck, I used flipped corrugated fences as roof-elements, hehe. Sadly, there are no appropriate/suitable building-elements for this and also the editor upgrades don't help either. Afterall I really need a set of matching building elements.

Thus - teeth grinding, hehe - I considered doing my own building elements as addons.. I mean, how hard can it be? hehe. Thanks to Mondkalb's tutorial (and others), it wasn't really hard to begin (after all, Mondkalb's tutorial has exactly that as subject, what I'm after, jay!).

But of course, problems arose soon, so I had to spend some more hours to make things actually work (like making the AI to use doors, ect..)... It's still too soon, to offer a playable demo (the pbo with the walls is 13mb due to bad texture useage, hahaha) but I wan't to show some pictures and start a general discussion and ask for some advice.. you know, the devil is in the detail and I really need your help!

First, please have a look:

Some pictures (WIP):

• Close Quarters Combat - picture serie
  
• Building Desctruction - picture serie
  
• Errors and problems - picture serie
  

Second,

My problems/questions:

1. Moddeling/Texturing: What's a reasonable size? How to exactly apply a tiled texture?
   At the moment I use one single 2048x2048 texture (incl. DT, NOHQ and SMDI), resulting in a pbo-size of 13.6mb(!) for two walls (one with a door) and a roof object.. everything is uv-mapped.. I guess, that's quite terrible. Most space in this texture is plain concrete.. which I probably should tile anyway (a BIS concrete-tile texture is 512x512, I've seen..)..
   Ok, so say I have my tiled texture, how do I apply it? I can hit A, draw a square over the model and hit B in Oxygen, there. But isn't there a more exact way? And what about unwrapping etc.?
   .
   
2. Rendering at distance/LOD: As you can see in the "Errors and problems - picture serie", I have a serious problem with the rendering of this. For one, the building (or rather the building elements) is rendered far too late. Note that other buildings much behind(!) our building are already rendered, while the building elements aren't rendered at all or only partially. What's the deal here and how do I manage, that all the building elements gets rendered like the houses?
   In the config file of the building objects, I inherit from "House". Is there a better option or do I need a certain command there?
   Or is it because my models have only one LOD-level (0.000) since they are very simple already. Would it help, if I copy LOD 0.000 and rename it to LOD 10.000? Or can't I do anything to better the render-situation? I guess, forcing that all building elements are rendered together and never partially isn't possible. But it should render at a reasonable distance.. how?
   .
   
3. Z-/Depth-fighting: Due to how my maze-algorithm works, I need to overlap the wall-elements a bit (to build corners, inner walls/chambers and such all with one and the same wall-element). And of course, we get z-fighting there. Also we get this flickering pixels at the edges, where objects (wall or roof elements) are placed to tight. I guess that's basically the same problem. Is there a way to stop or at least moderate this visual problem? I guess I could displace all the objects a tiny little bit in my maze script. Isn't there a better solution? Like a render flag? (I've tried "NoZWrite", yeah it didn't flicker anymore, but you can probably imagine how it looked now, hehehe.. it's certainly not what we want.)
   .
   
4. Plant's in the building: Of course, we have plant's inside the building. IMHO it's not too bad, but still... Would a simple floor-object be able to cut them? Or is there another way to get rid of the plants, be it a bush or just grass?
   .
   
5. Slopes, the building "falling appart" and countermeasurments: Right know I do nothing special here, so of course, the building "falls" apart if placed on a slopy terrain, a hill or something. Thus the question: what's the best strategy here?
   I can think of two options:
   
   1. 
      
   2. first we place some dummy objects as probes at the corners and one in the middle of the building, take note of the height above sea level, remove them again and calculate the minimal negative offset to place the elements, so that all elements are at the same height, thus some objects will end up burried a little or more..
      
   3. we spawn all building-elements, iterate over them to find the lowest absolut position to iterate once more over all of them and apply the needed offset.
      

Maybe there is even better option? A config-tweak in combination with "the false ground"-approach of the warefare objects? How about some extra-height for the wall elements in Oxygen below the ground-level? Could something like that work? Any advice on how to solve this problem would be much appreciated!

.

[*]Destruction/-types: As you can see in the "Building Desctruction - picture serie", a nice side effect of this approach is that the building is destructible in parts! (I remeber an old OFP-Demo where one could shoot out single bricks from a wall!... well, it's not like this, but IMHO already nice as is now)

What we need now is appropriate desctruction simulation/types. I haven't done a ruin-model yet, but I guess for the wall-elements this would be most appropriate. A small rest of the original wall and some concrete-bits here and there. That should work fine.

1. Question one here is: is it possible to have several ruin-models, where the actual ruin-model to be spawned get's choosen randomly, so we have a bit of a variation here? I fear that it sould look very awkward, if all wall-ruins would look the same. And also, I think I could easily create multiple variances of the same wall-ruin with hidden selections (hiding the single concrete-blocks/rumble for example). Would something like this work?
   .
   
2. Question two is related to the roof-elements. As you can see in the "Building Desctruction - picture serie", they can blown up too, which is nice, but we may also end up with them, flying in the air, because they survived, where as the supporting wall elements are gone. This is just wrong. Is there a way to make them dependent on certain other elements, so they would at least fall? Could I make them a "thing"/simulate a "thing" in the config? Any other idea? Or is the only option that could work at least a bit better be to just apply a very small mass/armor to the roof-elements, so that they should get destructed way earlier than any wall below it?
   .
   
3. Question three regarding the roof-elements again: what is the appropriate destruction-type? Right now, none is applied, so the roof just disapears (or falls very fast down, below the ground and vanishes).. This, I guess, isn't too terrible. Ideally the roof elements would vanish and several roof-pieces should be spawned in place as "things" so that they would fall down, applying damage to whatever is beneath them. That would be great? But I didn't se a DestructionType like this. Wouldn't that be a usefull new destruction type? Or what else do you suggest to make the destruction of roof elements well?
   .
   
4. How about partial destruction/destruction stages? I undersand I can apply a 50% damage and a 100% damage texture to the building elements. This could work nice (with pseudo holes per normal maps, etc.) I guess. But how about partial model destruction. E.g. can I make the door-selection of a wall-element destructible, while the wall still is alive? Sure, I could make them two separate objects, but is there a way to do this, while keeping them together in one model? Could hidden selections be used to make some parts vanish?
   

.

[*]High number of objects: a problem? I don't think this will cause any problems for single-player. Performance is normal (most objects won't be rendered anyway since you can't view them.. hehe), at least I can't note any fall-offs and I'm on a friggin notebook here, hehe. But what about multiplayer? Is this sort of thing a nogo? Are there some things I should consider?

Also: the spawn-time of all the objects varies. Sometimes a whole maze of considerable size is spawned instantly at startup.. and other times you can watch how every single pices gets spawned and setposed to.. But I don't think this will be a big problem, since this can be easily circumvented with clever scripting either at startup or at a later time ingame. The good news is, that the spawning-process dosn't slow anything down, even if it does take some seconds.

.

[*]Again regarding tightly placed/setPosed objects: As you can see, I spawn lot's of tables and also I like to put things on the tables. Problem one: the tables itself may be nicely in rest at the beginning, shot at one of them once (eg. the multiple tables forming a bigger one) and they all start to jump around as if I said them to simulate some fluid, hehe. Also things on them are a problem, since they can get stuck in the air. And third: If you drive into them, the fly soo easy and soo far, it's terrible (well, now with conrete walls, this can't happen anymore, hehe). Anyway, I ended up setting enableSimulation to false for the tables and now they behave way more normal. The problem is, you can't destruct them anymore.

The question now is: is this a general problem with arma-physics? Or is the FoldTable-Config messed up? IMHO this table should not jump around if placed tightly and shoot at due to it's weight and above all the weight and friction of all the other tables around. Second, if too much speed*weight hits a table, it shouldn't result in a flying table, but in a destructed one! Anyway, what's the best solution? Disabeling simulation for such objects? Modding new objects with more appropriate configs? Waiting until things get solved by a future patch?

.

[*]And last but not least: Illumination: Have a look at the cqc pictures. Do you note anything? It's bright inside of a bunker that has not a single light, as if there were no building at all. Note: there is not a single window and no light can possibly come in this bunker, exepct for the few doors there are. That's just wrong and I hope to manage to make it dark in there. To make there light again! Of course! (I think the roof-element would be a good object for a light, maybe not on every roof-element, but on some, which would result in good lighten and darker rooms, which would be awesome if you ask me..)

But how?

First: How can I make it dark? Is it even possible at all? Do I need to nullify any diffuse and specular light on my building elements?

Second: I guess makeing lights then isn't too hard (can I follow tutorials written for actual vehicles - just apply another light-form/direction?) The question here is more: is there a limit to the number of lightsources? And if so, how do I manage this?

.

Further plans:

• I plan to have several types of building elements/sets. Concrete, wooden walls, what else? Maybe a terrain-imitation for outer walls and roofs? Yeah, imagine a grass-layer ontop of the roof!! -> New question: can I manage it so the native/world grass will be there on top of my roof-elements? Possible? Or do I have to model my very own grass?
  .
  
• Second, I really wanna make more special building-elements: roof-corners, a ladder-to-roof-element, maybe even a stair, though it probably shouldn't be larger than cell-size, double-doors, garages with higher walls for tanks and trucks...
  .
  
• Then I probably will make some custom objects like beds and stuff.. For there is a distinct lack of furniture in vanilla ArmA2. Though nothing too complex I guess.
  .
  
• I plan to use the roof as a separate chamber and eventually spawn a second floor? Also complex mazes is a thing which I'd love to pull off...
  .
  
• Right now I have only few inner-design types: a meeting-room (one big central table), a class-room, a security-room, light/heavy armory, storage room with industrial material.. Unfortunately there aren't much useable objects in vanilla ArmA2.. Thus I think I'll create some own objects. Especially some beds are needed. What else do you suggest?
  .
  
• also there should be low-level and more/easily useable high-level scripts to spawn such buildings. I don't know yet if a module would be appropriate, since such a maze would need some initialization/parameters and stuff anyway.. hm..
  .
  
• btw. this should end up in a package for dynamic bases and stuff, based on a set of functions I'm working on like: grid-spawning, circle-spawning, rectangle-packer (packing problem), ... well, this may take some time (and I may need to rewrite/-structure a lot of my "prototypes".. oh boy..)... :/ hehe
  .
  

Soooo, what do you think? Lame or game? :D

Please keep in mind, that the building elements constitute my very first addon. So quality is still poor and I really could use some advice on lots of things regarding modelling and config tweaks. I'd highly appreciate if you can answer (if only partially) any of my question. Or just some general advice would be nice too. Thank you very much.

I don't know how fast I'll make progress and when I'll be able to give you a working demo. Probably as soon as my addon for 3 simple objects is trimmed down to a reasonable size. 13mb for this is just creepy. (well, what would be reasonable? hmm)

I'll keep you in the loop!

tweak on!

rübe

very nice from what I've seen in those screenshots, this game does need more Close quarters fights.

to 2.

featureSize for the config class makes it drawn further away.

Very nice project. Good fun with algorithms. :)

Plant's in the building: Of course, we have plant's inside the building. IMHO it's not too bad, but still... Would a simple floor-object be able to cut them? Or is there another way to get rid of the plants, be it a bush or just grass?

Try using the GrassCutter from A1. The following works in A2 (just ripped it straight out of an addon I'm working on), but you'll need the A1 GrassCutter model:

class CfgVehicles
{
   class Thing;
   class HMM_GrassCutter: Thing
   {
       model = "\hmm\misrec\cutter\grasscutter.p3d";
       displayName = "Grass Cutter";
       icon = "\ca\data\data\Unknown_object.paa";
       scope = 2;
       simulation = "thing";
       nameSound = "";
       transportFuel = 0;
       mapSize = 0.7;
       accuracy = 0.2;
       cost = 0;
       armor = 200000;
       vehicleClass = "Misc";
   };
};

You can probably modify the p3d (or create another) to achieve a desired effect (maybe mirroring a square shape instead, at the same size as your smallest cell).

featureSize for the config class makes it drawn further away.

Thanks, this seems to help, though that's all it does. It doesn't really solve the problem, since there are still buildings further aways drawn prior to my building elements. But I guess this is due to the sheer amount of the building elements versus one single building.

Also I'm not sure, what the value for featureSize exactly does, and what it's range is. BIS has used featureSize only on few things and the range goes from 0 (which is the default) to max. 150 for the TVTower.

I've set the featureSize to 1000 for my building elements (as you did for your proper mod/draw distance tweak; btw. more or less the only resource/documentation I've found for this), though I think there is a fixed cap somewhere, so 1000 probably gets trimmed down to this I guess..

Try using the GrassCutter from A1. [...]You can probably modify the p3d (or create another) to achieve a desired effect.

hm. sounds good. The problem is, I don't have A1, so I can't examine that GrassCutter. Unfortunatly this (nor the HeliPad) is not available in the BIS sample models pack I've found, so I don't have a clue how such a cutter-model should look like.

I've tried a plane slightly above the ground + geo-lod to set some mass, but no selections.. (and of course a config as you suggested, inheriting from Thing), but for one that thing didn't cut anything and for two: it was actually rendered as a white plane, despite the fact that I haven't set any texture or material. So what is it, that makes my model actually "cut" things, and how do I get my model invisible?

May I ask thus for some more info on how to model that grasscutter or would you upload an unbinarized grasscutter example? That'd be sweet.

Besides such a cutter "only" cut's the grass, but no bushes or anything other than the grass that can be planished, right?

--

Btw. I did some progress regarding texturing, so that all larger surfaces are textured with 512x512 seamless textures, while only the door is UV-mapped (again a 512x512 texture for one door).. and as a result, the pbo is currently down to 4.4mb, yet including more models (a second concrete texture alternative and some roof-top variations (plain, moss and stone))

Also it looks like it was a good idea to apply less armor and weight to the roof-elements. At least the last destruction-tests didn't result in any free-flying roof-elements anymore. Though that could have been more luck than anything else.

But, it's still too soon for a demo. I first want to do the roof-edge elements and a ladder-roof-element and adapt the scripts accordingly.

Keep the tips'n'trick comming. :D What currently troubles me most is the problem with the illumination or how to get rid of it inside my buildings. If the wall elements have some specular parts, it can really look funny inside (because the wall's - depending on their direction/facing - look totally different).. Well, maybe my material-settings aren't that sensible either :rolleyes:

Also I wonder if there are any tricks, that the mipmaps of tiled/seamless textures don't look that awefull. At close, it looks good and also the tile doesn't repeat too blatantly. But at a larger distant, the pattern looks terrible, not really because of the repetition, but because the mipmaps are bad. They loose somehow color/saturation the more they are scaled down. Hm, any advice on this one?

hm. sounds good. The problem is, I don't have A1, so I can't examine that GrassCutter. Unfortunatly this (nor the HeliPad) is not available in the BIS sample models pack I've found, so I don't have a clue how such a cutter-model should look like.

May I ask thus for some more info on how to model that grasscutter or would you upload an unbinarized grasscutter example? That'd be sweet.

I can send you a binarised version with an A2 config, but I'm no modeller, so I couldn't really do any more than that, sorry!

Besides such a cutter "only" cut's the grass, but no bushes or anything other than the grass that can be planished, right?

Just tested in A2, and some bushes (probably more like 'tall grasses') are removed. Trees (and most bushes) aren't. I expect it's because it only removes clutter, rather than removing map objects.

This could be circumvented by using nearestObjects, but the problem here is that trees and bushes don't have config entries. I know Xeno once took the approach of finding the unclassified objects and then parsing the filenames of the p3d's to find the models in which the words 'tree' or 'bush' occur (presumably in Czech) and only deleting those. If you're not frequently creating buildings, I can imagine that approach might work fine... but it'd be costly (execution time-wise) if you're doing it a lot.

I can send you a binarised version with an A2 config

I'm afraid that wouldn't help me much since I need to know how such a cutter-object has to look like and what LODs have to be used... Does the cutter need to be a 3d object or is a plane enough?.. and how to get it invisible?

As for the cutter not beeing able to cut any objects other than the world's clutter, that's fine since we can use isFlatEmpty or BIS_fnc_findSafePos to find a suitable place at random.

And maybe I don't need that cutter afterall, for a real floor-object could come in handy to circumvent the problem with slopes/slopy terrain. I'm thinking about a pretty deep/high floor (more like a block) that I could sink into the ground as needed (instead of sinking the walls).. Though it's yet another stack (x-cells times y-cells) of objects, where one single would do aswell..

There isn't a command to scale spawned objects, while ideally a texture is tiled and thus doesn't get streched, but repeated, is there? That would be very handy, though probably only usefull for really simple models...

Regarding my illumination-problem, you have to understand, that I'm a complete moron. :p I already mentioned that I'm on a crappy computer, yet I didn't tell you that I have disabled my shadows over here and did forget that detail, haha.

It certainly does look a lot better if shadows are enabled, though it's still much too bright in there. It's like one building element is casting the shadow, assuming that it's all bright around where it doesn't cast the shadow.. so it applies a "half" shadow.. but since everything in there should be cast in shadow, there shoud be a "full" shadow, but the shadows don't sum up or something (I don't have too much clue about how the lighting exactly works, so pardon my funny wording. Of course shadows don't sum up, since we speak of the absence of light and not the presence of a thing called shadow.. hehe).

The question is: is there a render-flag or something I could apply, so I'd get my "full" shadow? Or is this an engine-limitation, thus there is no way to get real darkness in a cube (at daytime), where door's are closed and no windows are present?

To 8: Use enableSimulation false for the tables :)