Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Rolling For Initiative

by Util (Priest)
on Dec 19, 2008 at 05:19 UTC ( [id://731452]=note: print w/replies, xml ) Need Help??


in reply to Rolling For Initiative

You are creating a long ruler, with physical lengths marked off according to the weight of each ship's initiative. You throw a stone randomly on the ruler, and whoever owns the area it lands in, wins the draw. That is a fine algorithm, but here is one might suit you better.

You, me, and Dupree each have ships - yours is 25 powerful, mine is 15, and Dupree's is 60.

  1. Make index cards for each of us, writing our names and power levels on each card.
  2. Total up all the power levels, and stack up the cards.
    (Conveniently, it adds up to 100, but this works with any total.)
  3. Roll a 100-sided (or whatever_the_total_is-sided) die. This time, we roll 41.
  4. Leaf through the cards, summing as you go. When your sum exceeds your rolled number, stop on that card.
    • No card - 0; sum = 0; less than 41 -> continue
    • You - 25; sum = 25; less than 41 -> continue
    • Me - 15; sum = 40; less than 41 -> continue
    • Dupree - 60; sum = 100; greater than 41 -> Stop! Dupree wins the draw.

Note that this technique works with real (non-integer) values (we do not round off the result of rand()), and works without having to sort the cards. Sorting in a descending order could yield a *slightly* faster search, depending on the distribution of values. In fact, if you are building the card deck few enough times, and scanning it many times, and never changing the values, you can speed it up even more by writing the running total on each card. This does not match your use-case, though.

I rely on other, less-sleepy monks to warn if I have an off-by-one error, or have completely botched the weighted implementation.
Completely untested code:

use List::Util qw( sum ); sub simulate_mayhem { my @shipsInCombat = @_; # Initiative levels for each ship. # This is a parallel array to @shipsInCombat. my @ship_initiatives = map { $_->{thruster} * 2 + 1; } @shipsInCombat; while ( my $total_initiative = sum @ship_initiatives ) { my $chosen_initiative = rand $total_initiative; my $initiative_sum = 0; # Required - can't use the loop var after the loop # See PBP 6.9. Non-Lexical Loop Iterators my $chosen_ship_number; for my $ship_number ( 0 .. $#shipsInCombat ) { $initiative_sum += $ship_initiatives[$ship_number]; next if $initiative_sum <= $chosen_initiative; $chosen_ship_number = $ship_number; last; } die "Can't happen" if not defined $chosen_ship_number; my $chosen_ship = $shipsInCombat[$chosen_ship_number]; ship_does_something($chosen_ship); # Now reduce that ship to 0, so it cannot be picked again. $ship_initiatives[$chosen_ship_number] = 0; # If you want, you can recalculate {thruster} on any ship # affected by ship_does_something(), as long as you have a # way of tracking the ones that had used their initiative, # and force it back to 0. ### $ship_numbers_that_used_initiative{$chosen_ship_number} = +1; ### recalc_thrusters(\@shipsToAct); ### @ship_initiatives = map { ### $_->{thruster} * 2 + 1; ### } @shipsInCombat; ### ship_initiatives[$_] = 0 for keys %ship_numbers_that_used_ +initiative; } } # Loop exits when all ships have 0 initiative.

Replies are listed 'Best First'.
Re^2: Rolling For Initiative
by JavaFan (Canon) on Dec 19, 2008 at 10:24 UTC
    It seems to me that the OP's algorithm is linear in the sum of the thrusters, while yours in quadratic in the number of ships. However, yours wins in memory usage, your memory usage is linear in the number ships, while the OPs algorithm needs memory linear in the sum of the thrusters.

    But since the OP says it's just 1000 ships, most of them having a weight of less than 10, I doubt the OPs approach (or yours) should be much of a resource hog.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://731452]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (1)
As of 2024-04-25 01:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found