3 ms·

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 st

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.

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.