I'm the developer of Metropolis 1998. Unfortunately the launch date in the article has come and passed, but that's how things are in game development world. :D
Some tech talk:
- Custom engine (C++) using SFML for the graphics framework, and SQLite for database/data oriented design
- True isometric engine. No 3D models, everything you see is hand drawn sprites (made to look like a 3D render ha)
- Since sorting sprites is O(N^2), I figured out a way to create a depth map for each sprite to depth sort on the GPU
- Tons of work went into the pathing code to make it efficient, since this is the traditional bottleneck in these types of games. The game can handle around 100K units and vehicles moving around (on one CPU core)
- The team is just me and a couple part time contractors for the art and buildings.
People really discount the complexity of doing isometric — it's a surprisingly nuanced thing to implement, especially if you want inner-tile sorting/depth, tiles that occlude others, etc.
For sorting for me I ended up using geometry shaders with fixed layers to basically emit objects on top of each other and render everything in one pass. It makes things like the editor and runtime incredible fast, which looks like you did as well! Happy to see more games with this style, I think the look is unbeatable.
"Screenshots suggest cities more complex than suburban plots are possible in Metropolis 1998."
Which sounds good, but naturally, all such simulators bake in assumptions about what good urban planning is. These are the kinds that get rewarded by the simulator. SimCity bakes in the awful postwar fetish for suburban sprawl and rigid zoning, for example. Perhaps it isn't always done explicitly - game developers could very well be absorbing prevailing sensibilities and expectations about urban planning unwittingly, for example. Most people today think suburban sprawl is just a fact. They even find it desirable, as that is what they are expected to want or what they grew up with themselves.
What I would like to see is a simulator based on traditional principles of urban planning or the 15 minute neighborhood or whatever. This could have the benefit of stirring the imagination of future urban planners to look beyond broken postwar patterns.
(Side note: the Venice Biennale this year features more examples of sustainable architecture and green adaptations of existing buildings, which is a welcome change compared to the usual practice of the weird architecture Olympics where vain architects compete to maximize how bizarre they can make a building, which is not to say beautiful or useful.)
You probably know this already but sorting is `N log(N)` in the general case but `N` when the range of values is known and relative small using pigeonhole sort [1]. That's probably what you're doing on the GPU.
It's been 2-3 years since I've thought about this. I dug around and found an article that said the time complexity (for topological sorting of sprites) was O(N^2) [1]
It appears there are O(n log n) algorithms though, I just didnt come across them at the time :)
EDIT: Or maybe not! I dont have time to dig into this, but it may not be accurate enough
Im not sure that would work for my use case though, since you can see inside the buildings in my game (and there's see thru windows!). A bunch of high density buildings will be drawing tens of thousands of sprites within the camera's field of view.
For anyone who's interested, here's the scope of the problem:
Isometric projection is simulating a 3D world by layering 2D sprites in a specific order. Notably, units/vehicles in the game have smooth (floating point) movement, so they can be e.g. partially occluded by a wall or another object. My game also has pixel thin walls that can be placed on any edge of a tile.
So imagine sorting a vehicle sprite behind two wall sprites (the vehicle sprites are twice as wide) as it's moving across them. All you have are rectangles to work with. Now add in a stationary plant in front the wall, and a person walking in front of the plant, the two walls, and the vehicle.
e.g. There will be a time when the front the vehicle (the bottom of the rectangle sprite) is lower (i.e. closer to the camera) than a wall sprite, but the vehicle would still be occluded by the wall.
If you're happy with your engine's behavior and performance than feel free to disregard. But if it is something you want to noodle on...
> I dug around and found an article that said the time complexity (for topological sorting of sprites) was O(N^2)
Topo sort in general is O(V + E) where V is the number of vertices in the graph and E is the number of edges. If you consider your set of sprites a graph with an edge between every pair of sprites, then it does become O(N + N*N) which is O(N^2).
If the only way to get topo sort to work is by treating the sprites as a fully connected graph, then it's not the right approach. Topo sort really only makes sense when the number of edges between nodes is relatively low. You'd be better off using quicksort which is O(N log N).
However, since you are going to be resorting the same data each frame and most sprites stay in the same order, what you want is a sorting algorithm that works well on mostly-sorted data. In that case, I suspect insertion sort is what you want. It will roughly behave like O(N) when the data is mostly sorted.
Alternatively, you could look at bucket sort. While your sprites can be freely positioned with floating point coordinates (which makes pigeonhole sort a poor fit), they still fall within a known finite range, and bucket sort is designed to handle that case.
It's a fun problem to think about. [1] I don't have a computer science background, so I appreciate you bridging the gaps in my knowledge.
I mostly understand what you're suggesting (I'd need to read up on how each individual algorithm works at a low level). It's true that most of the sprites would remain in the same order and in theory it would be worth looking into this (it may benefit low powered machines -> widen the potential market).
However, there are other limitations with the framework I'm using that make me pause. I'm using OpenGL and Vertex Buffer Objects (semi-dynamic Vertex Arrays, ie. a std::vector<> of vertex information that the GPU can store locally). When a vertex array is updated, the entire array must be resent to the GPU, or alternatively one can do individual range updates (which... are not working at the moment). There can be so many sprites on the screen that a full update would cause the FPS to drop (learned this by example). And since CPU -> GPU communication is so costly, I assume hundreds of individual updates would also drop the FPS.
With my custom depth maps for each sprite, the vertex array only needs to be sent once. (Side note: the world is broken into 40x40 chunks)
> If the only way to get topo sort to work is by treating the sprites as a fully connected graph, then it's not the right approach.
One trick the OpenRCT devs did was split the screen (or scene?) into 64 pixel wide vertical strips. Though they still said the performance was O(N^2) for each strip.
[1] I am content with the engines performance for now. Last I tested I, a very dense scene ran >165 FPS on a medium performance GPU.
It's a lost art, but I for one appreciate when the developer makes the effort to avoid all the bloat that typically comes with new software these days (and especially games).
The solution I went for was drawing a 3D box (in 2D space, i.e. in the sprite sheet over each sprite), and then using that box to calculate the local depth within the "diamond"/isometric space is occupies (er, hope that makes sense!)
I haven’t. One of the reasons I decided to write my own engine was to be able to organize the code/logic my way. I’m pretty sure I would have burnt out from the organizational friction of using eg unity
Love to see it! I think it's terribly unfortunate that we've left the isometric art style of the 90s behind. I'm sure this has been written about and thought about in deeper ways in different spaces, but there has to be more than mere nostalgia to the idea that the art and feel of everything from SimCity, to Age of Empires, to cRPGs had some specific affirmative artistic and aesthetic values that mattered in their own right and were not just a matter of being the best we could do in a given era.
I've recently watched a video [1] that mentions how pre-rendered graphics dominated the 90s-early 2000s and were replaced by real-time rendering. You'll probably like it too!
Great recommendation. I screenshotted the list of games at the end. I was aware of commandos but never played it, and I don't think I appreciated how many distinctly rich and interesting environments you get to play in.
Weren't some of those pre-rendered sprite sheets? Thinking especially of cRPGs and stuff like Diablo 1/2. Not to take away from either direction, or maybe even to say that there's a whole separate era and "look" in there that was post pixel art but before realtime 3D.
Roadmap [1] last updated in June 2025, so a reasonable chance that the project is alive. Though the status colours indicate there's a good percentage of development left to do even before early access.
The roadmap has both early access and 1.0 goals. I just wrapped up terrain generation/modification, so all that's left is to add in the municipal services, funds, and prob. street parking. Then wrap up the overlays.
> You’re putting your time in now, so you’ll be ready to start fresh when the game releases into early access (“ETA sometime between Q4 2024 and Q2 2025”).
'till I went back and looked at the publish date for the article. Might be worth appending a [2024] to the title.
Looks like lots of fun though, mellow and very zen. Suspect it's just the right time to learn about it too, with the release date considered and the amount of polish that implies.
As an old school TT/TTD fan this gives me so many good vibes :)
Been fun watching the progress and I do recommend people check out the demos on Steam if you just want to have a good nostalgia break even if the game isn't fully there yet.
I was comparing Steam accounts on Harrah's (Caesar's) patio with an acquaintance the other night and we both had the 21 years badge but mine was December 2003 and his was June 2004 so I still had bragging rights.
Hey HN!
I'm the developer of Metropolis 1998. Unfortunately the launch date in the article has come and passed, but that's how things are in game development world. :D
Some tech talk:
- Custom engine (C++) using SFML for the graphics framework, and SQLite for database/data oriented design
- True isometric engine. No 3D models, everything you see is hand drawn sprites (made to look like a 3D render ha)
- Since sorting sprites is O(N^2), I figured out a way to create a depth map for each sprite to depth sort on the GPU
- Tons of work went into the pathing code to make it efficient, since this is the traditional bottleneck in these types of games. The game can handle around 100K units and vehicles moving around (on one CPU core)
- The team is just me and a couple part time contractors for the art and buildings.
- Most recent update (some cool skyscraper construction): https://x.com/YesboxStudios/status/1978928991663776224
- Fun fact: the entire game is currently 27 MB.
- Steam: https://store.steampowered.com/app/2287430/Metropolis_1998/
From one hand-pixeled isometric dev (https://store.steampowered.com/app/690370/Cantata/) to another, congrats!
People really discount the complexity of doing isometric — it's a surprisingly nuanced thing to implement, especially if you want inner-tile sorting/depth, tiles that occlude others, etc.
For sorting for me I ended up using geometry shaders with fixed layers to basically emit objects on top of each other and render everything in one pass. It makes things like the editor and runtime incredible fast, which looks like you did as well! Happy to see more games with this style, I think the look is unbeatable.
Thanks! Sorting whole sprites is definitely a complicated problem and it took some time to arrive at the solution I use today.
I noticed this bit in the article...
"Screenshots suggest cities more complex than suburban plots are possible in Metropolis 1998."
Which sounds good, but naturally, all such simulators bake in assumptions about what good urban planning is. These are the kinds that get rewarded by the simulator. SimCity bakes in the awful postwar fetish for suburban sprawl and rigid zoning, for example. Perhaps it isn't always done explicitly - game developers could very well be absorbing prevailing sensibilities and expectations about urban planning unwittingly, for example. Most people today think suburban sprawl is just a fact. They even find it desirable, as that is what they are expected to want or what they grew up with themselves.
What I would like to see is a simulator based on traditional principles of urban planning or the 15 minute neighborhood or whatever. This could have the benefit of stirring the imagination of future urban planners to look beyond broken postwar patterns.
(Side note: the Venice Biennale this year features more examples of sustainable architecture and green adaptations of existing buildings, which is a welcome change compared to the usual practice of the weird architecture Olympics where vain architects compete to maximize how bizarre they can make a building, which is not to say beautiful or useful.)
Yes.. but: Don't forget this is a game, and the main mission of a game is to be FUN.
> Since sorting sprites is O(N^2),
You probably know this already but sorting is `N log(N)` in the general case but `N` when the range of values is known and relative small using pigeonhole sort [1]. That's probably what you're doing on the GPU.
[1]: https://en.wikipedia.org/wiki/Pigeonhole_sort
It's been 2-3 years since I've thought about this. I dug around and found an article that said the time complexity (for topological sorting of sprites) was O(N^2) [1]
It appears there are O(n log n) algorithms though, I just didnt come across them at the time :)
EDIT: Or maybe not! I dont have time to dig into this, but it may not be accurate enough
Im not sure that would work for my use case though, since you can see inside the buildings in my game (and there's see thru windows!). A bunch of high density buildings will be drawing tens of thousands of sprites within the camera's field of view.
For anyone who's interested, here's the scope of the problem:
Isometric projection is simulating a 3D world by layering 2D sprites in a specific order. Notably, units/vehicles in the game have smooth (floating point) movement, so they can be e.g. partially occluded by a wall or another object. My game also has pixel thin walls that can be placed on any edge of a tile.
So imagine sorting a vehicle sprite behind two wall sprites (the vehicle sprites are twice as wide) as it's moving across them. All you have are rectangles to work with. Now add in a stationary plant in front the wall, and a person walking in front of the plant, the two walls, and the vehicle.
e.g. There will be a time when the front the vehicle (the bottom of the rectangle sprite) is lower (i.e. closer to the camera) than a wall sprite, but the vehicle would still be occluded by the wall.
[1] https://mazebert.com/forum/news/isometric-depth-sorting--id7...
If you're happy with your engine's behavior and performance than feel free to disregard. But if it is something you want to noodle on...
> I dug around and found an article that said the time complexity (for topological sorting of sprites) was O(N^2)
Topo sort in general is O(V + E) where V is the number of vertices in the graph and E is the number of edges. If you consider your set of sprites a graph with an edge between every pair of sprites, then it does become O(N + N*N) which is O(N^2).
If the only way to get topo sort to work is by treating the sprites as a fully connected graph, then it's not the right approach. Topo sort really only makes sense when the number of edges between nodes is relatively low. You'd be better off using quicksort which is O(N log N).
However, since you are going to be resorting the same data each frame and most sprites stay in the same order, what you want is a sorting algorithm that works well on mostly-sorted data. In that case, I suspect insertion sort is what you want. It will roughly behave like O(N) when the data is mostly sorted.
Alternatively, you could look at bucket sort. While your sprites can be freely positioned with floating point coordinates (which makes pigeonhole sort a poor fit), they still fall within a known finite range, and bucket sort is designed to handle that case.
It's a fun problem to think about. [1] I don't have a computer science background, so I appreciate you bridging the gaps in my knowledge.
I mostly understand what you're suggesting (I'd need to read up on how each individual algorithm works at a low level). It's true that most of the sprites would remain in the same order and in theory it would be worth looking into this (it may benefit low powered machines -> widen the potential market).
However, there are other limitations with the framework I'm using that make me pause. I'm using OpenGL and Vertex Buffer Objects (semi-dynamic Vertex Arrays, ie. a std::vector<> of vertex information that the GPU can store locally). When a vertex array is updated, the entire array must be resent to the GPU, or alternatively one can do individual range updates (which... are not working at the moment). There can be so many sprites on the screen that a full update would cause the FPS to drop (learned this by example). And since CPU -> GPU communication is so costly, I assume hundreds of individual updates would also drop the FPS.
With my custom depth maps for each sprite, the vertex array only needs to be sent once. (Side note: the world is broken into 40x40 chunks)
> If the only way to get topo sort to work is by treating the sprites as a fully connected graph, then it's not the right approach.
One trick the OpenRCT devs did was split the screen (or scene?) into 64 pixel wide vertical strips. Though they still said the performance was O(N^2) for each strip.
[1] I am content with the engines performance for now. Last I tested I, a very dense scene ran >165 FPS on a medium performance GPU.
If you dont have twitter: https://old.reddit.com/r/Archapolis/comments/1o91vme/added_h...
Fun fact: the entire game is currently 27 MB
just got the demo, this is literally the smallest game in my collection. impressive
It's a lost art, but I for one appreciate when the developer makes the effort to avoid all the bloat that typically comes with new software these days (and especially games).
Agreed. Looking through my library, the only game remotely close is RoR1
I know this is probably super low on your priority list but any plans for a Linux port?
Ill be looking into porting after launch, so its possible!
> - Since sorting sprites is O(N^2), I figured out a way to create a depth map for each sprite to depth sort on the GPU
Could you elaborate on this some more? This seems very interesting.
See my other comment in this thread.
The solution I went for was drawing a 3D box (in 2D space, i.e. in the sprite sheet over each sprite), and then using that box to calculate the local depth within the "diamond"/isometric space is occupies (er, hope that makes sense!)
Have you investigated Unity’s “HPC#”? This is how you can write C++ in it. If you don’t even want to deal with ECS/DOTS.
I haven’t. One of the reasons I decided to write my own engine was to be able to organize the code/logic my way. I’m pretty sure I would have burnt out from the organizational friction of using eg unity
The art and little people walking around remind me of roller coaster tycoon. Very interesting looking game.
[dead]
Love to see it! I think it's terribly unfortunate that we've left the isometric art style of the 90s behind. I'm sure this has been written about and thought about in deeper ways in different spaces, but there has to be more than mere nostalgia to the idea that the art and feel of everything from SimCity, to Age of Empires, to cRPGs had some specific affirmative artistic and aesthetic values that mattered in their own right and were not just a matter of being the best we could do in a given era.
I've recently watched a video [1] that mentions how pre-rendered graphics dominated the 90s-early 2000s and were replaced by real-time rendering. You'll probably like it too!
[1] The Beauty of Pre-Rendered Graphics https://www.youtube.com/watch?v=e3SwbHIPnfo
Great recommendation. I screenshotted the list of games at the end. I was aware of commandos but never played it, and I don't think I appreciated how many distinctly rich and interesting environments you get to play in.
Weren't some of those pre-rendered sprite sheets? Thinking especially of cRPGs and stuff like Diablo 1/2. Not to take away from either direction, or maybe even to say that there's a whole separate era and "look" in there that was post pixel art but before realtime 3D.
It's also a ton better for people who get motion sickness from any 3d cameras. Like my wife.
Roadmap [1] last updated in June 2025, so a reasonable chance that the project is alive. Though the status colours indicate there's a good percentage of development left to do even before early access.
[1] https://yesboxstudios.com/roadmap/
Very much alive! (I'm the dev).
The roadmap has both early access and 1.0 goals. I just wrapped up terrain generation/modification, so all that's left is to add in the municipal services, funds, and prob. street parking. Then wrap up the overlays.
Was a little thrown reading
> You’re putting your time in now, so you’ll be ready to start fresh when the game releases into early access (“ETA sometime between Q4 2024 and Q2 2025”).
'till I went back and looked at the publish date for the article. Might be worth appending a [2024] to the title.
Looks like lots of fun though, mellow and very zen. Suspect it's just the right time to learn about it too, with the release date considered and the amount of polish that implies.
Not the same vibes exactly, but a pixel/voxel-ish city builder I've been enjoying recently is Town to City
https://store.steampowered.com/app/3115220/Town_to_City/
As an old school TT/TTD fan this gives me so many good vibes :) Been fun watching the progress and I do recommend people check out the demos on Steam if you just want to have a good nostalgia break even if the game isn't fully there yet.
One of the only recent games I've seen that have almost completely captured the style of the time. Looking good.
love the art style. if they support mac, I'll happily purchase a copy.
The Steam page shows the game will only be available for Windows.
I'll be looking into porting after launching
in development since 2021, and in pre-alpha? So a release date in 2030?
Are you an investor? did you pre-ordered? Are you his mom?
I guess we are getting to the age of moms with Steam accounts.
Steam launched in 2003. 22 years ago. The median age of a mother in the US is currently 27. There are probably grandmothers with Steam accounts.
I was comparing Steam accounts on Harrah's (Caesar's) patio with an acquaintance the other night and we both had the 21 years badge but mine was December 2003 and his was June 2004 so I still had bragging rights.
Was curious and checked my own, 20 Nov 2004. Which was 4 days after the release of Half Life 2 and for which I made the account.
I mean, my father made a Steam account 20 years ago and he's almost 70.