General > Off Topic

A point on movement in Darwin Bots

<< < (3/7) > >>

Numsgil:
I'd have to play with it to know for certain.  It may not be as bad as you think.  Each single cell can only bleed into the ones around it, right?

I made a forest simulator I while back that had this same problem.  I could look up the code for it.

If done right, it would only be on the order of O(n), which isn't bad at all.

PurpleYouko:
The way I have it working is that each cell only scans those directly above, below, left and right. I left out diagonals because it slowed down too much.

I also only update the grid on every 10th cycle to save game speed. When I tried doing it on every cycle it slowed the game down to a crawl.

Take a look at my code by all means. Speed it up if you can.

 :D  PY  :D

Numsgil:
Did you fix the order of updating bug that I had in my forest simulator?

Here's the problem I had:

1.2.3
4.5.6
7.8.9

^ egrid.

cell 1 updates.  This causes 2 and 4 to change.  Then cell 2 updates, this causes 1 5 and 3 to change.

But there's a problem!  Cell 1's bleed effect has changed cell 2 before cell 2 updates, but the same is not true for cell 2's update of cell 1.

The answer I came up with way back when was to create a psuedo grid that stored the changes, so all changes could be applied after all cells updated.

I'll look at your code later when I have a chance.  It shouldn't be computationally expensive.

PurpleYouko:
Actually my way does get around your problem to some degree but not quite in the way you suggest or possibly as efficiently.

What I was concerned about was making sure there were no net gains or losses of stuff in the entire grid.

Here is roughly how it works for a grid

1 . 2 . 3
4 . 5 . 6
7 . 8 . 9

Starting at cell 1, the program compares the value with 2 and 4. If there is a big enough difference then modifications are made otherwise nothing is done at all.

If the value in 2 is greater than that in 1 then a certain proportion of the difference is removed from 2 and stored temporarily in an independent variable.
next the value in 1 is compared to 4 and again if the difference is above a certain threshold, a portion of the difference is removed from 4 and added to the temporary store.

Once all neighboring cells have been checked, the temporary store value is added to cell 1

Then we move on to cell 2 and repeat.

In this method we are double checking cells that may have already been the central cell but changes will only be made if the value in that cell is bigger than the one in the present cell. In actuality I have never seen the value shared back again from cell 1 to cell 2.

At the end of the entire grid scan I inserted a check sum (not there in the present code) to see what the total was and it always stayed the same so I am happy that the math part is working.

I tried going the other way with each cell pushing its excess to the others in equal ammounts at first but that didn't work so well.

Using another layer of the grid to store changes and then adding them back in was one possible option to use but it would have meant scanning the grid twice to update the values. My way was a compromise that allowed for faster code.

here is the code for the grid updating (to save you looking for it)


--- Code: ---Public Sub RefreshGrid(z As Integer)
  Dim Change As Single
  Dim tot As Single
  Dim val As Single
  Dim Threshold As Integer
  Threshold = 3
  Change = 1
  For xx = 0 To 120
    For yy = 0 To 90
      val = grid(xx, yy, z)
      
        tot = 0
        If xx < 90 Then
          If grid(xx + 1, yy, z) - val > Threshold Then
            grid(xx + 1, yy, z) = grid(xx + 1, yy, z) - Change
            tot = tot + Change
          End If
        End If
        If xx > 0 Then
          If grid(xx - 1, yy, z) - val > Threshold Then
            grid(xx - 1, yy, z) = grid(xx - 1, yy, z) - Change
            tot = tot + Change
          End If
        End If
        If yy < 90 Then
          If grid(xx, yy + 1, z) - val > Threshold Then
            grid(xx, yy + 1, z) = grid(xx, yy + 1, z) - Change
            tot = tot + Change
          End If
        End If
        If yy > 0 Then
          If grid(xx, yy - 1, z) - val > Threshold Then
            grid(xx, yy - 1, z) = grid(xx, yy - 1, z) - Change
            tot = tot + Change
          End If
        End If
        grid(xx, yy, z) = grid(xx, yy, z) + tot
      
    Next yy
  Next xx
End Sub
--- End code ---

z represents the grid level to be scanned.

As you can see I only scan one layer at a time so that the program doesn't take such a speed hit. I tried doing all the layers and it pretty much stopped the program dead in its tracks. 20 cycles per second became 1 cycle.

Believe me when I say this stuff is extremely processor intensive.

 :D  PY  :D

shvarz:
I noticed that you guys are looking at spread in both directions at the same time.  It might be easier to do diffusion in horizontal and vertical directions in separate cycles.  On one cycles it diffuses horizontally, on the next - vertically.  Not as accurate, but may be much easier.  

The diffusion rate might be different, but let's say it is such that over one cycle 1/3 of all amount in one cell diffuses into next. And 1/9 into next and so on.  If you have cells

A B C D

Then to calculate the amount of A in the next cycle simply use

A+1/3B+1/9C+1/27D

Single pass - all values calculated.

Navigation

[0] Message Index

[#] Next page

[*] Previous page