# Grid Movement System

#### GIMLI_2

Level 17
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

Level 13
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

Level 17
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

Level 12
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

ISL

#### GIMLI_2

Level 17
thanks, i'll take a look at it

#### ISL

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

#### nedio95

Level 12
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

Level 25
Code:
``````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)``````

Last edited:

#### GIMLI_2

Level 17
Code:
``````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

Level 25
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).

Last edited:

#### GIMLI_2

Level 17
i tried to get it working, but no success

Initialization

JASS:
``````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

JASS:
``````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
endif
set j = j + 1
endloop
set i = i + 1
endloop
endfunction

endlibrary``````

Test

JASS:
``````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

Level 25
JASS:
``````    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
endif
set j = j + 1
endloop
set i = i + 1
endloop
endfunction``````

#### GIMLI_2

Level 17
well... that is embarrassing xD

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

#### WaterKnight

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

For example:

Code:
``````x000
0000``````

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

Code:
``````1400
2300``````

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

Code:
``````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.

Code:
``````1200
2340``````

Code:
``````1230
2340``````

Code:
``````1234
2340``````

Code:
``````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.

Last edited:

#### GIMLI_2

Level 17
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

Replies
13
Views
803
Replies
14
Views
800
Replies
4
Views
634
sentrywiz
S
Replies
4
Views
515
[Solved] Grid system
Replies
26
Views
713