2
\$\begingroup\$

I'm trying to spread temperature values evenly across the grid (Room) but somehow it has a bias to the right side of the map. My basic math skills are non existent so i could use some help with the following issue.

Background Information

I have a 2d array with the following data

public class HeatData
{
    public int x;
    public int y;
    public int radius;
    public double transferRate;
    public double dissipateRate;
    public double temperature;
}

I want to emit heat from certain tiles and spread them across the grid based on their set transfer / dissipation rates. Basically i'm adding temperature to a set of tiles and expect them to spread across the room. I have a method that gets all the surrounding neighbours and use that info in the following method.

private void TransferHeat()
{
    var newGridData = _grid.gridData;
    
    for (int x = 0; x < _grid.gridData.GetLength(0); x++)
    {
        for (int y = 0; y < _grid.gridData.GetLength(1); y++)
        {
            var data = _grid.GetData(new Vector2Int(x, y));

            var neighbours = _grid.GetNeighbours(data.position);

            foreach (var neighbour in neighbours)
            {
                var neighbourData = _grid.GetData(neighbour);

                var newData = HeatData.CleanCopy(data);
                var newNeighbourData = HeatData.CleanCopy(neighbourData);
                
                var difference = HeatValueForNeighbour(neighbourData, data);

                newData.temperature = data.temperature - difference;
                newNeighbourData.temperature = neighbourData.temperature + difference;

                newGridData[neighbour.x, neighbour.y] = newNeighbourData;
                newGridData[data.x, data.y] = newData;
            }
        }
    }

    foreach (var newData in newGridData)
    {
        _grid.SetData(newData.position, newData);
    }
}
private double HeatValueForNeighbour(HeatData neighbourData, HeatData data)
{
    var temperatureDifference = data.temperature - neighbourData.temperature;
    return temperatureDifference * data.transferRate;
}

The CleanCopy will copy the data into an new instance. I have been busting my brain for hours at this problem and i can't seem to figure out how to write it correctly. It seems like the temperature has a favour of spreading all the values to the right side of the map

\$\endgroup\$
1
  • \$\begingroup\$ Hint: var newGridData = _grid.gridData; gives you a new name to refer to the same underlying gridData array. No copy has been made on this line, you're just using two names to refer to the same variable. So as your loop progresses, writing new data into newGridData, you're overwriting the data you're trying to read from in _grid.gridData. \$\endgroup\$
    – DMGregory
    Commented Nov 2, 2021 at 22:07

1 Answer 1

2
\$\begingroup\$

First, I'd make this HeatData type into a struct so you don't generate a tonne of garbage collection churn every time you do an iteration and spawn a fresh batch of them. This also means we no longer need a clean copy method - we get a copy just via assignment. x and y are implicit in their position in the grid, so we don't really need to store them.

public struct HeatData
{
    public int radius;
    public double transferRate;
    public double dissipateRate;
    public double temperature;
}

Similarly, if you want to use double buffering to separate a read-only and write-only copy of your data, keep both around: that way you don't incur allocation overhead or generate new garbage on every iteration by creating a new buffer.

public class grid {
    HeatData[,,] _grid;

    int _readIndex = 0;
    int _writeIndex { get { return 1 ^ _readIndex; } }

    bool IsInGridBounds(int x, int y) {
        return x >= 0 && y >= 0 && x < _grid.GetLength(1) && y < _grid.GetLength(2);
    }

    public HeatData GetData(int x, int y) {
        if (IsInGridBounds(x, y))
            return _grid[_readIndex, x, y];
        else
            return default;        
    }

    public void SetData(int x, int y, HeatData data) {
        _grid[_writeIndex, x, y] = data;
    }

    public void FlipBuffers() {
        _readIndex = _writeIndex;
    }
}

Now we can clean up your loop a bit:

private void TransferHeat()
{
    for (int x = 0; x < _grid.gridData.GetLength(0); x++)
    {
        for (int y = 0; y < _grid.gridData.GetLength(1); y++)
        {
            // Implicitly copy since we made our type a struct.
            var data = _grid.GetData(x, y);

            var neighbours = _grid.GetNeighbours(data.position);

            foreach (var neighbour in neighbours)
            {
                // Also implicitly copy since we made our type a struct.
                var neighbourData = _grid.GetData(neighbour.x, neighbour.y);
                   
                var difference = HeatValueForNeighbour(neighbourData, data);

                data.temperature = data.temperature - difference;
                // We don't update the neighbour's data here - we'll visit them
                // individually at some point in our loop.
            }

            // Write our new data to the write-only buffer.
            _grid.SetData(x, y, data);
        }
    }

    // Done writing. Make our write-only buffer the new read-only version.
    // We can do this by flipping one bit, without copying the whole array over.
    _grid.FlipBuffers();
}

Because we're only updating "this" node in each iteration, not the neighbouring nodes, you'd also want to update your heat transfer function to include information about both nodes' transfer rates - to ensure the transfer is symmetrical:

private double HeatValueForNeighbour(HeatData neighbourData, HeatData data)
{
    var temperatureDifference = data.temperature - neighbourData.temperature;
    // Depending on your conventions here, an average might be appropriate,
    // rather than a sum.
    return temperatureDifference * (data.transferRate + neighbourData.transferRate);
}

We do end up calling this function twice for each neighbouring pair A, B: once when A is "this" node and B is the neighbour, and a second time when B is "this" node and A is the neighbour. You can reduce this overhead by updating your GetNeighbours function to only enumerate "neighbours we haven't visited yet" and go back to updating both "this" node and its neighbours in the same pass. But then you need to read "this" node from the writable buffer, to ensure you carry forward data we wrote earlier in the iteration, and be sure to seed your starting node with the readable data.

Another technique you can use to mitigate the directional bias, if you don't want to use full double buffering, is to alternate your direction of iteration between subsequent frames. So in frame n you have a rightward bias, but in frame n+1 you have a leftward bias, and the two effects "mostly" cancel out, at half the memory cost.

\$\endgroup\$
10
  • \$\begingroup\$ Your explanation is eye opening, thank you i will take your feedback and try to improve my code a bit. The idea with the buffer is also really smart thank you for letting me learn something new today. \$\endgroup\$ Commented Nov 3, 2021 at 7:34
  • \$\begingroup\$ I have implemented the double buffering system like you suggested, the only minor difference is that i added a method to directly write to the read buffer, since i want to apply heat to tiles before transferring. But i still see a bias to the lower left with the above implementation. Either i'm missing something stupid. or your wonderful explanation is not getting through my skull. If you have the time this is my write up of the current implementation gist.github.com/Plnda/bfe34bf01281d80d00930514ce89227e \$\endgroup\$ Commented Nov 3, 2021 at 11:02
  • \$\begingroup\$ and a more visual version: streamable.com/hjr9f7 \$\endgroup\$ Commented Nov 3, 2021 at 11:08
  • 1
    \$\begingroup\$ If you write to the read buffer during your iteration, then you change the "current" values that get used by cells you visit later in the iteration. That creates the bias. Cells get updated with the old value from their right-hand neighbour, but a new value from their left-hand neighbour. That lets heat transfer more quickly in the direction of iteration. A little excess heat in the first column can get carried all the way to the last column, riding the wave of the iteration, while heat from the last column can only propagate one column left per cycle. \$\endgroup\$
    – DMGregory
    Commented Nov 3, 2021 at 11:37
  • 1
    \$\begingroup\$ We generally ask folks to create a Minimal Complete Verifiable Example if they want help debugging code. This example is already over 500 lines, so it's not very minimal, and it's still missing dependencies like BaseService, BuildItem, and MeshUtils, so it's also not complete. You've made a lot of work for anyone who wants to try to reproduce the problem, which will slow down the troubleshooting process. (Not every user with 15 minutes to help you has an hour to learn and refactor this code into something they can run and test). \$\endgroup\$
    – DMGregory
    Commented Nov 5, 2021 at 13:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .