¿Cómo puedo ajustar este algoritmo de búsqueda de ruta de búsqueda A * para manejar diferentes valores de movimiento del terreno?

8

Estoy creando un juego de acción basado en mapas 2D con un diseño de interacción similar al de Diablo II. En otras palabras, el jugador hace clic alrededor de un mapa para mover a su jugador. Acabo de terminar el movimiento del jugador y estoy avanzando hacia la búsqueda de caminos.

En el juego, los enemigos deben cargar el personaje del jugador. También hay cinco tipos de terreno diferentes que otorgan bonificaciones de movimiento diferentes. Quiero que la IA aproveche estas bonificaciones de terreno mientras intentan llegar al jugador.

Me dijeron que revisara el algoritmo de búsqueda A * (http://en.wikipedia.org/wiki/A*_search_algorithm). Estoy haciendo este juego en HTML5 y JavaScript, y encontré una versión en JavaScript: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript Estoy tratando de descubrir cómo ajustarlo aunque.

A continuación se presentan mis ideas sobre lo que necesito cambiar. ¿De qué más debo preocuparme?

  • Cuando creo un gráfico, necesitaré inicializar la matriz 2D que paso con un recorrido de un mapa que corresponde a los diferentes tipos de terreno.
  • en graph.js: la definición "GraphNodeType" debe modificarse para manejar los 5 tipos de terreno. No habrá muros.
  • en astar.js: será necesario modificar la puntuación g y h . ¿Cómo debería hacer esto?
  • en astar.js: isWall () probablemente debería eliminarse. Mi juego no tiene paredes.
  • en astar.js: No estoy seguro de qué es esto. Creo que indica un nodo que no es válido para ser procesado. ¿Pero cuándo sucederá esto?
  • En un nivel alto, ¿cómo cambio este algoritmo de "oh, ¿hay un muro allí?" a "¿este terreno me llevará al jugador más rápido que el terreno que me rodea?"

Debido al tiempo, también estoy debatiendo la reutilización de mi algoritmo de Bresenham para los enemigos. Desafortunadamente, los diferentes bonos de movimiento del terreno no serán utilizados por la IA, lo que hará que el juego sea una mierda. : / Realmente me gustaría tener esto en el prototipo, pero no soy desarrollador de oficio ni científico de la computación. :RE

Si conoce algún código que haga lo que estoy buscando, ¡comparta!

Consejos de comprobación de cordura para esto también son apreciados.

javascript ai html5 usuario422318
fuente
Hola, autor de la biblioteca aquí. ¿Estás utilizando la última versión de github? github.com/bgrins/javascript-astar/blob/master/astar.js . Es mucho más rápido que la antigua implementación basada en listas.
Brian Grinstead

Respuestas:

7

Debe prestar atención a una línea muy específica en el algoritmo:

// g score is the shortest distance from start to current node, we need to check if
//   the path we have arrived at this neighbor is the shortest one we have seen yet
var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor

Este es el costo de ese nodo en particular. Desea modificarlo a algo como

var gScore = currentNode.g + currentNode.cost

Esto hará que el camino evite terrenos caros y prefiera terrenos baratos; es su responsabilidad hacer que 'currentNode.cost' devuelva algo apropiado para su terreno. Es el hecho de que no todo el terreno tiene un costo de 1 al que le estás prestando atención ... algunos terrenos son más baratos que otros. Hay otras consideraciones, pero este punto específico en el código debe ser el foco de su atención.

Myrddin Emrys
fuente
Gracias por esto. Modifiqué mi código para que cada nodo busque el píxel en sus coordenadas y lo almacene como un costo. Desafortunadamente, hice una ruta de prueba para encontrar dos puntos en mi cuadrícula de 800x500 y mi navegador falla. : / Hay varios factores en esto: el código astar puede necesitar optimización; el tamaño de mi lienzo es enorme; tal vez mi inicialización de gráfico es incorrecta; y tal vez los colores en los avatares de los personajes están arruinando las cosas. ¿Qué tengo que hacer? :(
user422318
Cuando dice 'almacena el píxel', quiere decir que almacena el costo del terreno del píxel, ¿sí? Porque es poco probable que algún valor RGB coincida con el costo real de ese terreno. Probablemente deberías almacenar algo entre 1 y 10 (1 es un camino, 10 es un pantano), aunque los valores exactos, por supuesto, dependen de tu juego preciso.
Myrddin Emrys
1
Hola, autor de la biblioteca aquí. ¿Estás utilizando la última versión de github? github.com/bgrins/javascript-astar/blob/master/astar.js . Es mucho más rápido que la antigua implementación basada en listas.
Brian Grinstead
2
@Brian Debes poner este comentario a la pregunta, en lugar de a mi respuesta, para que la persona que realmente usa la biblioteca reciba la notificación en su correo electrónico en lugar de a mí.
Myrddin Emrys
2

Este es exactamente el tipo de cosa para la que A * es. Todo lo que necesita hacer es asignar los vértices entre los costos de los nodos en función de los tipos de terreno. (Parece que sus ejemplos usan un gráfico donde todos los vértices tienen un costo de 1.)

caos
fuente
0

Esta implementación es un poco específica para el encendido / apagado en este momento. Como dice Myrddin Emrys, deberá modificar el puntaje g según el costo (en lugar de solo 1). Hubo una discusión sobre esto aquí: https://github.com/bgrins/javascript-astar/issues/3 .

¡Me encantaría portar esta solución a la biblioteca principal si la haces funcionar!

Brian Grinstead
fuente