Invalid get index '(0.707107, 0.707107)' (on base: 'Dictionary') for flood fill algorithm

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

I am modifying THE FLOOD FILL ALGORITHM on GDQuest so that each direction has its own amount of cells that you can move, like for instance, directly up (0,1) you can move 4 cells so I made a dictionary for that.

Input code:

func _flood_fill(cell: Vector2, move_cell_range: Dictionary) -> Array[Vector2i]:

	var array := []
	var stack := [cell]
	
	while not stack.is_empty():
		var current = stack.pop_back()

		# The conditions are :
		# 1. We didn't go past the grid's limits.
		# 2. We haven't already visited and filled this cell
		# 3. We are within the `max_distance`, a number of cells.
	
		# move_cell_range is a dictionary with
		# key: orientation, value: amount of cells traversible
	# distance_to will be compared to the value while direction_to will be for key

		# Invalid get index '(0.707107, 0.707107)' (on base: 'Dictionary').
		if not a_star_grid.is_in_boundsv(current) or current in array or cell != current and cell.distance_to(current) > move_cell_range[cell.direction_to(current)]:
			continue
			
		array.append(current)
		
		for direction in move_cell_range:			
			var total_direction := Vector2(0,0)
			for n in move_cell_range[direction]:
				# Is necessary to make sure stack gets all possible cells in all directions since different directions have different amount of walkable cells
				total_direction = direction + total_direction
				var coordinates = current + total_direction
			
				# Check if the cell is available to walk on, do we need to check to make sure the coordinate isn't past the edge of the map?
				if a_star_grid.is_point_solid(coordinates) or coordinates in array:
					continue
				
				stack.append(coordinates)
	for c in array:
		_set_disable_or_enable_cell(c, false)
			
	return array

For the cell parameter, the input is (7,5), and the move_cell_range parameter takes:

{
	Vector2(0,1): 4, 
	Vector2(1,1): 1, 
	Vector2(1,0): 4, 
	Vector2(1,-1): 1, 
	Vector2(0,-1): 4, 
	Vector2(-1,-1): 1, 
	Vector2(-1,0): 4, 
	Vector2(-1,1): 1
}

The key represents the direction and the value represents the amount of cells per direction.

The stack variable has values:

[
	Vector2(6, 4),
	Vector2(6, 5),
	Vector2(5, 5),
	Vector2(4, 5),
	Vector2(3, 5),
	Vector2(6, 6),
	Vector2(7, 4),
	Vector2(7, 3),
	Vector2(7, 2),
	Vector2(7, 1),
	Vector2(7, 6),
	Vector2(7, 7),
	Vector2(7, 8),
	Vector2(7, 9),
	Vector2(8, 4),
	Vector2(8, 5),
	Vector2(9, 5),
	Vector2(10, 5),
	Vector2(11, 5)
]

I then get that error: Invalid get index ‘(0.707107, 0.707107)’ (on base: ‘Dictionary’) when (8,6) is reached. The expected result should be this array below, with the comment in # representing the orientation

[
	# (-1, -1)
	Vector2(6, 4),
	# (-1, 0)
	Vector2(6, 5), Vector2(5, 5), Vector2(4, 5), Vector2(3, 5),
	# (-1, 1)
	Vector2(6, 6), 
	# (0, -1)
	Vector2(7, 4), Vector2(7, 3), Vector2(7, 2), Vector2(7, 1),
	# (0, 1)
	Vector2(7, 6), Vector2(7, 7), Vector2(7, 8), Vector2(7, 9),
	# (1, -1)
	Vector2(8, 4), 
	# (1, 0)
	Vector2(8, 5), Vector2(9, 5), Vector2(10, 5), Vector2(11, 5),
	# (1, 1)
	Vector2(8, 6)
]

I seriously cannot figure out how or why it’s checking for (0.707107, 0.707107). I think something about the coordinate variable is screwing up the system?

Thank you to anyone who replies.

:bust_in_silhouette: Reply From: jgodfrey

While I don’t follow everything you’re doing here, the problem would seem to be here:

move_cell_range[cell.direction_to(current)]

That’s taking the current cell (a Vector2) and calculating the direction to the Vector2 named current. As documented, that returns a normalized vector (the .707, .707 value).

You’re then using that value as a key value into the move_cell_range dictionary, which doesn’t exists - resulting in the error you report.

After looking closer, I assume you’re expecting 1,1 instead of .707,.707. Remember, a normalized vector has a length of 1, which this vector does…

jgodfrey | 2023-04-21 19:52

Ah, I see I see, first, thank you for responding, so is the goal not to use a normalised vector then? So in the code for the original tutorial, this is what is written.

# This is where we check for the distance between the starting `cell` and the `current` one.
		var difference: Vector2 = (current - cell).abs()
		var distance := int(difference.x + difference.y)
		if distance > max_distance:
			continue

and this is how I was trying to replicate it:

cell.distance_to(current) > move_cell_range[cell.direction_to(current)]

I think I still need to get the direction from cell to current in order to make sure I get the orientation to pass in as the key to return the value.

With the code, is there anything I should explain? To me it seems to be self explanatory combined with the tutorial I posted but I seem to be very much wrong.

I think I also remember a previous issue, if I didn’t check whether cell wasn’t equal to current, it would give me the same error, but the index being (0,0).

How would I add (8, 6) then, that’s the question. Another problem is in the original tutorial, once you add a value to stack, it will finish that sequence then go back to pop out the latest value from stack, I can’t figure out how I would do that in my version in order to add to array.

maict | 2023-04-21 20:24

:bust_in_silhouette: Reply From: maict

I changed cell and move_cell_range’s key to Vector2i.

# Invalid get index '(1, 0)' (on base: 'Dictionary'). HUH?
        if not a_star_grid.is_in_boundsv(current) or current in array or cell != current and Vector2(cell).distance_to(current) > move_cell_range[current - cell if Vector2(current - cell).abs() == Vector2(1, 1) else Vector2(cell).direction_to(current)]:
            continue

So I modified the original check to see if array would append the value to bypass the Invalid get index '(0.707107, 0.707107)' error, however, now it gives me that new error even though (1, 0) exists in my dictionary. current is (11, 5), cell is (7, 5).

Cast to Vector2i, otherwise it won’t work since the returned value is a Vector2 although my dictionary takes Vector2i:

if not a_star_grid.is_in_boundsv(current) or current in array or cell != current and Vector2(cell).distance_to(current) > move_cell_range[current - cell if Vector2(current - cell).abs() == Vector2(1, 1) else Vector2i(Vector2(cell).direction_to(current))]:
		continue

However there’s a new problem now, stack keeps adding values constantly.

Rewrote the entire thing, thank you to the person who rewrote this code:

func _not_really_a_flood_fill(cell: Vector2i, move_cell_range: Dictionary) -> Array[Vector2i]:
var valid_cells: Array[Vector2i] = []    
for direction in move_cell_range:
    for r in range(1, move_cell_range[direction] + 1):
        var current: Vector2i = cell + r * direction
        if not a_star_grid.is_in_boundsv(current) or a_star_grid.is_point_solid(current):
            break			
        valid_cells.append(current)
return valid_cells