Sign in to follow this  
King Mir

Dividing things up and adding things back together precision problems

Recommended Posts

King Mir    2490

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.

Edited by King Mir

Share this post


Link to post
Share on other sites
alvaro    21266

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.

 

Share this post


Link to post
Share on other sites
King Mir    2490

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).

Share this post


Link to post
Share on other sites
Randy Gaul    2762

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.

Edited by Randy Gaul

Share this post


Link to post
Share on other sites
frob    44973
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.

 

Share this post


Link to post
Share on other sites
King Mir    2490
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.

Share this post


Link to post
Share on other sites
frob    44973

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.

Share this post


Link to post
Share on other sites
King Mir    2490

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.

Share this post


Link to post
Share on other sites
alvaro    21266

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.

 

Share this post


Link to post
Share on other sites
King Mir    2490
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Similar Content

    • By MarcusAseth
      this is super strange...
      I have this function here:
      template<typename TFirst, typename... TArgs> bool util::LogConsole(const TFirst& first, const TArgs&... rest) { std::cout << first << " "; return LogConsole(rest...); } bool util::LogConsole() { std::cout << std::endl; return false; } it's recursive, keep printing "first" and recursively sending the rest, until rest is empty and the overload taking no argument is called, which just print a newline. Ignore the bool return.
      Anyway, now I have this code somewhere else:
      for (auto& E : Entities) { float valx = E->GetPosition().x;//return 751 float valy = E->GetPosition().y;//return 838 LogConsole(valx, valy); } Entities is a vector<unique_ptr<Entity>> which currently only contains the derived from Entity player Paddle, so I access the Base class Entity method called GetPosition, which is the center pivot coordinates of the object.
      I pass the variable to LogConsole which predictably prints:
      But not I try to call LogConsole without those 2 variables inbetween, like this:
      for (auto& E : Entities) { LogConsole(E->GetPosition().x, E->GetPosition().y); } and watch what kind of output I get! :
      ... the y value is an unreasonable value o_o
      How is this even possible?! Since only the second value is being affected, my assumption is that there is some weird interplay with the second template parameter, the variadic argument...but I wasn't able to debug it even stepping trough it line by line...can anyone come with an explanation for this really strange behaviour?
    • By MarcusAseth
      Maybe today I'm confused and I'm missing the obvious...
      I've made this simple struct inside my Utility.h 
      template<typename TFirst, typename TSecond> struct Pair { Pair(TFirst f, TSecond s):First{f},Second{s}{} TFirst First; TSecond Second; }; And I'm using it from App.h (which #include "Utility.h") like so:
      App.h
      Pair<Uint32, Uint32> GetWindowSize(); App.cpp
      Pair<Uint32, Uint32> App::GetWindowSize() { return Pair<Uint32, Uint32>(Width,Height); } And I'm getting a cascade of errors ALL on line 39 (image below).
      Any idea what I am doing wrong this time? x_x

       
      EDIT: please mod delete this topic, I just remembered Utility.h put everything inside namespace util, sorry x_x
    • By noodleBowl
      I've gotten to part in my DirectX 11 project where I need to pass the MVP matrices to my vertex shader. And I'm a little lost when it comes to the use of the constant buffer with the vertex shader
      I understand I need to set up the constant buffer just like any other buffer:
      1. Create a buffer description with the D3D11_BIND_CONSTANT_BUFFER flag 2. Map my matrix data into the constant buffer 3. Use VSSetConstantBuffers to actually use the buffer But I get lost at the VertexShader part, how does my vertex shader know to use this constant buffer when we get to the shader side of things
      In the example I'm following I see they have this as their vertex shader, but I don't understand how the shader knows to use the MatrixBuffer cbuffer. They just use the members directly. What if there was multiple cbuffer declarations like the Microsoft documentation says you could have?
      //Inside vertex shader cbuffer MatrixBuffer { matrix worldMatrix; matrix viewMatrix; matrix projectionMatrix; }; struct VertexInputType { float4 position : POSITION; float4 color : COLOR; }; struct PixelInputType { float4 position : SV_POSITION; float4 color : COLOR; }; PixelInputType ColorVertexShader(VertexInputType input) { PixelInputType output; // Change the position vector to be 4 units for proper matrix calculations. input.position.w = 1.0f; // Calculate the position of the vertex against the world, view, and projection matrices. output.position = mul(input.position, worldMatrix); output.position = mul(output.position, viewMatrix); output.position = mul(output.position, projectionMatrix); // Store the input color for the pixel shader to use. output.color = input.color; return output; }  
    • By MarcusAseth
       
      I start by saying that I am aware that what I am trying to do can easily be achieved trough the <functional> part of the library or trough a Functor or a Lambda, but I wanted to see this in template form.(Code below)
      So the first function works, the find_if algorithm find the first value in a vector greater than the specified parameter, but there is no template argument deduction for that function call because the algorithm require a pointer to a function but at that time it is not know I will pass an int into it, and so I need to specify like this:
      LargerThan_NoDeduction<30,int> But this seems ugly because now I have to take care of match the two, like <31.2, double>, and the worst part is that if I now decide to pass something else, like a <'d',char> or a <-10,float> , the function expects a size_t as first template parameter, so this won't do.
      So what I wanted to achieve was to pass a predicate to an algorithm in the form of
      LargerThan(30) where the template part of it takes care both of storing the data value (in this case 30, but could be a 'c') and deducing the type we compare from out of it, so in this case int.
      So I have a function LargerThan(Type) that returns a function pointer and passes down the value to an helper function which takes both the value and the deduced type, so I don't have to type them myself.
      Problem is, this helper function still has an auto in the first template parameter, and the compiler doesn't like this
      How would you make this work trough template magics?
      #include <iostream> #include <vector> #include <algorithm> using namespace std; //// template<size_t TestCase,typename Type> bool LargerThan_NoDeduction(Type value) { return value > TestCase; } //// template<typename Type> auto LargerThan(Type TestCase)-> bool(*)(Type) { return LargerThan_helper<TestCase, Type>; } template<auto TestCase, typename Type> //auto here is not liked!!! bool LargerThan_helper(Type value) { return value > TestCase; } //// int main() { vector<int> vec{ 0,11,21,35,67,102 }; //Must specify size and type. auto p = find_if(vec.begin(), vec.end(), LargerThan_NoDeduction<30,int>);//WORKS if (p != vec.end()) { cout << *p << endl; }//WORKS //Deduces type from the value passed. p = find_if(vec.begin(), vec.end(), LargerThan(30));//ERROR if (p != vec.end()) { cout << *p << endl; }//ERROR return 0; }  
    • By markshaw001
      hi i am new to opengl can someone here tell me how to render this 2d shape i want to make curve or arc in 2d in between two lines its a rough sketch i made i tried the internet but could not find much help beacuse their were no specific tutorials of making arcs or curves

  • Popular Now