Массив: Нарисовать траекторию движения объекта по массиву...

@Abomination_25 · Регистрация: 13.12.2016

Author24 — интернет-сервис помощи студентам

Всем привет, имеется такая задача: Сгенерировать двумерный массив размером MxN. Заполнить его препятствиями.
Обозначить точку старта и финиша. Нарисовать траекторию движения объекта по массиву. В общем дело об автомобиле, но не суть.
Уже второй день пытаюсь придумать алгоритм обхода препятствий, но бывают все равно ситуации, когда объект заходит в тупик
# # #
# o #
# .
И выход назад не катит, так как там уже траектория объекта(точка).
Кто что может посоветовать? Пока делал так: проверял в каком направление двигаться надо. Сначала проверял нужно вверх или вниз, а уже потом внутри этих условий выбирал рандомно между вертикальным и горизонтальным направлением(только вправо, так как движение начинается слева направо). Если же разница между вертикальными координатами равна финишу, то объект начинал двигаться только вправо, пока не встретит препятствие, если встретил, то рандомно идет вверх или вниз. Но если заходит в такой тупик, то там выхода нет... В общем алгоритм самодельный и некрасивый... Может кто-нибудь что посоветовать из этой области? Карты выглядит так:

Массив: Нарисовать траекторию движения объекта по массиву...

Сам класс карты:
Карта генерируется прямо в конструкторе, пока только без параметров конструктор, позже добавлю с параметрами. Но самое главное написать функцию MoveSimulation(); Там основной цикл do-while, где раньше код был, но он не работает, поэтому не буду скидывать сюда.

Java

package race;
 
public class NewMap {
    //[Map settings]
    private char [][] map;
    private int M=30; //represents <y> coordinate
    private int N=80; //represents <x> coordinate  
    //Help variables
    private int situation;
    private int direction;
    private int maxRadius=5;
    private int minRadius=2;
    private int spawnRadius;
    private int obstaclesAmount;
    private int steps=0;
    private boolean isFinished=false;
    //Coordinates
    private int startX;
    private int startY;
    private int finishX;
    private int finishY;
    private int x;          //player's x
    private int y;          //player's y
    //[Symbols]
    public char start_end='o';
    public char tail='.';
    public char border='#';
    public char obst='x';
    public char empty=' ';
    
    //[Constructor]
    
    public NewMap(){
        obstaclesAmount=(int)(M*N/7);
        spawnRadius=(int)(Math.random()*(maxRadius-1)+minRadius);
        startX=1;
        startY=(int)(Math.random()*(M-spawnRadius-1)+(spawnRadius));
        finishX=N-2;
        finishY=(int)(Math.random()*(M-3)+1);
        x=startX;
        y=startY;
        //Create Empty Map
        map=new char[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(i==0 || i==M-1){
                    map[i][j]=border;
                }
                else if(j==0 || j==N-1){
                    map[i][j]=border;
                }
                else map[i][j]=empty;
            }
        }
        
        //Setup Map
        
        do{
            boolean go=true;
            int a,b;
            
            a=(int)(Math.random()*(M-3)+1);
            b=(int)(Math.random()*(N-3)+1);
            
            for(int i=y-spawnRadius;i<y+spawnRadius;i++){
                for(int j=x;j<x+spawnRadius;j++){
                    if(a==i && b==j){
                        go=false;
                        break;
                    }
                }
            }
            
            if(go){
                obstaclesAmount--;
                map[a][b]=obst;
            }
            
        }while(obstaclesAmount!=0);
        
        //Setup start and end
        map[y][x]=start_end;
        map[finishY][finishX]=start_end;
        
    }
    
    public NewMap(int x,int y){
        
    }
    
    //[Functions]
    
    public void Show(){
        
        for(int i=0;i<M;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(j==N-1)
                {
                    System.out.println(map[i][j]);
                }
                else System.out.print(map[i][j]);
            }
        }
        if(isFinished){
            System.out.print("\nMap is finished within " + steps + " steps\n");
            System.out.print("Start Point:("+startX+";"+startY+")\n");
            System.out.print("Finish Point:("+finishX+";"+finishY+")\n");
        }
    }
    
    public void MoveSimulation(){
        int lastDir=1;
        situation=-1;
       // 0 is up || 1 is right || 2 is down \\ also 3 is left :)
       
       if(finishY-y>0){
           situation=2;         //moving only right and down
       }
       else if(finishY-y<0){
           situation=0;        //moving only right and up
       }
       else situation=1;       //moving only right 
       
       
       
       boolean exit=false;
        do{
            boolean stuck=false;
            boolean changed=false;
            
            if(changed)
                steps++;
                Show();
            exit=((x==finishX) && (y==finishY));
            if(exit){
                isFinished=true;
                map[y][x]=start_end;
            }
        }while(!exit);
    }
    
}

основной класс Race:

Java

package race;
public class Race {
 
    
    public static void main(String[] args) {
        NewMap map=new NewMap();
        map.MoveSimulation();
        map.Show();
        
        
    }
    
   
    
}

Может кто помочь? Буду очень благодарен, пока цикл бесконечный, так что не запускайте)

@Abomination_25 · 09.05.2018, 17:11 **[ТС]**

Java

public void MoveSimulation(){
        int [] lastDirection={1,1,1,1};
        int situation=-1;
       // 0 is up || 1 is right || 2 is down \\ also 3 is left :)
       if(finishY-y>0){
           situation=2;         //moving only right and down
       }
       else if(finishY-y<0){
           situation=0;        //moving only right and up
       }
       else situation=1;       //moving only right 
       boolean changed=false;
       boolean exit=false;
        do{
            if(situation==1){
                if(lastDirection[situation]!=3 && x+1<N-1){
                    if(map[y][x+1]!=obst){
                        x++;
                        map[y][x]=tail;
                        lastDirection[situation]=situation;
                        changed=true;
                    }
                    else {
                       int tmp=lastDirection[situation];
                       situation=(Math.random()>0.5)?0:2;
                       lastDirection[situation]=tmp;
                    }   
                }
                else {
                    int tmp=lastDirection[situation];
                    situation=(Math.random()>0.5)?0:2;
                    lastDirection[situation]=tmp;
                }
            } 
            else if(situation==0){
                int up_right=(Math.random()>0.5)?0:1;
                if(up_right==0){
                    if(lastDirection[situation]!=2 && y-1>1){
                        if(map[y-1][x]!=obst){
                            y--;
                            map[y][x]=tail;
                            if(y==finishY){
                                int tmp=lastDirection[situation];
                                situation=1;
                                lastDirection[situation]=tmp;
                            }
                            else if(finishY-y>0){
                                int tmp=lastDirection[situation];
                                situation=(Math.random()>0.5)?1:2;
                                lastDirection[situation]=tmp;
                            }
                            else{
                                lastDirection[situation]=up_right;
                                changed=true;
                            }
                        }
                        else{
                            int tmp=lastDirection[situation];
                            situation=(Math.random()>0.5)?1:3;
                            lastDirection[situation]=tmp;
                        }
                    }
                }
                else if(up_right==1){
                    if(lastDirection[situation]!=3 && x+1<N-1){
                        if(map[y][x+1]!=obst){
                            x++;
                            map[y][x]=tail;
                            if(x==finishX){
                                int tmp=lastDirection[situation];
                                if(finishY-y>0){
                                    situation=2;
                                }
                                else if(finishY-y<0){
                                    situation=0;
                                }
                                lastDirection[situation]=tmp;
                            }
                            else{
                                lastDirection[situation]=up_right;
                                changed=true;
                            }
                        }
                        else{
                            int tmp=lastDirection[situation];
                            situation=(Math.random()>0.5)?0:2;
                            lastDirection[situation]=tmp;
                        }
                    }
                }
            }
            else if(situation==2){
                int down_right=(Math.random()>0.5)?1:2;
                if(down_right==2){
                    if(lastDirection[situation]!=0 && y+1<M-1){
                        if(map[y+1][x]!=obst){
                            y++;
                            map[y][x]=tail;
                            if(y==finishY){
                                int tmp=lastDirection[situation];
                                situation=1;
                                lastDirection[situation]=tmp;
                            }
                            else if(finishY-y<0){
                                int tmp=lastDirection[situation];
                                situation=(Math.random()>0.5)?1:0;
                                lastDirection[situation]=tmp;
                            }
                            else{
                                lastDirection[situation]=down_right;
                                changed=true;
                            }
                        }
                        else{
                            int tmp=lastDirection[situation];
                            situation=(Math.random()>0.5)?1:3;
                            lastDirection[situation]=tmp;
                        }
                    }
                }
                else if(down_right==1){
                    if(lastDirection[situation]!=3 && x+1<N-1){
                        if(map[y][x+1]!=obst){
                            x++;
                            map[y][x]=tail;
                            if(x==finishX){
                                int tmp=lastDirection[situation];
                                if(finishY-y>0){
                                    situation=2;
                                }
                                else if(finishY-y<0){
                                    situation=0;
                                }
                                lastDirection[situation]=tmp;
                            }
                            else{
                                if(finishY-y>0){
                                    situation=2;
                                }
                                else if(finishY-y<0){
                                    situation=0;
                                }
                                lastDirection[situation]=down_right;
                                changed=true;
                            }
                        }
                        else{
                            int tmp=lastDirection[situation];
                            situation=(Math.random()>0.5)?0:2;
                            lastDirection[situation]=tmp;
                        }
                    }
                }
            }
            else if (situation==3){
                if(lastDirection[situation]!=1 && x-1>1){
                    if(map[y][x-1]!=obst){
                        x--;
                        map[y][x]=tail;
                        lastDirection[situation]=situation;
                        changed=true;
                    }
                    else {
                        int tmp=lastDirection[situation];
                        situation=(Math.random()>0.5)?0:2;
                        lastDirection[situation]=tmp;
                    }
                }
                else {
                    int tmp=lastDirection[situation];
                    situation=(Math.random()>0.5)?0:2;
                    lastDirection[situation]=tmp;
                }
            }
            steps++;
            if(changed)
                Show();
            exit=((x==finishX) && (y==finishY));
            if(exit){
                isFinished=true;
                map[y][x]=start_end;
            }
        }while(!exit);
    }

Прошлый код основной функции симуляции... но хочу найти более рациональной решение, чем это...

@xoraxax · 09.05.2018, 17:17

https://en.wikipedia.org/wiki/A*_search_algorithm
ну и там по релэйтед ссылкам походи

@Abomination_25 · 09.05.2018, 19:36 **[ТС]**

Спасибо,я уже нашел тоже этот алгоритм, но не могу понять с чего начать кодить, то есть надо проверить сначала клетки вокруг себя, записать их допустим в массив,но только какие данные о них записать в массив? А потом проверить уже соседей этих клеток? И так до каких пор? То есть какой конечное условие у цикла должно быть? Может кто-нибудь помочь понять этот алгоритм, а то я нахожу псевдо-код, а саму реализацию найти не могу...

@Abomination_25 · 09.05.2018, 20:00 **[ТС]**

Я не очень понимаю какие переменные для хранения нужны мне, сейчас я немного переделал генерацию карты - упростил препятствия:

Вот новый код, здесь почти ничего не изменилось кроме генерации карты...

Java

package astar;
 
public class Map {
    
    char [][] map;
    
    int M=50;
    int N=50;
    int amount=(int)(M*N/100);
    int radius=2;
    int w=5;
    int h=3;
    
    int x,y;
    int oldX,oldY;
    int startX,startY;
    int finishX,finishY;
    
    char border='#';
    char way='.';
    char start='o';
    
    public Map(){
        map=new char[M][N];
        startX=1;
        startY=(int)(Math.random()*(M-3)+1);
        finishX=N-2;
        finishY=(int)(Math.random()*(M-3)+1);
        x=startX;
        y=startY;
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(i==0 || i==M-1){
                    map[i][j]=border;
                }
                else if(j==0 || j==N-1){
                    map[i][j]=border;
                }
                else map[i][j]=' ';
            }
        }
        map[y][x]=start;
        map[finishY][finishX]=start;
        for(int z=0;z<amount;z++){
        int x1,y1;
        do{
            x1=(int)(Math.random()*(N-2)+1);
            y1=(int)(Math.random()*(M-2)+1);
        }while(!createShape(y1,x1));
        for(int i=y1;i<y1+h;i++){
            for(int j=x1;j<x1+w;j++){
                map[i][j]=border;  
            }
        }
        }
    }
    
    public void Show(){
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
              if(j==M-1){
                  System.out.println(map[i][j]);
              }
              else System.out.print(map[i][j]);
            }
        }
    }
    
    public boolean createShape(int a,int b){
        boolean created=false;
        if(a>1+radius && a <M-h-radius && b>1+radius && b<N-w-radius){
        for(int i=a-radius;i<a+h+radius;i++){
            for(int j=b-radius;j<b+w+radius;j++){
                if(map[i][j]==' '){
                    created=true;
                }
                else if(map[i][j]!=' '){
                    return false;
                }
            }
          }
        }
        return created;
    }
    
    public void Move(){
        /*
        boolean found=false;
        do{
            for(int i=0;i<4;i++){
                
            }
            found=((x==finishX) && (y==finishY));
        }while(!found);
        */
    }
    
}

Java

package astar;
public class AStar {
 
    
   
    public static void main(String[] args) {
        Map map=new Map();
        map.Show();
    }
    
}

Нужен ли мне динамический массив или можно обойтись обычным?

@Abomination_25 · 09.05.2018, 20:59 **[ТС]**

Я благодарен за информацию по алгоритму, он мне понятен, но как реализовать на java не представляю... буду очень благодарен, если сможете хоть чем-нибудь мне помочь!

Добавлено через 57 минут
Может быть хотя BFS осилить... Только я понимаю, что мы сначала рассматриваем соседние клетки(пустые) и ту на которой, стояли отмечаем как посещенную. И так для следующих соседей делаем. И где можно все эти данные хранить? Получается что первые соседи подразделяются, и так далее очень много раз... Какой-то рекурсией попахивает...Пока я не понимаю, как нам поможет эти посещения соседей... А дальше, если я смогу понять, как дойти до финиша таким способом. То как правильный путь выбрать и короткий? У нас ведь будет массив посещенных клеток, а не конкретно до финиша. Как получить ответ? То есть цепочку координат, по которым нужно пройти? Аааа. Хелп, очень хочу понять это!

@xoraxax · 09.05.2018, 21:16

короче идея простая, есть точка а, ставим туда цифру 0, в соседние клетки ставим 1, в следующие 2 и т.д, такая типа волна распространяется, делаем до тех пор, очевидно, пока не дойдем до точки Б. От точки Б необходимо соединить клетки в порядке уменьшения записанного в них числа. Т.о. получим путь от А к Б. На бумажке нарисуй, там все достаточно очевидно.

Добавлено через 1 минуту
реализаций дохрена ищи че-нибудь типа "a star java" (хотя я не вполне уверен, что описал именно а*)

@Abomination_25 · 09.05.2018, 21:17 **[ТС]**

Спасибо, то есть нужен массив int двумерный? А так нужно хранить где-то, что точка уже посещена?А препятствия нужно каким числом пометить?

@xoraxax · 09.05.2018, 21:34

Сообщение от Abomination_25

массив int двумерный?

а ты свое поле не в двумерном массиве хранишь?

Сообщение от Abomination_25

А так нужно хранить где-то, что точка уже посещена

если точка посещена, в ней, очевидно, должно быть какое-то число

Сообщение от Abomination_25

А препятствия нужно каким числом пометить?

любым, которое тебе нравится, -1 например

@Abomination_25 · 09.05.2018, 21:42 **[ТС]**

У меня двумерный, но char. Сейчас переделываю под int. Я помечаю стен и препятствия 9999 числом, а неизведанный клетки -1.
Но получается что для каждого соседа нужно запустить процесс поиска новых соседей, а как это сделать?

Java

int i=0;
            if(x-1>1){
                if(tmp[y][x-1]<tmp[y][x]){
                    tmp[y][x-1]=tmp[y][x]+i;
                    queue++;
                }
            }
            if(x+1<N-1){
                if(tmp[y][x+1]<tmp[y][x]){
                    tmp[y][x+1]=tmp[y][x]+i;
                    queue++;
                }
            }
            if(y-1>1){
                if(tmp[y-1][x]<tmp[y][x]){
                    tmp[y-1][x]=tmp[y][x]+i;
                    queue++;
                }
            }
            if(y+1<M-1){
                if(tmp[y+1][x]<tmp[y][x]){
                    tmp[y+1][x]=tmp[y][x]+i;
                    queue++;
                }
            }
            oldX=x;
            oldY=y;

Сейчас пытаюсь сделать так... Но это только для одной клетки...

@xoraxax · 09.05.2018, 21:52

В клетке а стоит 0. В других -1, допустим. Ставим в соседние клетки 1, ищем все клетки, в которых стоит 1, ставим в их соседях 2, ищем все клетки, где стоит 2, ставим в соседях 3 и т.д.

@Abomination_25 · 09.05.2018, 23:18 **[ТС]**

Java

public void BFS(){
        int z=0;
        boolean finish=false;
        do{
            for(int i=0;i<M*N;i++){
                for(int j=0;j<M;j++){
                    for(int t=0;t<N;t++){
                        if(tmp[j][t]==i){
                            Wawe(j,t,++z);
                        }
                    }
                }
            }
        }while(queue!=0 || finish);
    }
    
    public void Wawe(int y,int x,int v){
        if(y-1>1){
            if(tmp[y-1][x]==-1){
                tmp[y-1][x]=tmp[y][x]+v;
                queue++;
            }
        }
        if(y+1<M-1){
            if(tmp[y+1][x]==-1){
                tmp[y+1][x]=tmp[y][x]+v;
                queue++;
            }
        }
        if(x-1>1){
            if(tmp[y][x-1]==-1){
                tmp[y][x-1]=tmp[y][x]+v;
                queue++;
            }
        }
        if(x+1<N-1){
            if(tmp[y][x+1]==-1){
                tmp[y][x+1]=tmp[y][x]+v;
                queue++;
            }
        }
    }

Такая программа будет работать, просто не знаю как протестить...

Добавлено через 5 минут

Java

public void BFS(){
        int z=0;
        boolean finish=false;
        do{
            for(int i=0;i<M*N;i++){
                for(int j=0;j<M;j++){
                    for(int t=0;t<N;t++){
                        if(tmp[j][t]==i){
                            Wawe(j,t,++z);
                            finish=tmp[finishY][finishX]!=-1;
                            if(finish || queue==0){
                                break;
                            }
                        }
                    }
                    if(finish || queue==0){
                        break;
                    }
                }
                if(finish || queue==0){
                    break;
                }
            }
        }while(queue!=0 || finish);
        System.out.println("All good");
    }
    
    public void Wawe(int y,int x,int v){
        if(y-1>1){
            if(tmp[y-1][x]==-1){
                tmp[y-1][x]=tmp[y][x]+v;
                queue++;
            }
        }
        if(y+1<M-1){
            if(tmp[y+1][x]==-1){
                tmp[y+1][x]=tmp[y][x]+v;
                queue++;
            }
        }
        if(x-1>1){
            if(tmp[y][x-1]==-1){
                tmp[y][x-1]=tmp[y][x]+v;
                queue++;
            }
        }
        if(x+1<N-1){
            if(tmp[y][x+1]==-1){
                tmp[y][x+1]=tmp[y][x]+v;
                queue++;
            }
        }
    }

Исправил немного, теперь должно выходить после окончания очереди или как дойдет до финиша. Но не запускал еще...

Добавлено через 1 час 5 минут
Глянет кто? Я не понимаю... Он выводит числа волновые такие, но как найти путь нужный и короткий хз...

Java

package astar;
public class AStar {
 
    
   
    public static void main(String[] args) {
        Map map=new Map();
        
        map.BFS();
        map.Show();
    }
    
}

Java

package astar;
 
 
 
public class Map {
    
    char [][] map;
    int [][] tmp;
    boolean [][] pass;
    int queue=0;
    int lastQ=0;
    int wall=9999;
    int M=20;
    int N=20;
    int amount=(int)(M*N/100);
    int radius=1;
    int w=2;
    int h=2;
    
    int x,y;
    int oldX,oldY;
    int startX,startY;
    int finishX,finishY;
    
    char border='#';
    char way='.';
    char start='o';
    
    public Map(){
        map=new char[M][N];
        startX=1;
        startY=(int)(Math.random()*(M-3)+1);
        finishX=N-2;
        finishY=(int)(Math.random()*(M-3)+1);
        x=startX;
        y=startY;
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(i==0 || i==M-1){
                    map[i][j]=border;
                }
                else if(j==0 || j==N-1){
                    map[i][j]=border;
                }
                else map[i][j]=' ';
            }
        }
        map[y][x]=start;
        map[finishY][finishX]=start;
        for(int z=0;z<amount;z++){
        int x1,y1;
        do{
            x1=(int)(Math.random()*(N-2)+1);
            y1=(int)(Math.random()*(M-2)+1);
        }while(!createShape(y1,x1));
        for(int i=y1;i<y1+h;i++){
            for(int j=x1;j<x1+w;j++){
                map[i][j]=border;  
            }
        }
        }
        tmp =new int[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(map[i][j]==border){
                    tmp[i][j]=wall;
                }
                else tmp[i][j]=-1;
            }
        }
        tmp[y][x]=0;
        pass=new boolean[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                pass[i][j]=false;
            }
        }
        
    }
    
    public void Show(){
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
              if(j==N-1){
                  if(tmp[i][j]==wall)
                  System.out.println(border);
              }
              
              else {
                  if(tmp[i][j]==wall)
                  System.out.print(border);
                  else{ 
                      if(tmp[i][j]!=-1)
                      System.out.print(tmp[i][j]);
                      else System.out.print(' ');
                  }
              }
            }
        }
    }
    
    public boolean createShape(int a,int b){
        boolean created=false;
        if(a>1+radius && a <M-h-radius && b>1+radius && b<N-w-radius){
        for(int i=a-radius;i<a+h+radius;i++){
            for(int j=b-radius;j<b+w+radius;j++){
                if(map[i][j]==' '){
                    created=true;
                }
                else if(map[i][j]!=' '){
                    return false;
                }
            }
          }
        }
        return created;
    }
    
    public void BFS(){
        int z=0;
        queue=1;
        lastQ=queue;
        boolean finish=false;
        do{
            while(lastQ!=0){
            for(int i=0;i<M;i++){
                for(int j=0;j<N;j++){
                    if(!pass[i][j]){
                        if(tmp[i][j]==z){
                            Wawe(i,j,z);
                            Show();
                            lastQ--;
                        }
                    }
                }
            }
            }
            lastQ=queue;
            z++;
            System.out.println(finishX +"|"+finishY);
            finish=tmp[finishY][finishX]!=-1 || lastQ==0;
        }while(!finish);
        System.out.println("All good");
        
    }
    
    public void Wawe(int y,int x,int v){
        v++;
        queue--;
        if(y-1>1){
            if(tmp[y-1][x]==-1){
                tmp[y-1][x]=tmp[y][x]+1;
                queue++;
                
            }
        }
        if(y+1<M-1){
            if(tmp[y+1][x]==-1){
                tmp[y+1][x]=tmp[y][x]+1;
                queue++;
            }
        }
        if(x-1>1){
            if(tmp[y][x-1]==-1){
                tmp[y][x-1]=tmp[y][x]+1;
                queue++;
            }
        }
        if(x+1<N-1){
            if(tmp[y][x+1]==-1){
                tmp[y][x+1]=tmp[y][x]+1;
                queue++;
            }
        }
        pass[y][x]=true;
    }
    
}

Добавлено через 8 минут
Теперь у меня как бы есть всевозможные пути до точки, и мне нужно выбрать такой, который короче или? Просто у меня сейчас есть разные пути, но по длине одинаковые(по числам). Как преобразовать обратно числа в путь? Типа начинаю с 0 рандомно кидать направление(в четыре стороны, пока не попадется 1? А потом так же для 1 кидать в стороны, пока не попадется 2? и Так до финиша?
##########
# #
#23456789 #
#123##89 #
#012##780 #
#12345678 #
#23456789 #
#3456789 #
#456789 #
##########
Да и вот тут от 0 до 0(второй ноль для удобства поставил 0, там видимо 9 было). Можно пойти в разных направлениях, изначально. Если пойти вверх, то мы дойдем до 9 которая не приведет нас к финишу. Тоже самое и с самыми нижними девятками. Все два пути нас тут удовлетворяют, точнее две восьмерки, которые могут привести к нужной девятке... В общем надо еще одно условие ставить что ли? Как выбрать путь!!ААААА

@xoraxax · 09.05.2018, 23:25

Ты на форуме хочешь узнать, чего тебе надо? Удивительно, как естественный отбор плохо работает в современном мире.

Добавлено через 1 минуту
На бумажке нарисуй руками все этапы работы алгоритма и посмотри, что получается в итоге.

@Abomination_25 · 09.05.2018, 23:25 **[ТС]**

Название: Screenshot_3.png
Просмотров: 54

Размер: 2.6 Кб

Вот тут красным отмечен финиш. К нему можно придти разными вариантами. Как можно отобрать более-менее лучше варианты?
Аж 4-мя вариантами можно дойти благополучно, но если рандомно брать изначально направление и проверять их на 1, то можно изначально выбрать путь, который не приведет никуда.

@xoraxax · 09.05.2018, 23:48

От девятки до нуля линию проводишь - получаешь путь. Очевидно, если таких путей несколько, то они равнозначны и не важно, какой из них выбирать. Можно выбрать все возможные пути и, добавив какие-то дополнительные критерии выбрать подходящий, но это уже другой вопрос.

@Abomination_25 · 10.05.2018, 01:04 **[ТС]**

Java

package astar;
public class AStar {
 
    
   
    public static void main(String[] args) {
        Map map=new Map();
        
        map.BFS();
        map.Show2();
    }
    
}

Java

package astar;
import java.util.Random;
class Point{
    public int x;
    public int y;
    
    public Point()
    {
        x=0;
        y=0;
    }
}
 
public class Map {
    Random rand;
    Point [] point;
    char [][] map;
    int [][] tmp;
    boolean [][] pass;
    int queue=0;
    int lastQ=0;
    int wall=9999;
    int M=50;
    int N=50;
    int amount=(int)(M*N/100);
    int radius=1;
    int w=2;
    int h=2;
    
    int x,y;
    int oldX,oldY;
    int startX,startY;
    int finishX,finishY;
    
    char border='#';
    char way='.';
    char start='o';
    
    public Map(){
        rand=new Random();
        map=new char[M][N];
        startX=1;
        startY=(int)(Math.random()*(M-3)+1);
        finishX=N-2;
        finishY=(int)(Math.random()*(M-3)+1);
        x=startX;
        y=startY;
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(i==0 || i==M-1){
                    map[i][j]=border;
                }
                else if(j==0 || j==N-1){
                    map[i][j]=border;
                }
                else map[i][j]=' ';
            }
        }
        map[y][x]=start;
        map[finishY][finishX]=start;
        for(int z=0;z<amount;z++){
        int x1,y1;
        do{
            x1=(int)(Math.random()*(N-2)+1);
            y1=(int)(Math.random()*(M-2)+1);
        }while(!createShape(y1,x1));
        for(int i=y1;i<y1+h;i++){
            for(int j=x1;j<x1+w;j++){
                map[i][j]=border;  
            }
        }
        }
        tmp =new int[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(map[i][j]==border){
                    tmp[i][j]=wall;
                }
                else tmp[i][j]=-1;
            }
        }
        tmp[y][x]=0;
        pass=new boolean[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                pass[i][j]=false;
            }
        }
        
    }
    
    public void Show2(){
         for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
              if(j==N-1){
                  System.out.println(map[i][j]);
              }
              else {
                  System.out.print(map[i][j]);
              }
            }
        }
    }
    
    public void Show(){
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
              if(j==N-1){
                  if(tmp[i][j]==wall)
                  System.out.println(border);
              }
              
              else {
                  if(tmp[i][j]==wall)
                  System.out.print(border);
                  else{ 
                      if(tmp[i][j]!=-1)
                      System.out.print(tmp[i][j]);
                      else System.out.print(' ');
                  }
              }
              
            }
        }
    }
    
    public boolean createShape(int a,int b){
        boolean created=false;
        if(a>1+radius && a <M-h-radius && b>1+radius && b<N-w-radius){
        for(int i=a-radius;i<a+h+radius;i++){
            for(int j=b-radius;j<b+w+radius;j++){
                if(map[i][j]==' '){
                    created=true;
                }
                else if(map[i][j]!=' '){
                    return false;
                }
            }
          }
        }
        return created;
    }
    
    public void BFS(){
        int z=0;
        queue=1;
        lastQ=queue;
        boolean finish=false;
        do{
            while(lastQ!=0){
            for(int i=0;i<M;i++){
                for(int j=0;j<N;j++){
                    if(!pass[i][j]){
                        if(tmp[i][j]==z){
                            Wawe(i,j,z);
                            //Show();
                            lastQ--;
                        }
                    }
                }
            }
            }
            lastQ=queue;
            z++;
           
            finish=tmp[finishY][finishX]!=-1 || lastQ==0;
        }while(!finish);
        System.out.println("Start:"+startX +"|"+startY);
        System.out.println("Finish:"+finishX +"|"+finishY);
        System.out.println("Last point value:"+tmp[finishY][finishX]);
        
        point=new Point[tmp[finishY][finishX]+1];
        for(int i=0;i<point.length;i++){
            point[i]=new Point();
        }
        int a=point.length-1;
        point[a].x=finishX;
        point[a].y=finishY;
        boolean ex=false;
        do{
            a=Path(point[a].y,point[a].x,a);
            ex=((point[0].x==startX) && (point[0].y==startY));
        }while(!ex);
        
        for(int i=0;i<point.length;i++){
            System.out.print("x:"+point[i].x+" y:"+point[i].y+"\n");
        }
        
        System.out.println("All good");
        
        for(int i=0;i<point.length;i++){
            if(i==0 || i==point.length-1)
                map[point[i].y][point[i].x]=start;
            else 
                map[point[i].y][point[i].x]=way;
 
            
        }
        
        
    }
    
    public int Path(int y,int x,int z){
        int dir=rand.nextInt(3);
        if(dir==0){
            if(y-1>0){
                if(tmp[y-1][x]==tmp[y][x]-1){
                    z--;
                    point[z].x=x;
                    point[z].y=y-1;
                }
            }
        }
        else if(dir==1){
            if(y+1<M-1){
                if(tmp[y+1][x]==tmp[y][x]-1){
                    z--;
                    point[z].x=x;
                    point[z].y=y+1;
                }
            }
        }
        else if(dir==2){
            if(x-1>0){
                if(tmp[y][x-1]==tmp[y][x]-1){
                    z--;
                    point[z].x=x-1;
                    point[z].y=y;
                }
            }
        }
        return z;
    }
    
    public void Wawe(int y,int x,int v){
        v++;
        queue--;
        if(y-1>0){
            if(tmp[y-1][x]==-1){
                tmp[y-1][x]=tmp[y][x]+1;
                queue++;
                
            }
        }
        if(y+1<M-1){
            if(tmp[y+1][x]==-1){
                tmp[y+1][x]=tmp[y][x]+1;
                queue++;
            }
        }
        if(x-1>0){
            if(tmp[y][x-1]==-1){
                tmp[y][x-1]=tmp[y][x]+1;
                queue++;
            }
        }
        if(x+1<N-1){
            if(tmp[y][x+1]==-1){
                tmp[y][x+1]=tmp[y][x]+1;
                queue++;
            }
        }
        pass[y][x]=true;
    }
    
}

Рабочий код. Без комментариев, так как устал на сегодня. Завтра поправлю ООП и добавлю комментарии

Добавлено через 6 минут

Java

package astar;
public class AStar {
 
    
   
    public static void main(String[] args) {
        Map map=new Map();
        
        map.BFS();
        map.Show2();
    }
    
}

Java

package astar;
import java.util.Random;
class Point{
    public int x;
    public int y;
    
    public Point()
    {
        x=0;
        y=0;
    }
}
 
public class Map {
    Random rand;
    Point [] point;
    char [][] map;
    int [][] tmp;
    boolean [][] pass;
    int queue=0;
    int lastQ=0;
    int wall=9999;
    int M=50;
    int N=80;
    int amount=(int)(M*N/50);
    int radius=1;
    int w=3;
    int h=2;
    
    int x,y;
    int oldX,oldY;
    int startX,startY;
    int finishX,finishY;
    
    char border='#';
    char way='.';
    char start='o';
    
    public Map(){
        rand=new Random();
        map=new char[M][N];
        startX=1;
        startY=(int)(Math.random()*(M-3)+1);
        finishX=N-2;
        finishY=(int)(Math.random()*(M-3)+1);
        x=startX;
        y=startY;
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(i==0 || i==M-1){
                    map[i][j]=border;
                }
                else if(j==0 || j==N-1){
                    map[i][j]=border;
                }
                else map[i][j]=' ';
            }
        }
        map[y][x]=start;
        map[finishY][finishX]=start;
        for(int z=0;z<amount;z++){
        int x1,y1;
        do{
            x1=(int)(Math.random()*(N-2)+1);
            y1=(int)(Math.random()*(M-2)+1);
        }while(!createShape(y1,x1));
        for(int i=y1;i<y1+h;i++){
            for(int j=x1;j<x1+w;j++){
                map[i][j]=border;  
            }
        }
        }
        tmp =new int[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(map[i][j]==border){
                    tmp[i][j]=wall;
                }
                else tmp[i][j]=-1;
            }
        }
        tmp[y][x]=0;
        pass=new boolean[M][N];
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                pass[i][j]=false;
            }
        }
        
    }
    
    public void Show2(){
         for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
              if(j==N-1){
                  System.out.println(map[i][j]);
              }
              else {
                  System.out.print(map[i][j]);
              }
            }
        }
    }
    
    public void Show(){
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
              if(j==N-1){
                  if(tmp[i][j]==wall)
                  System.out.println(border);
              }
              
              else {
                  if(tmp[i][j]==wall)
                  System.out.print(border);
                  else{ 
                      if(tmp[i][j]!=-1)
                      System.out.print(tmp[i][j]);
                      else System.out.print(' ');
                  }
              }
              
            }
        }
    }
    
    public boolean createShape(int a,int b){
        boolean created=false;
        if(a>1+radius && a <M-h-radius && b>1+radius && b<N-w-radius){
        for(int i=a-radius;i<a+h+radius;i++){
            for(int j=b-radius;j<b+w+radius;j++){
                if(map[i][j]==' '){
                    created=true;
                }
                else if(map[i][j]!=' '){
                    return false;
                }
            }
          }
        }
        return created;
    }
    
    public void BFS(){
        int z=0;
        queue=1;
        lastQ=queue;
        boolean finish=false;
        do{
            while(lastQ!=0){
            for(int i=0;i<M;i++){
                for(int j=0;j<N;j++){
                    if(!pass[i][j]){
                        if(tmp[i][j]==z){
                            Wawe(i,j,z);
                            //Show();
                            lastQ--;
                        }
                    }
                }
            }
            }
            lastQ=queue;
            z++;
           
            finish=tmp[finishY][finishX]!=-1 || lastQ==0;
        }while(!finish);
        System.out.println("Start:"+startX +"|"+startY);
        System.out.println("Finish:"+finishX +"|"+finishY);
        System.out.println("Last point value:"+tmp[finishY][finishX]);
        
        point=new Point[tmp[finishY][finishX]+1];
        for(int i=0;i<point.length;i++){
            point[i]=new Point();
        }
        int a=point.length-1;
        point[a].x=finishX;
        point[a].y=finishY;
        boolean ex=false;
        do{
            a=Path(point[a].y,point[a].x,a);
            ex=((point[0].x==startX) && (point[0].y==startY));
        }while(!ex);
        
        for(int i=0;i<point.length;i++){
            System.out.print(i+" step >> x:"+point[i].x+" y:"+point[i].y+"\n");
        }
        
        System.out.println("All good");
        
        for(int i=0;i<point.length;i++){
            if(i==0 || i==point.length-1)
                map[point[i].y][point[i].x]=start;
            else 
                map[point[i].y][point[i].x]=way;
 
            
        }
        
        
    }
    
    public int Path(int y,int x,int z){
        int dir=rand.nextInt(3);
        if(dir==0){
            if(y-1>0){
                if(tmp[y-1][x]==tmp[y][x]-1){
                    z--;
                    point[z].x=x;
                    point[z].y=y-1;
                }
            }
        }
        else if(dir==1){
            if(y+1<M-1){
                if(tmp[y+1][x]==tmp[y][x]-1){
                    z--;
                    point[z].x=x;
                    point[z].y=y+1;
                }
            }
        }
        else if(dir==2){
            if(x-1>0){
                if(tmp[y][x-1]==tmp[y][x]-1){
                    z--;
                    point[z].x=x-1;
                    point[z].y=y;
                }
            }
        }
        return z;
    }
    
    public void Wawe(int y,int x,int v){
        v++;
        queue--;
        if(y-1>0){
            if(tmp[y-1][x]==-1){
                tmp[y-1][x]=tmp[y][x]+1;
                queue++;
                
            }
        }
        if(y+1<M-1){
            if(tmp[y+1][x]==-1){
                tmp[y+1][x]=tmp[y][x]+1;
                queue++;
            }
        }
        if(x-1>0){
            if(tmp[y][x-1]==-1){
                tmp[y][x-1]=tmp[y][x]+1;
                queue++;
            }
        }
        if(x+1<N-1){
            if(tmp[y][x+1]==-1){
                tmp[y][x+1]=tmp[y][x]+1;
                queue++;
            }
        }
        pass[y][x]=true;
    }
    
}

Рабочий код. Без комментариев, так как устал на сегодня. Завтра поправлю ООП и добавлю комментарии. Может кто потестить код на разных размерах карты(M и N)? Можно покрутить еще radius(расстояние между препятствиями) и размер самих препятствий(w и h). Так же еще есть amount - Количество препятствий. Естественно условие на проверку этих значений, чтобы не зациклилось еще не делал. Так, что если программа не сможет найти решение от каких-то значений, то нужно рестартнуть и вбить значения поменьше.

@Abomination_25 4 / 4 / 0 Регистрация: 13.12.2016 Сообщений: 246
	09.05.2018, 23:25 [ТС]	14
	Вот тут красным отмечен финиш. К нему можно придти разными вариантами. Как можно отобрать более-менее лучше варианты? Аж 4-мя вариантами можно дойти благополучно, но если рандомно брать изначально направление и проверять их на 1, то можно изначально выбрать путь, который не приведет никуда. 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	09.05.2018, 23:48	15
	От девятки до нуля линию проводишь - получаешь путь. Очевидно, если таких путей несколько, то они равнозначны и не важно, какой из них выбирать. Можно выбрать все возможные пути и, добавив какие-то дополнительные критерии выбрать подходящий, но это уже другой вопрос. 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	09.05.2018, 17:17	3
	https://en.wikipedia.org/wiki/A*_search_algorithm ну и там по релэйтед ссылкам походи 0

@Abomination_25 4 / 4 / 0 Регистрация: 13.12.2016 Сообщений: 246
	09.05.2018, 19:36 [ТС]	4
	Спасибо,я уже нашел тоже этот алгоритм, но не могу понять с чего начать кодить, то есть надо проверить сначала клетки вокруг себя, записать их допустим в массив,но только какие данные о них записать в массив? А потом проверить уже соседей этих клеток? И так до каких пор? То есть какой конечное условие у цикла должно быть? Может кто-нибудь помочь понять этот алгоритм, а то я нахожу псевдо-код, а саму реализацию найти не могу... 0

@Abomination_25 4 / 4 / 0 Регистрация: 13.12.2016 Сообщений: 246
	09.05.2018, 20:59 [ТС]	6
	Я благодарен за информацию по алгоритму, он мне понятен, но как реализовать на java не представляю... буду очень благодарен, если сможете хоть чем-нибудь мне помочь! Добавлено через 57 минут Может быть хотя BFS осилить... Только я понимаю, что мы сначала рассматриваем соседние клетки(пустые) и ту на которой, стояли отмечаем как посещенную. И так для следующих соседей делаем. И где можно все эти данные хранить? Получается что первые соседи подразделяются, и так далее очень много раз... Какой-то рекурсией попахивает...Пока я не понимаю, как нам поможет эти посещения соседей... А дальше, если я смогу понять, как дойти до финиша таким способом. То как правильный путь выбрать и короткий? У нас ведь будет массив посещенных клеток, а не конкретно до финиша. Как получить ответ? То есть цепочку координат, по которым нужно пройти? Аааа. Хелп, очень хочу понять это! 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	09.05.2018, 21:16	7
	короче идея простая, есть точка а, ставим туда цифру 0, в соседние клетки ставим 1, в следующие 2 и т.д, такая типа волна распространяется, делаем до тех пор, очевидно, пока не дойдем до точки Б. От точки Б необходимо соединить клетки в порядке уменьшения записанного в них числа. Т.о. получим путь от А к Б. На бумажке нарисуй, там все достаточно очевидно. Добавлено через 1 минуту реализаций дохрена ищи че-нибудь типа "a star java" (хотя я не вполне уверен, что описал именно а*) 0

@Abomination_25 4 / 4 / 0 Регистрация: 13.12.2016 Сообщений: 246
	09.05.2018, 21:17 [ТС]	8
	Спасибо, то есть нужен массив int двумерный? А так нужно хранить где-то, что точка уже посещена?А препятствия нужно каким числом пометить? 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	09.05.2018, 21:34	9
	Сообщение от Abomination_25 массив int двумерный? а ты свое поле не в двумерном массиве хранишь? Сообщение от Abomination_25 А так нужно хранить где-то, что точка уже посещена если точка посещена, в ней, очевидно, должно быть какое-то число Сообщение от Abomination_25 А препятствия нужно каким числом пометить? любым, которое тебе нравится, -1 например 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	09.05.2018, 21:52	11
	В клетке а стоит 0. В других -1, допустим. Ставим в соседние клетки 1, ищем все клетки, в которых стоит 1, ставим в их соседях 2, ищем все клетки, где стоит 2, ставим в соседях 3 и т.д. 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	09.05.2018, 23:25	13
	Ты на форуме хочешь узнать, чего тебе надо? Удивительно, как естественный отбор плохо работает в современном мире. Добавлено через 1 минуту На бумажке нарисуй руками все этапы работы алгоритма и посмотри, что получается в итоге. 0