Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411283 Posts in 69325 Topics- by 58380 Members - Latest Member: bob1029

March 29, 2024, 04:30:30 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)Shuffle Vectors: a really simple and really fast way to implement "random bags"
Pages: [1]
Print
Author Topic: Shuffle Vectors: a really simple and really fast way to implement "random bags"  (Read 948 times)
JobLeonard
Level 10
*****



View Profile
« on: February 18, 2019, 06:10:09 AM »

Figured this might have some use to some of the game devs out there:

https://beta.observablehq.com/@jobleonard/shuffle-vectors

(I can't believe this is a novel data structure, it's so simple it feels like it should have been discovered ages ago)
Logged
hotfeet
TIGBaby
*



View Profile
« Reply #1 on: February 21, 2019, 01:44:23 AM »

that is cool. thanks for sharing.
Logged
SLiV
Level 0
**



View Profile WWW
« Reply #2 on: April 06, 2019, 02:18:04 AM »

Interesting! I came up with a similar C++ template called Randomizer<T> as a catch-all random bag, where the vector was randomized before popping but only if it had been pushed to since the last pop, but this seems a lot more efficient. I will probably modify my randomizer so that instead of shuffling the vector, it just takes a random element on pop.

Well, now that I think about it like that, I guess that is basically the same as "a vector of elements, and every time you need an element you take a random element" with the (crucial) optimization of swapping to the end instead of erasing from the middle. So maybe the simplest solution is just the best.
Logged

@sanderintveld -- Currently working on Epicinium, a turn-based strategy game where nature is a finite resource. Now live on Kickstarter!
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic