I'm trying to find a good precise numeric solution for my problem.

Background:

I'm trying to create a trade simulation between cities. Each demands a certain amount of a resource and may have a certain number of importers cities that provide that resource. A city needs to take an equal fraction of each importer's resources, and the sum of the amounts taken must add up to the amount demanded. For example, if a city demands 2 bushels of grain, and has three importers, it will take 2/3 of the resources form each importer city, and the sum must add up to 2. Cities will always produce and demand an integer amount of goods, but a city may export to multiple places, so the amount of goods available may be a rational number. At no point are irrational numbers needed.

Limitations:

I'm working in C++ and emscripten. This means I cannot link any library to my project; I must include the whole source. For this reason, I'd prefer not to include any large library. I don't want to use boost. This is a closed source project, so I can't use anything GPL.

Options:

1) Use floating point with an epsilon. But I'm not sure how to pick the right epsilon here. This reproach has the advantage of being fast and simple though.

2) Use fixed point. If I use scaling factor that's a multiple or several lowest factors, it may be precise. But I need to ensure that any numerator of my fractions is a factor of the scaling factor. I'm not sure if I can ensure this. But if a city imports from at most N cites, and the scaling factor is N!, maybe this could work? or some version of it?

3) Use rational numbers. This ensure that calculations are precise all around. If I implement this myself, this is the most complex option.

The Ask:
I'm wondering if anyone here has any suggestions as to which is the best option for my use case, and if there are any libraries I might be able to use.

I would go with "3) Use rational numbers". If your numbers don't get out of whack and you can just use 64 bits for numerator and denominator, the code shouldn't be too bad.

Thanks for the feedback.

Note do to limitations of how I'm compiling this, I can't use 64 bit integers. I can use 32 bit integers or doubles (which are precise up to 52 bits).

You can write a little class that acts like a "large integer", but wraps around two 32-bit integers. Then you can carefully perform integer arithmetic as if you were using a 64-bit integer. I've seen this done before in older games.

Then you can use two of these "large integers" to represents an irrational number.

5 hours ago, King Mir said:

if a city demands 2 bushels of grain, and has three importers, it will take 2/3 of the resources form each importer city, and the sum must add up to 2. Cities will always produce and demand an integer amount of goods, but a city may export to multiple places, so the amount of goods available may be a rational number. At no point are irrational numbers needed.

I don't see why you need floating point numbers for this at all. 

You've got N products and M targets.  Do an integer divide and mod, assign accordingly.

For example, 10 products among 4 cities gives 2 for each, plus 2 remainder. Top two cities are assigned 3, the rest assigned 2.   Or 73 resources among 5 cities, 3 cities assigned 15, two are assigned 14.

Alternatively, if resources travel in smaller packets, draw from all sources until you've got what you need.  If one source runs out early you'll still be drawing from others until the need is satisfied.  

Drawing from all in smaller units also helps when resources may be limited, or when they may change over the time it takes for goods to be transported in the game's simulation. (I'm particularly thinking of games where transporters travel to the location, pick up a bundle of resources, and travel to the destination, repeating until all the bundles are transferred.  Consider the 73 being 15/15/15/14/14 example, if you've got one source that only has 3 of the resources, you'll just keep drawing resources from all the cities until the need is satisfied even if cities run out.  It shows up as an unsatisfied need rather than a demand for a specific number from each location.

4 minutes ago, frob said:

I don't see why you need floating point numbers for this at all. 

You've got N products and M targets.  Do an integer divide and mod, assign accordingly.

For example, 10 products among 4 cities gives 2 for each, plus 2 remainder. Top two cities are assigned 3, the rest assigned 2.   Or 73 resources among 5 cities, 3 cities assigned 15, two are assigned 14.

Alternatively, if resources travel in smaller packets, draw from all sources until you've got what you need.  If one source runs out early you'll still be drawing from others until the need is satisfied.  

Drawing from all in smaller units also helps when resources may be limited, or when they may change over the time it takes for goods to be transported in the game's simulation. (I'm particularly thinking of games where transporters travel to the location, pick up a bundle of resources, and travel to the destination, repeating until all the bundles are transferred.  Consider the 73 being 15/15/15/14/14 example, if you've got one source that only has 3 of the resources, you'll just keep drawing resources from all the cities until the need is satisfied even if cities run out.  It shows up as an unsatisfied need rather than a demand for a specific number from each location.

 

The problem with that is, which cities do I take the remainder from? It can matter because it effects the resources available to be exported to other cities. I could add a priority to importers, but that would be adding interface complexity. In short, it would be different algorithm to do it that way.

I don't plan to have transport delays; the timescale of the game is in years.

You'd have to make that decision no matter what route you took.  Unless it was always exactly divisible there would always be a mismatch.

Maybe pick them randomly through a shuffle or similar, maybe pick them based on some priority like how much the city produces or the number of resource the city is exporting in total, maybe always pick the first ones on the list that was passed to them, maybe let the player choose.

So if you're interested, here's the algorithm I'm using in some detail:

	For each city, A, (in an order that is complex to go into -- this isn't really a for loop but a recursive graph traversal)
	  needs = demand of this city + all cities it exports to
	  available = surplus of all importers added together
	  For each city, B, that imports to A
	    city_available = (production of B)  - (all the previously calculated exports of B)
	    if needs < available
	      import ( (city_available / available) * needs  ) resources
	    else
	       import (city_available) resources
	  (Then calculate how much each city that city A exports to gets -- I haven't done this part yet)
	

The outer order requires that cities have a priority of who they export to. For example a city would choose to export first to London, then everything that's left goes to Canterbury. But London is not going to prefer where its goods come from; demand is equal on all importers, and all of them end up with surplus if they can't pass it on their excess to Canterbury.

Now I wish I could get rid of the need to have export priorities, but I'm pretty sure that would make the whole calculation a way too complex differential equation.

As you can see, this takes an equal amount from each importer, even if it's a fractional amount; no remainder.

It's probably a good idea to think of your game design as if it were a board game, where you are using tokens to represent the goods, so you are forced to use small integers. Typical ways to break ties in board games involve some sort of turn order, so cities are sorted by some criterion (distance to London, size, foundation date...) and then if there is a remainder of 2 after integer division, the top 2 cities get an additional token.

If you don't want this mechanic to affect the game much, make the number of tokens large, so a difference of 1 token won't matter. It's probably not good to obsess over making things exact.

On 8/22/2017 at 9:16 AM, alvaro said:

It's probably a good idea to think of your game design as if it were a board game, where you are using tokens to represent the goods, so you are forced to use small integers. Typical ways to break ties in board games involve some sort of turn order, so cities are sorted by some criterion (distance to London, size, foundation date...) and then if there is a remainder of 2 after integer division, the top 2 cities get an additional token.

If you don't want this mechanic to affect the game much, make the number of tokens large, so a difference of 1 token won't matter. It's probably not good to obsess over making things exact.

 

So the problem with "not obsessing over making things exact" is that that could encourage micromanagement, because a micromanaging player can manage better than the ai in that case. I would prefer a system that just works for player and ai alike.

That said, I'm not sure my current design squares up with that goal entirely; a player will be able to optimize by adjusting export priorities.

With that in mind, I'm inclined to follow your original advice and use rational numbers.