# Grid-based movement - how to limit (and display) potential move distance

Attention Topic was automatically imported from the old Question2Answer platform.

Hey everyone! First time asking a question, so I hope it will be clear.

In a grid based game, I want to show the player the potential distance they can move.
But I am having difficulty with the diagonal tiles.

Basically I have a navigation map, and child to modulate the tiles the player can move to. In the below example you can see what I get when I allow the player one tile of movement:

The code in this regard, is just this:

``````func show_traversible_tiles():
var tile_pos = world_to_map(player.position)
var tile_id = get_cellv(tile_pos)

var move_distance = 1

for steps in move_distance+1:
``````

next up is one step further of potential movement

With this code (which is probably incredibly wrong):

``````func show_traversible_tiles():
var tile_pos = world_to_map(player.position)
var tile_id = get_cellv(tile_pos)

var move_distance = 2

for steps in move_distance+1:
``````

But it just completely breaks down after this.
I’m having a hard time figuring out how to cleanly write this and make it scale. So that it works at every distance.

Here’s a rather naive (but working) implementation:

``````func get_reachable_tiles(starting_pos, move_distance):
if move_distance == 0:
return []

var reachable_positions = [starting_pos]

while move_distance > 0:
var new_positions = []
for tile_pos in reachable_positions:
new_positions.append(tile_pos + Vector2(1, 0))
new_positions.append(tile_pos - Vector2(1, 0))
new_positions.append(tile_pos + Vector2(0, 1))
new_positions.append(tile_pos - Vector2(0, 1))
for tile_pos in new_positions:
if not tile_pos in reachable_positions:
reachable_positions.append(tile_pos)
move_distance -= 1

return reachable_positions
``````

This does not consider obstacles (i.e. tiles they player cannot walk on), has no notion of terrain/movement cost, will check many nodes multiple times and as GDscript does not have sets like e.g. python, I used an array. If you want to refine this, I recommend you read up on “Djikstra’s algorithnm” and the “Manhattan distance”.

Hey Njamster!

Thanks a lot for this solution!
It’s working just as I could’ve hoped for.

I will definitely look into those two, thanks for advising me on some stuff to read up on

I struggled with something for just a couple minutes, as I hadn’t realised that the starting_pos argument in the function had to be my player’s position already converted with world_to_map(). After I noticed that, everything worked swimmingly.

Thanks again!

Blissful | 2020-05-25 12:10

Hi, I’m not sure how late I am to the party but I’ve come up with a solution to your problem. I’m sure our projects are set up differently so I’ll make notes of how mine are set up as it becomes necessary.
Here is my code.

``````# Uses a Depth First Search algorithm to find paths.
func get_paths(start_position, distance):
# Standard start to a Deapth First Search algorithm.
# Crate a queue to hold values. In this case I'm using a Vector3 so I can hold
# positional vectors as well as the distance allowed left.
var queue = [Vector3(start_position.x, start_position.y, distance)]
# This array is going to be used to hold the values that we have checked.
# It is going to help us save a little bit of time in calculations.
var checked_tiles = []
# Loop while the queue is not empty.
while queue.size() > 0:
# Get the current tile to check. On the first iteration this is going
# to be the starting position.
var current_tile = queue.pop_front()
# If the current tile has surpassed it's move limit it will be forgotten
# and the function will continue to loop. If the tile we are looking at
# has already been checked continue.
if current_tile.z == -1 or Vector2(current_tile.x, current_tile.y) in checked_tiles:
continue
# In my program I made a translucent tile that I used to represent the
# available spots to move to. Seeing that this position is in the queue
# we know it is supposed to be a square we can go to, so I give it that
# translucent square.
set_cell(current_tile.x, current_tile.y, 2)

# I create a new Vector2 so that I can do some operations on the values
# easier. This one I am getting the tile to the right of it.
var newVector = Vector2(current_tile.x, current_tile.y) + Vector2.RIGHT
# My project is using the "Grid Based Movement" project as a base. So
# if the tile I'm checking is able to be walked on, add that tile to the
# queue.
if newVector in walkable_cells_list:
queue.append(Vector3(newVector.x, newVector.y, current_tile.z - 1))
# Reassign the vector and repeat this process for all four directions.
# Note that if you wanted diagonals you would have four more if statements
# that would do something like: ... + Vector2.Left + Vector2.UP
newVector = Vector2(current_tile.x, current_tile.y) + Vector2.LEFT
if newVector in walkable_cells_list:
queue.append(Vector3(newVector.x, newVector.y, current_tile.z - 1))
checked_tiles.append(Vector2(current_tile.x, current_tile.y))
newVector = Vector2(current_tile.x, current_tile.y) + Vector2.UP
if newVector in walkable_cells_list:
queue.append(Vector3(newVector.x, newVector.y, current_tile.z - 1))
checked_tiles.append(Vector2(current_tile.x, current_tile.y))
newVector = Vector2(current_tile.x, current_tile.y) + Vector2.DOWN
if newVector in walkable_cells_list:
queue.append(Vector3(newVector.x, newVector.y, current_tile.z - 1))
checked_tiles.append(Vector2(current_tile.x, current_tile.y))
``````

This is basically a Deapth First Search algorithm but we are not looking for anything, so it continues to loop until it exhaust all it’s options. Instead of changing a tile like I did you can add it to a list and return the list of you liked.