Discord Thread chunk-based region outlines

  • Welcome to skUnity!

    Welcome to skUnity! This is a forum where members of the Skript community can communicate and interact. Skript Resource Creators can post their Resources for all to see and use.

    If you haven't done so already, feel free to join our official Discord server to expand your level of interaction with the community!

    Now, what are you waiting for? Join the community now!

This thread came from the skUnity Discord. You can't reply to it here but if you join the skUnity Discord, you'll be able to post a reply there. The thread link is part of the thread's message.
Status
Not open for further replies.
so for reference: code

code_language.skript: 
applescript
on load:
    set {-vector1} to vector(-0.5,0,-0.5)
    set {-vector2} to vector(0.5,0,-0.5)
    set {-vector3} to vector(0.5,0,0.5)
    set {-vector4} to vector(-0.5,0,0.5)

function getOutermostCorners(chunks: chunks) :: locations:
    set {_world} to world of {_chunks::1}
    
    # get all unique edges, parse them into locations
    # and set up a map of valid edges
    loop getUniqueEdges({_chunks::*}):
        set {_i} to 0
        loop split loop-value by ";":
            set {_coords::*} to split loop-value-2 by "|"
            set {_x} to {_coords::1} parsed as number
            set {_z} to {_coords::2} parsed as number
            set {_parsed} to location({_x}, 0, {_z}, {_world})
            add 1 to {_i}
            set {_parsed-corners::%{_i}%} to {_parsed}
        
        set {_parsed-edges::%{_parsed-corners::1}%-%{_parsed-corners::2}%} to {_parsed-corners::1}
        set {_parsed-edges::%{_parsed-corners::2}%-%{_parsed-corners::1}%} to {_parsed-corners::2}

    # order CCW
    set {_offset::1} to vector(0,0,16)
    set {_offset::2} to vector(-16,0,0)
    set {_offset::3} to vector(0,0,-16)
    set {_offset::4} to vector(16,0,0)

    set {_current} to first element of {_parsed-edges::*}
    set {_corners::0} to {_current}
    loop size of {_parsed-edges::*} / 2 times:
        # look in SWNE order
        loop {_offset::*}:
            # get prospective corner
            set {_prospective} to {_current} ~ loop-value-2
            # if we have an edge to it, it's the next corner
            # otherwise, keep looking
            if {_parsed-edges::%{_current}%-%{_prospective}%} is set:
                # delete edges we've used
                delete {_parsed-edges::%{_current}%-%{_prospective}%} 
                delete {_parsed-edges::%{_prospective}%-%{_current}%}
                # add corner to list and move to next corner
                set {_corners::%loop-value-1%} to {_prospective}
                set {_current} to {_prospective}
                exit 1 loop


    return {_corners::*}

function getUniqueEdges(chunks: chunks) :: strings:
    loop {_chunks::*}:
        loop getEdges(loop-value):
            # check for duplicate edge
            if {_edges::%loop-value-2%} is set:
                delete {_edges::%loop-value-2%}
                continue
            
            # check for duplicate reverse edge
            set {_corners::*} to split loop-value-2 by ";"
            set {_reverse-edge} to join reversed {_corners::*} with ";"
            if {_edges::%{_reverse-edge}%} is set:
                delete {_edges::%{_reverse-edge}%}
                continue

            # store edge
            set {_edges::%loop-value-2%} to loop-value-2    
    return {_edges::*}

function getEdges(chunk: chunk) :: strings:
    set {_corners::1} to block at 0,0,0 of {_chunk} ~ {-vector1}
    set {_corners::2} to block at 15,0,0 of {_chunk} ~ {-vector2}
    set {_corners::3} to block at 15,0,15 of {_chunk} ~ {-vector3}
    set {_corners::4} to block at 0,0,15 of {_chunk} ~ {-vector4}

    # add all edges in x|z;x|z format
    loop {_corners::*}:
        add 1 to {_i}
        set {_next} to {_corners::%mod({_i}, 4) + 1%}
        set {_edges::%loop-index%} to "%x coord of loop-value%|%z coord of loop-value%;%x coord of {_next}%|%z coord of {_next}%"
    return {_edges::*}
So getUniqueEdges will give you every single boundary edge, be it a connected shape, an inner or outer boundary, or whatever
it doesn't care, and it doesn't order anything
it'll just give you all the data
Then in getOutermostCorners we have basically two things happening
1) We take the output of getUniqueEdges, turn it into actual locations, and create a list of valid edges
applescript
# get all unique edges, parse them into locations
    # and set up a map of valid edges
    loop getUniqueEdges({_chunks::*}):
        set {_i} to 0
        loop split loop-value by ";":
            set {_coords::*} to split loop-value-2 by "|"
            set {_x} to {_coords::1} parsed as number
            set {_z} to {_coords::2} parsed as number
            set {_parsed} to location({_x}, 0, {_z}, {_world})
            add 1 to {_i}
            set {_parsed-corners::%{_i}%} to {_parsed}
        
        set {_parsed-edges::%{_parsed-corners::1}%-%{_parsed-corners::2}%} to {_parsed-corners::1}
        set {_parsed-edges::%{_parsed-corners::2}%-%{_parsed-corners::1}%} to {_parsed-corners::2}

This is all so we can order it later
parsed-edges is just a set of valid edges (see the indices?)
we make the value a location just for ease of getting started, it's not that necessary
the indices are the important part
So then this code does the actual ordering of the corners
applescript
    # order CCW
    set {_offset::1} to vector(0,0,16)
    set {_offset::2} to vector(-16,0,0)
    set {_offset::3} to vector(0,0,-16)
    set {_offset::4} to vector(16,0,0)

    set {_current} to first element of {_parsed-edges::*}
    set {_corners::0} to {_current}
    loop size of {_parsed-edges::*} / 2 times:
        # look in SWNE order
        loop {_offset::*}:
            # get prospective corner
            set {_prospective} to {_current} ~ loop-value-2
            # if we have an edge to it, it's the next corner
            # otherwise, keep looking
            if {_parsed-edges::%{_current}%-%{_prospective}%} is set:
                # delete edges we've used
                delete {_parsed-edges::%{_current}%-%{_prospective}%} 
                delete {_parsed-edges::%{_prospective}%-%{_current}%}
                # add corner to list and move to next corner
                set {_corners::%loop-value-1%} to {_prospective}
                set {_current} to {_prospective}
                exit 1 loop
To break it down:
1. We start with a corner. Doesn't matter what corner, just some corner in our set (this is why we set the locaitons earlier, it's just easy to get started)
2. We look at the 4 adjacent corner possibilities, first South, then West, North, East (clockwise order)
3. For each of those possibilities, we'll check if we have a valid edge between the two. If we do, we can "use up" that edge and "travel" along it to the next corner. The "using up" or deleting prevents us from going back the way we came.
4. If we don't have an edge, we check the next possible corner and repeat

So this basically walks us around the perimeter of the shape, right? Then, once we get back to the start, we have no more edges to do and so the algorithm just ends.
However, if we have a hole, or a disconnected shape, we'll never be able to walk to those edges, by definition.
So we'll run out of edges to use to walk, but there will still be edges in the list.

So we can modify the section a bit to handle holes/disconnected shapes
First, we'll set a flag at the start of the loop that says "hey, we have not yet found a valid edge from this corner"
Then, when we find an edge, we set that to true, saying we have found an edge.

Now, when we exit the {_offset} loop, we know if we found something or if we hit a dead end
If we found something, business as usual
If we hit a dead end, then we know we currently have a full boundary in our
{_corners::*}
 list. We (normally) return this and call it good. Here, though, we want to do something with it right now. Draw it, send it to dynmap, whatever.
Then, we can clear the list and basically start again. We pick a new random corner from the edges list, so we're starting at a new boundary now. Then we can just repeat our walk with this new boundary
Repeat until completely out of edges.

Posted by: sovde from the skUnity Discord.
 
Okay this is quite interesting, but it turns out, it's not possible to make regions in dynmap that have holes... so it seems like I will just use the outermost corners as it is and overwrite holes

Posted by: sluhtie from the skUnity Discord.
 
oh i was going to explain the hole protection thingy
also, the code for this:
code_language.skript: 
applescript
function drawOutlines(chunks: chunks) :: number:
    set {_world} to world of {_chunks::1}
    
    # get all unique edges, parse them into locations
    # and set up a map of valid edges
    loop getUniqueEdges({_chunks::*}):
        set {_i} to 0
        loop split loop-value by ";":
            set {_coords::*} to split loop-value-2 by "|"
            set {_x} to {_coords::1} parsed as number
            set {_z} to {_coords::2} parsed as number
            set {_parsed} to location({_x}, 0, {_z}, {_world})
            add 1 to {_i}
            set {_parsed-corners::%{_i}%} to {_parsed}
        
        set {_parsed-edges::%{_parsed-corners::1}%-%{_parsed-corners::2}%} to {_parsed-corners::1}
        set {_parsed-edges::%{_parsed-corners::2}%-%{_parsed-corners::1}%} to {_parsed-corners::2}

    # order CCW
    set {_offset::1} to vector(0,0,16)
    set {_offset::2} to vector(-16,0,0)
    set {_offset::3} to vector(0,0,-16)
    set {_offset::4} to vector(16,0,0)

    set {_current} to first element of {_parsed-edges::*}
    set {_corners::0} to {_current}
    while true is true:
        add 1 to {_iterations}
        set {_found} to false
        # look in SWNE order
        loop {_offset::*}:
            # get prospective corner
            set {_prospective} to {_current} ~ loop-value
            # if we have an edge to it, it's the next corner
            # otherwise, keep looking
            if {_parsed-edges::%{_current}%-%{_prospective}%} is set:
                # delete edges we've used
                delete {_parsed-edges::%{_current}%-%{_prospective}%} 
                delete {_parsed-edges::%{_prospective}%-%{_current}%}
                # add corner to list and move to next corner
                set {_corners::%{_iterations}%} to {_prospective}
                set {_current} to {_prospective}
                set {_found} to true
                exit 1 loop

        if {_iterations} > 1000:
            broadcast "too many iterations"
            return -1


        {_found} is false
        # if we get here, we've looped around and found no corner
        # this means we've found the last corner of this shape
        # so we'll draw the shape and start a new one
        drawBoundary({_corners::*})
        add size of {_corners::*} to {_total}
        clear {_corners::*}

        # if the list is empty, we're done
        # otherwise, get a new corner to start from
        if size of {_parsed-edges::*} is 0:
            return {_total}
        
        set {_current} to first element of {_parsed-edges::*}
        set {_corners::0} to {_current}
        broadcast "new corner is %{_current}%"
    return {_total}
but for the hole protection
So let's say our current area is blue, and we're trying to add the yellow chunk
We want a list of rules that can cause holes
First, let's define what is and is not a hole
Red is a hole. Yellow is technically not a hole, but it's up to you if you want to treat it as one. Green is umbiguously not a hole
So let's look at the case for turning green into red
First things first
Yellow connects between two blue squares
This is red flag number 1
If a square only connects one side to a shape, you're in the clear
no possible holes can come from adding that
So our
Also, if it borders 3, it also can't form a hole
But there's a case where when it borders 2 it does not form a hole:
In every case like this one, those 2 bordering tiles have to be "adjacent":
However, we can't stop there
this is what we're really worried about
the 2 neighbors are adjacent, but it still forms a hole.
So what we do is check whether the 4th square in our little 2x2 is filled in or not.
If it is, we're ok.
If it's not, we're not ok
so to sum up, we have a few rules:
* First, any square bordered by 1 or 3 direct neighbors is fine.
* If it's bordered by 2 neighbors, then those neighbors MUST be adjacent
* If they're adjacent, then the square between them (purple above) MUST be filed in
Those 3 should be enough to determine whether a claim will make a hole or not
questions?

Posted by: sovde from the skUnity Discord.
 
oh sure
nothing outside of the immediate 8 neighbors of the yellow square actually matter
as long as everything followed the rules up to now, it'll all work
extreme example:
still the same situation
so these rules will keep valid shapes valid, but they won't turn invalid shapes valid
garbage in, garbage out

Posted by: sovde from the skUnity Discord.
 
here, both those squares need to be checked
And here, 3 out of 4 must be filled in
so to sum up, we have a few rules:
* First, any square bordered by 1 direct neighbor is fine.
* If it's bordered by 2 or 3 neighbors, then those neighbors MUST be adjacent (always true for 3 neighbors)
* If they're adjacent, then the square(2) between them MUST be filed in
* if it's bordered by 4 neighbors, 7 out of the 8 surrounding tiles must be claimed
direct neighbor: shares an edge
indirect neightbor: connected at a corner

Posted by: sovde from the skUnity Discord.
 
Status
Not open for further replies.
Top Bottom
Back