Leveling as a progression systems
Although leveling is almost a synonym of RPG, in that I say RPG and you imagine levels – and this has its roots in table top, pen and paper, RPGs and war games – as game designer, you should be thinking of progression systems.
RPG is a label, used to classify games, you do not have to be limited to it (unless you are submitting to a game development competition or something like that).
First of all, experience and levels are means to simulate characters getting stronger. You need to decide on theme of your game. On its "fantasy". Often, we have power fantasy, then getting stronger is part of the theme, and then leveling is a core mechanic. However, that might not be the case for a given particular game.
A vanilla leveling system has a couple distinctive characteristics when it comes to progression systems:
- They are linear. You earn level 1, then level 2, and so on.
- They are not locked to an area or boss.
Your variation is still leveling, still linear. Except, the player has to figure out what exactly to do for each level. You are removing to option to decide where to go for leveling.
I suppose, in that case, it make sense to allow to get them out of order. However, then, it also makes sense to scale them, so that whatever the player chooses to do first, is the easier, and whetever the player chooses to do later is harder.
By the way, one motivation for a grindy game, is to extends game play time, and that is a selling point. In the case MMOs it is also so that it allows time to create more content. Although, sometimes an RPG is grindy because the quests are not great.
Other progression systems
You can, of course, mix and match progressions systems. Give them flavor. In fact, it is very easy to use levels to unlock progression mechanics instead of simply having curves for the different stats as a function of the level.
For example, some RPGs grants you points to allocate upon level up. Some will grant particular abilities at certain levels, some even make you choose between abilities. There could also be items that directly affect stats or straight up grant a level up, etc…
Addendum: I also want to mention that some games level up abilities or weapons instead of characters.
Now, take, for example, games such as Metroid or Zelda, where the player will find items that increment their stats (more missiles, more hit points, etc…) or grant new abilities (often in the form of unique items). They are not labeled as levels, however they are a valid progression system.
Pay particular attention to abilities, because they are not just numbers. In particular if used as they are in Metroid and Zelda games, where they allow access to new areas.
Upgrades are not inherently linear, it is possible to allow the player to acquire – at least some – of these upgrades out of order. However, they are tied to a location.
Note: Using procedural generation to place upgrades in the game world is viable.
I also would like to mention card collecting games, where getting more and rarer cards is the progression system.
Progression does not have to be in-game. If the game is heavily skill based, then the progression is just the players improving their skill. There is also knowledge as progression, that is, the progression is figuring out what to do.
The scaling problem
Let us consider scaling. If we have a character that gains experience by defeating enemies… this experience becomes levels… but the enemies scale with the level of the character… then the character might not feel stronger. The character would be becoming stronger and the enemies too, at the same rate. So, why would you do that? Instead you do not scale the enemies… the result is that after a while they are not a challenge but a chore.
Scaling enemies with level is something that should be used sparingly. In particular, it makes sense for bosses and unique enemies, but not for the fodder enemies.
When enemies are becoming too weak for the player, you want to encourage them to go to a new area where enemies are stronger. This is usually done with a quest to go the new area. Also, enemies could give less experience the higher level the character is, making it inefficient for leveling to stay in the same place.
Addendum: To be honest, the loop of enter new area, then do quests for the area, then quests move you to new area, can be boring. I no longer find it appealing. Not only it is repetitive, but also, it is hand-holding. Plus, it can lead to towns that do not feel alive. This is not about leveling, so I'll leave it at that.
On quest design
What you suggest is not entirely unprecedented. There have been games that tie a progression system to something similar to your mini-quests. Think achievements, which grant titles, which have status bonuses. So, you kill a blue wolf and you gain the title blue wolf slayer, which grants extra damage… or something like that. We have seen this in games. It is a progression system. Just, not as a leveling mechanic.
We need to think about the ways the player can interact with the world. If the answer is going (to new areas) and killing (enemies). Well, you are going to gain experience by killing stuff (and perhaps entering new areas). Guess what player will be doing 99% of the time. Don’t get me wrong, it can be very engaging if the mechanics have intrinsic rewards (people enjoy killing enemies, so that killing enemies is the motivation, not the means for something else).
You do not need to grant experience from killing enemies (you can, you do not have to). In fact, quests could be the sole source of experience. And the fact that they are finite works well with a level cap. There could be, of course, quest that can be repeated. Then people would not be grinding for levels, but questing... your job is then to make those quests interesting.
There are four common kinds of interactions we find in RPGs: “go”, “talk”, “take” and “kill”, these give you some variety in quest design (being “go to area w and kill x and from them take y amount of z and talk to me” very prominent)… but, yeah, that is what they all do, isn't it?
It becomes boring because it does not deviate much from the same formula. In fact, deviating too much is a risk. For example escort missions are often not very engaging, despite the addition of a quest mechanic which technically mean variety.
Ideally you have a greater variety of quest types, but not by convoluted quest mechanics, but by more kinds of interactions. In fact, quests that have more than one way to complete them are often more appealing. However, consider it in the context of the theme of the game. Failure in executing these quests one way could results in the player falling back to a different way to approach them. I'll suggest old Fallout games and Hitman for inspiration.
Having more kinds of interactions makes a huge difference. See for example Pokémon. You can “kill” or you can “capture” the enemies. You build the game on top on that, and you get something that feels very different to the traditional RPGs. And probably gets labeled as a Pokémon clone.
There are other things that you can include in your quest design for extra variety. For example, “craft” and “build” are kinds of interactions that have earned their place in gaming. Building your game on top of these will lead to something like Minecraft, or Factorio.
I would also suggest to separate “talk” and “give”. And also, depending on the game, stuff like “steal”, “persuade”, “hack”… which are great for alternative ways to complete quests.
By the way, each one of these kinds of interactions could have their own progression system associated with them. For example, traversing progression could be mounts, or unlocking fast travel points.