-
Notifications
You must be signed in to change notification settings - Fork 0
CollisionWorlds
Having a loose assortment of collision shapes that can check against each other is useful, but it leaves a lot to be desired when it comes to creating a unified game world. So here's how you can create a unified game world.
You might consider just keeping a list or array with every shape in the game and checking for collisions by iterating over it, but in large collision worlds (or let's face it - this is GameMaker - not very large collision worlds) this will start to be a little slow. There's no sense in checking if two objects are in contact with each other if they're on opposite sides of the universe, so instead we can organize the world into some kind of spatial hierarchy so that we only have to deal with collisions between objects that are (relatively) close by.
There are three kinds of spatial hierarchies available here: octrees, quadtrees, and spatial hashes. All three hierarchies allow you to cull out large chunks of the world for collision detection by only considering regions of space around the player, but the way they divide the space differs.
Other types of hierarchies exist. I might implement others if I get really bored.
| Parameter | Type | Description |
|---|---|---|
| bounds | ColAABB | The total bounding area of the octree |
| depth | real | The maximum recursion depth of the octree |
Octrees recursively partition the world, dividing it in half on each axis several times, creating smaller and smaller regions of space.
As recursive operations such as this can sometimes involve an excessive amount of overhead, the octree will only subdivide a region if the number of objects in it exceeds the value in the [[COL_MIN_TREE_DENSITY|CollisionEtc]] configuration setting.
Objects that exist the bounds of the octree will be ignored in collision checks.
Octrees are also used to partition ColMeshes.
| Parameter | Type | Description |
|---|---|---|
| bounds | ColAABB | The total bounding area of the quadtree |
| depth | real | The maximum recursion depth of the quadtree |
Exactly the same as an Octree, except instead of partitioning space on all three axes it only partitions space on the XY plane. This can be desirable if most of the contents of your game world are not very far apart on the Z axis, such that partitioning space in that direction would mostly be a waste of time.
| Parameter | Type | Description |
|---|---|---|
| chunk_size | real | The size of each chunk of space within the spatial hash |
Rather than doing binary partitions on the world recursively, spatial hashes divide the world into chunks of a fixed size. This tends to work better than tree structures if you have a lot of small objects that are unlikely to occupy more than one chunk of space.
Frustum culling currently does not work on spatial hashes.
Once you have a hierarchy representing your game space, it's time to start putting things in it.
However, collision shapes on their own can be a bit clunky to work with. Collision Objects are a useful abstraction that hide most of the annoying parts.
| Parameter | Type | Description |
|---|---|---|
| shape | Any collision shape, except Rays, because that makes no sense | The collision shape that this object represents |
| reference | Whatever you want | A reference to a GameMaker instance, some other struct of your own creation, etc |
| mask | int64 | The 64-bit collision mask for the object, representing the types of collision that can be triggered by this object (defaults to 1) |
| group | int64 | The 64-bit collision mask representing the types of collisions that this object can identify (defaults to 1) |
Collision Objects are the link between your GameMaker instances and the collision system. Objects contain a Collision Shape and a reference that can be anything but, in practice, should a reference to whatever GameMaker instance you want the collision data to be associated with.
Collision masks are a pretty common concept in 3D collision detection in general, but unfortunately in GameMaker it means something else so for the purpose of this system you need to forget everything you know about whatever this is. In the past I've used the example of magic force fields such as the ones GLaDOS might use to prevent you from getting too attached to your Companion Cube and Unity's collision layers to illustrate the concept. They're very useful whenever you want to use the same collision system to handle separate types of collisions.
When two objects check each other for collision, a binary AND is performed between the group of the object initiating the collision check and the mask of every relevant object in the world. If the mask and the group share any common bits, the two objects will be considered for collision detection, and will be ignored otherwise.
Imagine you want to have one kind of collision to handle collisions with solid objects, and another to handle bullets. You might create two collision masks like this:
#macro COLLISION_MASK_SOLIDS 0b0001
#macro COLLISION_MASK_BULLETS 0b0010
You would create an object for a solid wall and give it the COLLISION_MASK_SOLIDS mask, and another object for the player and give it the COLLISION_MASK_SOLIDS group. Checks done against the World using the player's object will detect collisions with any object whose mask includes COLLISION_MASK_SOLIDS, and walls will stop the player.
If you then wanted an object that was passable to the player but could stop bullets, you could instead give it the mask COLLISION_MASK_BULLETS. Collisions with the player would then be ignored, but raycasting against the world using mask COLLISION_MASK_BULLETS would produce a hit.
If you wanted an object that could stop both, you could combine the two masks with binary OR
#macro COLLISION_MASK_BOTH (COLLISION_MASK_SOLIDS | COLLISION_MASK_BULLETS) // equivalent to 0b0011
and assign the object a collision mask of that instead.
If all of that just went in one ear and out the other, the default values for both the mask and the group are 1 and that'll probably be fine most of the time.
Objects have a few methods, and they're mostly wrappers around the shape.
CheckObject will automatically resolve collision filtering based on the two objects' mask and group. CheckRay will use the group specified.
Lastly, here are the relevant methods for collision worlds. In almost all cases, this is the only part of the collision system you'll have to directly check for collisions against from the outside.
Returns: N/A
| Parameter | Type | Description |
|---|---|---|
| object | ColObject | An object you want to add to the collision world |
Adds an object to the collision world. It'll be sorted into the hierarchy accordingly.
Returns: N/A
| Parameter | Type | Description |
|---|---|---|
| object | ColObject | An object you want to remove from the collision world |
Removes an object from the collision world.
Returns: N/A
| Parameter | Type | Description |
|---|---|---|
| object | ColObject | An object you want to update the position of in the collision world |
Update an object's position in the collision world. Equivalent to removing and re-adding it. You need to call this whenever an object moves, as the way it's stored in the hierarchy may need to change.
Returns: boolean
| Parameter | Type | Description |
|---|---|---|
| object | ColObject | An object you want to check for collisions against the collision world |
Check an object for collision against the collision world. The object does not have to be part of the collision world itself. "Collisions" between an object and itself can never happen.
Returns: Vector3
| Parameter | Type | Description |
|---|---|---|
| object | ColObject | An object you want to do a sphere displacement operation against the world with |
| max_attempts | number | The maximum number of attempts the system will make to push the sphere out of collision with objects; defaults to whatever value was configured in COL_DEFAULT_SPHERE_DISPLACEMENT_ATTEMPTS
|
Perform a sphere displacement operation on the world as a whole. In the event that pushing the sphere out of collision with one shape moves it into collision with another, it'll try to do it again. You can control the maximum number of times it will do this. The default is probably fine most of the time.
The position of the sphere will not be modified. If you want to do anything with the result, you should Set() it to the shape and then update it in the world.
Returns: RaycastHitInformation
| Parameter | Type | Description |
|---|---|---|
| ray | ColRay | The ray you want to cast against the world |
| group | int64 | Optional; the group(s) of collision masks you want to raycast against; defaults to 1 |
| distance | number | Optional; the maximum distance to return results for; defaults to infinity |
Perform a raycast against the collision world. If one or more hits are detected, a RaycastHitInformation struct will be returned containing information on the nearest one. Undefined will be returned otherwise.
Collisions can be filtered by with the group argument in the same way as described in the objects section above.
Raycasts will be infinite by default, but if you only care about results that are nearer than a certain distance you can specify the distance argument.
Returns: array
| Parameter | Type | Description |
|---|---|---|
| frustum | ColCameraFrustum | The camera frustum you want to get the objects contained within |
Used for frustum culling. This is usually used so that you can only render objects that are within view of a camera.
All objects visible to the camera will be included, but some that are outside but close to the boundary may also be. The culling results are imprecise, trading accuracy for speed. Culling is performed on the world hierarchy, rather than individual objects. This means that objects that are in parts of the hierarchy that are partially inside the camera frustum will be included, even if they themselves are not visible to the camera. Frustum culling itself is not the cheapest operation, and in a lot of cases, precise frustum culling is slower than actually just drawing everything.
There may also be duplicates in the last, because for whatever reason the array_unique function on desktop is fiendishly slow. (Whenever that gets fixed I'll change it so that it filters out duplicates.)
Frustum culling only works with quadtrees and octrees. Spatial hashes will return an empty array.