¿zonas Con Listas Enlazadas?

[Althair]

 Hola. Estoy haciendo engine 2d (usando c++ y opengl) junto con otros amigos y quisiera saber que pensais de utilizar listas enlazadas para tener una lista enlazada con las zonas de cada mapa (llamo zona a cada región cuadrada o rectangular en las que estarán divididos nuestros mapas, y sirven para agilizar la visualización y la colisión, y no tener que estar trabajando con todo el mapa). Cada zona es una clase y tiene un puntero que puede apuntar a objetos como coche, personaje,.. para poder tener una lista enlazada para cada zona, que corresponda a los objetos que están en ella. el problema aparece porque los objetos (que tienen un cierto área. trabajamos con sus vértices) pueden estar hasta en 4 zonas a la vez, cosa que ocurre cuando un coche por ejemplo está encima de uno de los vértices que una 4 zonas (las zonas están pegadas unas a otras, como valdosas, y el coche tiene un cierto área -trabajamos con los vértices de cada objeto-). Podemos trabajar cun 4 punteros hacia "alante" y 4 hacia "atrás" (la lista es dóblemente enlazada), pero hay que hacer algún que otro cálculo cada vez que algo se mueve para que todo funcione bien (si quereis os lo explico. es que cuando se recorre la lista de coches de una zona hace falta saber cúal de los 4 siguientes punteros corresponde a la zona que estamos recorriendo, y no a un coche que esté en la zona adyacente, por ejemplo).
Concretamente la pregunta es: ¿Álguien sabe como se trabaja en realidad en 2D/3D a nivel "profesional" en este tipo de engines? me refiero a cuando se parte el espacio en rectángulos o prismas (BSP, por ejemplo), ¿se utilizan listas enlazadas? ¿arrays? es que las listas parecen la forma más ordenada y rápida para que entren y salgan objetos contínuamente de cada una de esas porciones de mapa, pero no se puede hacer que funcione bien a no ser que uno complique un poco las cosas, y me parece extraño que para el quake o el unreal no utilicen un método rápido, sencillo y eficaz, de esos que todos intentamos hacer pero no siempre logramos  (nooo) .
Si no me explicado bien, preguntadme e intentaré explicarlo mejor.  (ole)  Gracias por adelantado.

[nsL]

 los BSP creo recordar que eran arboles (probablemente binarios de busqueda), que dividen el mapa en zonas y repintan las que sean visibles en ese momento.. (oi algo de octree por aqui, pero prefiero no decir nada porq meto la pata seguro)

no tengo mucha idea en esto de programacion de videojuegos, porq yo toi emepzando..
pero por lo que he leido por aqui, para hacer un engine 2D nadie usa listas, simplemente usan mapas de tiles q viene a ser un array que recubre la pantalla con sprites en forma de baldosa y luego pintan encima los demas elementos, coches o personajes como dices tu y se basan en la coordenadas para saber su adyacencia con los demas elementos..

eso creo eh! mejor espera a que enga alguien q entiende mas  ;)

[vicho]

 el bsp es un modelo de arbol, de todas formas creo que para escenarios 2d te convendria hacer tu propio formato de mapas, con tiles, de todas formas todo depende del tipo de juego que quieras hacer

[Thenend]

 No te entiendo muy bien Althair. Las listas doblemente enlazadas solo tienen un puntero al siguiente elemento y otro al anterior, si usas 8 punteros será una especie de grafo, no se. Tampoco tengo muy claro cuál es tu problema. A ver si diciendo cosas a lo tonto acierto y te digo algo util   :D

Lo normal para dividir un espacio bidimensional es usar BSPs o Quadtrees que van subdividiendo el espacio hasta que se alcanza cierto límite (que en cada hoja solo haya un objeto, cuadrados de 10x10 unidades, X niveles de profundidad...). Cuando llegas a las hojas, como estás en 2D, con usar listas te sobra y si tienes algún problema con objetos que están en varios sectores a la vez puedes marcarlos en cuanto los hayas recorrido y así no los procesarás más de una vez.

Si no sabes cómo funcionan los árboles (estructuras de datos me refiero, no cojas un libro de botánica  :blink: )  míratelos, que igual es lo que necesitas. Pon "binary space partitioning" o "quadtree" en el google que salen un montón incluso en castellano. Hay varias formas de usarlos, sobre todo los BSPs, algunas que no te valen para nada en 2D como determinar el orden de dibujado, oclusiones y cosas así, pero para dividir sectores también te valen.

Los juegos como Quake y Unreal, para dividir el espacio usan cosas como octrees y portals, y grafos de escena o listas de escena para organizar los datos (lo de las listas de escena no se lo que es pero como lo he leido lo pongo  :P )

[Althair]

 Hola. Pues gracias, ya le hecharé un vistazo a los árboles. Sobre lo de los 8 punteros, es que la lista símplemente enlazada necesita ya 4 punteros en nuestro caso, porque hicimos una lista para cada zona, y como un objeto puede estar entre cuatro de esas zonas (porque al tener un cierto "volumen" pueden chocar contra él los que estén en las zonas adyacentes también), necesita 4 punteros para poder estar en las 4 listas. y si son dóblemente enlazadas, son 8 punteros.
Y por cierto, uso listas porque es muy general y queremos incluir muchos objetos y procesos que estén teniendo lugar a la vez y queremos optimizarlo mucho, además en principio alguna cosa será en 3d (al estilo de los 2 primeros Grand Thief Auto) pero con una colisión 2d (no habrá movimiento en la coordenada z), pero posíblemente querramos pasar al 3d puro más tarde, de ahí que pregunte por métodos de 3d.
Sobre marcar los objetos, no se si te entiendo. Eso no me lo soluciona a no ser que te refieras a tener una lista general para todo el mapa, pero cada vez que algo se mueva tendrá que recorrer los tropecientos objetos de la lista de colisión, aunque sea símplemente para comprobar un flag, y eso lo tendría que hacer cada uno de los objetos que se muevan :( .

[codeMonkey]

 algo como esta http://www.tulrich.com/geekstuff/partitioning.html idea,  no necesariamente usando octrees. , donde las zonas se superponen ?