This is a Turn Based Strategy game, where you battle another player on a 2D landscape.
Hedgewars is available in the GetDeb repository
Hedgewars 0.9.3 and 0.9.6
The graphics in this game are very cartoony which fits in well with this genre. It's not a First Person Shooter with realistic physics simulation: it's hedgehog wars. The images are surprisingly high quality and a lot of work must have been put into them.
As of writing this there is no story or unlockables that make a game "completable", you just set your team against the computer or another human and use your skills to (try to) win. The beauty of this is that unlike other games where you get better weapons as you progress, it's all based on how well you can play.
Multiplayer is this games biggest advantage; you'll get bored after playing against the simple AI computer. You can choose between 3 modes for this: Local (on the same computer), LAN (on your home network), and Internet.
The internet server is never empty so you'll always have someone to play and you can choose to go to the Beginners or Experts rooms depending on your level. I never play single player anymore as multiplayer is so much better (my username is turtle153 if you see me around).
My favourite game on Ubuntu - great for passing the hours on a rainy day or the 5 minutes before dinner. Make sure you have a decent internet connection however, if you want the full potential of Hedgewars.