Jump to content
  • Advertisement
Sign in to follow this  
Acharis

Algorithm for automatic ships production

This topic is 1102 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The question is mostly a programming one but also a game design one. The solution does not need to be perfect mathematically, just more or less so it does what the player would expect.

* I prefer it simple, I don't want to spend too much time implementing it

* while performance is not super important I would like it to be reasonably fast

 

 

The player has different ships: Frigates, Destroyers, Battleships, etc. Each costs a different amount of minerals. There is no production queue, instead the player explicitly says "I want 5 battleships and 10 destroyers" (slider on the interface). Then there are battles, combat casualties and other unpredictable things and the game each turn tries to produce the ships according to player wishes (like: if there are 4 battleships and 4 destroyers the game would try to build destroyers first since there is "more of these missing").

 

In addition the player can set priorities like "Frigates are priority 5 and Battleships priority 1, which means Frigates should be built first (it should "stack" with the "the player requested X ships and there are only Y existing"). Actually, it will be more complex (like certain fleets having higher priorities and separate pool of ships for each fleet) but for the purpose of the topic just the 3 ship types should be enough.

 

So, we have these variables:

NUMBER OF SHIPS EXISTING CURRENTLY (PER SHIP TYPE)

NUMBER OF SHIPS THE PLAYER REQUESTED TO EXIST (PER SHIP TYPE)

PRIORITY (PER SHIP TYPE)

COST IN MINERALS OF ONE SHIP (PER SHIP TYPE)

MINERALS AVAILABLE (GLOBAL)

 

Now, I look for an algoritm that would take these variables into account and produce these ships (again, it does not need to be perfect).

Tip: I was thinking of a statistical algoritm (a chance of building a ship based on requested to exist + priority) but that's just a random thought and it could be done different way.

 

 

A rough concept how it could work (again, just my example, feel free to propose something completelly different):

for(;;) // infinite loop
{
  for(iterate through ship types)
  { 
    CShip ship;
    if(minerals<ship->cost) EXIT;  // out of resources, stop production for this turn
    if(no more build requests) EXIT;  // all done, stop production for this turn
    if(ship->requiredtoexist<ship->number) continue; // skip, no needed to build that one

    // decide if build it now (based on requiredtoexist & priority)
    ...

    produceOneShip(ship->type); // just one ship build per iteration
    minerals-=ship->cost;
  }
}

Share this post


Link to post
Share on other sites
Advertisement
I am going to ignore costs for now, because I don't fully understand how that works in your game (e.g., if I don't have enough money for a big ship now, should I always build a cheaper one, or can I wait a bit until we have saved more money?).

The problem of assigning the next ship so the total ship distribution more closely resembles a desired one is something I have encountered before. You can compute for each type the quantity

score[type] = desired_number[type] / (0.5 + existing_number[type])

This is a measure of how under-represented this type of vessel is, proportionally. Now just pick the maximum and build that. If you are interested, the formula comes from the Sainte-Laguë method for assigning seats in parliamentary elections.

You can introduce priorities into the mix perhaps by modifying the formula a bit. For instance, you could make the priority be a multiplicative factor in the score[type] formula.

Share this post


Link to post
Share on other sites

 I'd go a direct approach.

 

For larger systems I might go with a statistical approach, but this is small.
 
You already a number of each item to build, and priorities associated with them.  
 
Now you need a queue of one item, or a "next item to build" slot.  This lets the player know what the AI is planning to do, making them happier.  You might want a longer queue, in that case just continue with this routine removing the items from the list as they get added to the queue.  Adding some complexity, you could let them cancel items or move items in the queue, pushing queued items forward in line and then filling the back again.  
 
Run this:

If nothing on queue (or empty spots in a multi-item queue):
  For each priority in priority order:
    If items needed at this priority:
      Build collection of all needed items in that priority
      Shuffle collection (or just pick a random item number within the collection)
      Queue first item in shuffled collection (and subsequent items if multiple slots)

If you've got a longer queue with room at the end, use that to fill up slots at the end until all slots are filled.

That method won't work too well if you are queuing up many thousand items, but from your description you're in single digits and double digits. A simple shuffle will mean slots with more items get built more often by virtue of it appearing more often. No fancy weighting required.
 

 

 

You'll need to decide what to do when the player adjusts the sliders.  You might do nothing (the easiest option) allowing the current queue items to build.  You might validate that the first item in the queue is still the highest priority and then insert items at their desired spot. You might remove items if they dropped the needed count to zero. 

Share this post


Link to post
Share on other sites

You can do a random draw.

 

Assume eg you have 3 ship types A, B, C. You have 3 priorities prA, prB, prC. You have 3 missing ship counts mA, mB, mC.

Each missing ship is it "priority" worth for getting build (higher priority means bigger chance of getting build). Inverting priority is not difficult if you need that.

Then do something like:

missing = mA*prA + mB*prB + mC*prC
val = random(0, missing)  // Random integer value 0 upto but excluding 'missing'.
if val < mA*PrA then { buildA(); return; }
val = val - mA*prA;
if val < mB*prB then { buildB(); return; }
buildC();
return;

Bigger priority or more missing ships within one shiptype makes that it gets a bigger chunk in the [0, missing) interval, and thus a higher chance of getting picked.

 

 

With lack of money, you may have a problem here. The seemingly simple solution of dropping shiptypes that are too costly means, you will spend your little money on the smaller (cheaper) shiptypes, and never ever building anything big (costly).

You either have to block building, waiting for money, or allow the user to steer the behavior.

Share this post


Link to post
Share on other sites

The collections of things to build at each priority can be persistent, since they change only on sparse and easily handled events: a ship ceases to exist (build one more), a ship is gained without being built (build one less), player changes number wanted (delete or add the appropriate number of ships to build), ship type changes priority (move all ships to build of one type between collections), and little more.

I suggest making multiple factories and multiple ships under construction the normal case: it's realistic, it doesn't harm game balance, and it allows conquest, construction and improvement of shipyards to be important that with an abstract system.

Share this post


Link to post
Share on other sites

I'd go with a slot mechanic using std::map or std::unordered_map (if you want hard optimization).

 

Define a ShipData structure:

- all game data (stats, etc).

- number of missing ships to build (at the production phase)

- priority

- priority counter (explained later)

 

Now the map should be something like:

std::map<string, ShipData*> m_SlotsData;

 

During the production stage (when a player sets the sliders and proceeds), you compute the normalized priorities (you divide them all by the greatest priority).

All priority counters are reset to 0.

You run an infinite loop which adds normalized priority to the priority counter value. (example: you had a ship with priority=5 and another with priority=2; normalized priorities are then 1 and 0.4, respectively)

Whenever any of priority counters reaches or exceeds 1 AND there are remaining funds, you build that ship, decrease the number of missing ships in that slot by 1 and decrease the priority counter by 1.

If more than one slot reaches 1 during a single loop iteration, build the one with greatest value atm; in case of ties, use random().

When lowest cost of types_of_ships_to_build exceeds global funds or no more ships to build, BREAK.

Edited by Ryder052

Share this post


Link to post
Share on other sites


score[type] = desired_number[type] / (0.5 + existing_number[type])
Implemented that one, works great. Thanks everyone :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!