0
\$\begingroup\$

I'm building a system for distributing ingame events for a strategy game. The game is heavily driven by the events and each country/player should receive one or more per time unit.

The algorithm is similar to the "The Soft-coded Probabilities Solution" from this question: How do I create a weighted collection and then pick a random element from it?

The main differences are:

  1. I need conditions for if events can happen or not, like only triggers if unrest is above 2% or if you are at war etc. Maybe half the events will have conditions (but this may change over time as more are added while the algorithm probably won't).
  2. I need a mechanism to prevent the same event repeating for the same player in too short a time period. This applies to some events but not all.

It seems that no matter how I go about this I have to do either a lot of condition checking in advance to maintain my list(s) or a lot of iteration over events that are anyway not selectable. So is this algorithm still a good choice to build upon in this case or should I be looking elsewhere?

\$\endgroup\$
2
\$\begingroup\$

I recommend this plan:

  1. Check conditions, create a list of eligible events. Don't add event if it is the same as the one most recently shown to the user.
  2. Assign weights to each event. E.g. Event[0].weight = 5; Event[1].weight = 10;
  3. Get random number from 0 to N - 1, where N is the sum of all weights.
  4. Check if the random number is less than Event[0].weight. If so, choose that event. Else, subtract Event[0].weight from the random number. Then check Event[1].weight and so on.
  5. Once an event is selected, store it so the next time you pick one, you can keep it out of the list.
\$\endgroup\$
  • \$\begingroup\$ This is a valid solution and may work better in some scenarios. The reason I will not use it is because it will make me check every condition once per country per event interval, which in my case becomes more expensive than re-picking. \$\endgroup\$ – SpacemanSpiff Jan 11 at 8:43
  • \$\begingroup\$ Prove this method is "too expensive" for a modern computer, and that repicking is "better". Repicking is very, very poor architecture. \$\endgroup\$ – Almo Jan 11 at 14:11
  • \$\begingroup\$ I actually agree with you, but would say it all depends on parameters like total number of events, condition evaluation cost, chance to get a valid event - which admittedly I don't know yet but can only estimate. It would also change the whole equation if the list(s) of valid events can be prepared ahead of time for each event interval, in a separate thread etc. \$\endgroup\$ – SpacemanSpiff Jan 11 at 14:32
  • \$\begingroup\$ Repicking is bad architecture, regardless of anything else. It's ok for just putzing around, but if you're serious about writing good code, it should never be done. \$\endgroup\$ – Almo Jan 11 at 15:00
  • \$\begingroup\$ My case may be more of an exception from the norm than I first thought, accepting this as best answer for posterity as the more clean design matching the question as stated. Thanks. \$\endgroup\$ – SpacemanSpiff Jan 17 at 16:29
0
\$\begingroup\$

As I was writing this I arrived at an answer that seems "good enough" for me even if not necessarily the best one so adding it separately instead of in the question.

My thinking right now is to put everything into the list and only check the conditions after selecting from it. Then if necessary reselect until I get a valid event. This will also let me reuse the the same list to "draw" events for several countries even if conditions differ.

A sleep time is added per event (which can be 0). But rather than actually sleeping the event (as in removing it from the selectable list) it stays in the list and a check is made during condition evaluation if this country had the event inside the timer value.

As long as there is at least one event with no condition and no sleep time this will not create an endless loop.

\$\endgroup\$
  • 2
    \$\begingroup\$ Just be cautious that you never have a situation where the only valid events have low total weight, otherwise you could still burn a substantial amount of tike picking & re-picking the more probable but invalid outcomes \$\endgroup\$ – DMGregory Jan 3 at 14:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.