Although the game Pizza Tycoon – known as Pizza Connection in Europe – probably doesn’t ring a bell for many folk, this 1994 DOS title is special enough for [cowomaly] to write an open source engine to bring it into the modern age as Pizza Legacy. Along the way, some questions popped up, such as how to animate the little cars that you see driving around in the simulated city and how the heck this was done back in the day on a 25 MHz 386 CPU.
On today’s GHz+, multi-core CPUs, we can just brute-force shovel pixels, sprites, and even 3D models around without a second thought while dedicating an entire core to pathfinding and other algorithms. Naturally, the original game developers had no such luxury. To understand how this animation was originally achieved, [cowomaly] had to dive into the assembly code of the original game.
The original algorithm was very simple: each road tile has at least one direction associated with it, so that a car that is on such a tile knows which direction it can travel, essentially creating a grid of one-way roads. When there’s a crossing, a random direction is picked, with the extra rule that you cannot do two consecutive turns in the same direction, presumably to keep cars from going around in circles.
Meanwhile, collision detection is simply a matter of checking the list of cars for a potential collision and not moving said car if it’s the case. This check is also optimized to take the road directions and one-way nature into account, with a 10-tick wait if there’s a block. Amusingly, this seems to enable the formation of brief traffic jams to add to that feeling of realism.
Although not a perfect algorithm and with some small bugs due to unchecked conditions with collisions, it’s hard to deny that the effect is very natural car movement, something that games like Sim City likely used as well.
I would also point to Transport Tycoon Deluxe.
Open TTD is a thing. Works amazingly well and comes with gazillion freebie plugins.
Indeed! I love what they have done.
Now Micropolis btw.
that’s a little misleading, imho. The version you linked to is a Java re-write of the original C code. There is also Micropolis in C++,
https://github.com/SimHacker/MicropolisCore
Although that seems to be a 16-bit rewrite “SimCity Classic” rather than the original 8-bit DOS SimCity (or the original Amiga version?) There’s an article online (Medium dot com?) interviewing how Don Hopkins got his one of his contracted Unix rewrites(in C for X11, based off the Macintosh port!) open sourced for the One Laptop Per Child project; resulting in various Micropolis versions. I appreciate your effort, but I wish you linked to Don Hopkins’ (SimHacker on GitHub) because But Micropolis ≠ Will Wright’s Sim City, and not just for legal reasons.
I was a huge fan of Transport Tycoon and a few other games like it, but I did also spent quite a lot of time playing (and failing at) Pizza Tycoon. There was and still is something quite charming about it’s graphics, though the whole lobster on a pizza was always a weird one.
We can see 13 cars on one of the screens, which represents 12×12 tiles. So, based on the blog post the full map might contain 160×120/144×13=1,733 cars.
Let’s say we have a 5Hz frame rate, since that’s what it looks like on the animation on the blog. So, on a 25MHz CPU we have 25000000/1733/5=2,885 cycles per car.
Without wanting to rubbish the post, which is certainly interesting, it seems reasonable to me that the car checking can be done in that time. I’m surprised each car checking checks all other cars. Surely one only needs to perform collision detection by checking the adjacent tiles to any given car? That’s only 4 checks per car?
Let’s say it’s an 8MHz 68000. Same calcs: 2885×8/25=923.2 cycles. Still very reasonable. Now 1MHz C64… 2885/25=115.4 cycles. Bit more tricky!
Or have I missed something?
The rest of the game…. I’ve never played it but the car logic is probably a tiny part of the cpu budget. Early games even did sound effects and music using cpu driven pwm to the speaker. If it was just a simple traffic simulator you’d be spot on but I suspect those other cycles were put to good use.
Yes. The rest of the game…
You’re missing quite a bit. For the first car, you would have to calculate 1732 potential collisions (well, times 4, but that’s not the problem). For the second, 1731. So you see, there aren’t 1733, but 1733! checks that need yo be done. In other words, even a modern supercomputer couldn’t calculate that in 10 billion years. 1732! is a number that has 4859 digits. It’s MUCH bigger than the number of atoms in the universe. Like 10^4817 times bigger.
That’s partly why combinatorial problems are so amazing and hard to comprehend: their size tends to explode exponentially.
Hi Andy,
Thanks for the reply.
You don’t need to calculate 1732! potential collisions, because well firstly, you’d only need to calculate 1732² at worst: every car + its movement colliding with any other car. But in reality, you only need to check against cars within (dx,dy) of a given car in the direction of the car’s movement in the next frame.
I think, from the videos, a given car only moves 1 pixel per frame. So, the cheapest way to check is to create an off-screen 1bpp bitmap; clear it at the start and then plot the new positions of cars and as soon as you try to set a pixel that’s already been set, you have a collision.
Another way though is to split the map into a grid of (gx, gx) pixels where gx is the maximum speed of any car. Then pointers to each car are copied into that grid. Collisions then need to be checked between any car and another in the same grid square and between a given car and any other in an adjacent grid square in the direction of the car’s travel if it crosses a grid square.
If the checking grid is the size of the grid on the screen (12×12 tiles) we’ll be checking 13×13=169 x (160×120/144)=22,477 possible collisions each frame, plus a subset for cars crossing grid squares, maybe 25% of them, leading to: 28,096 collisions.
That’s quite a lot. If we had a smaller grid size, say 4×4 tiles; we’d expect about 13x(4×4)/(12×12)=1.444 cars per grid square, so that’s 2x2x(160×120/(4×4))=4,800 possible collisions, or 6000 including crossing grid squares. We need 1200 grid squares containing up to 1732 pointers in total, but if they’re linked lists it’s only 3464 bytes on an 8 or 16-bit system (don’t think you need double-linked lists).
4800 checks x 5fps= 24000 checks/second, about 300 cycles per check on an 8MHz 68000. Again, very doable. There aren’t many cases to check either. A car travelling on the same side of a road at different speeds, or a car travelling at right angles. That means you can probably split a grid’s set of cars into 4 (U, D, L, R). Only UU, UL, UR, DD, DL, DR, LL, LR, RR can collide. That’s 9/16 combinations, so 13,500 checks/second. 593 cycles per check.
SimCity from that era didn’t have individual car animations – not until SimCity 3000.
Certainly seems like there were bugs, look at the animation. On the left lower corner the cars go in circles and take a wrong turn and end on in a pile of 5 cars in the opposite direction, and on the right lower corner the cars end up making u-turns in a 90 degree turn.
It is simulating Boston Massachusetts drivers accurately.
With this limited amount of resources, I would seed an algorithm to place “traffic” sprites. This way a single number can encode the sprite states, and changing them is as simple as reseeding. The downside is my solution is not a traffic simulator, its a novel method for making flashing light patterns
You can see in the screenshot that the roads are two-way, although they use a white center dividing line instead of the proper yellow. What they did was create a network of one-way travel lanes, which is how every paved, divided road network operates.
It looks like their streets were set up left-hand drive / right-side travel (US, rather than British, driving rules), so when you reach an intersection, there are three directions the car can proceed: forward in the same lane/direction; turn right, into the nearer cross-lane proceeding away; or turn left, into the farther cross-lane proceeding away. The other five lanes (the one the car is traveling in, the one next to it traveling in the opposite direction, and the three oncoming lanes from the other directions) aren’t considered available exit paths from that approach to that intersection.
And if the algorithm allowed turns in both directions, then the entire network was interconnected, it isn’t like there were two separate one-way grids. A car turning left from one approaching direction, and a car turning right from the opposite approaching direction, would end up in the same lane, despite being in separate/opposing lanes before their turns.
In what country are dividing lines yellow??
For a two lane road? US, Canada… the outer lines are white, giving simple feedback on proper intended direction of travel. Keep the yellow on the left.