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

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Blissful

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:one-space-movement.png

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:
	navigation_overlay.set_cell(tile_pos.x+steps, tile_pos.y, tile_id)
	navigation_overlay.set_cell(tile_pos.x-steps, tile_pos.y, tile_id)
	navigation_overlay.set_cell(tile_pos.x, tile_pos.y+steps, tile_id)
	navigation_overlay.set_cell(tile_pos.x, tile_pos.y-steps, tile_id)

next up is one step further of potential movement Knipsel.png

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:
	navigation_overlay.set_cell(tile_pos.x+steps, tile_pos.y, tile_id)
	navigation_overlay.set_cell(tile_pos.x-steps, tile_pos.y, tile_id)
	navigation_overlay.set_cell(tile_pos.x, tile_pos.y+steps, tile_id)
	navigation_overlay.set_cell(tile_pos.x, tile_pos.y-steps, tile_id)
	navigation_overlay.set_cell(tile_pos.x+int(steps/2), tile_pos.y+int(steps/2), tile_id)
	navigation_overlay.set_cell(tile_pos.x-int(steps/2), tile_pos.y-int(steps/2), tile_id)
	navigation_overlay.set_cell(tile_pos.x+int(steps/2), tile_pos.y-int(steps/2), tile_id)
	navigation_overlay.set_cell(tile_pos.x-int(steps/2), tile_pos.y+int(steps/2), tile_id)

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.

2
:bust_in_silhouette: Reply From: njamster

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 :slight_smile:

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

3
:bust_in_silhouette: Reply From: Fluff3rNutt3r

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.