Algunas preguntas con pacman path finding

Question

He aprendido sobre A *, BFS, DFS y puedo implementarlas bastante bien. Sin embargo, surgen algunos problemas cuando trato de hacer eso para resolver el problema de búsqueda de ruta de pacman. Supongamos que solo hay dos tipos de laberintos: uno tiene elementos completos, como en ningún cuadrado en blanco, todo es pacman o item-to-collect o wall; y uno solo tiene algunos artículos (4 o menos).

1. ¿Cómo se implementan exactamente BFS y DFS si hay más de un artículo para recolectar? En tal caso, ¿todavía producen un resultado óptimo?

2. ¿Cuál es el mejor algoritmo/heurística para el mapa del artículo completo? Lo que he encontrado hasta ahora es algo así como una heurística codiciosa, pero es bastante aleatorio debido a que el mapa tiene demasiados elementos para recopilar y, por lo tanto, no es una buena idea para resolver ese laberinto.

3. Usando A *, en el mapa de pocos artículos, ¿hay alguna manera de determinar qué elemento se debe tomar primero? Pensé en intentar usar la distancia de Manhattan como una estimación aproximada, pero eso no suena bien, especialmente en algunas situaciones difíciles.

Answer 1

Los algoritmos no cambian si agrega más alimentos. Lo único que cambia es el espacio de estado. Tienes que pensar en una nueva forma de representar tu problema. Cuando solo tienes 1 comida para comer, solo necesitas la posición x, y de pacman. Cuando tiene 3 puntos para comer, por ejemplo, debe agregar esta información a su modelo. Puede agregar 3 variables booleanas para indicar que pacman ha pasado por el punto. Ahora el espacio de estados es una gráfica hecha de nodos de los siguientes tipos:

((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food 
((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food 
((x,y),TRUE,TRUE,TRUE) -> this is the goal state 

Para resolver el problema que acaba de ejecutar el mismo algoritmo en su nuevo modelo. BFS ans A * siempre le dará la solución óptima. El problema es que mientras más comida pones, más lento se vuelve para encontrar una solución. Entonces estos algoritmos no darán una respuesta en un tiempo razonable. Tienes una nueva forma de hacerlo.

Answer 2

1) El problema que tendría con el uso de BFS o DFS en esta situación es lo ineficaz que resultará, especialmente en el ejemplo del mapa completo. Para que cualquiera de los algoritmos funcione con múltiples objetivos, puede compilar la búsqueda para que no termine una vez que se encuentre la primera ruta, pero esto aún no le dará una ruta "óptima" para cada porción de comida en el mapa. , o podrías hacer un camino de pacman a la comida más cercana, esa comida a la siguiente más cercana, etc., encontrar esos caminos, luego compararlos para encontrar un camino verdaderamente óptimo, pero no quiero pensar en cuánto tiempo eso tomar.

2) Probablemente me quedaría con un A * codicioso, que solo mira a la comida más cercana (no veo un problema con la distancia de Manhattan en la mayoría de los casos, ya que el mapa de pacman ya es una cuadrícula; no es óptimo para las cajas de borde donde las paredes impiden que Pacman acceda al más cercano, pero este es un problema difícil de resolver. Manhattan sería una decente, posiblemente modificada por densidad de comida en lugar de distancia, algo como: (distancia de Manhattan)/(total de alimentos dentro de 3x3 cuadrados de alimentos)

3) Si no se utiliza el pathfinding en cada elemento, entonces elegir el más corto, creo que Manhattan estaría bien en el escenario de pocos artículos. No siempre elegiría lo mejor, pero una IA 100% óptima generalmente no es el mejor objetivo para jugar.

En este caso, me gustaría probar codiciosos A * con el peso que favorece los grupos de elementos como una solución simple, decentemente rápida.

Una solución más compleja que debe devolver más cerca de las rutas óptimas para el Pacman a seguir sería el uso de un algoritmo para encontrar un Minimum Spanning Treehttp://en.wikipedia.org/wiki/Minimum_spanning_tree pero no sé lo fácil que sería poner en práctica. Aquí hay una pregunta sobre los méritos de dos algoritmos del árbol de expansión mínimo: Kruskal vs Prim