I am eternally grateful for you gifting me a membership!
In the future, I will give you free subscriptions to my game(s)!
I said I was going to 'show' something for my Open Planet game in this blog post, so indeed I will.
But! It is code!
proc/GetWaterBody(World/water/start)
var/list/result = list(start)
var/current
for (var/i = 1, i <= result.len, ++i)
current = result[i]
for (var/turf/W in orange(1, current))
if ((istype(W, /World/water) || istype(W, /World/hole)) && !(W in result))
result += W
return result
Currently, I am attempting to optimize this proc!
What it does is get a 'body of water' by finding all waters and holes that are adjacent to each other (from a given starting turf). The main thing is that it puts the turfs in the result in a particular order so that if they are updated in that order, it looks like the water is rushing out from the starting turf. (e.g. every turf is adjacent to the ones next to it in the list.)
Now, it is really slow if the body of water is really big. Which is why I want to optimize it. (Mainly because it makes the game start up really slow, which is annoying when testing things.)
It's obvious why it's slow. For every turf, it checks every turf next to it, and for every turf next to those it checks the ones next to those and so on. And, since it is using a (W in result) check, it has to search the list to find if it is in it, for every single nested iteration. (Which is horrible design!)
My plan for optimizing it is as such:
- Make a deterministic algorithm that touches every turf in a body of water only one time, or a very minimal amount of times.
- Use a binary insert to order the turfs based on their distance from the starting turf, so that it doesn't matter the order they are touched.
I already made a binary insert proc:
proc/binary_insert(list/L, value, key)
if (L.len == 0)
L[value] = key
return L
var/static/left
var/static/right
var/static/mid
var/static/val
left = 1
right = L.len
while (left + 1 < right)
mid = round((left + right + 1) / 2)
val = L[L[mid]]
if (val < key)
left = mid
else
right = mid
val = L[L[left]]
if (key < val)
L.Insert(left, value)
else
val = L[L[right]]
if (key < val)
L.Insert(right, value)
else
L.Insert(right + 1, value)
L[value] = key
return L
This will insert the values in a list, keeping the list sorted with each insert (the sorting uses list associations) and also has a log2 number of iterations. The value is the value to insert into the list, and the key is a number that determines how the values are sorted. (Lower numbers are at the beginning of the list, larger numbers at the end.)
Essentially, every turf will be added to the list using binary_insert with a key that matches their distance from the starting turf. (Square distance to avoid a square root. Using the sum of the x and y distance would work too.)
As for doing the touching each turf once, I have a vague idea of what I'm going to do. My current idea involves starting at the center and making a border around it, getting all of the turfs in it, then making a border around that border and repeating until you reach a border where no turfs get added. (A lot of thought and planning still needs to go into this.)
Okay, on the topic of my CSS.
Now that I'm a member, I can do fancy things to my blog.
What do you think of it?
