4x is a pretty badly defined genre.
JarlFrank came up with a decent heuristic when he said that in a 4x the cities, forts, colonies or whatever are built by the player, as opposed to being predefined provinces like in a grand strategy game. But then what do you do about MoO, where you can think of stars as provinces?
In MOO, the vast majority of planets start empty, and need to be colonized, so it doesn't really go against this definition. Also, the term 4X was created for MOO in the first place, so it'd better qualify!
Certainly, IMO, MoO is a 4X. But, I mean, even in Total War most provinces start unowned by any actual player (human or computer) faction vying for victory. I am just saying it's an interesting heuristic
JarlFrank proposed, and it makes sense in a fuzzy way, but falls apart if you try and make it a hard rule.
The problem with a genre definition for 4X is that it's very fuzzy and highly based on "game feel" rather than concrete factors. The objective criteria are the 4X: eXplore, eXpand, eXploit, eXterminate. But from a purely mechanical perspective, that would include 99.9% of all strategy games ever made.
Do you explore in Age of Empires? Yes, scout to uncover fog of war. Expand? Yes, build new buildings. Exploit? Yes, harvest resources. Exterminate? Yes, destroy the enemy base. But is it a 4X? Not really.
Although AoE is an interesting case because it was inspired by Civilization: the devs thought, what if we took Civ and turned it into an RTS? Yet by turning it into an RTS it no longer feels like a 4X despite having all the X!
Same with grand strategy: a lot of people lump Total War, Europa Universalis, and Heroes of Might and Magic in with the 4X genre. Even Wikipedia (a shit and useless site when it comes to genre definitions, Mobygames is much better for that) lists HoMM and Total War as 4X games.
But they aren't 4X. They don't feel like 4X. Total War is turn based grand strategy, and the rebel-owned provinces were just a consequence of engine limitations at the time. From Empire onward, every province is ruled by a minor faction rather than rebels, and mods for Rome Remastered do the same thing. Also, only very few provinces in Shogun 1 and Medieval 1 were rebel-owned, most were owned by playable factions!
That said, neutral cities also exist in Heroes of Might and Magic but that's not a 4X either, is it?
The genre is mostly defined by lineage. Most 4X games are directly influenced by Civilization, Master of Orion, and Master of Magic. Those are the three 4X games the majority of future 4X are based on, and they have several things in common.
- start small, usually all factions begin with the same empire size (one city/planet) and tech level
- you have to explore a completely black fog of war and slowly reveal the shape of the land; in space 4X, you have to visit star systems before knowing what planets they have
- you expand your empire by founding new cities or colonizing new planets
- the environment can be exploited to your advantage: different terrain tiles have different resource values (flood plains give more food, hills more production, different planet types have higher fertility or resource yield, etc)
- you can usually build some kind of infrastructure or exploit things outside of your cities (build farms and roads, or exploit asteroid fields)
- you create armies using the production capabilities of your cities, and can wage war against the enemy
- you research technologies to improve all 4X capabilities of your empire: exploration, expansion, exploitation, and extermination
Now, not all of these are necessary for a game to qualify as 4X, but if too many are missing, it's probably a different strategy subgenre.
For example, Aggressors: Ancient Rome and Imperiums: Greek Wars are historical strategy games that feel distinctly 4X despite having a fixed historical map and empires with different technological and territorial starting conditions.
Why do they feel 4X when Total War and Europa Universalis don't?
They have unknown fog of war to explore, empty land that can be settled, all tiles can be improved with farms/roads/mines, there's a tech tree to go through, population growth from food production is an important factor. They are very close to Civ, but with a historical scenario.
What grand strategy games usually lack is both the founding your own cities part, and the building up the surrounding lands part.