Algoritmo de relleno de inundación stackoverflow
– UnityAssets3Free
hola , soy Daniel y hoy os traigo
esta unity pregunta
Estoy trabajando en un juego de pintura, pero no puedo hacer que el algoritmo de relleno de inundación funcione en áreas grandes. Es un algoritmo recursivo y he leído que implementar una pila podría funcionar, pero también puedo hacer que funcione. Aquí está el código;
private void FillCluster(int x, int y, int colorIndex, HashSet<string> traversedCells)
2 respuestas 2
una versión sin tener que recordar todas las celdas visitadas porque ya están marcadas por color
private void FillCluster(int x, int y, int colorIndex)
Debug.Log(colorIndex);
var currentSeam = new Queue<PointDirection>();
if (FillPoint(x, y, colorIndex))
currentSeam.Enqueue(new PointDirection(x - 1, y, Direction.Left));
currentSeam.Enqueue(new PointDirection(x + 1, y, Direction.Right));
currentSeam.Enqueue(new PointDirection(x, y - 1, Direction.Up));
currentSeam.Enqueue(new PointDirection(x, y + 1, Direction.Down));
while (currentSeam.Count > 0)
var current = currentSeam.Dequeue();
if (FillPoint(current.X, current.Y, colorIndex))
if (current.Direction != Direction.Right)
currentSeam.Enqueue(new PointDirection(x - 1, y, Direction.Left));
if (current.Direction != Direction.Left)
currentSeam.Enqueue(new PointDirection(x + 1, y, Direction.Right));
if (current.Direction != Direction.Down)
currentSeam.Enqueue(new PointDirection(x, y - 1, Direction.Up));
if (current.Direction != Direction.Up)
currentSeam.Enqueue(new PointDirection(x, y + 1, Direction.Down));
private bool FillPoint(int x, int y, int colorIndex)
y >= ActivePictureInfo.YCells
private struct PointDirection
public PointDirection(int x, int y, Direction direction)
X = x;
Y = y;
Direction = direction;
public int X get;
public int Y get;
public Direction Direction get;
private enum Direction : byte
Up,
Right,
Down,
Left
Entonces, la razón por la que obtiene un stackOverflow es porque el estado de la iteración anterior se guarda en la pila a menos que se cumplan ambas condiciones:
- Estás haciendo recursividad de cola (búscalo pero no es relevante ahora)
- Su idioma optimiza la recursividad de la cola (C# no lo hace)
Dado que el tamaño de la pila es limitado y su algoritmo alcanza muy rápidamente miles de llamadas una tras otra, no puede hacer que la versión recursiva funcione en C#, esto es imposible, pero parece que ya lo ha descubierto.
Aquí hay una solución de pseudocódigo para hacer esto sin recursión. No conozco C#, por lo que la sintaxis no es correcta, pero la idea es correcta, tendrás que convertirla en C# adecuado.
private void FillCluster(int x, int y, int colorIndex, HashSet<string> traversedCells)
Debug.Log(colorIndex);
// Check if this cell is within the bounds of the picture and has a color number and the
//Declare a set, add inside the current node
Set<Tuple> nodesToFill = new Set<>()
nodesToFill.add(new Tuple(x, y));
//Replace the recursion by a loop
for (Tuple tuple in nodesToFill)
//initialize the current position
x = tuple.first
y = tuple.second
//Deal with the current node
if(FillClusterInner(x, y, colorIndex, traversedCells))
//Add the new nodes to the set instead of using recursion
nodesToFill.add(new Tuple(x-1, y))
nodesToFill.add(new Tuple(x + 1, y))
nodesToFill.add(new Tuple(x, y - 1))
nodesToFill.add(new Tuple(x, y + 1))
nodesToFill.add(new Tuple(x - 1, y - 1))
nodesToFill.add(new Tuple(x - 1, y + 1))
nodesToFill.add(new Tuple(x + 1, y - 1))
nodesToFill.add(new Tuple(x + 1, y + 1))
//Remove the current tuple from the set as you have dealt with it
nodesToFill.remove(tuple)
//This is a non-recursive method which fills a single specified node
bool FillClusterInner(int x, int y, int colorIndex, HashSet<string> traversedCells)
Puedes ver la idea: en lugar de recursividad, usamos un conjunto, que contiene todos los índices de los nodos que aún necesitamos llenar. Agrega a este conjunto en lugar de llamar a la función recursiva y elimina cada posición manipulada del conjunto. Cuando el conjunto está vacío, ha completado todas las celdas que debían completarse.
nota: si aun no se resuelve tu pregunta por favor dejar un comentario y pronto lo podremos de nuevo , muchas gracias
por hoy,espero que te funcione
