{"id":65,"date":"2008-09-15T15:46:37","date_gmt":"2008-09-15T21:46:37","guid":{"rendered":"http:\/\/blog.blockos.org\/?p=88"},"modified":"2014-09-21T17:08:07","modified_gmt":"2014-09-21T16:08:07","slug":"fireballs-of-fire","status":"publish","type":"post","link":"https:\/\/blog.blockos.org\/?p=65","title":{"rendered":"Fireballs of fire!"},"content":{"rendered":"

EEK! 6 months !<\/p>\n

It’s not that I had nothing to write. On the contrary, I have a lot to post. I just didn’t found the time to write… Erm.. Let’s go with a 7 months old stuff.<\/p>\n

While working on the tracker, I wanted to add some kind of “live” mode. The user could choose which sequence to play, modify it, control volume, add an effect etc… So I came with the idea to associate a command to a key combo.<\/p>\n

Combos are detected by walking down a tree. Each time a button is pressed, we look at the current node and check if one of its children is associated to this button. If that’s the case, this child becomes the new current node. Otherwise there’s no matching combo and we reset the current node to the tree root. If the button pressed didn’t not changed for a certain amount of time (timeout), we check there’s a child corresponding to the current button. This way, we can detect combo containing a sequence like “press A button during t seconds”.<\/p>\n

Let’s look at a simple example.<\/p>\n

\"\"<\/p>\n

Mkit will successively return : DOWN<\/strong> – DOWN+RIGHT<\/strong> – RIGHT<\/strong> – 0<\/strong> (aka nothing) – A<\/strong><\/p>\n

We have 0<\/strong> because when you go from RIGHT<\/strong> to A<\/strong>, there’s a moment when you don’t press any button. And as we check keys every vsync, we necessary get 0<\/strong> (unless if you are Superman on Redbull).<\/p>\n

Consider we want to handle the following combos :<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

The combo tree is very similar to a lexical tree. A node can have 0 to N children but only one parent.
\n\"\"<\/p>\n

The tree is store in level-order with the longest path first. This means that you’ll have to be very careful and store node children by their depth. We have for our example :<\/p>\n

Root – Down – A – Down+Right – Down+Left – Nothing – Left – Right – A – Nothing – Nothing – Leaf – A – B – Leaf – Leaf<\/strong><\/p>\n

In the current implement, the tree is stored in 2 arrays. The first one contains the index to first child of a node. And the second the key for each node.<\/p>\n

combo_tree : 1, 3, 5, 6, 7, 8, 9, 10, 128 | 2, 11, 12, 128 | 0, 128 | 1\r\ncombo_keys: .db 255, JOY_DOWN, JOY_I, JOY_DOWN | JOY_RIGHT, JOY_DOWN | JOY_LEFT\r\n.db 0, JOY_RIGHT, JOY_LEFT, JOY_I, 0, 0, JOY_I, JOY_II<\/pre>\n
The root is always at index 0<\/strong> and we associate the key value 255<\/strong> to it.
\nThe tree traversal algorithm is very simple. For a given node i<\/strong>, we know that its children are at indices j<\/strong> from combo_tree[i]<\/strong> to combo_tree[i+1]-1<\/strong>. And that we can reach them only if the current key is combo_key[j]<\/strong>. If the bit 7<\/strong> of a value in the children list is set, this means that we have a transition a leaf. The remaining bits are used as an index to a jump table.
\nThe traversal looks like this:<\/p>\n
 i \/\/ current node index
\nfor(j=combo_tree[i]; jCOMBO_DEFAULT_DELAY<\/strong> in combo.asm). Note that in current code combo_tree<\/strong>, combo_keys<\/strong> and combo_jumpTable<\/strong> are in RAM. So you’ll have to initialize them before-hand.<\/p>\n