Saber si existe continuidad

[KarlsBerg]

Hola señores, necesito hacer algo similar a las tuberias de SimCity, a los tendidos electricos de Simcity y a el sistema de riego de Simfarm, todos ellos son lo mismo

(Bomba o Central electrica) > (Tendido o tuberia) > Aspesor o edificio

Necesito hacer un sistema de riego en un juego basado en tiles (iso).
El usuario podra construir bombas de agua, tuberias y aspersores por donde quiera, y mi mision es conocer si tal aspersor tiene continuidad hacia alguna bomba, (en otras palabras, saber si esta recibiendo agua) puede ser que este copnectada a dos bombas, por tanto debo saber por cuantas le llegan.

Mi idea es tambien añadirle llaves de pasos con varios tipos de cerrado (poco paso, abierta totalmente o cerrada) de forma que de ahi en adelante el flujo no pase.

Alguna idea? :?
Gracias!

PD: lo hare en python pero con saber el sistema a fondo me valdria.

[Martinez]

Umm prueba con un algoritmo de encaminamiento. Mirate el algoritmo de Dijkstra.

Cada tile es una posicion que esta conectada conectada con sus cuatros vecionos.

[KarlsBerg]

lo conozco aunque nunca lo he usado, la pregunta es... como va el tema de por donde puede pasar?

Por algunos lados me han recomendado grafos, pero nose.. porque cuando el usuario construlla tuberias fuera del grafo (no conectadas) aver como las mantengo para que cuando esten conedctadas las meto y las saco es un coñazo y encima feo.

Estoy pensando en tener otra matriz al igual que la que tengo para el mapa con objetos Tile, tener una con 0, 1, 2, 3, 0 es campo, 1 es bomba, 2 es  tuberia y 3 aspersor,

cuando el usaurio aparte de ir modificando el mapa segun lo que valla construyendo el usuario, cuando construya bomba meto la tile pos en una lista bombs = [] y con aspersores igual, y el algoritmo seria comprobar por cada bomb comprobar A* hacia un aspersor.

Sera esto lento? los tilemap son de 70x70 aprox. se puede cambiar, seria mas optimo una potencia de 2?

[Martinez]

En todo caso seria desde recorrer desde el aspersor todos los caminos posibles hasta que encuentres una bomba. Yo haria lo que has comentado, un array de tyles con el tipo de objeto. Da igual que sea potencia de 2 o no, simplemente cuanto mas tiles mas tarda. Yo meteria en la lista de objetos un campo "indice" que te indice la posicion del objeto en su correspondiente lista.

Una vez que tienes la matriz que contiene la pos y el tipo de objeto ya tienes un grafo.

[Zaelsius]

Lo suyo es que valores ambos algoritmos, A* y Dijkstra, veas si ambos resuelven tu problema, y en caso afirmativo los compares en términos de complejidad espacial y temporal en tu caso.

Un apunte: Con Dijsktra también puedes usar matrices estáticas para trabajar.

los tilemap son de 70x70 aprox. se puede cambiar, seria mas optimo una potencia de 2?

Norrl.

[tamat]

yo creo que una manera sencilla y coherente con el tema sería que en cada iteracion del update cada celda tuviera tanta agua como el agua de las celdas conectadas a ella dividido por el numero de celdas conectadas. De este modo el agua "viaja" a traves de los tiles. Ademas modela el tema de como el agua se propaga, si está lejos tarda mas en llegar, etc.

[Tei]

puede valer lo que dice tamat, me parece

[Vicente]

Si quieres hacer algo más realista simulando la capacidad de las tuberías y viendo como se mueve el flujo desde un comienzo hasta un final (y viendo si hay flujo suficiente para todas las tuberías) puedes darle un vistazo al algoritmo de Ford-Fulkerson.

Un saludo!

Vicente