- Simplest game ever is a number guessing game. Obviously solvable by binary search on the player side. It's like an exciting counterpart for Fibonacci for learning PL flow-control structures. Additional features: limit number of guesses, make players guess floats instead of just ints. Latter will obviously teach you about FP handling in your language of choice.
- Next up, make that two dimensional, so the player is now guessing coordinates instead of numbers. Needs more math, you will definitely implement the distance formula. You can add a backstory if you like (are you bombing enemies in stealth perhaps?) and add mechanics based on that backstory.
- For something more complex---and I think this is your level now---people might suggest a constrained DF/Rogue-like. But me, that always grows more complex than a pedagogical device when I do it. So I stick to boring text games, sometimes inspired by game shows. Quizmaster-types (ala Who Wants to be a Millionaire), hangman-types (ala Wheel of Fortune), would force you to create structures for abstraction, all staying within complexity budget.
Happy hacking!