Back to General and Gameplay Programming

problem with circular resource movement in strategy game

General and Gameplay Programming Programming

Started by djsteffey February 22, 2015 03:58 PM

2 comments, last by Acharis 9 years, 2 months ago

djsteffey

1,347

Author

February 22, 2015 03:58 PM

I have a problem. I am making a game played on a grid (not necessarily the size above). The orange dot denotes a "resource" producer. The numbers represent the amount of resource in each cell. The arrows are the ways that resources move from cell to cell and is selectable by the player to move the resources around the map. Resources in each cell are capped at 100.

The problem is that on each update each cell is checked to see if it has an "arrow" moving out of it to a neighbor cell and if so it will transfer some resources. It will only do so if it its own resources are at least 2 (since we must retain at least 1 in each cell) and if the neighbor cell is not already maxed out. Cells are updated in order from bottom left to top right. In the example in the picture I get a deadlock like situation where no additional resources make it into the system from the producer. Since the updates take place from bottom left to top right the first one to get an update is the bottom left. It checks it has more than one, has an arrow going up, the one going to it is not maxed so it transfers one resource reducing itself to 1 and the one above it to 100. Next update is the bottom right "2" and it does same thing. The issue that happens is that when it gets to the producer cell the producer cannot transfer a resource right into the connected cell because it was updated to 100 by the cell below it. And then the next one updated is that new "100" which transfers resources to the cell to its right and falls back down to 99.

So what happens is that there in that tight loop those 4 keep passing around 1 resource to each other in a loop and doesnt allow the producer to inject more because its neighbor is at the max (100) when it is the producers turn.

yes i have considered updating from top down but it will still be the same problem just with a different corner or orientation of the loop.

I have also consider updating all producer cells first then go through the rest but the problem still remains if there is an additional cell between the producer and the loop. Just image the loop moved one space to the right with an extra normal cell now linking the producer to the loop.

I do not want to limit the ability to make loops. I have considered each arrow to be bi-directional and only allow resource movement to lower resource level cell but this causes all cells to update at same value and doesnt allow "surging" of resources to given areas.

How to overcome this prevention of introducing new resources by the producer?

Waterlimon

4,401

February 22, 2015 05:51 PM

Do not write the same data you are reading, or at least write the system such that the iteration order adds no directional bias.

You can do this by double buffering the relevant game state.

A more memory efficient method, if you can guarantee that you only read data from adjacent tiles and write to the current tile, is to go on a row by row basis, and BEFORE writing to a row, save that entire row in its 'previous state'. Use that saved row for the reads that access that row when processing the next row (instead of reading the 'new state' you just wrote to that row!). And when processing the row itself, use a similar method for the other axis, as iterating from start of the row to the end of it.

Basically, make sure you are only using previous state when calculating the new state (you can forget the previous state when you no longer need it to save memory, and you dont need to save a copy until you are about to update it with new data).

This issue is usually discussed together with grid based fluid simulations (since iteration order bias can cause fluid to prefer to flow in one direction).

Another 'hackier' solution that is probably easier to add, is to change the iteration order between each update, such that the bias will even out over time. In your example, this would mean that sometimes you get that lock situation, but sometimes dont, so it still works out. This solution causes your simulation rules to be somewhat 'nondeterministic' or unpredictable, so take that into consideration.

o3o

Strewya

2,802

February 22, 2015 07:57 PM

Given your example loop, what is your expected result of one iteration? What about the one after that? And after that?
Taking this specific situation, you have to resolve which of the two cells (the producer and the 2 cell below the 99 cell) actually moves its resource to the 99 cell.

I would solve this by having two passes over the cells before actually doing the transfer of resources, which is taken into consideration when checking if the receiver can take the resource.
For each cell in any order, check if it can give a resource (>= 2), and check the receiver if it can take resources (receiver.resource + receiver.resourceDelta < 100), and only then should it increase the receivers delta, and decrease it's own.
After you do this first pass, all that remains is to iterate all cells one more time, and do self.resource += self.resourceDelta; self.resourceDelta = 0;
The only thing you need to do is define transfer priority. Should the producers be updated first or should the nodes that have multiple givers be updated first, seeing as they will be receiving more then one resource per turn.

devstropo.blogspot.com - Random stuff about my gamedev hobby

Acharis

5,990

February 22, 2015 10:34 PM

Maybe do not make the move order by the grid position but by the number of resources? Those with 100 are to try and get rid of resources first, then 99, then 5, then 2 (it's also intuitive and easy to explain to the player).

Or move order by the difference of resources (so 99 would move to 5 first).

Or try some flooding algorithm (big resource grids "flood" neighbour lower resource grids).

Or make more than one pass per turn? Or track how many resources per gird were made (assuming you move 10 resource per turn max from a grid for example) and repeat until all grids exchaused their quota or 10 passes were made.

Stellar Monarch (4X, turn based, released): GDN forum topic - Twitter - Facebook - YouTube

problem with circular resource movement in strategy game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

problem with circular resource movement in strategy game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines