Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Algorithm Help

by dreadpiratepeter (Priest)
on Jan 18, 2010 at 18:19 UTC ( #818015=perlquestion: print w/replies, xml ) Need Help??
dreadpiratepeter has asked for the wisdom of the Perl Monks concerning the following question:

I could use some help here as I am a bear of little brain. I am writing some rpg stuff and I am working on a method that generates random items a la Diablo. Things like a "Flaming silver +3 longsword of Slay Undead".

The items are of a form:

<prefix1>? <prefix2>{0,3) <plus> <weapon_type> <suffix>?

For purposes of discussion assume my list of each type of component looks like:

@prefix1 = ( [flaming => 2], [frost => 2], [acid => 4], ... );
where the second parameter is a weight. The weapon type is just a simple unweighted choice and for argument the plus runs from 0-5 with the value also being the weight.

So, for example:

  +2 mace  = weight 2
  Flaming longsword = weight 2
  Acid +3 dagger = weight 7

Here is the challenging part, that I haven't solved. Given a weight range, generate an item within that range.

Note that you can add only 1 prefix and 1 suffix to an item, but you can add up to 3 prefix2.

I had a few thoughts as to an algorithm, but they all have problems:

  • I could just randomly generate items till I got one in the range. Obviously, this is flawed because it could take a very long time
  • Randomly choose a thing to add to the item (that is still available), keep a running weight and stop when I hit the right range or run out of available slots. I think this would bias the items toward high pluses and large numbers of prefix2 parts, because a low weight for prefix and suffix would leave a lot of weight left to fill with prefix2 items. Also it would seriously lower the chance of getting items the don't have all of the component types.
  • Some sort of heuristic that would set an appropriate lower limit on weight to prevent the above bias from occuring. This would be good because higher weight items should not have a lot of lower weight compoents.

I hope it is clear what I am trying to do. I am not looking for code, just some ideas for an elegant solution.

"Worry is like a rocking chair. It gives you something to do, but it doesn't get you anywhere."

Replies are listed 'Best First'.
Re: Algorithm Help
by jethro (Monsignor) on Jan 18, 2010 at 19:48 UTC

    How about this:

    1) choose a weight among the weight range randomly

    2) With the weight fixed, randomly distribute the weight to prefix1,prefix2 and suffix. I.e. for a weight of 8 you might get a distribution of 3,3,2 (or 3,1,4 or 0,6,2...)

    3) Now randomly choose a prefix1 with the chosen weight (or none if prefix1 weight is 0). In the example that would be 3. Also select one suffix with the chosen weight (2 in the example). And finally select as many prefix2s until you have reached the chosen weight for prefix2s. Since you could get more than 3 items for prefix2, you should add a step where you combine two lesser prefixes into one (of their combined weight) until you reach 3 items.

    If you still get too many prefix2s in your items, you could have higher weight prefixes more often in your prefix2-table than lower weight prefixes. For example a prefix of weight 4 would be 4 times in the table, a prefix of weight 1 only once (this is just a simple method to select higher items more often. If you don't like that, there are other methods)

Re: Algorithm Help
by BrowserUk (Pope) on Jan 18, 2010 at 19:31 UTC

    Am I right in thinking that the term "weight" in your examples has nothing to do with the probabilities of a particular weapon or prefix being chosen, but rather the in-game strength or effectiveness of the composite weapon?

    Ie. It is not your intention that 'acid' should be chosen twice as frequently as 'fire' or 'frost'?

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      Yes, you are correct. I should probably not use that term. Lets call it strength instead

      "Worry is like a rocking chair. It gives you something to do, but it doesn't get you anywhere."
Re: Algorithm Help
by Anonymous Monk on Jan 18, 2010 at 18:35 UTC
    Wouldn't it be easy to just randomly choose a prefix from a cache ?
    Putting the probabilities aside, it's easy to deterministically generate all possible prefixes, and to classify them into weight categories.
    With all prefixes separated by weight it's also easy to randomly choose one, given a weight.

      Yes, but the issue is that I will pass in a weight range for an object, not a prefix. the total of prefix, all prefix2, plus and suffix is the weight of the object. and that needs to be in the given range

      "Worry is like a rocking chair. It gives you something to do, but it doesn't get you anywhere."
        sorry, now reading my reply again made me realize I used 'prefix' to describe 2 different things.
        I meant generate all possible combinations, classify those combinations by weight and, given a weight range, randomly choose from this 'combination pool'
Re: Algorithm Help
by tilly (Archbishop) on Jan 19, 2010 at 04:44 UTC
    Here are two possible ideas for a solution.

    The first is that rather than target a "weight range", have some tunable parameters that are correlated with the likely weight of the result. Then insert values for those parameters, and pick your combination of items, pluses, etc.

    The second is to go through an iterative generative process. Make it look like this. On each iteration you randomly pick a trait to modify out of (prefix, prefix2, plus, weapon_type, suffix). If you pick a prefix2 and you have one, you randomly decide whether to regenerate the existing or generate a new one. (If you have 2 already you repeat this decision making process with the third.) Then you make a random choice of that component. (For a prefix2 make a valid choice be "none".) If adding (replacing if need be) that characteristic makes your weapon closer to the target weight, do so.

    Continue this process until the target weight is reached, or until a fixed number of rounds has passed.

    In essence this is a genetic algorithm, where you're trying to evolve a random weapon that fits your target weight.

Re: Algorithm Help
by TGI (Parson) on Jan 19, 2010 at 01:50 UTC

    You might want to edit your post to clarify that weight does not affect the probability of a given selection.

    Two ideas

    You could pre-calculate (perhaps write to data files if there are many) all possible items and their strength/weight values. If your list of possible weight values is dense (few skipped values) put an array of items at each weight at a coresponding index in a master array. So:

    my @items = ( # 0 [ 'sword', 'mace', 'turtle' ], # 1 [ '+1 sword', '+1 mace', '+1 turtle' ], # 2 [ 'frost sword', 'frost mace', 'frost turtle', 'flame sword', 'flame mace', 'flame turtle' ], ... );

    If the set of weights is sparse, you might use a hash instead.

    Then if you want to select a random item of weight 3-5, you can do:

    my @in_range = map @{$items[$_]}, 3..5; my $item = $in_range[ int rand( @in_range ) ];

    Another way, would be:

    1. Pick a random weight value in your range. eg 7
    2. Prefix list is sorted by weight, and starts with an entry for ['' => 0].
    3. Find last prefix with weight less than or equal to weight. Eg. Pointy (6)
    4. Pick Random Prefix up to max prefix from last step. eg. Acid (4)
    5. Set plus value equal to desired weight - prefix weight. Eg. Plus = 7 - 4 = 3
    6. Result: Acid +3 Sword

    TGI says moo

Re: Algorithm Help
by scorpio17 (Abbot) on Jan 19, 2010 at 15:00 UTC

    sorry - but I think you're going about this all wrong!

    Having played lots of games like this, I think it's dumb to generate random treasure in a way they will frequently give high-level players garbage items, and yet might give a low level player a game-breaking, super-powerful item.

    I suggest the following: generate a table of all known weapons, and assign each a cost. For example, let's say a +1 sword costs 100gp, a +2 sword costs 400gp, a +3 sword costs 900gp, etc. Adding an energy-type bonus (flaming, frost, acid, etc.) counts the same as an extra plus, i.e., a "+2 flaming sword" costs the same as a "+3 sword".

    Once all weapons and their costs are tabulated, bin them accordingly (the set of all 100gp weapons, the set of all 200gp weapons, etc.). Each area of the game should have a standard difficulty level used to determine appropriate treasure (level 1 of the dungeon has 100gp treasures, level 2 has 400gp, level 3 900gp, etc.). Then for a given treasure, randomly select an item from the appropriate bin. (the same metric would be used to determine which monsters to use in order to provide a good challenge)

    An easy modification would be to generate a random number between 1 and 100, and do something like this:

    1-5 use treasure for level-2
    6-20 use treasure for level-1
    21-80 use treasure appropriate for this level
    81-95 use treasure for level+1
    96-100 use treasure for level+2

    So, on average, you get a level appropriate treasure, but you have a 15% chance of getting something better (and and equal change of getting something not quite so good).

      You may have misread something. What you call gp he calls weight. Same thing though basically.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://818015]
Approved by Corion
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (4)
As of 2017-01-22 06:57 GMT
Find Nodes?
    Voting Booth?
    Do you watch meteor showers?

    Results (186 votes). Check out past polls.