# Dividing things up and adding things back together precision problems

## Recommended Posts

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.

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 on other sites

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 on other sites

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 on other sites

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 on other sites
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 on other sites
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 on other sites

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 on other sites

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 on other sites

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 on other sites
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.

## Create an account

Register a new account

• ### Similar Content

• I am a talented 2D/3D artist with 3 years animation working experience and a Degree in Illustration and Animation. I have won a world-wide art competition hosted by SFX magazine and am looking to develop a survival game. I have some knowledge of C sharp and have notes for a survival based game with flexible storyline and PVP. Looking for developers to team up with. I can create models, animations and artwork and I have beginner knowledge of C sharp with Unity. The idea is Inventory menu based gameplay and is inspired by games like DAYZ.
Here is some early sci-fi concept art to give you an idea of the work level. Hope to work with like minded people and create something special. email me andrewparkesanim@gmail.com.
Developers who share the same passion please contact me, or if you have a similar project and want me to join your team email me.
Many thanks, Andrew.

• By mike44
Hi
saw in dependency walker that my app still needs msvcp140d.dll even after disabling debug.
What did I forget in the VS2017 release settings? After setting to multithreaded dll I get linker errors.
Thanks

• So I have been playing around with yaml-cpp as I want to use YAML for most of my game data files however I am running into some pretty big performance issues and not sure if it is something I am doing or the library itself.
I created this code in order to test a moderately sized file:
Player newPlayer = Player(); newPlayer.name = "new player"; newPlayer.maximumHealth = 1000; newPlayer.currentHealth = 1; Inventory newInventory; newInventory.maximumWeight = 10.9f; for (int z = 0; z < 10000; z++) { InventoryItem* newItem = new InventoryItem(); newItem->name = "Stone"; newItem->baseValue = 1; newItem->weight = 0.1f; newInventory.items.push_back(newItem); } YAML::Node newSavedGame; newSavedGame["player"] = newPlayer; newSavedGame["inventory"] = newInventory; This is where I ran into my first issue, memory consumption.
Before I added this code, the memory usage of my game was about 22MB. After I added everything expect the YAML::Node stuff, it went up to 23MB, so far nothing unexpected. Then when I added the YAML::Node and added data to it, the memory went up to 108MB. I am not sure why when I add the class instance it only adds like 1MB of memory but then copying that data to a YAML:Node instance, it take another 85MB of memory.
So putting that issue aside, I want want to test the performance of writing out the files. the initial attempt looked like this:
void YamlUtility::saveAsFile(YAML::Node node, std::string filePath) { std::ofstream myfile; myfile.open(filePath); myfile << node << std::endl; myfile.close(); } To write out the file (that ends up to be about 570KB), it took about 8 seconds to do that. That seems really slow to me.
After read the documentation a little more I decide to try a different route using the YAML::Emitter, the implemntation looked like this:
static void buildYamlManually(std::ofstream& file, YAML::Node node) { YAML::Emitter out; out << YAML::BeginMap << YAML::Key << "player" << YAML::Value << YAML::BeginMap << YAML::Key << "name" << YAML::Value << node["player"]["name"].as<std::string>() << YAML::Key << "maximumHealth" << YAML::Value << node["player"]["maximumHealth"].as<int>() << YAML::Key << "currentHealth" << YAML::Value << node["player"]["currentHealth"].as<int>() << YAML::EndMap; out << YAML::BeginSeq; std::vector<InventoryItem*> items = node["inventory"]["items"].as<std::vector<InventoryItem*>>(); for (InventoryItem* const value : items) { out << YAML::BeginMap << YAML::Key << "name" << YAML::Value << value->name << YAML::Key << "baseValue" << YAML::Value << value->baseValue << YAML::Key << "weight" << YAML::Value << value->weight << YAML::EndMap; } out << YAML::EndSeq; out << YAML::EndMap; file << out.c_str() << std::endl; } While this did seem to improve the speed, it was still take about 7 seconds instead of 8 seconds.
Since it has been a while since I used C++ and was not sure if this was normal, I decided to for testing just write a simple method to manually generate the YAMLin this use case, that looked something like this:
static void buildYamlManually(std::ofstream& file, SavedGame savedGame) { file << "player: \n" << " name: " << savedGame.player.name << "\n maximumHealth: " << savedGame.player.maximumHealth << "\n currentHealth: " << savedGame.player.currentHealth << "\ninventory:" << "\n maximumWeight: " << savedGame.inventory.maximumWeight << "\n items:"; for (InventoryItem* const value : savedGame.inventory.items) { file << "\n - name: " << value->name << "\n baseValue: " << value->baseValue << "\n weight: " << value->weight; } } This wrote the same file and it took about 0.15 seconds which seemed a lot more to what I was expecting.
While I would expect some overhead in using yaml-cpp to manage and write out YAML files, it consuming 70X+ the amount of memory and it being 40X+ slower in writing files seems really bad.
I am not sure if I am doing something wrong with how I am using yaml-cpp that would be causing this issue or maybe it was never design to handle large files but was just wondering if anyone has any insight on what might be happening here (or an alternative to dealing with YAMLin C++)?

• So I am trying to using Yaml as my game data files (mainly because it support comments, is a bit easier to read than JSON, and I am going to be working in these files a lot) with C++ and yaml-cpp (https://github.com/jbeder/yaml-cpp) seems like the most popular library for dealing with it however I am running into an issue when using pointers.
Here is my code:
struct InventoryItem { std::string name; int baseValue; float weight; }; struct Inventory { float maximumWeight; std::vector<InventoryItem*> items; }; namespace YAML { template <> struct convert<InventoryItem*> { static Node encode(const InventoryItem* inventoryItem) { Node node; node["name"] = inventoryItem->name; node["baseValue"] = inventoryItem->baseValue; node["weight"] = inventoryItem->weight; return node; } static bool decode(const Node& node, InventoryItem* inventoryItem) { // @todo validation inventoryItem->name = node["name"].as<std::string>(); inventoryItem->baseValue = node["baseValue"].as<int>(); inventoryItem->weight = node["weight"].as<float>(); return true; } }; template <> struct convert<Inventory> { static Node encode(const Inventory& inventory) { Node node; node["maximumWeight"] = inventory.maximumWeight; node["items"] = inventory.items; return node; } static bool decode(const Node& node, Inventory& inventory) { // @todo validation inventory.maximumWeight = node["maximumWeight"].as<float>(); inventory.items = node["items"].as<std::vector<InventoryItem*>>(); return true; } }; } if I just did std::vector<InventoryItem> items and had the encode / decode use InventoryItem& inventoryItem everything works fine however when I use the code above that has it as a pointer, I get the following error from code that is part of the yaml-cpp library:
impl.h(123): error C4700: uninitialized local variable 't' used The code with the error is:
template <typename T> struct as_if<T, void> { explicit as_if(const Node& node_) : node(node_) {} const Node& node; T operator()() const { if (!node.m_pNode) throw TypedBadConversion<T>(node.Mark()); T t; if (convert<T>::decode(node, t)) // NOTE: THIS IS THE LINE THE COMPILER ERROR IS REFERENCING return t; throw TypedBadConversion<T>(node.Mark()); } }; With my relative lack of experience in C++ and not being able to find any documentation for yaml-cpp using pointers, I am not exactly sure what is wrong with my code.
Anyone have any ideas what I need to change with my code?

• I already asked this question on stack overflow, and they got pissed at me, down-voted me and so forth, LOL .... so I'm pretty sure the answer is NO, but I'll try again here anyway just in case..... Is there any way to get the size of a polymorphic object at run-time? I know you can create a virtual function that returns size and overload it for each child class, but I'm trying to avoid that since (a) it takes a virtual function call and I want it to be fast and (b) it's a pain to have to include the size function for every subclass. I figure since each object has a v-table their should be some way since the information is there, but perhaps there is no portable way to do it.

• This is the code I have:
//Create Window     DWORD windowStyle = WS_VISIBLE;     DWORD windowExStyle = WS_EX_OVERLAPPEDWINDOW;     SetThreadDpiAwarenessContext(DPI_AWARENESS_CONTEXT_SYSTEM_AWARE);     RECT client{ 0, 0, 100, 40 };     UINT dpi = GetDpiForSystem();     AdjustWindowRectExForDpi(&client, windowStyle, false, windowExStyle, dpi);     UINT adjustedWidth = client.right - client.left;     UINT adjustedHeight = client.bottom - client.top;     m_hwnd = CreateWindowEx(windowExStyle,                             className.c_str(),                             windowName.c_str(),                             windowStyle,                             CW_USEDEFAULT,                             CW_USEDEFAULT,                             adjustedWidth,                             adjustedHeight,                             nullptr,                             nullptr,                             m_hInstance,                             m_emu     ); The generated window has a client area of 1 pixel in height, even though I'm asking for 40. so I'm always getting 39 pixel less than what I need...can someone help me with this? x_x

• I've spent quite a while (and probably far longer than I actually should) trying to design an allocator system.  I've bounced ideas around to various people in the past, but never really gotten something satisfactory.
Basically, the requirements I'm trying to target are:
Composability -- allocators that seamlessly allocate from memory allocated by other allocators.  This helps me to do things like, for example, write an allocator that pads allocations from its parent allocator with bit patterns to detect heap corruption.  It also allows me to easily create spillovers, or optionally assert on overflow with specialized fallbacks.   Handling the fact that some allocators have different interfaces than others in an elegant way.  For example, a regular allocator might have Allocate/Deallocate, but a linear allocator can't do itemized deallocation (but can deallocate everything at once).   I want to be able to tell how much I've allocated, and how much of that is actually being used.  I also want to be able to bucket that on subsystem, but as far as I can tell, that doesn't really impact the design outside of adding a new parameter to allocate calls. Note:  I'm avoiding implementation of allocation buckets and alignment from this, since it's largely orthogonal to what I'm asking and can be done with any of the designs.

To meet those three requirements, I've come up with the following solutions, all of which have significant drawbacks.
Static Policy-Based Allocators
I originally built this off of this talk.
Examples;
struct AllocBlock { std::byte* ptr; size_t size; }; class Mallocator { size_t allocatedMemory; public: Mallocator(); AllocBlock Allocate(size_t size); void Deallocate(AllocBlock blk); }; template <typename BackingAllocator, size_t allocSize> class LinearAllocator : BackingAllocator { AllocBlock baseMemory; char* ptr; char* end; public: LinearAllocator() : baseMemory(BackingAllocator::Allocate(allocSize)) { /* stuff */ } AllocBlock Allocate(size_t size); }; template <typename BackingAllocator, size_t allocSize> class PoolAllocator : BackingAllocator { AllocBlock baseMemory; char* currentHead; public: PoolAllocator() : baseMemory(BackingAllocator::Allocate(allocSize)) { /* stuff */ } void* Allocate(); // note the different signature. void Deallocate(void*); }; // ex: auto allocator = PoolAllocator<Mallocator, size>; Advantages:
SFINAE gives me a pseudo-duck-typing thing.  I don't need any kind of common interfaces, and I'll get a compile-time error if I try to do something like create a LinearAllocator backed by a PoolAllocator. It's composable. Disadvantages:
Composability is type composability, meaning every allocator I create has an independent chain of compositions.  This makes tracking memory usage pretty hard, and presumably can cause me external fragmentation issues.  I might able to get around this with some kind of singleton kung-fu, but I'm unsure as I don't really have any experience with them. Owing to the above, all of my customization points have to be template parameters because the concept relies on empty constructors.  This isn't a huge issue, but it makes defining allocators cumbersome. Dynamic Allocator Dependency
This is probably just the strategy pattern, but then again everything involving polymorphic type composition looks like the strategy pattern to me. 😃
Examples:
struct AllocBlock { std::byte* ptr; size_t size; }; class Allocator { virtual AllocBlock Allocate(size_t) = 0; virtual void Deallocate(AllocBlock) = 0; }; class Mallocator : Allocator { size_t allocatedMemory; public: Mallocator(); AllocBlock Allocate(size_t size); void Deallocate(AllocBlock blk); }; class LinearAllocator { Allocator* backingAllocator; AllocBlock baseMemory; char* ptr; char* end; public: LinearAllocator(Allocator* backingAllocator, size_t allocSize) : backingAllocator(backingAllocator) { baseMemory = backingAllocator->Allocate(allocSize); /* stuff */ } AllocBlock Allocate(size_t size); }; class PoolAllocator { Allocator* backingAllocator; AllocBlock baseMemory; char* currentHead; public: PoolAllocator(Allocator* backingAllocator, size_t allocSize) : backingAllocator(backingAllocator) { baseMemory = backingAllocator->Allocate(allocSize); /* stuff */ } void* Allocate(); // note the different signature. void Deallocate(void*); }; // ex: auto allocator = PoolAllocator(someGlobalMallocator, size); There's an obvious problem with the above:  Namely that PoolAllocator and LinearAllocator don't inherit from the generic Allocator interface.  They can't, because their interfaces provide different semantics.  There's to ways I can solve this:
Inherit from Allocator anyway and assert on unsupported operations (delegates composition failure to runtime errors, which I'd rather avoid).   As above:  Don't inherit and just deal with the fact that some composability is lost (not ideal, because it means you can't do things like back a pool allocator with a linear allocator) As for the overall structure, I think it looks something like this:
Memory usage tracking is easy, since I can use the top-level mallocator(s) to keep track of total memory allocated, and all of the leaf allocators to track of used memory.  How to do that in particular is outside the scope of what I'm asking about, but I've got some ideas. I still have composability Disadvantages:
The interface issues above.  There's no duck-typing-like mechanism to help here, and I'm strongly of the opinion that programmer errors in construction like that should fail at compile-time, not runtime. Composition on Allocated Memory instead of Allocators
This is probably going to be somewhat buggy and poorly thought, since it's just an idea rather than something I've actually tried.
Examples:
struct AllocBlock { void* ptr; size_t size; std::function<void()> dealloc; } class Mallocator { size_t allocatedMemory; public: Mallocator(); AllocBlock Allocate(size_t size) { void* ptr = malloc(size); return {ptr, size, [ptr](){ free(ptr); }}; } }; class LinearAllocator { AllocBlock baseMemory; char* ptr; char* end; public: LinearAllocator(AllocBlock baseMemory) : baseMemory(baseMemory) {end = ptr = baseMemory.ptr;} AllocBlock Allocate(size_t); }; class PoolAllocator { AllocBlock baseMemory; char* head; public: PoolAllocator(AllocBlock baseMemory) : baseMemory(baseMemory) { /* stuff */ } void* Allocate(); }; // ex: auto allocator = PoolAllocator(someGlobalMallocator.Allocate(size)); I don't really like this design at first blush, but I haven't really tried it.

"Composable", since we've delegated most of what composition entails into the memory block rather than the allocator. Tracking memory is a bit more complex, but I *think* it's still doable. Disadvantages:
Makes the interface more complex, since we have to allocate first and then pass that block into our "child" allocator. Can't do specialized deallocation (i.e. stack deallocation) since the memory blocks don't know anything about their parent allocation pool.  I might be able to get around this though.
I've done a lot of research against all of the source-available engines I can find, and it seems like most of them either have very small allocator systems or simply don't try to make them composable at all (CryEngine does this, for example).  That said, it seems like something that should have a lot of good examples, but I can't find a whole lot.  Does anyone have any good feedback/suggestions on this, or is composability in general just a pipe dream?

• Hi
I’ve been working on a game engine for years and I’ve recently come back to it after a couple of years break.  Because my engine uses DirectX9.0c I thought maybe it would be a good idea to upgrade it to DX11. I then installed Windows 10 and starting tinkering around with the engine trying to refamiliarise myself with all the code.
It all seems to work ok in the new OS but there’s something I’ve noticed that has caused a massive slowdown in frame rate. My engine has a relatively sophisticated terrain system which includes the ability to paint roads onto it, ala CryEngine. The roads are spline curves and built up with polygons matching the terrain surface. It used to work perfectly but I’ve noticed that when I’m dynamically adding the roads, which involves moving the spline curve control points around the surface of the terrain, the frame rate comes to a grinding halt.
There’s some relatively complex processing going on each time the mouse moves - the road either side of the control point(s) being moved, is reconstructed in real time so you can position and bend the road precisely. On my previous OS, which was Win2k Pro, this worked really smoothly and in release mode there was barely any slow down in frame rate, but now it’s unusable. As part of the road reconstruction, I lock the vertex and index buffers and refill them with the new values so my question is, on windows 10 using DX9, is anyone aware of any locking issues? I’m aware that there can be contention when locking buffers dynamically but I’m locking with LOCK_DISCARD and this has never been an issue before.
Any help would be greatly appreciated.

• I'm writing a small 3D Vulkan game engine using C++. I'm working in a team, and the other members really don't know almost anything about C++. About three years ago i found this new programming language called D wich seems very interesting, as it's very similar to C++. My idea was to implement core systems like rendering, math, serialization and so on using C++ and then wrapping all with a D framework, easier to use and less complicated. Is it worth it or I should stick only to C++ ? Does it have less performance compared to a pure c++ application ?

• Hi guys, I'm trying to learn this stuff but running into some problems 😕
I've compiled my .hlsl into a header file which contains the global variable with the precompiled shader data:
//... // Approximately 83 instruction slots used #endif const BYTE g_vs[] = { 68, 88, 66, 67, 143, 82, 13, 236, 152, 133, 219, 113, 173, 135, 18, 87, 122, 208, 124, 76, 1, 0, 0, 0, 16, 76, 0, 0, 6, 0, //.... And now following the "Compiling at build time to header files" example at this msdn link , I've included the header files in my main.cpp and I'm trying to create the vertex shader like this:
hr = g_d3dDevice->CreateVertexShader(g_vs, sizeof(g_vs), nullptr, &g_d3dVertexShader); if (FAILED(hr)) { return -1; } and this is failing, entering the if and returing -1.
Can someone point out what I'm doing wrong? 😕

• 35
• 12
• 10
• 9
• 9
• ### Forum Statistics

• Total Topics
631357
• Total Posts
2999527
×