Skip to main content
gamedev.net
🔒 Locked

generating combinations

Started by telengard 6 replies 1.3k views
Original Post
telengard
telengard
I'm working on an MtG style minis game and I need to generate combinations relating to assigning damage. I do rules enforcement and AI and I've run into a snag. I understand generating basic combinations but this for some reason is throwing me for a loop. I have to generate all the combinations of assigning X damage (just a number) to N minis. Each mini has 2 stats that the damage relates to (defense and life). If I assign >= defense 1 thing happens, >= life something else. Ideally I'd generate all the combinations that go though assigning damage amounting to each mini's life and defense until I run out of damage to assign. Remainder damage that isn't enough for the defense or life would still be assigned. This is really hard to articulate for some reason. I am currently doing it 1 point of damage at a time for each mini over and over but the rules state that damage is assigned all at once for each mini. Any ideas or links to read would be greatly appreciated. I've done some searching and have found lots of stuff, but nothing that seems similar to this. ~telengard
alvaro
alvaro
This sounds like the kind of problem that is easily solved with backtracking. I don't think I fully understand the statement of the problem, though. Perhaps a simple example would help clarify things.
telengard
telengard
Sorry about that, I was afraid I wasn't doing a very good job of presenting the problem.

As an example I have to assign 10 damage to 3 miniatures. Let's say they all have a defense of 3 and a life of 5 and are named 'A', 'B', and 'C'.

A rule I have to employ is that all damage must be assigned up until the point that all creatures have damage applied that is at least equal to the higher of the 2 stats (defense/life). The order doesn't matter. I just need all unique combinations.

I need to come up with all combinations of assigning the damage to all 3 miniatures where I assign up to their defense and also their life.

So going with the above numbers the combinations would look something like this:

A assigned 5, B assigned 3, C assigned 2
A assigned 5, B assigned 2, C assigned 3
A assigned 3, B assigned 2, C assigned 5
A assigned 3, B assigned 5, C assigned 2
A assigned 2, B assigned 5, C assigned 3
A assigned 2, B assigned 3, C assigned 5
A assigned 5, B assigned 5, C assigned 0
A assigned 5, B assigned 0, C assigned 5
A assigned 0, B assigned 5, C assigned 5

I think that is all the combinations for that scenario. With each one I've assigned up to either their life or defense and then applied the remainder as needed.

Does it make more sense now? I currently have code to do come up with the combinations for attackers and that was pretty straightforward but this one I'm finding much more difficult to put into code.

I will look into "backtracking", thanks for that info.

~telengard
alvaro
alvaro
Oh, I've solved a very similar program before. It is kind of tricky, though.

There are still a few details that are not clear. For instance, is it OK to assign more damage to a miniature than the maximum of its life and its denfense? Otherwise, what do you do if the total damage is too much to distribute among the miniatures? Depending on exactly how that works, you'll have to adjust the algorithm a bit. In the code below I am restricting the distributions of damages to those that distribute the whole damage without going beyond the maximum of life and defense at any miniature.

I apologize for the lack of comments. If you have questions on how this code works, feel free to ask.

#include <iostream>#include <vector>#include <set>struct MiniatureLifeDescription {  int defense, life;    MiniatureLifeDescription(int defense, int life)    : defense(defense), life(life) {  }};class CombinationGenerator {  std::vector<MiniatureLifeDescription> minis;    std::vector<int> current_distribution;  std::set<std::vector<int> > result;    int n;    void recursively_generate_combinations(int damage, int i) {    if (i==n) {      if (damage==0)        result.insert(current_distribution);      else {        for(int k=0; k<i; ++k) {          if(current_distribution[k]+damage <= minis[k].life &&             current_distribution[k]+damage <= minis[k].defense) {            current_distribution[k]+=damage;            result.insert(current_distribution);            current_distribution[k]-=damage;          }        }      }    }    else {      if(damage>=minis.life) {        current_distribution+=minis.life;        recursively_generate_combinations(damage-minis.life,i+1);        current_distribution-=minis.life;      }      if(damage>=minis.defense) {        current_distribution+=minis.defense;        recursively_generate_combinations(damage-minis.defense,i+1);        current_distribution-=minis.defense;      }      recursively_generate_combinations(damage,i+1);    }  }  public:  CombinationGenerator(std::vector<MiniatureLifeDescription> const &minis)    : minis(minis), current_distribution(minis.size(),0), n(minis.size()) {  }    std::set<std::vector<int> > generate(int damage) {    recursively_generate_combinations(damage, 0);    return result;  }};int main() {  MiniatureLifeDescription minis[3]={    MiniatureLifeDescription(3,5),    MiniatureLifeDescription(3,5),    MiniatureLifeDescription(3,5)  };    CombinationGenerator cg(std::vector<MiniatureLifeDescription>(minis, minis+3));  std::set<std::vector<int> > distributions = cg.generate(10);  for(std::set<std::vector<int> >::const_iterator it=distributions.begin(),end=distributions.end();      it!=end; ++it) {    std::vector<int> const &v=*it;    for(std::vector<int>::const_iterator v_it=v.begin(), v_end=v.end(); v_it!=v_end; ++v_it)      std::cout << *v_it << ' ';    std::cout << '\n';  }}


telengard
telengard
Wow, thanks for the code! To answer your question, yes it is legal to "overkill" and there is 1 piece in the game that *could* benefit from that in some circumstances so I probably should support it. Problem is, all these extra steps kills the minimax performance. I was thinking for the AI just always ignore the overkilling.

Technically speaking *any* combination of damage is legal and for a very good player it can be very important due to some aspects of the games. The biggest one being that damage persists until the end of the phase and minis can move around etc. I imagine that many combinations would be HUGE.

Maybe it's better to be correct than super fast. :)

thanks again!
~telengard
telengard
telengard
I went through the thought process of implementing this and spot checking pieces' abilities to see if it would still work. I don't think it will unfortunately. I think I'll need to keep my 1 point of damage at a time and re-evaluating but then modifying how it's actually applied.

The issue shows up with pieces with these abilities. One piece prevents damage (2 points per attack to each piece) and another one has a rule (Bodyguard) that says "you can't assign damage to others without this ability until this one has been assigned enough past it's defense or life".

So with the generated combinations, the piece that prevents damage would work fine but then after applying, the rules for Bodyguard's condition for assignment to the others wouldn't be met since 2 points of damage was prevented.

I'm thinking I have to do something like this:

Apply damage 1 point at a time (as I'm doing now) but then keep track of the total and apply that to the game state going through the "hooks" used for overriding the rules (which for example, the piece that prevents damage would do). I think I have to do this because damage is applied in total not one point at a time. If it were actually applied one point at a time, the piece that prevents damage (in this case 2 points of damage) would prevent all of it.

Not sure if this makes sense, but I can put in more detail if necessary. I'm curious to hear if anyone has any other ideas on how to deal with this...

~telengard
alvaro
alvaro
I went through the trouble to write some code that satistied your original description of the problem. If the specification changes, well you just don't pay me enough to keep up. :)

You'll have to try to learn the idea behind the code I posted and then adapt it to your [new] specific needs.
telengard
telengard
Hey there,

Sorry, didn't mean to come across as ungrateful. I really appreciate the code and your time. I do think it will come in handy with some modifications as you mentioned.

~telengard

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.