All Questions

Community

Daniel Queiroz Porto
posted to: The Grid

Function "as_index()" doesn't generate unique indices

The PathFinding in the game I'm making based on this course was behaving really strange so I started printing out things to try to figure it out and I got this:

PathFinder | cell_mappings: {(10, 2):30, (10, 3):40, (10, 4):50, (10, 5):60, (11, 1):22, (11, 2):33, (11, 3):44, (11, 4):55, (11, 5):66, (11, 6):77, (12, 2):36, (12, 3):48, (12, 4):60, (12, 5):72, (12, 6):84, (13, 3):52, (13, 4):65, (13, 5):78, (8, 4):40, (9, 3):36, (9, 4):45, (9, 5):54}

If you take a look at it both (10, 3) and (8, 4) have an index of 40. and it makes sense as:

(10 + (10 * 3) = 40

(8 + (8 * 4)) = (8 + 32) = 40

Also (10, 5) and (12, 4) are both 60 as well.

So to fix it I tried to look up if there was another formula for it and I found something called Cantor Pairing Function but it returns a float so I couldn't use it, then I changed PathFinder,gd so that `cell_mappings` is a member variable and `calculate_point_path()` look for the start and end vectors in `cell_mappings` instead of asking the grid for the index.

This also removed the PathFinder's dependency on the `Grid` but now I have to check if the Vectors are both present into `cell_mappings` before trying to calculate a path.

Here is the script in the end:

# Helper class to find paths
class_name PathFinder
extends Reference

### Member Variables and Dependencies -----------------------------------
#--- signals ------------------------------------------------------------

#--- enums --------------------------------------------------------------

#--- constants ----------------------------------------------------------

const DIRECTIONS = [ Vector2.UP, Vector2.RIGHT, Vector2.DOWN, Vector2.LEFT]

#--- public variables - order: export > normal var > onready ------------

#--- private variables - order: export > normal var > onready -----------

var _cell_mappings: = {}
var _astar: = AStar2D.new()

### ---------------------------------------------------------------------


### Built in Engine Methods ---------------------------------------------

func _init(walkable_cells: Array) -> void:
	for index in walkable_cells.size():
		var cell: Vector2 = walkable_cells[index]
		_cell_mappings[cell] = index
	
#	print("PathFinder | cell_mappings: %s"%[_cell_mappings])
	_add_and_connect_points(_cell_mappings)

### ---------------------------------------------------------------------


### Public Methods ------------------------------------------------------

func calculate_point_path(start: Vector2, end: Vector2) -> PoolVector2Array:
	var point_path: = PoolVector2Array()
	if not _cell_mappings.has(start) or not _cell_mappings.has(end):
		return point_path
	
	var start_index: int = _cell_mappings[start]
	var end_index: int = _cell_mappings[end]
	
	if _astar.has_point(start_index) and _astar.has_point(end_index):
		point_path = _astar.get_point_path(start_index, end_index)
	
	return point_path

### ---------------------------------------------------------------------


### Private Methods -----------------------------------------------------

func _add_and_connect_points(cell_mappings: Dictionary) -> void:
	for point in cell_mappings:
		_astar.add_point(cell_mappings[point], point)
	
	for point in cell_mappings:
		_connect_neighbour_indices(point, cell_mappings)


func _connect_neighbour_indices(cell: Vector2, cell_mappings: Dictionary) -> void:
	for direction in DIRECTIONS:
		var neighbour: Vector2 = cell + direction
		if not cell_mappings.has(neighbour):
			continue
		
		if not _astar.are_points_connected(cell_mappings[cell], cell_mappings[neighbour]):
			_astar.connect_points(cell_mappings[cell], cell_mappings[neighbour])

### ---------------------------------------------------------------------
  • Nathan Lovato replied

    There's an error in the calculations. Given a fixed grid size, the function should calculate:

    x + grid_size.x * y

    So for your two points (10, 3) and (8, 4), given the grid size is 10 * 10, the calculations are:

    10 + 10 * 3 = 40

    8 + 10 * 4 = 48

    The two indices are different.

    Did you test this issue with the course's project? The code looks fine to me: it returns x + row_size * y

    func as_index(cell: Vector2) -> int:
        return int(cell.x + size.x * cell.y)
  • Daniel Queiroz Porto replied

    I see! I'm so sorry! It was probably a typo on my end then, my function looked like:

    func as_index(cell: Vector2) -> int:
        return int(cell.x + cell.x * cell.y)
    And even after looking at the course code again I couldn't see it! It was size.x and not cell.x in the middle!

    Though I did like the alternative with PathFinder without the Grid dependency, so maybe I'll keep it? Do you think there's any big disavantages in using the array index instead of calculating one through the grid?

    I mean we're creating a new PathFinder everytime we change units, and that was the only place that was using the "as_index" method, so I though there would be no problem.

    This is the first time I'm not following the course exactly step by step as I'm making a "virtual tabletop game" with a friend and it's in 3d, so I took this chapter and the grid movement as a base to adapt it to 3D, so I must have done this typo at some point and since I also had to change some other stuff, I just didn't notice it!


  • Nathan Lovato replied

    It's completely fine to use array indices or another method. The main advantage of being able to map coordinates and indices is when your game scales, you can find cases where the ability to convert comes in handy. But if that's not the case in your project, you don't have to worry about it.