[vJASS] System Problem

[Chaosy]

hi, I was playing around in vjass and I was making a function called GetClosestTile() but its not working well at all.

• demo Copy
  • Events
    • Player - Player 1 (Red) skips a cinematic sequence
  • Conditions
  • Actions
    • Set terrain = Lordaeron Summer - Grassy Dirt
    • Set x = (Center of Region 000 <gen>)
    • Custom script: set udg_location = GetClosestTile(udg_terrain,udg_x)
    • Unit - Create 1 Footman for Player 1 (Red) at location facing Default building facing degrees

globals
    real searchRange = 9000
endglobals

function GetClosestTile takes integer tileid, location loc returns location point
    local location start = loc
    local location x
    local location closestLoc
    local real startDistance = 1
    local real startAngle = 0
    local real closestDistance = 9999
    local real tempDistance
    local integer exit = 0
    call BJDebugMsg("function called")
    loop
        exitwhen exit == 1
        set x = PolarProjectionBJ(start, startDistance, startAngle)
        if GetTerrainType(GetLocationX(x), GetLocationY(x)) == tileid then
            set tempDistance = DistanceBetweenPoints(x, start)
            call BJDebugMsg("found tile")
            if tempDistance <= closestDistance then
                set closestDistance = tempDistance
                set closestLoc = x
            endif
        endif        
        set startDistance = startDistance + 1        
        if startDistance <= searchRange then
            set startAngle = startAngle + 1
            set startDistance = 1
            if startAngle >= 360 then
                set exit = 1
                call BJDebugMsg("ended")
            endif
        endif       
    endloop
    return closestLoc
endfunction

I even made the detectrange extremely huge just for testing but it wont detect a single one. It only works if you put the tile ON that location.

 

[PurgeandFire]

Usually when I have some algorithm that isn't working, I just run through the loop in my head.

First, the loop finds a location offset from the start, 1 unit away towards 0 angle. It checks if the terrain type is equal to the tileid. Keep in mind that tiles occupy more than 1 unit, so moving 1 unit away will likely just return the same tile (unless the start location is on the very edge of the tile). You should be iterating with higher units, such as 64 units.

Anyway, when the check fails, it'll set increment startDistance by 1. Thus, it goes from 1 to 2. Then it checks if the startDistance is less than/equal to searchRange (9000), then it increments the angle, and sets startDistance back to 1. So startDistance now equals 1, and startAngle now equals 1. Now, on this pattern, it'll go through and check all points 1 unit away from the start, at different angles from 1 to 360, until it hits 360 degrees. Then it will exit the loop, and display "ended".

All in all, there is definitely room for optimization:

• Use coordinates instead of locations. If you use locations, then remove them to clear the leak.
• Use offsets of 64 (or however much space a tile occupies) to check for the nearest tile. Using 1 unit offsets will likely hit the op limit, and it'll be a lot of wasted performance.
• You only need to check at particular angles. When you have some tile, there will be one tile to the west of it, one tile northwest of it, one tile north of it, one northeast, one east, one southeast, one south, and one southwest of it. That's 8 angles, which are 0, 45, 90, 135, 180, 225, 270, and 315.

You'll probably end up with two loops: one will be the outer loop that'll change the offset. The inner loop will check each of the 8 angles for the terrain type, at that offset.

loop
    set offset = offset + 64 // offset should be initially 0
 
    // in case the offset gets too high
    exitwhen (offset > maxRange)

    set angle = 0
    loop
        exitwhen angle > 315
        if GetTerrainType(x + offset * Cos(angle * bj_RADTODEG), y + offset * Sin(angle * bj_RADTODEG)) == tileid then
            call BJDebugMsg("Found")
            exitwhen true
        endif
        set angle = angle + 45
    endloop

endloop

Eh, something like that. That is just pseudocode, untested. There might be some design flaws in it, such as if the starting point is off to the side of the tile, but it should be a step in the right direction.

 

[Chaosy]

thanks. I changed the values and I use 2 loops now.
it works better now but its still bugging.

globals
    real searchRange = 9000
endglobals

function GetClosestTile takes integer tileid, location loc returns location point
    local location start = loc
    local location x
    local location closestLoc
    local real startDistance = 1
    local real startAngle = 0
    local real closestDistance = 9999
    local real tempDistance
    local integer exit = 0
    call BJDebugMsg("function called")
    loop
        exitwhen exit == 1
        set startAngle = startAngle + 45
        loop
            set startDistance = startDistance + 64
            set x = PolarProjectionBJ(start, startDistance, startAngle)
            if GetTerrainType(GetLocationX(x), GetLocationY(x)) == tileid then
                set tempDistance = DistanceBetweenPoints(x, start)
                call BJDebugMsg("found tile")
                if tempDistance >= closestDistance then
                    set closestDistance = tempDistance
                    set closestLoc = x
                endif
                exitwhen true
            endif
            if startDistance >= searchRange then
                exitwhen true
            endif
        endloop
        if startAngle >= 360 then
            set exit = 1
            call BJDebugMsg("ended")
        endif
    endloop
    return closestLoc
endfunction

 

[WaterKnight]

The function is super inefficient, easily hits the oplimit. You should execute it in another thread anyway.

The line

set tempDistance = DistanceBetweenPoints(x, start)

is futile because that's the same as startDistance of that iteration. If that were not the case, when comparing distances, it's enough to compare their squares to save the SquareRoot in Pythagoras.

You only need to check at particular angles. When you have some tile, there will be one tile to the west of it, one tile northwest of it, one tile north of it, one northeast, one east, one southeast, one south, and one southwest of it. That's 8 angles, which are 0, 45, 90, 135, 180, 225, 270, and 315.

That only works if you want the adjacents from one tile. Here, the origin remains the same and if you just go the multiples of 45° in each direction for more than one field's distance, you will miss everything in between.

There are different approaches. What I guess would be simple and not too bad is to draw rect frames around the center, each iteration adds one tile size in every direction. This way, you get all the tiles and each time a new one. You can stop when the rect is about to get bigger and if something has been found meanwhile.

 

[Chaosy]

I am aware of that. I allways want the thing working before I think about hmm that native is faster or w/e. BJ functions is comfortable in this case. Saves me a few lines.

and yeah I noticed that too. I change the distance with 64 and the angle with 1 else I miss locations that are far away.