mazoweb
v1.0.1
Published
Algoritmos de laberintos en Java y bb
Downloads
3
Readme
mazoweb
Entendiendo el algoritmo del laberinto
Como muchos algoritmos de juegos, crear un laberinto aleatorio solo requiere un poco de razonamiento matemático. Piense en los caminos a través del laberinto como si fueran un gráfico. Los vértices son los puntos donde se unen dos caminos o donde podrías girar, y los caminos que conectan los vértices son los bordes. Está claro que para un laberinto, desea que su gráfico sea un árbol conectado; en otras palabras, un gráfico sin ciclos. Siempre que el punto de entrada y el punto de salida formen parte de un árbol conectado, habrá exactamente un camino desde el principio hasta el final.
Para aplicar esta idea y crear el laberinto, el primer paso es usar las dimensiones de la pantalla y los gráficos para determinar el tamaño de su cuadrícula de vértices (cuántos cuadrados de ancho y cuántos de abajo). Comienza dividiendo todo el campo de juego en cuadrados del mismo tamaño, que forman parte de los caminos del laberinto si son de color blanco y parte de la pared del laberinto si son de color negro. Puede ver que hay un entramado de cuadrados que sabe que deben ser negros y un entramado que sabe que debe ser blanco. El truco consiste en averiguar qué colores dar a los cuadrados comodín.
Todos los cuadrados cuyo color debe decidir el algoritmo están coloreados en gris (tenga en cuenta que esta pantalla nunca aparece en el juego final). En términos gráficos, los cuadrados blancos son los vértices y los cuadrados grises son los cuadrados que potencialmente podrían ser bordes si se agregan al camino del laberinto y se vuelven blancos. Puede ver a partir de esto que el número de filas y el número de columnas deben ser números impares.
El algoritmo funciona seleccionando uno de los cuadrados blancos al azar del centro de la cuadrícula y haciendo crecer el árbol desde allí seleccionando cuadrados indecisos (grises) y volviéndolos blancos. A lo largo del algoritmo, mantiene una lista de todos los cuadrados blancos (vértices) que aún no están conectados al laberinto, pero que están a solo un cuadrado gris de estar vinculados. En cada ronda del algoritmo, usa el java. util.Random class para elegir un cuadrado de la lista y adjuntarlo al laberinto (convirtiendo un cuadrado gris en blanco, agregando así un borde al gráfico). Luego continúa hasta que no queden cuadrados blancos que no estén conectados al gráfico del camino del laberinto, y colorea los cuadrados grises restantes de negro.
Al agregar solo bordes para conectar vértices que aún no estaban conectados al gráfico, puede ver que nunca obtendrá un ciclo. Y al hacer crecer el gráfico desde un punto central, puede estar seguro de que todos los vértices estarán conectados al mismo componente. Entonces, al final, por cada dos cuadrados blancos en el laberinto, hay exactamente un camino que lleva de uno a otro; en particular, hay un camino único desde la casilla de entrada hasta la casilla de salida.
Algoritmo de laberintos en Blackberry
Los dispositivos BlackBerry tienen limitaciones sobre la cantidad de objetos Java que pueden almacenar en la memoria. Por ejemplo, un teléfono inteligente BlackBerry con 16 MB de memoria flash puede almacenar 56 000 objetos. Son muchos objetos, pero tenga en cuenta que esa es la cuenta de todos los objetos en todo el sistema, incluidos los objetos creados por el AMS y los creados por otras aplicaciones que se ejecutan en segundo plano, incluso en redes locales como 192.168.l.254
En general, debe tener cuidado con la creación de muchos objetos complejos (objetos con campos que son otros objetos), y especialmente con el llenado de vectores y tablas hash con objetos complejos. Aquí, el algoritmo de laberinto usa un Vector cuando construye los datos del laberinto, pero, como puede ver en el constructor, el Vector se libera para la recolección de basura tan pronto como ya no se necesita. Otra posible optimización podría ser borrar y reutilizar el objeto Grid al crear un nuevo laberinto en lugar de crear una nueva instancia de rejilla cada vez. En última instancia, la cantidad de objetos sigue siendo la misma, pero liberar una instancia de Grid para crear otra agrega trabajo adicional para el recolector de elementos no utilizados. Es por eso que muchas de las clases son singletons (que se lanzan para la recolección de basura cuando finaliza el juego) si solo se necesita una instancia de la clase.
Los dispositivos BlackBerry también tienen limitaciones en el uso del almacenamiento persistente. La plataforma de dispositivos RIM tiene una funcionalidad integrada para serializar objetos en la memoria persistente mediante net.rim.device.api.system.PersistentStore y net.rim.device.api.system.PersistentObject. Al igual que la cantidad de objetos vivos, la cantidad de objetos persistentes también es limitada y, en este caso, tiene más de qué preocuparse por la competencia con otras aplicaciones, ya que los datos de las otras aplicaciones permanecen almacenados, ya sea que la aplicación se esté ejecutando o no.
El juego Maze utiliza una pequeña cantidad de almacenamiento persistente, lo suficiente para almacenar el tamaño cuadrado preferido del usuario. Las paredes del laberinto pueden variar en ancho, lo que afecta la complejidad del laberinto. El usuario puede cambiar el tamaño del cuadrado, y si lo hace, la aplicación guarda el tamaño del cuadrado elegido. Entonces, ese es el tamaño que tendrán los cuadrados de la cuadrícula del laberinto la próxima vez que el usuario juegue, incluso si el dispositivo está apagado y se quita la batería entre juegos.
Dado que estamos optimizando los ejemplos de BB Maze y MIDP Maze para la compatibilidad entre diversos sitios web, la clase PrefsStorage utiliza el Sistema de gestión de registros (RMS) MIDP, que está disponible en todos los dispositivos MIDP. Para aplicaciones que requieren una estructura de archivos más compleja, la API de conexión de archivos (de JSR 75) sería una mejor opción.
MIDP RMS en BlackBerry no tiene las mismas restricciones de tamaño que el almacén de objetos persistentes de RIM. A partir de la versión 4.1 de BlackBerry, el tamaño de un RecordStore individual está limitado a 64 KB o 512 KB, pero la cantidad total de memoria que se puede asignar para el uso de MIDP RMS solo está limitada por la cantidad de memoria libre que queda en el dispositivo. Sin embargo, aún puede haber problemas de optimización, ya que un dispositivo generalmente reserva un bloque de memoria de tamaño fijo cuando se crea un RecordStore (y cuando se crea un Registro en RecordStore), y el tamaño de bloque predeterminado puede variar de un dispositivo a otro.