Looking through some arcade stuff for a review I stumbled onto Data East,s Caveman Ninja game.
But I remember it on the Sega Genesis as Joe & Mac. As best I can tell they are pretty much the same accept the arcade version is more polished.
Do you remember the original or the home ports of this game. (Reminds me of Toki)
http://www.youtube.com/watch?v=Tf6TMsmcNm4