I cannot see the error: remove: Index p_index = 29 is out of bounds (size() = 16)

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

Okay, so I understand what the error means, but I don’t understand why it’s happening. The problem is at a point where I remove elements in an Array, but I though that the way I was doing wouldn’t give me errors. I attach the the function that gives me problems. I highlight the part where the error is with many # (the error happens for many indeces and sizes, since the array is changing and the are some randomness):

func _continents_tiles(continentsProportion : float, tries : int = 10, maxContinentDist : int = 50):
	
	# auxilar variable for continent
	var continent : PoolVector2Array
	# continents 'Array' (output)
	var continents : Array = []
	# auxiliar proportion between, the while loop is broken when
	# 'proportion > continentsProportion'
	var proportion : float = 0
	# auxilar 'Array' containing the hexagonal distance between the initial tile
	# of the continent and the other tiles
	var radiusArray : Array
	# the maximun distance of the above 'Array'
	var radius : int	
	
	
	# warning-ignore:integer_division
	var ring : Array = Array(GLOBALS.hex_ring(Vector2.ZERO, self.R/2))
	# auxiliar variable
	var ringDist : int
	var toRemoveFromRing : Array
	
	var initial : Vector2
	
	# set an initial continent
	initial = GLOBALS.random_array_element(ring)
	ring.remove(ring.find(initial))
	# create the continent and add it to the list of continents
	continent = GLOBALS.self_avoinding_compact_random_walk(initial, 2*self.R, self.tilesVpositions)
	continents.append(continent)
	# calculate the biggest radii in the continent
	radiusArray = PoolIntArray([])
	for i in range(continent.size()):
		radiusArray.append(GLOBALS.hex_dist(initial, continent[i]))
	radius = radiusArray.max()
	# recalculate proportion and tries
	proportion = float(GLOBALS.ArrayArray_size(continents))/self.tilesVpositions.size()
	tries -= 1
	
	while proportion <= continentsProportion and tries > 0:
		
		# add some distance, or not, to the next continent
		radius += self.rng.randi_range(0, maxContinentDist)
		# remove ring tiles that are too close
		# recalculate ring
		toRemoveFromRing = []
		#######################################################################
		#######################################################################
		#######################################################################
		#######################################################################
		#######################################################################
		for i in range(ring.size()):
			ringDist = GLOBALS.hex_dist(ring[i], initial)
			if ringDist <= radius:
				toRemoveFromRing.append(i)
		for i in range(toRemoveFromRing.size()): # HERE
			ring.remove(toRemoveFromRing[i])
		#######################################################################
		#######################################################################
		#######################################################################
		#######################################################################
		#######################################################################
		if ring.size() == 0:
			break
		
		# set next continent
		initial = GLOBALS.random_array_element(ring)
		ring.remove(ring.find(initial))
		# create the continent and add it to the list of continents
		continent = GLOBALS.self_avoinding_compact_random_walk(initial, 2*self.R, self.tilesVpositions)
		continents.append(continent)
		# calculate the biggest radii in the continent
		radiusArray = PoolIntArray([])
		for i in range(continent.size()):
			radiusArray.append(GLOBALS.hex_dist(initial, continent[i]))
		radius = radiusArray.max()
		# recalculate proportion and tries
		proportion = float(GLOBALS.ArrayArray_size(continents))/self.tilesVpositions.size()
		tries -= 1
	
	return continents
2
:bust_in_silhouette: Reply From: loipesmas

If I’m understanding correctly, it seems it goes like this:
Let’s assume ring variable at that point looks like this:

[ foo, bar, buzz ]

foo has index 0, bar index 1, buzz index 2.
Now, let’s say we want to remove foo and buzz, so we get their indexes, 0 and 2 respectively. (That’s what you store in toRemoveFromRing)
We do ring.remove(0) to remove foo.
Now ring looks like this:

[ bar, buzz ]

And now we want to remove buzz, which had index 2, so we would do ring.remove(2). But now buzz is actually at index 1, and index 2 is out of bounds. All that because when we removed an element in “moved” other elements that were after that one index lower.

There are two solutions that come to my mind:

  1. Store objects to be removed instead of indexes and use .erase(). It most of the time works the way you want, but you need to remember that it removes the first occurrence of the item from the array. So if you have var arr = [ foo, bar, buzz, foo ] and do arr.erase(foo) it would result in [ bar, buzz, foo]. Which might not always be what you wanted.
  2. Instead of removing from the old array, make a new one with only the things you need. Code would look like this:
var new_ring = []
for i in range(ring.size()):
        ringDist = GLOBALS.hex_dist(ring[i], initial)
        if ringDist > radius:
            new_ring.append(ring[i])
ring = new_ring

Not sure which one is more optimal, I’d guess they are similar.
There’s probably a better way to do this, but that’s what I’ve come up with and it should work (I haven’t tested this particular code though).
Hope this helps!

If performance isn’t a concern, OP could also iterate through toRemoveFromRing backwards while removing. That way the indexes that change would have already been removed.

Your solution #2 is probably more efficient than that, though, since it doesn’t repeatedly move all the later entries for each .remove() call.

cheese65536 | 2021-04-14 06:27

Thanks to everyone. The methods take the same time more or less. The fastest way was:

	for i in range(ring.size()):
		ringDist = GLOBALS.hex_dist(ring[i], initial)
		if ringDist <= radius:
			toRemoveFromRing.append(i)
	for i in range(toRemoveFromRing.size()): # HERE
		ring.remove(toRemoveFromRing[toRemoveFromRing.size()-1-i])

with erase the time is slightly bigger (order of 0.1 seconds bigger). The option 2) proposed by @loipesmas is the slowest with a difference of 0.5 seconds approximately.

abelgutierrez99 | 2021-04-14 09:54