Collision Rework

DCurrent

Site Owner, OpenBOR Project Leader
Staff member
Plombo

I'd like to get your opinion on a pretty drastic internal change I'm thinking about.

I've been working on cleaning up the collision logic, and more and more I'm thinking the collision types need unifying. I don't mean as in make one super box, but instead to add a layer of abstraction.

Current Method

Code:
s_collision_attack_list (one) -- (many) s_collision_attack
					- s_coords	* coords
					- int		index
					- int		tag
					- ...

s_collision_body_list (one) -- (many) s_collision_body
					- s_coords 	* coords
					- int		index
					- int		tag
					- ...

s_coords * attack_coords = {entity}->animation->collision_attack[{frame}]->instance[{instance}]->coords;
s_coords * body_coords = {entity}->animation->collision_body[{frame}]->instance[{instance}]->coords;

There's also a third collision set at the moment, but we won't get into that. The thing you'll notice is that coords all use the same structure across the board, but because coords are a property of attack and body respectively, they are part of separate parent pointers on an entity and have to be handled as such. In turn, this means the collision logic starts to get redundant real quick.

Here's how we find collisions now:

[list type=decimal]
[*]Loop through each entity as a possible target.
[*]Loop through all of SELF attack boxes at current animation frame.
[*]
[list type=decimal]
[*]Loop through all body boxes for current TARGET, calculate absolute coordinates for body/attack, and compare for a collision.
[*]If SELF attack has counter property (or upcoming clash property), we loop through all attack boxes for current TARGET'S's animation frame, calculate absolute coordinates for body/attack, and compare for a collision.
[/list]

[/list]

Possibly two nested loops, and a LOT of redundant code.

Proposed Change

Code:
s_collision_list (one) -- (many) s_collision
					- e_collision_type	type (bitwise flags)	
					- s_coords 		* coords
					- int			index
					- int			tag
					- s_attack		* attack (old attack properties)
					- s_body		* body (old body properties)

s_coords * <any type>_coords = {entity}->animation->collision[{frame}]->instance[{instance}]->coords;

  • We'll avoid wasting memory by simply not allocating properties that aren't needed (i.e. if it's just a body box, don't allocate memory for attack properties). Obviously several properties between the collision types could be consolidate, so there actually should be a net memory savings.
  • Entity has a single array pointer for all collisions replacing the current array pointers for attack, body, and space.
  • The type property will tell us if this is a space box, a body box, attack box, or whatever else. We'll use bitwise logic so its possible to be more than one type.

Now the collision logic looks like this:

[list type=decimal]
[*]Loop through each entity as a possible target.
[*]Loop through all of SELF collision boxes at current animation frame.
[*]
[list type=decimal]
[*]If SELF collision box is an attack, loop through all collision boxes for current TARGET, calculate absolute coordinates for body/attack, and compare for a collision.
[*]If the opposing box is an attack, then verify SELF attack can clash or counter. Otherwise ignore it.
[/list]

[/list]

I think this logic will be slightly faster overall, and it will certainly eliminate a lot of redundant code. It should also be easier to deal with when using script access, and IMO much more extensible.

Other than the code work (which is on me), do you see any major pratfalls to this approach?
 
The collision code breaks the x64 build on android hopefully this rework can fix the issue.
 
I've never understood the collision code very well, but I don't see any obvious issues with your proposed rework.
 
Damon Caskey

If you are going to do this can you help me with something.  Can you make a private build that logs each step of the collision into the logs so i can pin point where the code breaks on the android build please.
 
I will once I'm done with the rework. I'm a little too busy to put a bunch of log traces in the current system and it's getting thrown out soon anyway.

DC
 
I made some encouraging progress on this. I've already built the new structures, and more importantly, dynamically allocating them on request.

Previously I'd set it up where the author predefined a global number of collisions per frame, and then you identified them by 0 index. So if you wanted two boxes per frame, you set a maximum of 2, and then you could use attack/body 0 and 1. Main issue is it meant every model in the game had the global maximum collision boxes per frame in memory whether or not you used them.

The way it will work now is the author just defines however many collision boxes they want on a per frame basis, and assign any numeric index they like. Engine will handle the rest. It's a major PITA to code, but is obviously a lot more convenient for authors, and also saves a ton of resources compared to the old setup since now only frames you actually give extra collision boxes have them in memory.

Still not done, but getting there. Only the allocation code is in place, but thankfully the detection code (i.e the actual collision checks) won't need a rewrite. I already finished up refactoring that portion last week and it's an easy import from the old system. The real bear is refactoring the text interpreter to accept indexed box commands from authors...

DC
 
Sounds good i also noticed a few posts around the forum where your mentioning variouse memory saving codes i cant wait to test the final product against the old to see how much more efficent we are running.

I am also hoping this rework does not break the android 64 bit port but if it does can you work with me to resolve any issues.
 
Yikes - I had no idea how right I was about the text interpreter portion. The only reasonably workable way I could figure to do it is with a linked list. So I may as well make the entire collision system a linked list.

I've refactored the new collision system as a linked list, and thus far it allocates and loops successfully. Still don't have the write in working, but unlike before I have a rough idea how I'll do it.

Basically, I'm going to add nodes to a linked list as attack, body, or spaces lines are encountered. The input will be sent to a function that looks at current index (or 0 if none provided), and looks for a match (index and collision type) in the list.

  • If there's no list at all yet, we create one, and apply data to the head node.
  • If there's no match, we build a new node, then apply data.
  • If there is a match, we apply the data.

When we reach end of text and call add frame, we send it a pointer to the list head. The add frame function will loop through the list, and make a new copy of it. The new frame's collision property is populated with head node of copied list. The old list is deleted, and we move on to the next read loop.

DC
 
Thank you msmalik681.

Here's some encouraging progress, albeit a bit sidetracking. The addframe() function that takes data compiled from a text file and allocates frame properties to an animation accordingly is now much cleaner. Previously it had 18 parameters! Now granted, my collision rework would have removed 6 of them anyway, but I'm a firm believer if a function has more than 3 parameters you're probably doing something wrong.

More to the point it just makes testing an unbelievable pain because it's so hard to know what parameter does what - you have to go back, check, and recheck you aren't putting something in the wrong spot. So you're never sure if the new code doesn't work right, or it's just a wayward argument.

To fix it, I've applied the injected dependency model from my PHP work. Basically you take all the parameters, package them up into a class, define an object from the class, and send that to the function as a single argument. It's worth the extra steps because you abstracted all that data into one unit. Now its much easier to see where you are sending your arguments, the order you apply them doesn't matter, and it grows much more gracefully if you need to add parameters in the future. Of course C doesn't have classes (one of the many reasons I wish OpenBOR would compile in C++), but structures are a reasonable substitute.

Have a look:

Old addframe() definition and call:

Code:
int                     addframe(s_anim             *a,
                                int                 spriteindex,
                                int                 framecount,
                                int                 delay,
                                unsigned            idle,
                                s_collision_entity  *ebox,
                                s_collision_body    *bbox,
                                s_collision_attack  *attack,
                                s_move              *move,
                                float               *platform,
                                int                 frameshadow,
                                int                 *shadow_coords,
                                int                 soundtoplay,
                                s_drawmethod        *drawmethod,
                                s_axis_plane_vertical_int         *offset,
                                s_damage_recursive  *recursive,
                                s_hitbox            *attack_coords,
                                s_hitbox            *body_coords,
                                s_hitbox            *entity_coords);

// Call in loadcachedmodel() function.
curframe = addframe(newanim, index, framecount, delay, idle,
                                    &ebox_con, &bbox_con, &attack, &move, platform_con,
                                    frameshadow, shadow_coords, soundtoplay,
                                    &dm, &offset, &recursive, &attack_coords,
                                    &body_coords, &entity_coords);


New addframe() definition and call:
Code:
typedef struct {
    s_anim*                     animation;      // Animation we will add frame to.
    int                         spriteindex;    // Image displayed during frame.
    int                         framecount;     // Number of frames.
    int                         delay;          // Frame duration (centiseonds)
    unsigned                    idle;           // TRUE = Set idle status during frame.
    s_collision_entity*         ebox;           // "Entity" box added by WD. To be removed.
    s_hitbox*                   entity_coords;  // Coordinates for "Entity" box. To be removed.
    s_collision_body*           bbox;           // Legacy body box parameters.
    s_hitbox*                   body_coords;    // Coordinates for legacy body box.
    s_collision_attack*         attack;         // Legacy attack box.
    s_hitbox*                   attack_coords;  // Coordinates for legacy attack box.
    s_damage_recursive*         recursive;      // Recursive damage properties for attack.
    s_move*                     move;           // Move <n> pixels on frame.
    float*                      platform;       // Platform coordinates.
    int                         frameshadow;    // TRUE = Display shadow during frame.
    int*                        shadow_coords;  // Shadow position.
    int                         soundtoplay;    // Sound index played on frame.
    s_drawmethod*               drawmethod;     // Drawmethod to apply on frame.
    s_axis_plane_vertical_int*  offset;         // X & Y offset coordinates.    
    s_collision*                collision;      // Head node of collision list for frame.
} s_addframe_data;

int addframe(s_addframe_data* data);

// Call in loadcachedmodel() function.
curframe = addframe(&add_frame_data);

I've already implemented and tested. The collision rework should be a lot easier going now, and I'll probably do this to other out of control parameter lists I run into. I'm curious what your thoughts are Plombo.

DC
 
Just got a working test case. I'm now able to read a collision property from text and push it to frame. Above I said I would build a list in the read in function, and populate it with read in data. Then I'd build a second list in the addframe() function, copy date to it from the read-in function list, and delete the read-in list to be fresh for next frame.

Had a duh moment and realized I didn't need to over-complicate it like that. Now all I do is take the head pointer of read in list and drop it into the frame's collision property...done! The frame is ready to go. Then I reset the local variable in read in function that held the pointer to head node. That means the node append functions will start up a new list for the next frame that has a collision request, and cycle continues.

Tested with guard cost, and it's looking good. Three attack boxes allocated to one frame, each with a unique guardcost property.

Code:
-- append_collision --

	 head: 00000000

	 new_node: 0F48E698

	 last: 00000000

	 new_node->next: 00000000

		 head == NULL

		 head: 0F48E698

 -- append_collision --

	 head: 0F48E698

	 new_node: 0F48E9B8

	 last: 0F48E698

	 new_node->next: 00000000

	 last->next: 0F48E9B8

	 new_node: 0F48E9B8

 -- append_collision --

	 head: 0F48E698

	 new_node: 0F48E990

	 last: 0F48E698

	 new_node->next: 00000000

		 last->next: 0F48E9B8

		 last: 0F48E9B8

	 last->next: 0F48E990

	 new_node: 0F48E990

--- addframe() ---

	 allocated data->animation->collision_list - 5 frames, 20 bytes.

		 temp_collision: 0F48E698

	 Frame: 1

		 temp_collision[0F48E698]->index: 0
			 temp_collision->attack: 0F78AD60
			 ...->guardcost: 27
		 temp_collision (next): 0F48E9B8

		 temp_collision[0F48E9B8]->index: 1
			 temp_collision->attack: 0F78AC20
			 ...->guardcost: 28
		 temp_collision (next): 0F48E990

		 temp_collision[0F48E990]->index: 2
			 temp_collision->attack: 0F78AE00
			 ...->guardcost: 29
		 temp_collision (next): 00000000

Next step is to clean up the code, implement it to for all collision commands, and begin testing the new system in collision detect functions.

DC
 
O Ilusionista said:
Wow. Why so many parameters?

O Ilusionista, that function is what builds the animation frame data. The function loadcachedmodel() interprets the model text files line by line, reading the data and preparing it for insert. When all of that is ready and its time to build the frame, addframe() runs. It allocates and populates the arrays that comprise a "frame" (remember how I explained that frames don't really exist - there's just certain animation properties that are arrayed and when taken as a whole act as one frame).

Anyway, there obviously a LOT of frame properties. Many more than 18. Some of them are were already grouped together in structures of properties (like attack and its 15 billion sub properties), but many others were just passed individually. There's not much to do about the sheer amount of data. It has to get into a frame somehow, and in this case it's better to handle that with a single function call. I will probably break the function down into smaller pieces later, but already existing addframe() will still act as a "master". Either way, it has to take all that data to work.

That's why I packaged it up into a structure. Now the addframe() function has 1 parameter. That master parameter points to a data structure that contains all the other parameters. So what we do now is populate the data structure, send its pointer as an argument to addframe(), and then addframe() draws from the data structure members as it needs. It's an extra step, but makes the code a lot more manageable.

DC
 
Testing fault tolerance and so far, so good.

It's a common mistake to include the same attack property more than once in a frame, and with multiple collision box support I dare say that will happen even more often. So it's important the system can catch this and deal with it accordingly.

Test case:

Three attack.block.cost properties on the same frame. The first has no index specified, so it should default to 0. The second specifies an index of 0, meaning it should affect the same collision box as the first. The third specifies an index of 1, so it should result in allocating a separate collision box.

Results:

[list type=decimal]
[*]The first block cost reads with a value of 27. Since no index is given, the engine defaults to index 0. Search is conducted for a collision node of the same type (attack vs. body or space), and index. There is no defined at all yet for this frame, so a new list is allocated, and its head node is populated with block cost value.
[*]The second block cost reads with a value of 28. An index of 0 is provided, which happens to be the same index as first block cost. Search is conducted, and a node matching the index is found. Its value is overwritten with the new value of 28. This is identical to previous engine behavior where "last read wins".
[*]Third block cost call reads with a value of 29. An index of 1 is provided. Search is conducted, and no matched index is found. New node is allocated to the collision list, and its value is populated. The frame now has two collision boxes, with an index of 0 and 1 respectively.
[/list]

Model text:
Code:
attack.block.cost 27

collision.index 0
attack.block.cost 28

collision.index 1
attack.block.cost 29

Log:
Code:
-- find_collision_index(00000000, 1, 0) --

	 (pre loop) current: 00000000

	 No match

 -- append_collision --

	 head: 00000000

	 new_node: 115414D8

	 last: 00000000

	 new_node->next: 00000000

		 head == NULL

		 head: 115414D8

 -- find_collision_index(115414D8, 1, 0) --

	 (pre loop) current: 115414D8

		 current: 115414D8

		 current->index: 0

		 current->type: 1

			 Found: 115414D8

 -- find_collision_index(115414D8, 1, 1) --

	 (pre loop) current: 115414D8

		 current: 115414D8

		 current->index: 0

		 current->type: 1

	 No match

 -- append_collision --

	 head: 115414D8

	 new_node: 115416B8

	 last: 115414D8

	 new_node->next: 00000000

	 last->next: 115416B8

	 new_node: 115416B8

-- addframe --

	 allocated data->animation->collision_list - 5 frames, 20 bytes.
		 temp_collision: 115414D8

	 Frame: 1
		 temp_collision[115414D8]->index: 0
			 temp_collision->attack: 1139CDC8
			 ...->guardcost: 28
		 temp_collision (next): 115416B8

		 temp_collision[115416B8]->index: 1
			 temp_collision->attack: 1139D228
			 ...->guardcost: 29
		 temp_collision (next): 00000000
 
sounds super confusing but it looks like you really know what your doing with all the testing please keep us updated as you progress.
 
msmalik681 said:
sounds super confusing but it looks like you really know what your doing with all the testing please keep us updated as you progress.

lol, sorry msmalik681, some of this is really just me thinking out loud. What the last post was about is making sure that multiple collision boxes are created when the author wants them, but are NOT created when they don't. It all comes down to index and type (collision type, not attack type).

When building your models, you specify the index you want (collision.index <int>). All subsequent attack/body/space box commands use that index until the next frame or you specify a different one. If an attack/body/space with that index doesn't already exist on the frame, the engine creates one. What this means is you can have as many attack/body/space boxes as you want, and you can use index you like - they don't even have to be in order or make any numeric sense. You could have a box of 0, and a second one of 28. As long as it's an integer, it will work.

If you never specify any index, the engine just assumes 0, and only one box of a given type is created - the same as things are now.

DC
 
Some big news - the new collision system now reads from model text and parses to the entity frames. Good gravy that was an undertaking. Right now it's running concurrently with the old collision system. The old system is still handling the actual collisions, but the when you turn on debugging, it displays the new system.

Here's Ryu showing off three attack boxes on his jab.

Collisions_0.png


There's still plenty more to do. Body boxes are still using dummy values - only attacks are read in fully. There's also a bug where one of the attacks always stays active till the end of an animation. Once those are resolved, I can begin to implement the new system fully and remove the old the collision boxes from source code.

DC

 
Back
Top Bottom