Collision detection

Collision detection is undoubtedly an important part of the game. Broadly speaking, there are a combinatino of 16 types of collision that can occur, between the 4 different object types (the map, peds, cars, and objects).

Collision models

There are only 4 collision models in use:

  1. The map. This is the most complex collision model, and requires the most complex collision code. As far as implementation is concerned, the map is made up a series of cubes (or cubes with sloping tops), aka blocks, and thus the collidable elements for the map is the block structure.
  2. Points. Points are the simplest collision model, and are used when moving peds and objects through the world.
  3. Cylinders. Cylinders are used to model peds and objects (whether large like bollards and meats or small like bullets). Although they have varying radii, the heights of the cylinders are fixed at compile-time (PED_HEIGHT and OBJECT_HEIGHT, respectively).
  4. Cars. These are rotating rectangles, of fixed height (CAR_HEIGHT).

Collision types

Just as there are varying collision models, there are varying collison types supported. This allows the collision system to provide a more specialised list of objects within the collision box, rather than a raw list of all objects. For example, when moving an entity, you will only want the collision code to return a list of solid objects that are in the way, so you use the CFILTER_SOLID flag. However when moving a bullet, you want objects which are solid or can take bullet damage, so you use CFILTER_SOLID+CFILTER_BD.

Checking for collisions

The collision code uses the colllist linked-list structure to return lists of objects to the caller. The objects in the returned list will have matched one or more of the collision filter flags (see above), and will have their bounding box interpenetrating the bounding box passed to the collision handler. There are only two functions that return collision lists; these are get_stuff_in_cylinder() and get_stuff_in_car(), used for cylinders and cars (or other rotated rectangles) respectively. The functions also take an 'ignore' parameter, which allows one object (typically the caller) to be ignored during collision checks. These collision codes make use of the loclist structure to ensure the minimal number of objects are checked for collision (Although, this does place an upper limit on the size of objects which can be reliably collided).

The collision code also allows access to some of the low-level collision detection functions:

A couple of functions are also available for manipulating collision lists - colllist_kill() to destroy a list, colllist_refilter() to produce a second list from a first, that only contains objects matching certain flags, and colllist_prune(colllist *a,colllist *b) that removes all items from a that are also in b.

bbox collider

The bbox collider in bbox.c is a more generic collider for checking for collisions between two quadrilaterals. This is the collider used by car_intersect(), thus it suffers from the same problem of not detecting overlapping objects which have all their corners on the exterior.

bbox.c also contains the bbox_worldintersect() function, that checks whether a bbox at a specific height intersects any solid piece of the world map. More specifically, it finds the highest point underneath the bbox (or above it if it intersects the floor). This function is used for car movement, and is more accurate than other colliders since it reuses polyon clippping code from WOUM to find all instances of interpenetration between the rotated bbox and the unrotated world geometry. However it currently lacks the ability to detect collisions with thin walls between blocks.

TODO:
MUST-CODE: UNKNOWN: Improve bbox collider to cope with thin walls
CODE: MED: Proper collision reactions - resulting velocities, impact damage, damage deltas
CODE: MED: Play with car-ped collision strength
MUST-CODE: MED: BLOCK_WALL_NORTH/BLOCK_WALL_EAST collision detection for ped/car/obj movement
MUST-CODE: QUICK: Fix standing inside cars! This happens whether the ped is moving or not, so we need to detect that he's inside it and force him to jump/bump out the way. Sensible thing to do would be to do it in the car move func (since ped movement will cause the ped to jump out? If not, fix it!). When getting the list of objects the car is stuck inside, do a check to see if any standing peds are found, and if so bump them to be ontop of the car (or under?)
DOCS: UNKNOWN: Add some extra carjacking flags to collision.h? empty drivers seat, empty passenger seat, is occupied, etc.
DOCS: UNKNOWN: Find permanent solution to ignoring owners of objects (bullets, train carriages, etc.) when doing collision stuff (builtin to the objects, instead of passed as parameter to collision func?)
MUST-CODE: MED: Fix collision_getline() for cars to (a) work and (b) not be an ugly hack - the only way to fix it is to include the source coordinate as well as the destination?
???
Profit!