How Pizza Tycoon (1994) simulated traffic on a 25 MHz CPU
Posted by Optdev@reddit | programming | View on Reddit | 45 comments
Posted by Optdev@reddit | programming | View on Reddit | 45 comments
Murky-Relation481@reddit
I know you can find the source now, but I'd also love to see a write up of how Falcon 4.0 simulated an entire war across the Korean Peninsula in campaign mode and did it in such tight constraints for 1997/1998. As I understand it was even written as an afterthought (and became one of its most popular features, one that DCS doesn't even have now).
walen@reddit
Back in 1997 I had a 350 MHz Pentium II with 128 MB RAM and several GB of HDD, and that was just average. What kind of game was Falcon 4 that would make those specs qualify as "tight constraints"?
postmodest@reddit
You are more of an outlier than you might think. In late 1998 I went from a 100mhz 5x86 500MB, to a 400Mhz Celeron A, with 32MB of RAM and IIRC a 4GB HDD. And I worked in IT.
walen@reddit
Maybe it was 1998 then. Edited. Game came out in December 1998 anyways so my question still applies.
Worth_Trust_3825@reddit
Average at the time was pentium 1 with 160 mhz and 32mb ram.
SkoomaDentist@reddit
I bought a brand new computer in the summer of 1997. It was a 200 MHz Pentium 1 with 32 MB ram. Pentium 2 had just been launched and only people who really needed one bought them yet.
walen@reddit
Maybe it was 1998 then. Edited. Game came out in December 1998 anyways so my question still applies.
walen@reddit
Maybe it was 1998 then. Edited. Game came out in December 1998 anyways so my question still applies.
ThePonderousBear@reddit
It's one of the big reasons it is still played(BMS)
humanquester@reddit
That would be a really facinating read.
TwerpOco@reddit
Spatial partitioning seems like it might offer an improvement for the O(n^2) collision check. At the expense of memory, though.
moh_kohn@reddit
I can't believe someone else remembers this insane game. You can run guns, release rats in rival pizza restaurants, even march in with a flamethrower and kill the customers. You also have to design your own pizzas to keep up with pizza topping trends, and slowly save up for better decor.
joonazan@reddit
Using a grid for collision detection would be arguably easier and would perform better. A 64-bit bitset might be enough to represent it, so the memory use of it is nonexistent, too.
If you wanted to do efficient large-scale simulations, look at Factorio devlogs: https://www.factorio.com/blog/post/fff-176
happyscrappy@reddit
I was just thinking of counting the cars entering and exiting a square. You could do it for all roads or perhaps just intersections. When a car wants to enter a square, check the car count in the square and if it's too high, then don't enter. When it successfully enters increase the count of cars in the square. When a car leaves a square decrement the count.
It's a bit more memory and a bit more work but collision checks are O(1). You just have a fixed value of how many cars can fit in a square without overlapping. That is your max value.
This does not keep cars from overlapping within the square if there are not too many but they happen to be on top of each other. So you'd have to ensure they don't spawn on top of each other. And since they all move at the same speed they don't overtake each other.
Now that I think of it it has a big issue with stopping. When you stop you have to work out where to stop within the square such that you do not overlap (overtake). I don't think there's an easy fix for this. You could keep it to 1 car per square (as you seemed to suggest) but I don't think it would look any good that way.
What you and I propose are both basically implementations of a train block system.
Perfect-Campaign9551@reddit
You would have to check all squares each time in the loop for your proposal. That's slower than just checking the cars since there are more squares than cars.
happyscrappy@reddit
If by "in the loop" you mean per car, then no. It's easy to calculate which square the car is trying to enter. Even if exiting an intersection there are only 3 possibilities (no u-turns). On a straight road section there's only 1 possibility.
Perfect-Campaign9551@reddit
I'm saying that it sounds like you would keep a count of car entering a square. Meaning the counts would be in the squares - a data structure that keeps a count for each square. That means you have to check each square's count to know , when you do your check. That is may take longer than to just check each car against other cars the way the code currently does since there are so many more squares than there are cars.
happyscrappy@reddit
I only have to check the count of the square I am entering. One check.
It doesn't matter how many squares there are, I only check the one I enter.
If a car is in square 8,10 and moving west the next square is 7,10. I only need to check that one square when the car is trying to move.
I think maybe you assumed a don't have a record of cars and their locations anymore. That's not what I was implying. You still have a record of cars it's just when you move them you only have to check them against one entry in the squares data structure (3 tops). Instead of having to check every car against every other car. So the lookup is O(1) per car instead of O(n). The overall act of moving the cars is O(n) instead of O(n*n).
Having a 2D array of square values may not make sense if the world grid is big. So you may have a sparse data structure for that instead.
Optdev@reddit (OP)
I'm not sure it would be easier; that's actually what I tried but I got stuck on it... I'm sure I could have gotten it to work if I liked working on it but given it's a hobby project I just couldn't be bothered to invest enough time into it :) The problem I had is that you can have more than one car per cell, so just a bitset is not enough, and you have to deal with complexity inside the cell and when something is partially in one and partially in another cell, taking a turn, things like that.
joonazan@reddit
There is definitely a bigger design space with the accelerated collision check. Being in multiple cells is usually solved by checking the four closest ones.
Doing something simple and reliable is a good. This is just a problem that I really enjoy solving.
There is a nice data structure for bigger collision detection grids. Clearing a big grid is slow and so is iterating over it. We can add an array that lists all entries in the grid to accelerate iteration. If the grid entries also contain their index in the array, you can clear just by resetting the auxiliary array's length. Grid entries are only valid if the matching array entry still exists.
WiseStrawberry@reddit
i love this kind of write up so much.
FunkyMuse@reddit
Finally some good read, thank you
KyLeggiero@reddit
Hmm... lemme guess, grid-based particle system?
KyLeggiero@reddit
YES!!! Great to see
Perfect-Campaign9551@reddit
A lot of software engineers these days overthink things. Probably because they didn't grow up with the simple constraints
Trang0ul@reddit
Also a lot of devs these days rush, for the same reason.
In case of Pizza Legacy it was not needed, but a more complex game would require a quick O(n log(n)) check instead of a straightforward, yet inefficient O(n\^2) one. Yet with today's gigabytes of memory and gigahertzes of CPU speed, the devs usually leave such optimizations for "later" (read: never).
jcGyo@reddit
In this day and age most game devs leave such optimizations up to the engine developer.
Infamous_Guard5295@reddit
honestly those old games had to be so clever with memory and cpu constraints, makes modern webapps that struggle to render a todo list look embarrassing lol. falcon 4.0's dynamic campaign was insane for the time, basically procedural warfare before anyone called it that. would love to dig through that codebase too, bet it's full of brilliant hacks that we've forgotten about.
WoodyTheWorker@reddit
Have you guys ever seen Descent (first) in 1995, played on a 80486?
Hot-Employ-3399@reddit
That reminds Turbo Esprit, it managed to be GTA about a decade before GTA existed and ran on ZX spectrum with 3.5MHz and 48KB memory.
acuddlyheadcrab@reddit
holy crap i hate that i totally forgot about this game despite playing it in my childhood
awesome post, thanks op
jduartedj@reddit
Man I love reading about old game engine tricks like this. Devs back then had to be SO creative with constraints that we just dont think about anymore. 25 MHz and they're simulating actual traffic patterns...
Its kinda humbling when you compare it to modern dev where we'll casually spin up 16GB of RAM for a TODO app. Those guys were writing optimized assembly while we're importing left-pad from npm lol
The pathfinding approach they used is really clever too, essentially pre-baking routes instead of computing them in realtime. Similar concepts still show up in modern routing algorithms, just at a completley different scale.
Infotaku@reddit
Good read, I always like to learn how old games dealt with hardware limits
rwl420@reddit
These are the articles I like to read in this subreddit. Thank you for this.
canton7@reddit
Nice write up. Unfortunately it reads like you ran it through an LLM, and that ruins it a bit for me, as I'm never quite sure whether I'm just reading hallucinated slop.
Optdev@reddit (OP)
It was hand written, with LLM review to catch typos and such but definitely not "run through an LLM". Then again I guess it's hard to put anything on the internet nowadays without people suspecting it's AI generated :)
scavno@reddit
Same. It’s not even about hallucinations, but more on how it reads. In tired of reading “here’s why” or “this is how” or “why this matters” over and over again. Perhaps it’s LLMs or perhaps it’s just how people express themselves these days.
flurinegger@reddit
Loved that game as a kid! What an awesome project and write-up.
humanquester@reddit
That's cool. Nice post. I wonder if there are any games that expanded this kind of basic tile based pathfinding?
radol@reddit
Topic which you might find interesting as similar but more complicated implementation is "flocking simulation" optimized for high number of entities.
BeautifulCuriousLiar@reddit
i love reading about how developers implemented features in older games. thanks for sharing.
skinnybuddha@reddit
Sometimes, ignorance is bliss.
mw44118@reddit
Very cool writeup
bohoky@reddit
Yep, tis a good read.
BlueGoliath@reddit
UE5 RTX remake: 9800X3D for 30FPS with frame gen.