6 ms·

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 eve

by epups 4y ago

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?

hypertele-Xii 4y ago
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.
- eru 4y ago
  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.
  - chongli 4y ago
    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!
    - db48x 4y ago
      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.
  - hypertele-Xii 4y ago
    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.
    - eru 4y ago
      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.
- mjburgess 4y ago
  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.
- adql 4y ago
  >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.
  - VMG 4y ago
    and better algorithms
    - db48x 4y ago
      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.
- deleted 4y ago
  [deleted]
- smcl 4y ago
  > 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 :)
  - fragmede 4y ago
    GPUs are that card given the GPGPU craze in days past.
    - smcl 4y ago
      You're not wrong, but the idea of a sort of alt-history of various acceleration cards really tickled me :)
- fragmede 4y ago
  Between Dwarf Fortress and Factorio's ability to simulate huge numbers of agents, I'm not convinced.
casenmgreen 4y ago
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).

by epups 4y ago

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?

hypertele-Xii 4y ago

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.

eru 4y ago
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.
- chongli 4y ago
  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!
  - db48x 4y ago
    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.
- hypertele-Xii 4y ago
  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.
  - eru 4y ago
    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.
mjburgess 4y ago
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.
adql 4y ago
>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.
- VMG 4y ago
  and better algorithms
  - db48x 4y ago
    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.
deleted 4y ago
[deleted]
smcl 4y ago
> 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 :)
- fragmede 4y ago
  GPUs are that card given the GPGPU craze in days past.
  - smcl 4y ago
    You're not wrong, but the idea of a sort of alt-history of various acceleration cards really tickled me :)
fragmede 4y ago
Between Dwarf Fortress and Factorio's ability to simulate huge numbers of agents, I'm not convinced.

casenmgreen 4y ago

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