Grid Movement System

[GIMLI_2]

Hi,
I am working on a map with grid movement - that means: the battlefield is like a chess field, units have no "free" movement, they can move X squares in any direction, however, not diagonal (if you know the game "Fire Emblem", you know what i'm talking about). What i have to create is a system that shows me which squares are accessible to move to, there are also non-pathable squares that can hinder movement. On the screenshot you can see the unit (resembled by an X), blocked paths (black blocks), paths that you can move to (green dot) and paths that you could move to without blocked paths (yellow dot). The unit in the example has 6 movement. Until now, i didnt come up with a solution and want to ask you guys if there is a mathematical or warcraftish way to solve it

 

[ISL]

I'm not sure how exactly your system will work, but for that passability case, I'd suggest a scanning/checking thing that would determine whether the path is possible to walk through or not.

You'd need to save all squares between the position of your unit and it's given destination into an array,
Then, use a loop that would check every square that the unit must walk through for passability.

Looking at the picture, all squares on the path are marked with green untill the first unpassable square is met. In case the pass contains an unpassable tile, the tile itself is marked with black, and all tiles afterwards are marked with yellow.

 

[GIMLI_2]

thanks for the reply

I'm not sure how exactly your system will work, but for that passability case, I'd suggest a scanning/checking thing that would determine whether the path is possible to walk through or not.

this is not necessary, the whole battlefield is saved into a hashtable. that means for example Tile(x: 3,y: 2) is not passable and is given the integer 2 (for not passable)

Then, use a loop that would check every square that the unit must walk through for passability.

the thing is that you can walk around the blocked path, so you would need to check several directions

Looking at the picture, all squares on the path are marked with green untill the first unpassable square is met. In case the pass contains an unpassable tile, the tile itself is marked with black, and all tiles afterwards are marked with yellow.

this is not always the case, imagine the units movement would be 7 instead of 6, it could move around the blocked path.

this is what i want to achieve exactly at minute 03:53

 

[nedio95]

You may want to look up A* on google.
It is pretty much exactly what you are describing/need here.
If you have an already done coordinate system, you have 50-ish % done already.

Hope this helps!
-Ned

 

[GIMLI_2]

thanks, i'll take a look at it

 

[ISL]

I'm gonna check it too
Could never really understand how the pathing works in games.
Thank you!

 

[nedio95]

I'm gonna check it too
Could never really understand how the pathing works in games.
Thank you!

This has nothing to do with the pathing in the game, gimli is making his own pathing for this.

Edit// Well, the game pathing is most certainly using A* variant anyway...

 

[WaterKnight]

func step(x, y, remainingSteps)
    if (x < minX || x > maxX || y < minY || y > maxY || isBlocked(x, y) || remainingSteps < 1 || finalMarks[x][y])
        return

    finalMarks[x][y] += true

    step(x - 1, y, remainingSteps - 1)
    step(x + 1, y, remainingSteps - 1)
    step(x, y - 1, remainingSteps - 1)
    step(x, y + 1, remainingSteps - 1)

finalMarks = [][]
step(startX, startY, movementVal + 1)

 

[GIMLI_2]

func step(x, y, remainingSteps, parentMarks)
    if (x < minX || x > maxX || y < minY || y > maxY || isBlocked(x, y) || remainingSteps < 1 || pair(x, y) in parentMarks)
        return

    finalMarks += pair(x, y)
    parentMarks = clone(parentMarks)

    parentMarks += pair(x, y)

    step(x - 1, y, remainingSteps - 1, parentMarks)
    step(x + 1, y, remainingSteps - 1, parentMarks)
    step(x, y - 1, remainingSteps - 1, parentMarks)
    step(x, y + 1, remainingSteps - 1, parentMarks)

finalMarks = []
step(startX, startY, movementVal + 1, [])

thanks for the reply. i get what this piece of code is supposed to do, it basically spreads out in every direction by recalling the function until it hits map end, an unpathable block or a tile that already got checked. (or the unit hits its movement cap)
all the working coordinates get saved in finalMarks, which is basically what i need.
there are some steps i dont understand:
what does clone() do? does it simply copy the input? why do i need it? i guess because every instance has its own parents, but i'm not sure.
"pair(x, y) in parentMarks" does WE support this? or do i have to make it by myself?
all in all, i'm not quite sure how to "translate" this into WE, i do only have basic to no knowledge of structs which i will probably need for pair(x, y) instances

 

[WaterKnight]

what does clone() do? does it simply copy the input? why do i need it? i guess because every instance has its own parents, but i'm not sure.
"pair(x, y) in parentMarks" does WE support this? or do i have to make it by myself?

The parentMarks stuff was just an attempt to optimize it a bit by disallowing to step backwards/run in cycles. I thought that just checking for which fields have been finally marked, it would cut off some paths, leaving gaps. But since the forerunner actually steps in all directions, that does not happen. I have adjusted the algorithm above and would definitely suggest to prefer it because the other one had a really bad complexity, travelling much more sub paths.

Apart from that, the pair could have been translated to a scalar, for example, tile=y*(maxY-minY + 1)+x. The += and in operators there were to denote a set data structure, using an array or hashtable in wc3 for example. An alternative to the scalar approach would be to use two parallel arrays or a struct/class instance like in vjass/wurst. The clone, of course, meant to make a copy of the whole collection up to this point.

Instead of LIFO stack processing, you can also use FIFO/queue. That would yield a more consistent propagation. Maybe if you want to cancel somewhere or want to animate it. See:

Flood fill - Wikipedia

I am not sure about using an A* algorithm because its objective is actually a different one. The A* algorithm tries to find a shortest path between a starting point and destination. My guess is that you could preselect all tiles with a max distance to the starting point, then apply the A* algorithm between the respective tile and the starting point each and throw away the tiles that have been walked intermediately (and make sure the max move distance is considered).

 

[GIMLI_2]

i tried to get it working, but no success


Initialization

Hidden

library Initialization initializer Init

    globals
        real OFFSET_X = -563.
        real OFFSET_Y = -9391.
      
        constant integer TILE_GRASS     = 0
        constant integer TILE_FOREST    = 1
        constant integer TILE_MOUNTAIN  = 2
      
        hashtable FIELD = InitHashtable()
    endglobals

    private function Init takes nothing returns nothing
        call SaveInteger(FIELD, 6, 5, TILE_FOREST)
        call SaveInteger(FIELD, 6, 6, TILE_FOREST)
        call SaveInteger(FIELD, 7, 3, TILE_FOREST)
        call SaveInteger(FIELD, 7, 4, TILE_FOREST)
        call SaveInteger(FIELD, 7, 5, TILE_FOREST)
        call SaveInteger(FIELD, 7, 6, TILE_FOREST)
        call SaveInteger(FIELD, 8, 3, TILE_FOREST)
        call SaveInteger(FIELD, 8, 4, TILE_FOREST)
        call SaveInteger(FIELD, 8, 5, TILE_FOREST)
        call SaveInteger(FIELD, 8, 6, TILE_FOREST)
        call SaveInteger(FIELD, 9, 3, TILE_FOREST)
        call SaveInteger(FIELD, 9, 4, TILE_FOREST)
        call SaveInteger(FIELD, 10, 3, TILE_FOREST)
        call SaveInteger(FIELD, 10, 4, TILE_FOREST)
        call SaveInteger(FIELD, 10, 5, TILE_FOREST)
        call SaveInteger(FIELD, 11, 3, TILE_FOREST)
        call SaveInteger(FIELD, 11, 4, TILE_FOREST)
        call SaveInteger(FIELD, 11, 5, TILE_FOREST)
        call SaveInteger(FIELD, 11, 6, TILE_FOREST)
        call SaveInteger(FIELD, 12, 3, TILE_FOREST)
        call SaveInteger(FIELD, 12, 4, TILE_FOREST)
        call SaveInteger(FIELD, 12, 5, TILE_FOREST)
        call SaveInteger(FIELD, 12, 6, TILE_FOREST)
    endfunction
  
    function GetUnitTileX takes unit u returns integer
        return R2I(((GetUnitX(u) - OFFSET_X) / 128) + 0.5)
    endfunction
  
    function GetUnitTileY takes unit u returns integer
        return R2I(((GetUnitY(u) - OFFSET_Y) / 128) + 0.5)
    endfunction
  
    function X takes integer i returns real
        return OFFSET_X + i * 128
    endfunction
  
    function Y takes integer i returns real
        return OFFSET_Y + i * 128
    endfunction

endlibrary

Pathing

Hidden

library MoveOrder initializer Init uses Initialization

    globals
        constant integer minX = 0
        constant integer minY = 0
        constant integer maxX = 14
        constant integer maxY = 14
        hashtable finalMarks = InitHashtable()
    endglobals
  
    private function Init takes nothing returns nothing
    endfunction
  
    function Step takes integer x, integer y, integer remainingSteps returns nothing
        if (x < minX or x > maxX or y < minY or y > maxY or LoadInteger(FIELD, x, y) == TILE_FOREST or remainingSteps < 1 or LoadBoolean(finalMarks, x, y)) then
            return
        endif
      
        call SaveBoolean(finalMarks, x, y, true)
        call Step(x-1, y, remainingSteps-1)
        call Step(x+1, y, remainingSteps-1)
        call Step(x, y-1, remainingSteps-1)
        call Step(x, y+1, remainingSteps-1)
    endfunction
  
    function HighlightMarks takes nothing returns nothing
        local integer i = 0
        local integer j = 0
        loop
            exitwhen i > 14
            loop
                exitwhen j > 14
                    if LoadBoolean(finalMarks, i, j) then
                        call AddSpecialEffect("Abilities\\Spells\\Undead\\AntiMagicShell\\AntiMagicShell.mdl", X(i), Y(j))
                    endif
                    set j = j + 1
                endloop
            set i = i + 1
        endloop
    endfunction

endlibrary

Test

Hidden

function Trig_Unbezeichneter_Ausl__ser_002_Actions takes nothing returns nothing


    call BJDebugMsg("X: "+R2S(GetUnitX(gg_unit_hpea_0001)))
    call BJDebugMsg("Y: "+R2S(GetUnitY(gg_unit_hpea_0001)))
    call BJDebugMsg("TILE_X: "+I2S(GetUnitTileX(gg_unit_hpea_0001)))
    call BJDebugMsg("TILE_Y: "+I2S(GetUnitTileY(gg_unit_hpea_0001)))
    //call AddSpecialEffect("Abilities\\Spells\\Human\\ThunderClap\\ThunderClapCaster.mdl", X(3), Y(6))
    call Step(GetUnitTileX(gg_unit_hpea_0001), GetUnitTileY(gg_unit_hpea_0001), 6+1)
    call HighlightMarks()
  
endfunction

//===========================================================================
function InitTrig_test takes nothing returns nothing
    set gg_trg_test = CreateTrigger(  )
    call TriggerRegisterPlayerEventEndCinematic( gg_trg_test, Player(0) )
    call TriggerAddAction( gg_trg_test, function Trig_Unbezeichneter_Ausl__ser_002_Actions )
endfunction

obviously it does not clear the hashtable and reset things for now, but it doesnt work on the first attempt anyways

 

[WaterKnight]

    function HighlightMarks takes nothing returns nothing
        local integer i = 0
        local integer j = 0
        loop
            exitwhen i > 14
            set j = 0 //<-------
            loop
                exitwhen j > 14
                    if LoadBoolean(finalMarks, i, j) then
                        call AddSpecialEffect("Abilities\\Spells\\Undead\\AntiMagicShell\\AntiMagicShell.mdl", X(i), Y(j))
                    endif
                    set j = j + 1
                endloop
            set i = i + 1
        endloop
    endfunction

 

[GIMLI_2]

well... that is embarrassing xD

edit: the result seems to work almost, for some reason, it gets cut at the top

 

[WaterKnight]

Hm, the marks can cut off remaining paths after all.

For example:

x000
0000

0 are walkable fields, x is the start position. If it gets 3+1 steps, it can go like this:

1400
2300

stepping 1-2-3-4, then it would revert to the 3 and do:

1400
2340

It cannot go to the left because that's already taken and right is another exhaustion end. 1 and 2 cannot move either, their neighbors already taken. The problem is that 1 could have initially taken another route to reach two more tiles on the right side.

I guess you would have to do it so that for each tile traversed, you save the remaining steps/the steps taken up to this point and allow traversing there again if you have more steps left than were previously saved there. Then the 1 would propagate a 2 to the right, for example, 2<4, so the 2 would overwrite the 4 and continue. Else you would have to remove that check completely and it became very non-performant + jass execution limit problems.

1200
2340

1230
2340

1234
2340

func step(x, y, remainingSteps)
    if (x < minX || x > maxX || y < minY || y > maxY || isBlocked(x, y) || remainingSteps < 1 || remainingSteps < marks[x][y])
        return

    marks[x][y] = remainingSteps

    step(x - 1, y, remainingSteps - 1)
    step(x + 1, y, remainingSteps - 1)
    step(x, y - 1, remainingSteps - 1)
    step(x, y + 1, remainingSteps - 1)

finalMarks = [][]
step(startX, startY, movementVal + 1)

Afterwards check marks[x][y] > 0.

This also enables you to make field types of different movement costs.

 

[GIMLI_2]

it works now, thanks alot!

This also enables you to make field types of different movement costs.

that's great, i wanted to do this anyway