3 ms·

But do they use linked lists for them? I would have assumed you would use an arena for something like that, precisely because you already need to iterate over a

But do they use linked lists for them? I would have assumed you would use an arena for something like that, precisely because you already need to iterate over all of them and can represent any graph as keys into a generational index, so that reading stale keys is trivially handled. Again, I'm not a game dev and this is just my understanding after reading up on these topics after watching https://youtu.be/aKLntZcp27M https://youtu.be/aKLntZcp27M.

chongli 7y ago
They certainly used linked lists all over the place in StarCraft, WarCraft, and Diablo [1]. I don't know that many game developers would use complicated data structures like the one you've described here. Linked lists are fantastic for insertion/removal in arbitrary places. Game development is not really about showing off with cutting-edge CS research, it's about getting things done. Maybe your arenas with generational indices would be better, but they could take a long time to figure out and lead to a big mess that doesn't go anywhere. [1] https://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft https://www.codeofhonor.com/blog/tough-times-on-the-road-to-...
- ssalazar 7y ago
  Arenas aren't "cutting edge CS research," theyre used widely in latency-sensitive applications like gaming. This article [1] describes how to implement one for a game engine. Basic versions are easy to understand and provide good results. Starcraft/etc. are 20+ year old games and software development patterns as well as gaming hardware have changed in fundamental ways since then. Conventional wisdom nowadays is that cache misses on every list iteration are a lot worse than shuffling a few contiguous bytes around or marking things inactive when removing items. [1] https://www.gamasutra.com/blogs/MichaelKissner/20151104/258271/Writing_a_Game_Engine_from_Scratch__Part_2_Memory.php https://www.gamasutra.com/blogs/MichaelKissner/20151104/2582...
- Narishma 7y ago
  Those are pretty old games written when caches were small and the CPU-memory speed gap wasn't as large as it is today.
- jfkebwjsbx 7y ago
  You are wrong in several fronts: + Linked lists are a thing of the past. + Game engines use complex data structures and algorithms. Some are cutting-edge research implemented from papers, specially in graphics. + A generational index is not complex. Yes, game development (as opposed to game engine development or video/audio rendering) is a mess. That does not mean the actual technical fields involved are simple.
  - renox 7y ago
    While I don't disagree on your first two points, I disagree with you third: there's nothing complex about generational index.

chongli 7y ago

They certainly used linked lists all over the place in StarCraft, WarCraft, and Diablo [1]. I don't know that many game developers would use complicated data structures like the one you've described here. Linked lists are fantastic for insertion/removal in arbitrary places. Game development is not really about showing off with cutting-edge CS research, it's about getting things done. Maybe your arenas with generational indices would be better, but they could take a long time to figure out and lead to a big mess that doesn't go anywhere. [1] https://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft https://www.codeofhonor.com/blog/tough-times-on-the-road-to-...

ssalazar 7y ago
Arenas aren't "cutting edge CS research," theyre used widely in latency-sensitive applications like gaming. This article [1] describes how to implement one for a game engine. Basic versions are easy to understand and provide good results. Starcraft/etc. are 20+ year old games and software development patterns as well as gaming hardware have changed in fundamental ways since then. Conventional wisdom nowadays is that cache misses on every list iteration are a lot worse than shuffling a few contiguous bytes around or marking things inactive when removing items. [1] https://www.gamasutra.com/blogs/MichaelKissner/20151104/258271/Writing_a_Game_Engine_from_Scratch__Part_2_Memory.php https://www.gamasutra.com/blogs/MichaelKissner/20151104/2582...
Narishma 7y ago
Those are pretty old games written when caches were small and the CPU-memory speed gap wasn't as large as it is today.
jfkebwjsbx 7y ago
You are wrong in several fronts: + Linked lists are a thing of the past. + Game engines use complex data structures and algorithms. Some are cutting-edge research implemented from papers, specially in graphics. + A generational index is not complex. Yes, game development (as opposed to game engine development or video/audio rendering) is a mess. That does not mean the actual technical fields involved are simple.
- renox 7y ago
  While I don't disagree on your first two points, I disagree with you third: there's nothing complex about generational index.