Hacker News Reader

Comment by epups | Hacker News Reader

Can you explain this a little bit more? Are you saying that the game actually simulates each vehicle trip individually, and then decides on a random path at every intersection?

View on HN

Mmm. The simulation engine as part of simulation any given zone, produces "trips" (I don't know how many or how often) from each zone, and figures out where those trips end up - successfully reached a useful destination, went too far and gave up, etc.

In SC2K the graphics do not depict individual cars or people, and I have no idea if in later games there is a correlation between individual cars and people and "trips" (or if trips are still used as mechanism in later versions - although from what people are writing, it seems they are).

RollerCoaster Tycoon does the same, guests wander aimlessly around park and interact with whatever they come across while considering their needs.

The Sims displays the other end of this spectrum, where agents path deliberately (while still considering their needs), and the difference in simulation scale is immense.

Simple fact is, pathfinding is a performance bottleneck that hasn't been solved yet. We are still using algorithms from the 1960s, and no hardware acceleration exists.

SimCity has always been more of a spreadsheet with houses on top.

You can do a lot of shortcuts with the pathing, because you are doing a lot of pathing on a graph that doesn't change much from frame-to-frame.

Exactly. The only time you should be calculating paths is after the player places new roads. Repeatedly calculating paths on a fixed graph is a huge waste of time!

It’s even easier than that since each agent only needs to plans a path once, when they start their trip. After that they are simply following a cached path, removing road segments from it as they go. Most games will simply not recalculate those paths when you change the network, because it causes a lag spike every time the player makes a change, and because most routes wouldn’t end up changing. Better to just have cars ignore roads that didn’t exist when they departed, and have them vanish if they need to take a road that has since been deleted.

My graph is changing a lot, my whole environment from walls to objects is destructable and contains complex logic like access controlled doors.

Maybe your game doesn't change much. Lack of good pathfinding is what's constricting that the most. If good pathfinding existed, games in general could become more dynamic.

You could look into whether good-enough approximations exist?

Especially if the moving entities in your game aren't supposed to be omniscient. They could gradually learn about what good enough paths are.

I suspect pre-generation caching, game design, multi-core, SIMD versions of algs, etc. have evolved a lot.

Real-world performance isn't that determined by the form of the time-complexity.

>Simple fact is, pathfinding is a performance bottleneck that hasn't been solved yet.

But we got thousand times faster CPUs than at Sim City 2000 times.

And they have multiple cores. And if that is not enough there are GPUs with even more compute.

and better algorithms

But that still doesn't change the fact that path finding must necessarily occupy a larger and larger fraction of the cpu time as the player builds a larger and larger city. Each path becomes longer, there are more paths to plan, etc. In order to maintain an acceptable frame rate in a large city on the minimum spec computer at the time of release, Cities: Skylines has a fixed limit of 16k moving vehicles. This caps the time spent path finding as well as maximum frame time because once the vehicle limit is hit, agents start teleporting rather than being forced to traverse the map.

> no hardware acceleration exists

I'm picturing an alternate history where in addition to dedicated graphics cards, we also start building dedicated common algorithm cards - NVidia and AMD duking it out over whose hardware-accelerated sorting implementation performs best, Phoronix benchmarking how each companies' Linux drivers handle A* etc :)

GPUs are that card given the GPGPU craze in days past.

You're not wrong, but the idea of a sort of alt-history of various acceleration cards really tickled me :)

Between Dwarf Fortress and Factorio's ability to simulate huge numbers of agents, I'm not convinced.

Reply on news.ycombinator.com