Retrocomputing Stack Exchange is a question and answer site for vintage-computer hobbyists interested in restoring, preserving, and using the classic computer and gaming systems of yesteryear. It only takes a minute to sign up.
Sign up to join this community
The famous Konami cheat code is the sequence
up, up, down, down, left, right, left, right, B, A
What original algorithm was used to detect that the code was entered? I can think of two possible ways:
Keep an array of the last button presses. When a new button is pressed, add it to the array and check for a matching sequence.
Use a finite state machine. When a new button is pressed, determine the next state based on the current state and which button was just pressed.
Of course, there are many ways in which this could be implemented. So the question is most interesting if we consider the earliest usage for Gradius on the NES. For an 8-bit console like the NES, the programmer would take into account both execution and space efficiency.
The algorithm is trivially implemented using only two bytes of RAM and some simple bitwise shift and OR operations. This would seem appropriately efficient for the NES.
The NES has 4 directions so Up, Down, Left, and Right are each represented by 2 bits. This means the the full sequence corresponding to UUDDLRLR can be stored in two bytes. So in the ROM we have the value for that sequence and we need to OCCASIONALLY compare that known sequence with the last 8 directional inputs to see if it matches. The last 8 inputs would be stored in the 2 bytes of RAM, using shift and OR to remove the oldest and add the newest each time there is a new input. It's basically a 16 bit array, and we are adding the newest 2-bits at one end while removing the oldest 2-bits at the other end using our shift + OR operations.
The comparison between the last 8 inputs and the secret code in ROM is only required when the user presses "A" after having pressed "B". This is best described as a really simple Finite State Machine having only two states.
So when you activate the 'Check' state, you just need to compare the two bytes representing the last 8 direction inputs with the secret ROM code for UUDDLRLR. If it matches, then the code checks and you grant the cheat/reward.
There is only a little additional logic for resetting directional input buffer to $0000 after an A input, and for toggling whether State 'B' is active or not. You might use an additional single-byte variable for that, or you might save memory space by using some branching.
All said, it can be done this way with little execution overhead and very little RAM, which is good for the NES. And you were on the right track, but I think the solution is really a combination of a simple array for the directions and a simple FSM for the A/B buttons.
