Getting neighbor cells in an Array that stores Polygon2D states.

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

(You can right click on the pictures to see them, I can’t figure out how to upload them as url properly)

In advance, I might not be using the best solution to this problem, but using this simple array lets me reference the polygons in an easy way, without each polygon haveing a seperate script. The 2D array version is just there, because it helps in visualisation and the examples I found (wich were in other languages) used them to solve this issue, and I tought it might help you figuring out a solution to this.

I have a script that (randomly) generates something like this:

every polygon’s color is a “state” and is stored in an array.
(wich I can make a 2D version of)

var possible_states : Array = [0, 1, 2, 3, 4] 

For an example let’s work with a smaller array:

var polygon_states = [2, 3, 3, 3, 1, 3, 4, 4, 2, 0, 2, 3, 3, 2, 2]

these are states of polygons in spawn order (from upper right-corner to bottom-left)

If it makes it simpler, I can make a 2D version of this array:

var polygon_states = [ [2, 3, 3, 3, 1], # Row 0 (= basiccally y position)
                       [3, 4, 4, 2, 0], # Row 1
                       [2, 3, 3, 2, 2] ] # Row 2

I calculate x and y like this: (It might not be the best solution IDK)

var x = int(child_index / row_legth)
var y = int(child_index % row_legth)
# child_index = the index of a polygon's state in "polygon_states"

I want a function that would take this array and an index (as it was a 1 dimensional array) and return it’s 8 neigbor’s values.
You could represent the neighbours’ place in 2D array like this:

var neighbors : Array = [
    array2D[x][y+1], array2D[x][y-1],
	array2D[x+1][y], array2D[x-1][y],
	array2D[x+1][y+1], array2D[x+1][y-1],
	array2D[x-1][y+1], array2D[x-1][y-1]   ]

And Using indexes, I want to be able to get it to look like this:

 var neighbors_index = [0, 1, 2, 5, 7, 10, 11, 12] # Order doesn't matter

I tried doing this, to get the indexes like above:

var neighbor_indexes : Array = [
	(x) * row_legth + (y+1), (x) * row_legth + (y-1),
	(x+1) * row_legth + (y), (x-1) * row_legth + (y),
	(x+1) * row_legth + (y+1), (x+1) * row_legth + (y-1),
	(x-1) * row_legth + (y+1), (x-1) * row_legth + (y-1)       ]

However, when I plug in an index of a polygon, that is on the edge, that means, there aren’t 8 neighbors, but this method doesn’t know that, so it calculates uncorrect or impossible indexes for neighbors. (Here’s a visualisation of which indexes work with this:)

So I tried solving this problem like this:

for index in neighbor_indexes:
	if index < 0 || index > polygon_state.size():
		neighbor_indexes.erase(index)

This way, I just delete the indexes, that aren’t in the polygon_states (so the negative indexes, plus the ones that are higher than the array’s size), but there are two problems with this:

  • It doesn’t do what it’s supposed to (I have no Idea why it doesn’t work)
  • It doesn’t solve the problems at the sides, where it returns possible, but incorrect
    values

The problem at the sides, at a small, (3 rows) scale

PS: Hope you understand this ramble. I tried to give as much information as I could. If you don’t understand something or think you can tell me something about tips at using this Q&A let me know.

:bust_in_silhouette: Reply From: Szesan

What I usually do in a situation like this is, that I don’t store plain integers in my array, but I create a specific class or struct to hold the positional data. Then I store instances of this new class in my arrays.

These instances can track all the indexes you need.

You know, not a bad idea.

TheoTheTorch | 2020-12-25 20:31

:bust_in_silhouette: Reply From: Omicron
for index in neighbor_indexes:
    if index < 0 || index > polygon_state.size():
        neighbor_indexes.erase(index)

there are two problems with this code:

  • you are mutating a collection on which you are iterating, that might lead to undefined behaviors, like skipping elements or even crashing
  • you aren’t detecting 2d sides

first to help debug/clean a bit, i would refactor those things:

  • create array of relative neighbourgh coord, like [[-1,-1],[0,-1],[1,-1]],…]
  • iterate on that array to compute coord of interest
  • check on those coords, they are inside your both 2d sizes of you array of polygon_states

try to split your code with funcs :

  • 2d->1d index conversion to use it when needed, instead of inlining everywhere
  • is_valid coords

And how should I go about that is_valid() function?

 is_valid_index(index):
if index > 0 || index < polygon_states:
	return false
# Some more stuff that IDK how to start with
return true

TheoTheTorch | 2020-12-25 22:00

convert index to coord first
then test coord

Omicron | 2020-12-25 22:50