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:
- 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.
- Points. Points are the simplest collision model, and are used when moving peds and objects through the world.
- 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).
- 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:
- sideofline(), for calculating what side of a 2D line a point is on (and returning the distance from the line in the process)
- car_intersect(), which calculates whether the two given cars (actually rotated rectangles) intersect. Note that it only checks whether the corners of each car lie within the edges of the other; so if the cars are too far interpenetrated then it may not be detected.
- cylinder_intersect(), which calculates whether the two given cylinders intersect
- cylinder_car_intersect(), which calculates whether the given cylinder and car intersect. Note that it actually treats the cylinder as a box, with the same rotation as the car.
- car_box_intersect(), a for checking whether the given car intersects an unrotated box of infinite height (Faster than calling car_intersect()). Note that it also suffers from the same problem as car_intersect(), in that it only checks if each point is inside the edges of the other object.
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!