There I was, standing at the back of the line for the Nintendo area at the EB Games Expo in Australia. I knew I'd be in line for a good thirty minutes or so, but it didn't matter: this was Nintendo. I knew (hoped) that I wouldn't be disappointed once I finally got in. Yeah, I got to play some Wii U and some Super Mario Bros Wii U, but, honestly, compared to playing Paper Mario: Sticker Star, all that was nothing. When I first saw it was available to be played, I'm pretty sure my jumps of joy freaked out a couple of guys standing next to me. Even better, the game lived up to my high expectations.

Though the demo may have been limited in scope, it was still pretty lengthy compared to other games on display at the show. Also, unlike many other demos, Sticker Star began at the, uh, beginning. The story unfolded (pun intended) in typical Mario fashion: Bowser sets out on a rampage, Toads are terrorised, etc. etc. throw in some stickers and magical items to recover and you have a pretty good idea what Sticker Star is about. The dialogue, as you'd expect, is both well-written and rather funny.

Once the game started in earnest, I had a chance to explore the first town of the game: Decalberg. The beautifully detailed and brightly-coloured town was a joy to explore. Though perhaps not as large as towns from past Paper Mario games, there was still shopping to do, houses to enter, Toads to speak to and plenty of secrets to uncover. The graphics are stunning in their bright, cartoony style, and the 3D effects draw you into the world. Similar to Super Mario 3D Land, the 3D is often helpful in navigating certain jumps too.

After sorting out a few things, it was time to set out on the adventure. Unlike past Paper Mario games, Sticker Star introduces a world map. It's laid out a lot like maps from past 2D Mario platformers such as Super Mario World, and individual locations are even named W1-1, 1-2 and so on. Don't be fooled though, this game is nothing like Super Paper Mario on Wii. Each location houses large areas on a 3-dimensional plane to explore, just like the N64 and GameCube entries in the series. There are enemies to fight, coin blocks to whack, secret areas to locate and items to pick up. The demo only allowed me to explore the grassy hill locations, but from the world map I could also see a desert and a spooky forest. No doubt there are plenty of other interesting locations out there too.

So, let's talk about the stickers! I, along with many others, was a little concerned about how they would work as commands in battle. No longer do you have default actions to use such as hammer or jump, but, instead, the stickers in your possession dictate the abilities you have. It's sort of like using items for everything. My initial worry was what would happen if you ran out of stickers? After playing the game, it quickly became clear this wouldn't happen. Stickers are liberally spread throughout every single environment and even respawn when you leave and return. Even after the short demo, I had multiple pages of stickers to spare.

In battle, choosing a sticker is as simple as tapping one from your collection on the touch screen. Even early in the game there was a good variety, including hammer, jump, recovery mushroom, and even some new ones such as the shiny hammer, which deals extra damage, and a multi-bounce jump, which, with proper timing, allows you to continue jumping on an enemy indefinitely. As you may have already heard, there are no partners in Sticker Star, so Mario is on his own in battle.

As I continued to play the demo, Mario and Kersti (a helpful crown-shaped sticker) were delayed in their journey as Bowser Jr. arrived and literally tore a bridge out of the page and crumpled it up. Well, after we beat him, that is. Calling on the help of some trusty Toads, Mario managed to recover the bridge paper. I then got to place it back across the river by lining it up and using a very flat Mario to paste it down properly. A little further along we recovered the first of the Comet Stars, and that was pretty much the end of the demo.

So, am I excited about Paper Mario: Sticker Star? Absolutely. It may be missing some elements that made past games in the series great such as leveling up and partners, but the new sticker mechanics are incredibly clever in their execution and the overall feel of the game is one of tremendous fun. This is definitely a game to keep your eye on over the next month.