El juego de Bumper Cars se desarrolla en un espacio de dos dimensiones
dividido en casillas, donde en cada casilla puede haber un obstáculo
(la casilla es inaccesible), un coche verde , o un coche azul
.
Además entre algunas casillas existe un muro que las incomunica
con otras casillas vecinas. Existe además un muro rodeando el espacio
del juego que sólo tiene 2 salidas (una verde y una azul). El objetivo
es sacar cada coche a la salida de su color. Los muros, obstáculos
y salidas son fijos durante cada ejecución del juego. (3).
![]() |
|
Los operadores son {norte,sur,este,oeste}. Un coche sólo puede moverse a una casilla adyacente si ésta está libre. Al ejecutar cualquiera de estos operadores, avanzará un coche, los dos o ninguno, dependiendo de si el movimiento es posible para cada coche, es decir, si no hay obstáculos ni otro coche ni un muro.
Para simplificar el problema se tendrá en cuenta que una vez que un coche sale por alguna de las salidas, ya no puede moverse más. Por tanto es posible que dos coches salgan por su salida en momentos diferentes.
Si los coches se encuentran en el siguiente estado: AV,y se ejecuta el operador Oeste, sólo se puede mover el coche azul, ya que los movimientos deben ser simultáneos. No importa que al mover el coche verde, el coche azul podría moverse al oeste a continuación. Debe hacerse la misma consideración en los casos similares a este para todas las posibilidades de coches adyacentes.
El estado inicial se leerá de un fichero inicio con el formato arriba indicado. El estado final es el que se corresponde con el objetivo definido y por tanto viene dado por la posición de las salidas.
Una vez obtenida la solución se ideará alguna forma de visualizarla paso a paso.
Para el análisis experimental, se usaran cinco escenarios:
-el de la figura mostrada.
-el de la figura mostrada cambiando el coche verde a (4,3)
-el de la figura mostrada cambiando el coche azul a (1,1)
-el de la figura mostrada cambiando la salida azul a la cara oeste
coordenada 2.
-el de la figura mostrada cambiando el obstáculo (2,3) a la
posición (0,2)
Se utilizará en cada caso búsqueda primero en anchura y busqueda heurística A* con dos heurísticas distintas. Se medirá el coste de la búsqueda :