Consejos sobre listas para implementar "deshacer"

[Drumpi]

Hola a todos:

Ya conoceis mis peripecias con el editor de mapas de tiles v2 (necesito ponerle un nombre :P). Ahora iba a implementar la función de deshacer, pero al darle vueltas no consigo encontrar la mejor solución para implementarlo, a ver si me podeis aclarar un poco las ideas. Primero os cuento qué es lo que necesito y luego os cuento algunas ideas.

Para deshacer quiero implementar una lista dinámica por cada mapa que tenga cargado, con opción de deshacer y rehacer. Cada clic con una herramienta generaría un "paso", donde se almacenaría la coordenada del tile, el valor antiguo y el nuevo. Pero hay herramientas como "rellenar" o "mover" que requieren modificar más de un tile, por lo que ese tipo de "pasos" tendrá varios "elementos" de tamaño indefinido.
La idea es tener un puntero que señale a la posición del último cambio realizado, de forma que si se le da a deshacer, se consulta ese paso y sus elementos para deshacerlos, y mover el puntero una posición atrás, sin borrar dicho paso, por si queremos rehacer. Pero si tras dar el paso atrás hacemos otro cambio, borraríamos todos los pasos que hay a continuación del puntero y añadiríamos el nuevo.

Para los pasos voy a usar una lista doblemente enlazada, para poder moverme con libertad adelante y atrás, y voy a tener dos punteros, el de inicio de la lista para no perderla, y el que indica la posición en la que estamos para deshacer y rehacer.
Lo que me preocupa es que, si tengo que añadir un montón de elementos en un solo frame a un paso, el algoritmo sería "busca el paso" (que no sería difícil por el segundo puntero), "recorre la lista de elementos hasta el final" y "añade otro elemento". No es un problema si tenemos pocos pasos, pero imaginemos que tenemos un mapa de 50x50 tiles (2500 tiles) y los rellenamos todos ¡hay que recorrer una lista que se incrementa cada vez 2500 veces! Creo que es mucha tela para un solo frame, al que hay que sumar el algoritmo que modifica el mapa (hablo, por supuesto, del algoritmo de relleno).

No quería tener dos punteros en la lista de elementos (como sí tengo en el de pasos), y la única solución que se me ha ocurrido, de momento, es crear un array usando realloc (puntero, sizeof(elemento) * (tamaño + 1)), pero no sé cómo de eficiente es realloc a la hora de reasignar memoria (y se va a hacer, eso, 2500 veces en un frame). Desde luego me ahorro un puntero al siguiente elemento por cada elemento, y el acceso a la última posición es inmediato, pero con una lista simple cada ampliación es sencilla y no requiere mover un bloque enorme.
Pero cualquier otra idea es bienvenida. Ya sabeis que los elementos de un paso van todos juntos, y se deshacen, rehacen y borran en bloque, al contrario que los pasos.

Gracias.

[Ulthar Kaufman]

¿Me ha parecido entender que al deshacer una operación de relleno vas a guardar una referencia a todos los tiles afectados?
Si en ese array de operaciones te guardas también el tipo de operación no sería necesario, no? Quiero decir, si sabes que era un rellenado, con saber X e Y, tile nuevo y tile anterior, si les das la vuelta y vuelves a llamar a la función rellenado no sería suficiente?

[Drumpi]

No, porque supongamos que tenemos un círculo rojo relleno de azul, y ahora pulso en un tile azul con la herramienta de relleno de color rojo. Si ahora relleno con la herramienta azul, tanto lo que era el relleno azul como el borde rojo se pondrían azul.
Por eso necesito el "deshacer", porque eso mismo me pasó varias veces con la edición normal de mapas en la v1, y no podía restaurar el estado anterior.
Y si, guardo una referencia a la herramienta usada... ahora mismo no sé para qué, pero viene bien tenerla (no sé si para indicarlo en el menú desplegable cuando lo haga, o para diferentes métodos de deshacer en función de la herramienta... ya veremos :P).

[Yawin]

Podrías hacer una lista dinámica que guarde los pasos, los cuales sean a su vez listas dinámicas con tareas. Me explico:

[paso]
  paso *siguente_paso, *paso_anterior
  tarea *tareas
[/paso]
[tarea]
  tarea* siguiente tarea
  comoseaqueguardeslasacciones acción
[/tarea]

De esta manera tendrías un paso para rellenar y dentro una tarea por cada tile. Las tareas las aplicarías en bloque.

En el motor 3D que empecé a hacer pero que dejé a medias seguía un esquema parecido. Tenía una lista dinámica de "objetos 3D" los cuales a su vez tenían cada uno una lista dinámica de vértices y otra de caras.

[Drumpi]

Yawin, es que eso es lo que hago :D Os pongo el header provisional de lo que hago:

Code Select Expand

type undo_element
   int x;
   int y;
   int old_tile;
   int new_tile;
   undo_element pointer next_element;
end

type undo_step
   int tool;
   int x;
   int y;
   int z;
   int old_tile;
   int new_tile;
   undo_element pointer next_element;
   undo_step pointer next_step;
   undo_step pointer previous_step;
end

type undo_data
   undo_step pointer step_list;
   undo_step pointer current_position;
end

El tipo Undo_data es el que uso para que el mapa almacene la lista, tiene un puntero a la lista, y un puntero a la posición de la última acción realizada (coincide con la última si no se ha deshecho ningún paso).
La lista es de tipo undo_step, que contiene la información de la posición del tile, el valor antiguo, el nuevo, y dos punteros para crear la lista doblemente enlazada (siguiente paso y anterior).
Cada undo_step tiene una lista de undo_element, que son los cambios que se realizan a la vez que el paso, es decir, todos los tiles que se rellenan a la vez (olvidé poner el valor Z ^^U).

La duda es cómo implemento esa lista de undo_element:
- Si uso una lista enlazada (teniendo que recorrer toda la lista cada vez que quiera añadir un elemento)
- Si uso una lista enlazada con puntero al último elemento (añade una variable que sólo se usa en la creación).
- Si reservo con alloc x espacios, lo trato como un array, y uso realloc cada vez que tenga que añadir un elemento (lo que decía de usar 2500 reallocs en un frame).
- O si hay otra forma mejor de implementar esto.

De momento, me parece que la segunda es la mejor opción. Aunque gaste más memoria que la de realloc, no tiene que estar moviendo el bloque de memoria cada vez. Además, es un proceso muy crítico, porque, aparte de que en el peor de los casos tiene que crear muchísimos elementos, tiene que hacerlo en un solo frame, y compartirlo con otra función que debe evaluar el mapa de tiles y modificarlo (ejemplo: herramienta de relleno). Y no necesito que sea doblemente enlazada porque no voy a recorrer los elementos adelante y atrás, voy a leerlos siempre todos en bloque.

Con eso, necesito aun vuestro consejo, cuanto antes, mejor, a ver si hoy o mañana dejo finiquitado el tema del deshacer (lo he probado ya con la herramienta poner, que sólo usa pasos, y funciona de lujo).[/code]

[Abash]

Mi idea es un poco alocada pero bueno, es otro punto de vista y puede que sí funciona, algo más sencillo.
Supongo que el mapa lo guardas en una tabla.
Crea unas cinco tablas más, tantas como undos necesites.
Suponiendo que guardas los datos en la primera, haz que la primera vez que alteras el mapa, cambiando un tile, borrando un tile, rellenando, te guarde los cambios en la primera tabla y en la segunda.
La segunda vez que cambies algo, te lo guarde en la primera y en la tercera, la siguiente en la primera y la cuarta...
Hiciste cuatro cambios y quieres volver atrás? Muy fácil. Copias la tabla cuatro sobre la primera, que es la que estamos viendo en el editor.
Pulsando por ejemplo el botón guardar o al salir del programa sería cuestión de vaciar todas las tablas menos la primera, que es la buena.
Si es cuestión de usar menos memoria, se podría guardar en un archivo temporal y borrarlo al finalizar.
No se sí me e explicado bien, ya digo que podría ser algo alocado.

[Drumpi]

Abash, agradezco tu ayuda y tu intención, lo que propones sí que funciona, pero eso es el "deshacer" más básico del mundo :)
Es ideal cuando hay cambios en más del 30% del mapa, pero tiene varias pegas:
- El número de veces que puedes deshacer es limitado.
- Aunque pudiéramos tener tantos arrays como quisiéramos (que se puede), se perdería mucha memoria si sólo se modifican uno o dos tiles ¡Imagina que modificas 200 veces un tile!
- Usar ficheros para esto no es recomendable: el disco duro es "lento", y si se escribe demasiadas veces se estropea (para eso está la RAM). Puede ser una buena idea usarlo para guardar parte de la lista de deshacer si esta se vuelve demasiado grande, me lo anoto para futuras referencias.

De momento he implementado la lista simple con puntero señalando al final. Es probable que se quede así, pero si hay alguna sugerencia más eficiente que esta, soy todo oidos :)

[SplinterGU]

lo que dice Abash no es una locura... muchos productos tienen deshacer limitado... y tambien muchos usan disco para esto... diria que es mas logico que usar RAM... la cuestion es que si es limitado, se notifique de tal situacion...

muchos programas incluso hay casos donde advierten que tal o cual operacion no se puede deshacer...

[Drumpi]

Hace años era muy habitual. El propio Paint se limitaba a 3 operaciones, y Photoshop podía configurarse cuánta memoria se podía utilizar en ello.
Pero hoy día no he visto yo muchas limitaciones en las herramientas de deshacer. El propio Photoshop, o cosas como Maya o Unity3D he podido deshacer un montón de veces y nunca me ha llegado a negar más operaciones.
Desde que tenemos 4GB de RAM, eso ya no es tanto problema (podríamos almacenar un DVD entero en RAM), y es cuestión de qué tan eficiente es el programador para que se pueda aprovechar al máximo... y en eso estoy.

No te creas, llegué a evaluar que para deshacer el rellenado podría crear un array bidimensional del tamaño de la zona afectada, pero requería crear una lista con los valores a modificar, evaluar cuáles eran los límites laterales, superior e inferior, crear el bloque de memoria, identificar los tiles que se modificaban y almacenarlo junto con la posición de dicho bloque. Súmale a eso el algoritmo de rellenado :S

[gecko]

Creo que es la solucion que planteas inicialmente, pero creo que la solucion mas escalable

-una lista dinamica con cada uno de los pasos (operaciones), que dentro tenga
-- una lista dinamica con cada uno de los tiles modificados

Eso si, vas a tener que tener muchisimo cuidado con allocar y liberar exactamente la memoria que vayas necesitando.

[Drumpi]

Muy bien ¿y cómo implementarías esa "lista dinamica con cada uno de los tiles modificados"? Hay como 20 maneras de hacerlo.

[gecko]

Creí que esa parte es la que ya tenias resuelta! jajajaja

Para operaciones simples (modificar un tile solo) no haria falta que sea una lista, pero para operaciones mas grandes (por ejemplo rellenado de un area) podrias ir agregando a esa lista cada uno de los tiles que vas cambiando.

Tal vez deberias guardar el valor inicial y final de cada tile, asi cuando vas deshaciendo los pasos, tenes directamente la informacion que necesitas en cada paso.

Es super a alto nivel lo que te estoy planteando, no se que tan bien se adaptaria a lo que ya tenes implementado.

[Drumpi]

Gecko, es que eso es lo que ya tengo implementado ¿No has visto las cabeceras que puse más arriba? :D
De hecho, la lista dentro de la lista es una enlazada simple, con un puntero al principio y otra al final. Mientras que la primera lista es una lista doblemente enlazada para que el puntero que marca la última operación pueda avanzar y retroceder sin tener que consultar la lista desde el primer nodo.

Y tanto como super alto... es el nivel que nos pedían en clase de programación, concretamente en el laboratorio. Al menos, el ser capaces de implementar listas y colas usando un puntero o dos según el ejercicio (no quieres implementar una cola con un solo puntero, creeme).

Si vieras la cantidad de listas mixtas que tengo ya implementadas en el editor: la estructura que alamacena la info del mapa contiene esta lista con sub-lista, una estructura TMapa que contiene hasta tres punteros con información del mapa, una estructura TScroll con una lista de procesos tile... ¡¡y esta estructura es un nodo de una lista!!