global collision detection

so im making a procedural dungeon generator. i place rooms randomly, and checking everytime a room is placed if it collides with the rooms already placed. currently i use the bounds.Intersects() method, but i think this is not the best.
so i want to understand how the collision detection works. i read the scripting API and such, but all i can find is these "messages", OnCollisionEnter etc. all of them seem to be privatly used by the game object.
in my case though, i want something like;

Code (CSharp):

1. dungeonGenerator{
2. List rooms;
3.  
4. for(amount of rooms){
5.       gameobject newRoom = new gameobject();
6.       newRoom.position = random position;
7.  
8.       for(int i = 0; i < rooms.Count; i++)
9.            if(!newRoom.collidesWith(rooms[i]))
10.                 rooms.Add(newRoom)
11. }
12. }

like i want the dungeonGenerator class to check if theres a collision between two gameobjects. how do i do this? should i use those methods, OnCollisionEnter and such to achive this?

 

What's wrong with it?

Sidenote: your algorithm as pseudocoded would add a -lot- of new rooms instead of just one. Make a bool "doesIntersectRoom", start it false, set it true if an intersection is found, and then "if (!doesIntersectRoom) rooms.Add(newRoom);"

 

hehe yeah i saw that now. would been a lot unnecessary rooms.

but yeah whats wrong with bounds.Intersect is that its done on a box shape, and i have rooms of almost any arbitrary shape so in some cases a bounding box is a very bad approximation. i want the exact collision the physics engine uses. or if there is some other equally precise

 

You can do it with Rigidbody.SweepTest, but it's going to be a little gnarly. Basically you'd have to position the room up above the other rooms, and then sweep it straight down, and see if it hits anything.

Usually, 2D dungeon generation is instead done with a grid, which is a LOT easier and more efficient. Are you sure that wouldn't work in your case?

 

yes im sure it wouldnt work. its not 2D. and i dont really want to constrict room shapes to a grid pattern.
this is more or less what im doing. pic stolen from daggerfall.

thanks for the suggestion though! ill look into the rigidbody.sweep.
i dont think im trying to complicate things either. surely unitys physics system most compare meshes all the time to see if they intersect or not.
i am prepared to write my own collision method if its necessary. just feels like wasted time if unity already have such methods. if anybody have a suggestion, or a guide to check if two meshes of arbitrary shape intersects i would also be grateful.

 

Well, it sometimes compares convex meshes to meshes, but it never actually does raw mesh-to-mesh collision detection aside from that - mesh colliders don't collide with mesh colliders unless at least one of them is marked as convex. I would say that your best bet is to roll your own (or find some third party mesh-to-mesh collision algorithm/package).

 

Unity's underlying physics system - PhysX - lives in the c++ side of the engine, and is not something you have access to directly - you have to use the Physics interface.

If you rooms are somewhat box-shaped (or you can accept box-based collision detection), you can use Physics.CheckBox, which is new in 5.3. It let's you define the center, extents and rotation of the box, and get if there's anything there. This is vastly superior to the old Bounds.intersect, which could only check bounding boxes.

 

@Baste, that's cool, I hadn't discovered that one yet.

If your rooms aren't box-shaped, they may nonetheless be composed of multiple smaller boxes. So you could just check each one using this new CheckBox method.

 

hmm... i kind of want the freedom to create non box shaped rooms. i guess i can be ok with using convex shapes, but there is no Physics.CheckConvex only box and capsule. probably i will write my own instead. just wanted to know it was not unecessary work.

 

It's a bit tricky, but you can use a wrapper to send the OnCollisionEnter events to DungeonCollisionManager and have DCM cache the collisions. Sorry about the gawdawful formatting.

//Goes in script called "DungeonCollisionNotifier"
class DungeonCollisionNotifier : MonoBehaviour {
void OnCollisionEnter (Collision col) {
DungeonCollisionManager.CollisionEnter (this.gameObject, col.gameObject);
}
void OnCollisionExit (Collision col) {
DungeonCollisionManager.CollisionExit (this.gameObject, col.gameObject);
}
}

//static for easier prototyping; goes anywhere
static class DungeonCollisionManager {
static HashSet<long> Collisions= new HashSet<long> (); //Constant Add, Remove, and Contains performance
public static void CollisionEnter (GameObject obj1, GameObject obj2) {
Collisions.Add (GetDeterministicID (obj1.GetInstanceID (), obj2.GetInstanceID ()));
}
public static void CollisionExit (GameObject obj1, GameObject obj2) {
Collisions.Remove (GetDeterministicID (obj1.GetInstanceID (), obj2.GetInstanceID ());
}
public static bool IsColliding (GameObject obj1, GameObject obj2) {
return Collisions.Contains (GetDeterministicID (obj1.GetInstanceID (), obj2.GetInstanceID());
}

private static long GetDeterministicID (int i1, int i2) {
//Generates a unique 64 bit int from 2 32 bit ints where order doesn't matter.
return i1 > u2 ? (long) i1 | (long)i2 << 32 : (long)i2 | (long)i1 << 32;
}
}

 

thanks man but i decided to do my own.

on that note, could anyone please point me in the right direction for writing something like that? a test to see if two convex meshes intersect? i dont need to know intersection points or areas, just true or false.
would be super grateful for anything more beginner friendly than scientific papers

 

That's not a beginner-friendly topic. As in, it's really hard. You should seriously consider instead approximating your geometry with simple shapes, and intersecting those instead. (That's still quite mathy, but far more approachable than intersecting arbitrary convex meshes.)

 

I think you need to consider some of your constraints for this. So you said above that it's not 2D, the Daggerfall pic seems to be only somewhat 3D, and to find a simple solution you'll need to answer some questions.

• Are all the rooms joined to each other (adjacent to another room) or connected by hallways/passages?
• Are the rooms boxes? You said they weren't, but for collision you might be able to approximate them with boxes. It depends how snug you want them to fit together.
• How 3D is the dungeon? I've never played Daggerfall, but it looks like in that image there are no rooms laying above other rooms.
• Are rooms themselves 3D? Do their roofs have different heights? If not, could you just treat them as 2 dimensional polygons (viewed from the top)?

Testing to see if two objects are intersecting can range from extremely trivial to extremely complex, depending on how much precision you want. Very often in games you can get away with low precision algorithms without anyone noticing. Try to draw out an example dungeon (or just manually place rooms in Unity) and it might be easier to help.

Or, if you are a mega keener, the Separating Axis Theorem is the simplest way to test intersection between two convex shapes.

Forreal tho Unity needs to expose all of PhysX intersection methods. They're just sitting there in the DLL, wasting their life away

 

alright i think i need to clarify; the rooms are fully 3d, of any given shape. they can be at any position or rotation.

heres a picture of what i have already;


the rooms are placed randomly in clusters, and then connected to eachother with corridors (pink lines)

currently it works somewhat, im using bounding spheres to see if rooms intersect before placing them. it works alright, but now i want to to the same with the corridors, they currently dont care if they intersect. and you can see that very few of them would pass an intersection test with a bounding sphere.

so i decided i will get the highest precision and best looking dungeon with full 3d mesh intersection test.
and since im pretty interested in this stuff, at least i think its fun to learn, i will try it this way. if it proves to hard, ill try it with convex collision shapes. if that proves to hard, ill try it with segmented bounding boxes.

so i just wanted somekind of advice where to start, if anybody knew some library or easy to read pappers on this stuff.
googling for it was hard, must of the stuff that came up was hard-to-read scientific papers.