Je recherche un algorithme qui m'aidera à créer une limite autour des points d'un tableau à 2 dimensions qui ne sont pas nuls. Laissez-moi vous donner un exemple.

J'ai le tableau suivant :]

enter image description here

Je veux un algorithme qui me donnera le moyen le plus efficace de créer une "barricade" autour de chacune des petites "îles". Pour le contexte, chaque groupe de 1 représente une source de ressources dans ce jeu de gestion de ressources, et je veux construire des murs autour pour le protéger de mon adversaire.

Essentiellement, cet algorithme doit donner la valeur des 2s dans la figure suivante :

enter image description here

Il y a quelques points à cela :

  • Le tableau est toujours carré mais la taille de chaque dimension peut varier de 12 à 40 ;
  • Les unités ne peuvent pas se déplacer en diagonale ;
  • Il peut y avoir différentes îles (groupes de 1s), et peut avoir toutes sortes de formes irrégulières ;
  • Parfois, il peut être plus efficace de barricader deux "îles" proches en utilisant la même barricade, si elles sont très proches.

Des idées à ce sujet ? Je ne sais même pas comment googler ce problème, alors j'ai fini par ne rien trouver. Merci!

EDIT1 : Code pour créer le tableau initial EDIT2 : Correction de la réponse

import numpy as np

size = 15
test_mat = np.zeros((size, size))
test_mat[(4, 5, 5, 6), (5, 4, 6, 5)] = 1
test_mat[(9, 9, 9, 10, 10, 11, 11), (8, 9, 10, 8, 10, 8, 10)] = 1
0
David Marques 21 sept. 2021 à 23:13

2 réponses

Meilleure réponse

Que dis-tu de ça:

import numpy as np
from scipy.ndimage import binary_dilation, binary_erosion

size = 15
test_mat = np.zeros((size, size))
test_mat[(4, 5, 5, 6), (5, 4, 6, 5)] = 1
test_mat[(9, 9, 9, 10, 10, 11, 11), (8, 9, 10, 8, 10, 8, 10)] = 1

dilated = binary_dilation(test_mat).astype(int)
eroded = binary_erosion(dilated)
borders = dilated-eroded

Qui donne:

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 1 0 1 0 0 0 0 0 0 0 0]
 [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 1 0 1 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 1 1 1 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 1 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 1 0 0 0]
 [0 0 0 0 0 0 0 1 0 1 0 1 0 0 0]
 [0 0 0 0 0 0 0 0 1 0 1 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]
1
alex 21 sept. 2021 à 21:58

Cela ne résout pas mon problème, je voulais juste poster une idée avec laquelle je jouais. Voici le code :

import numpy

# Generate the map
size = 15
test_mat = np.zeros((size, size))
test_mat[(4, 5, 5, 6), (5, 4, 6, 5)] = 1
test_mat[(9, 9, 9, 10, 10, 11, 11), (8, 9, 10, 8, 10, 8, 10)] = 1

# Find a solution by applying a convulsion
conv_mat = np.array([
        [0, 1, 0], 
        [1, 1, 1],
        [0, 1, 0]])

conv = convolve(test_mat, conv_mat)
conv[test_mat > 0] = 0
conv[conv > 0] = 2
conv[test_mat > 0] = 1 # Mark the resources as 1

En utilisant ce code vous obtenez :

enter image description here

Cependant, comme vous pouvez le voir, lorsqu'il y a un écart, cela ne trouve pas la bonne solution..

0
David Marques 21 sept. 2021 à 22:01