+1 vote

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.

in Engine by (23 points)

2 Answers

+2 votes
Best answer

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".

by (10,221 points)
selected by

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 startingpos argument in the function had to be my player's position already converted with worldto_map(). After I noticed that, everything worked swimmingly.

Thanks again!

0 votes

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.

by (14 points)
Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to webmaster@godotengine.org with your username.