This is pretty easy. You use the power up that replace the character color. Each color, you use each power up. So every time character hit the power up it change to that color. behind the scenes that, you feel it's change to random color, but in fact, it's change to random scenes.
@Machine Rises any chance you could share the secret sauce as to how you achieved the change color of the character? Did you use an Action Animation to replace the Character and set a long duration?