I have a field of tiles - basically each tile is a country that has some kind of sovereign. The tiles - countries - have different weight. For now I use some numerical value but in the future the weight will depend on tile size, produced resources and so on.

So I want for those countries to make alliances if their sole weight is much lower - or at least lower than a certain threshold - than the weight of the neighborhood tile (each sovereign is basically a primitive AI at that stage that is able to make decision to create the alliance). Here is couple of scenarios

enter image description here

Here are the examples for bigger maps with possible alliances

enter image description here

So my question is - is there some kind of algorithm that allows to achieve that or I have to create it myself or use training sets for AI to gain the ability to form alliances?

  • 2
    \$\begingroup\$ Looks close to the Bin packing problem, which is NP-hard. A bit harder to be precise since the bin size is not fixed. \$\endgroup\$
    – wondra
    May 7 '18 at 14:44
  • \$\begingroup\$ @wondra quite possible. need to dig into it. \$\endgroup\$
    – lapots
    May 8 '18 at 6:53

It seems my problem is the similar to Bin packing problem mentioned by @wondra. Here is the definition of bin packing problem

Given a multiset S = { s1, s2..., sN } of N elements and a bin
capacity C, all positive integers, the bin packing problem is
to separate the elements of S into as few subsets (bins) as
possible, such that the sum of each subset is no greater than C

The definition of my problem is

Given a multiset S = { s1, s2..., sN } of N elements and number C,
all positive integers, my problem is to combine elements of S
into a few subsets, such that the sum of each subset is no
much greater than C (or possible threshold)

They are indeed similar


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .