The Collision Engine

If an entity is moved not by displacing it's position, but by the c_move function or by the physics engine, collisions with other entities or level geometry are automatically detected and can cause reactions. Possible reactions are gliding along the obstacle that is handled automatically, or script functions triggered by entity events like event_impact, event_block, event_entity, or event_push. The level must be surrounded by a hollowed sky block for collisions to work.

Several collision methods are built into the engine, which use different collision hulls for the moving object and the obstacle. Moving entities normally use a simple hull - a box or an ellipsoid. Non-moving obstacles like terrain or map entities use a polygon hull in their own shape. Alternatively, a model can use a polygon hull based on its first frame, depending on the state of its POLYGON flag. For physics collision detection there's also the choice between simple hulls - a box, sphere, or cylinder - and a polygon hull through phent_settype. However it is not recommended to collide polygon hulls with each other. This would not only be slow, but can also lead to undesired behavior like 'hooking together' depending on the complexity of the polygonal shape.

The two collision systems

Physics entities move and collide automatically, but non-physics objects must be moved through script collision functions, like c_move. They must not collide with physics objects (but physics objects can collide with non-physics objects). There are two collision systems, a fast one - AABB - that only works with BSP levels, and a slow, but more accurate one - OBB - that works with every level. The collision system can be choosen either through activating USE_AABB mode in any collision function, or by globally disabling the OBB system through resetting the enable_polycollision variable.

 A7   P  The AABB collision system uses Axis Aligned Bounding Boxes for the simple hulls. Axis aligned means that the bounding boxes do not rotate with the entity. This is the fastest collision system, however requires a BSP tree level and only offers two standard hull sizes - FAT and NARROW - for collision of entities with polygons. In A7, BSP trees and the AABB collision system are only supported by the Pro Edition.

The default OBB collision system uses either oriented ellipsoids versus a polygon hull, or oriented bounding boxes versus oriented bounding boxes. It does not require a BSP tree level and can use any box sizes. However it is more CPU intensive than the AABB system.

Obstacle	Model, Sprite	Model (POLYGON)	Terrain, Map, Level
c_trace	Ray Polygon	Ray Polygon	Ray Polygon
c_trace (USE_AABB)	Ray AABB	Ray AABB	Ray Polygon
c_move	OBB OBB	Ellipsoid Polygon	Ellipsoid Polygon
c_move (USE_AABB)	AABB AABB	AABB AABB	AABB Polygon

The size of the collision hull

The size and shape of the bounding ellipsoids or boxes is essential for a proper OBB collision detection. By default, entities get an X/Y symmetrical hull in two standard sizes, depending on their fat and narrow flags. This is best suited for actors in a shooter or RPG to ensure that they fit through doors regardless of their real shape.

NARROW		FAT

The hull can be set to the entities' real size by checking BBox in WED, or by calling c_setminmax, or by manipulating the entities' min_x...max_z bounding box parameters directly and setting fat and narrow simultaneously. This is recommended for any entity that is not an actor. For objects like cars, rockets or torpedoes the best suited shape is a slim elongated hull; for actors it's a hull in the shape of a symmetrical vertical column. Symmetrical is recommended because when an oriented box or ellipsoid rotates, it can otherwise collide with obstacles, even if the entity position does not change. Therefore the c_rotate function must be used for rotating an unsymmetrical entity when it can collide during rotation. If a hull has the same size in X and Y direction however, the entity can change its horizontal angle (pan) directly without caring about c_rotate. For a cubic box or a sphere shaped ellipsoid, c_rotate is not required at all.

Advanced notes on c_trace, c_move and c_rotate

c_trace, c_move and c_rotate replace the A5 functions trace, ent_move and ent_rotate. The A5 functions used only the AABB system, while the new functions can use either the AABB or the OBB system.

The AABB system is very efficient, but requires level preprocessing by the map compiler and is limited when doing entity to entity collisions. The OBB system on the other hand deals with level files and dynamically created entities in a similar manner which makes using them easier. However, it is far more CPU intensive and thus you are advised to avoid unnecessary using it. For example don't do a box trace (USE_BOX) where a ray trace would suffice.

Collision functions

Both c_move and c_rotate internally make use of c_trace by automatically setting USE_BOX and providing additional functionality such as gliding. Therefore anything pertaining to c_trace in these pages also applies to c_move and c_rotate.

c_move and c_trace uses 4 different collision routines:

• Ray against oriented box ,
• Ray against polygons,
• Ellipsoid against polygons,
• Oriented box against oriented box (c_move and c_rotate only).

If USE_BOX is not set, the c_trace collision will always use a ray. If the USE_BOX mode is set, c_trace tests an ellipsoid shape against polygonal targets. The collision shape used by c_move or c_rotate is either an oriented ellipsoid or an oriented box. Which one of these two is used depends on whether the collision is with a polygonal or a nonpolygonal target.

Level collisions are always performed using the ellipsoid. Entity collisions are also performed with the ellipsoid vs. polygon routine, provided that the target entity (the one that is not moving) has the POLYGON flag set, or the USE_POLYGON mode is activated. By default, terrains have POLYGON at on and all other entities have POLYGON set to off.

The reason for using different collision hulls is speed and stability. For entities with a high polygon count using its box will be faster. Entities that move can get entangled when collision is done with the ellipsoid-polygon routine. For this reason, do not use the ellipsoid-polygon routine for collision obstacles that have 'hooks' or 'gaps' where a moving entity could get stuck.

To summarize: when you have static entities with low polygon count set my.POLYGON=on for these entities. When you have entities that move about (enemies, other players in a multiplayer game) or that have a lot of polygons you should set their my.POLYGON flag to off.

Hull size

The ellipsoid or box size can be either set manually or you can use default values. The default values are meant for backwards compatibility and there is no speed or feature difference between using custom or default values.

The default hulls are called NARROW and FAT. NARROW is a sphere with a 16 quant radius around the entity's center. FAT is an ellipsoid with a 32 quant radius along the X and Y and positive Z axis. It only extends 16 units down along the negative Z axis though. You activate a default hull size by setting the appropriate flag to on and the other one to off. All subsequent c_trace/c_move/c_rotate calls will then use the new hull size. Thus to activate the NARROW hull in an entity's action you would write (see images above):

my.narrow=on; my.fat=off;

In in order to use custom hull sizes you have to set both the NARROW and FAT flag to on. Then you will need to adjust the bounding box by setting the min_x, min_y, min_z and max_x, max_y, max_z parameters of the entity. The easiest way to do this is to call c_setminmax (me). When pressing [F11] twice in the engine window, you'll see the bounding boxes of all entities highlighted in blue.

Please note that currently hull size changes can not be performed at the same time that the entity is created ! Thus you should add a wait statement before doing so.

wait(1); c_setminmax(my); 

c_setminmax() uses only the vertex extents of an MDLs first frame. If you want to use extents from a different frame you need to call c_updatehull (my, N) instead. This sets my.min_xyz / max_xyz according to the bounding box at frame number N. The minimum and maximum extents of an entity are calculated upon loading/ ent_creating it, thus c_setminmax can quickly copy these values to my.min_xyz/ max_xyz. While c_setminmax is essentially free (very little time required to update the hull size), c_updatehull can take some time to execute because it needs to reload the vertices of the specified frame. Thus you should not call c_updatehull every single frame but only for major animation changes such as a standing character who now kneels. For the same reason you should not call c_setminmax(my) instead of c_updatehull(my,0) - they both give the same result but c_updatehull will be much slower. If you know your entity's dimensions the fastest way to change the hull size is to set my.min_xyz/ max_xyz directly.

Though you can set the hull to arbitrary dimensions, it is recommended that it be symmetrical whenever possible. When using different radii along the x, y, and z axes c_rotate is more likely to get your player stuck while turning.

With an ellipsoid collision gliding along walls and slopes is a very simple process. In the function call just provide the relative forward motion and for gravity also add the absolute downward velocity. This will allow your character to move about the environment and along slopes efficiently. However, when using stairs or slopes the values need to be tailored to a certain character height and framerate. To prevent an entity from moving up a stair you will have to either reduce its forward momentum or increase the gravity. If on the other hand you want to make an entity climb a particularly high stair you would have to increase its forward velocity or reduce gravity. Given sufficiently large velocities an entity can climb any stair that is up to half its size (assuming that c_setminmax was used to set the ellipsoid to be as tall as the entity).

For these reasons the GameStudio Template Scripts use two c_move calls instead. One to handle gravity, the second to handle the forces acting on the player. This is a more flexible solution that allows for more control but is slower than a single c_move call.

How collision internally works

After initial setups, c_trace and c_move proceed with inspecting entities for potential collisions. If ACTIVATE_TRIGGER is not enabled then the engine can use its binary tree to only check nearby entities. If ACTIVATE_TRIGGER is enabled however, it is necessary to check every entity in the level because the trigger range can be arbitrarily large. Therefore you should only use ACTIVATE_TRIGGER if you have to.

Assuming IGNORE_CONTENT is set then for each of the entities in the tree leaf (or in the whole level when using ACTIVATE_TRIGGER) their type is checked to see if it matches the flags IGNORE_MODELS, IGNORE_WORLD, IGNORE_SPRITES and IGNORE_MAPS. If the entity can be ignored according to these flags, the next entity in line gets checked. Should the entity type be valid, it is then compared with you and me (assuming that IGNORE_ME or IGNORE_YOU is set). Finally the bounding spheres of me and the current entity are checked for overlapping. If all these tests indicate that the entities might collide, then further processing is required.

If IGNORE_CONTENT is not set, a precise collision is done with all nearby passable map and terrain entities, no matter whether IGNORE_MAPS, IGNORE_PASSENT or IGNORE_WORLD is set. At this point in_passable, on_passable and passable_ent are updated to point to the current entity if the trace starting point lies within the entity's axis-aligned bounding box. For terrains the bounding box is assumed to extend all the way down to the bottom of the level. If there is no passable entity at the starting point, but one can be found along the trace line, then passable_ent will be set to this one instead and on_passable gets set as well.

Once all entities have been processed in this way the level blocks get checked. To disable this check IGNORE_WORLD needs to be set.

When this is done a thorough (i.e. slow) test is performed between the requested bounding shapes (ray, polygons, OBB, or ellipsoid). All intersections are stored and sorted by distance from the trace origin. At this point contacts with pushable and passable entities are discarded. The closest hit (if any) is returned.

Gliding and rotating

Movement and rotation is achieved internally by calling c_trace with USE_BOX set.

In case of a collision while the GLIDE flag is set, GameStudio will calculate a reflection vector based on travel direction and contact normal. A second trace is then performed along this reflection vector. If this results in another collision then a new reflection vector is calculated, etc. After a maximum of 3 collisions c_move gives up.

Gliding can be restricted to the XY plane by setting disable_z_glide to 1. By default the ellipsoid can move up any slope, no matter how steep it is. To restrict this motion you can alter the global variable move_min_z. If the contact normal's Z axis is less than this minimum value no gliding along Z will take place at all. Hitting the ground plane will result in a normal.z value of 1.0 (pointing straight up). Hitting the ceiling will yield -1.0 (straight down) and a head on collision with a perpendicular wall will have a normal.z value of 0. The default value of move_min_z is -1 which allows gliding at all angles. If you were to set it to 0.5 instead all slopes steeper than 60 degrees (=acos[0.5]) would cause the entity to stop and not glide up. This example is valid only for a spherical hull. For an ellipsoid some trial and error is required to find the right value. Rather than relying on move_min_zit is recommended that you place invisible entities in front of steep walls to block them off.

c_rotate first attempts an in-place rotation by setting the desired angles. If this results in a collision then a glide vector similar to the one above is calculated and c_move is called to push the entity a certain distance away from the wall. Again a rotation is attempted. Should this one succeed then the entity is moved back towards its starting point. Otherwise another reflection is calculated and c_move gets called. In a worst case scenario c_rotate calls c_trace 5 times and c_move 4 times before giving up and returning the player to its starting position/orientation. Keeping entity hulls mostly symmetrical and avoiding V-shaped level geometry is essential to increasing the performance of c_rotate.