Справочная информация : я делаю 2D-игру для моба, и мне нужен поиск пути для всех монстров в игре.Я хочу дать стартовые и конечные позиции и сделать так, чтобы монстры путешествовали туда, избегая объектов.
Вопрос : Я уже некоторое время пытаюсь внедрить поиск пути в мою игру, и я просто не могуПосмотрите, чтобы это заработало.Все, что мне нужно, - это какой-нибудь метод / класс, где я могу дать ему двумерный массив значений (т. Е. True = busy & false = free), startPos, endPos, и он дает мне список шагов, чтобы добраться до конца.Пока все мои реализации провалились.Может ли кто-нибудь помочь, дав мне код, который легко реализовать?
Примечание : До сих пор я пытался реализовать A , и он либо игнорировал стены, либо отправлял персонажа в совершенно случайном направлении.* Я получил это работает, но уродливо и неправильно.Я заставил персонажа двигаться вперед, пока он не ударится о стену.Затем он повернул направо и продолжал двигаться, пока не смог повернуть налево и продолжить движение к месту назначения.Это работает, но я не думаю, что люди хотят, чтобы их монстры бегали по стенам
Редактировать : приведенный ниже код теперь работает!Я обнаружил, что по какой-то причине точки были задом наперед, поэтому мне пришлось инвертировать список точек.Нет, все, что мне нужно сделать, это интерполировать между точками, чтобы обеспечить плавное движение.Тем не менее, я спрашиваю, есть ли способ добавить больше уклона к стенам.Например, сделать так, чтобы точка никогда не входила в 1 единицу стены?
package NavMesh;
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import toolbox.Maths;
public class MovementPath {
private Node[][] mapOriginal;
private Node[][] mapPath;
public boolean solving = true;
public int startX, startY, finishX, finishY, cells;
private int checks = 0;
private int length = 0;
int realStartX, realStartY, realFinishX, realFinishY;
NavMesh mesh;
private Algorithm alg;
List<Point> path = new ArrayList<Point>();
public MovementPath(NavMesh mesh,int startX, int startY, int finishX, int finishY) {
this.mapOriginal = mesh.getMapCopy();
this.mesh = mesh;
this.startX = startX;
this.startY = startY;
this.finishX = finishX;
this.finishY = finishY;
this.cells = mapOriginal.length;
realStartX = startX;
realStartY = startY;
realFinishX = finishX;
realFinishY = finishY;
this.startX = (int) (Math.floor((float) startX / (float) mesh.cellWidth));
this.startY = (int) (Math.floor((float) startY / (float) mesh.cellHeight));
this.finishX = (int) (Math.floor((float) finishX / (float) mesh.cellWidth));
this.finishY = (int) (Math.floor((float) finishY / (float) mesh.cellHeight));
mapPath = new Node[mapOriginal.length][mapOriginal.length];
System.arraycopy(mapOriginal, 0, mapPath, 0, mapOriginal.length);
mapPath[this.startX][this.startY] = new Node(0,this.startX,this.startY);;
mapPath[this.finishX][this.finishY] = new Node(1,this.finishX,this.finishY);
addPointCentered(realFinishX,realFinishY);
alg = new Algorithm();
//alg.AStar();
alg.Dijkstra();
addPointCentered(realStartX,realStartY);
mesh.drawMap(Integer.toString(Maths.randomRange(0, 1000)), mapPath);
}
public Path getPath(){
//System.out.println("Returning path with " + getPathPoints().size() + " points");
return new Path(getPathPoints());
}
private void addPointCentered(int x, int y) {
path.add(new Point(x+(mesh.cellWidth/2),y+(mesh.cellHeight/2)));
}
public List<Point> getPathPoints(){
List<Point> rPath = new ArrayList<Point>();
for(int i = path.size()-1; i >= 0; i--) {
rPath.add(path.get(i));
}
return rPath;
}
class Algorithm { //ALGORITHM CLASS
//A STAR WORKS ESSENTIALLY THE SAME AS DIJKSTRA CREATING A PRIORITY QUE AND PROPAGATING OUTWARDS UNTIL IT FINDS THE END
//HOWEVER ASTAR BUILDS IN A HEURISTIC OF DISTANCE FROM ANY NODE TO THE FINISH
//THIS MEANS THAT NODES THAT ARE CLOSER TO THE FINISH WILL BE EXPLORED FIRST
//THIS HEURISTIC IS BUILT IN BY SORTING THE QUE ACCORDING TO HOPS PLUS DISTANCE UNTIL THE FINISH
public void AStar() {
ArrayList<Node> priority = new ArrayList<Node>();
priority.add(mapPath[startX][startY]);
while(solving) {
if(priority.size() <= 0) {
solving = false;
break;
}
int hops = priority.get(0).getHops()+1;
ArrayList<Node> explored = exploreNeighbors(priority.get(0),hops);
if(explored.size() > 0) {
priority.remove(0);
priority.addAll(explored);
} else {
priority.remove(0);
}
sortQue(priority); //SORT THE PRIORITY QUE
}
}
public void Dijkstra() {
ArrayList<Node> priority = new ArrayList<Node>(); //CREATE A PRIORITY QUE
priority.add(mapPath[startX][startY]); //ADD THE START TO THE QUE
while(solving) {
if(priority.size() <= 0) { //IF THE QUE IS 0 THEN NO PATH CAN BE FOUND
solving = false;
break;
}
int hops = priority.get(0).getHops()+1; //INCREMENT THE HOPS VARIABLE
ArrayList<Node> explored = exploreNeighbors(priority.get(0), hops); //CREATE AN ARRAYLIST OF NODES THAT WERE EXPLORED
if(explored.size() > 0) {
priority.remove(0); //REMOVE THE NODE FROM THE QUE
priority.addAll(explored); //ADD ALL THE NEW NODES TO THE QUE
} else { //IF NO NODES WERE EXPLORED THEN JUST REMOVE THE NODE FROM THE QUE
priority.remove(0);
}
}
}
public ArrayList<Node> sortQue(ArrayList<Node> sort) { //SORT PRIORITY QUE
int c = 0;
while(c < sort.size()) {
int sm = c;
for(int i = c+1; i < sort.size(); i++) {
if(sort.get(i).getEuclidDist(finishX,finishY)+sort.get(i).getHops() < sort.get(sm).getEuclidDist(finishX,finishY)+sort.get(sm).getHops())
sm = i;
}
if(c != sm) {
Node temp = sort.get(c);
sort.set(c, sort.get(sm));
sort.set(sm, temp);
}
c++;
}
return sort;
}
/*
public ArrayList<Node> exploreNeighbors(Node current, int hops) { //EXPLORE NEIGHBORS
ArrayList<Node> explored = new ArrayList<Node>(); //LIST OF NODES THAT HAVE BEEN EXPLORED
for(int a = -1; a <= 1; a++) {
for(int b = -1; b <= 1; b++) {
int xbound = current.getX()+a;
int ybound = current.getY()+b;
if((xbound > -1 && xbound < cells) && (ybound > -1 && ybound < cells)) { //MAKES SURE THE NODE IS NOT OUTSIDE THE GRID
Node neighbor = mapPath[xbound][ybound];
if((neighbor.getHops()==-1 || neighbor.getHops() > hops) && neighbor.getType()!=2) { //CHECKS IF THE NODE IS NOT A WALL AND THAT IT HAS NOT BEEN EXPLORED
explore(neighbor, current.getX(), current.getY(), hops); //EXPLORE THE NODE
explored.add(neighbor); //ADD THE NODE TO THE LIST
}
}
}
}
return explored;
}
*/
public ArrayList<Node> exploreNeighbors(Node current, int hops) { //EXPLORE NEIGHBORS
ArrayList<Node> explored = new ArrayList<Node>(); //LIST OF NODES THAT HAVE BEEN EXPLORED
//test(hops, current, explored,current.getX(),current.getY());
//test(hops, current, explored,current.getX()+1,current.getY());
//test(hops, current, explored,current.getX()-1,current.getY());
//test(hops, current, explored,current.getX(),current.getY()+1);
//test(hops, current, explored,current.getX(),current.getY()-1);
for(int a = -1; a <= 1; a++) {
for(int b = -1; b <= 1; b++) {
test(hops, current, explored,current.getX()+a,current.getY()+b);
}
}
return explored;
}
private void test(int hops, Node current, ArrayList<Node> explored, int xbound, int ybound) {
if((xbound > -1 && xbound < cells) && (ybound > -1 && ybound < cells)) { //MAKES SURE THE NODE IS NOT OUTSIDE THE GRID
Node neighbor = mapPath[xbound][ybound];
if((neighbor.getHops()==-1 || neighbor.getHops() > hops) && neighbor.getType()!=2) { //CHECKS IF THE NODE IS NOT A WALL AND THAT IT HAS NOT BEEN EXPLORED
explore(neighbor, current.getX(), current.getY(), hops); //EXPLORE THE NODE
explored.add(neighbor); //ADD THE NODE TO THE LIST
}
}
}
public void explore(Node current, int lastx, int lasty, int hops) { //EXPLORE A NODE
if(current.getType()!=0 && current.getType() != 1) //CHECK THAT THE NODE IS NOT THE START OR FINISH
current.setType(4); //SET IT TO EXPLORED
current.setLastNode(lastx, lasty); //KEEP TRACK OF THE NODE THAT THIS NODE IS EXPLORED FROM
current.setHops(hops); //SET THE HOPS FROM THE START
checks++;
if(current.getType() == 1) { //IF THE NODE IS THE FINISH THEN BACKTRACK TO GET THE PATH
backtrack(current.getLastX(), current.getLastY(),hops);
}
}
public void backtrack(int lx, int ly, int hops) { //BACKTRACK
length = hops;
while(hops > 1) { //BACKTRACK FROM THE END OF THE PATH TO THE START
Node current = mapPath[lx][ly];
current.setType(5);
addPointCentered(lx*mesh.cellWidth,ly*mesh.cellHeight);
//System.out.println("New Point: " + path.get(path.size()-1).toString());
lx = current.getLastX();
ly = current.getLastY();
hops--;
}
solving = false;
}
}
}