Genre-mash up battle game
The game is called Heroscape. It was primarily fantasy based, but there were some other expansions like a Marvel themed one. The game was discontinued in 2010 but Wizards of the Coast has recently created a Magic: the Gathering board game called Arena of the Planeswalkers that seems to have similar gameplay.