How Pizza Tycoon (1994) simulated traffic on a 25 MHz CPU

[-]

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

That means you have to check each square's count to know , when you do your check.

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 :)

[-]