Omijanie przeszkód w labiryncie - najkrótsza droga

0

Witam, potrzebuję algorytm na obliczenie najkrótszej drogi, w której występują przeszkody. O ile to możliwe, muszę znaleźć najkrótszą drogę, która nie zawiera przeszkód. Jeśli takiej nie ma - wtedy wyliczam najkrótszą drogą z przeszkodami. Pierwszą część zrobiłem tj. znajdywanie najkrótszej drogi bez przeszkód, ale nie mam zielonego pojęcia jak napisać obsługiwanie przeszkód. Przykładowo w labiryncie wolne pola są oznaczone spacją, a przeszkody znakiem '#'. Czy mógłby mi ktoś wytłumaczyć jak taki algorytm zaimplementować?

PS. Przeszkody mogę omijać tylko wtedy, gdy przed przeszkodą jest wolne pole, oraz za przeszkodą.

To co dotychczas napisałem:

const int VISITED = 1;
const int EMPTY = 0;
const int LEFT = 2;
const int RIGHT = 3;
const int DOWN = 4;
const int UP = 5;
const int WALL = 6;

int graph(vector<vector<int> > board, Point start, Point end, int n, int m)
{
    int count = 0;
    int reallyCount = 0;
    queue<Point> q;
    Point p(start.x, start.y);

    board[p.x][p.y] = VISITED;

    q.push(start);
    while(!q.empty())
    {
        //drawBoard(board, n, m);
        count++;

        p = q.front();
        q.pop();

        if(p == end)
        {
            while(board[p.x][p.y] != VISITED)
            {
                switch(board[p.x][p.y])
                {
                    case LEFT: board[p.x++][p.y] = VISITED; reallyCount++; break;
                    case UP: board[p.x][p.y++] = VISITED; reallyCount++; break;
                    case RIGHT: board[p.x--][p.y] = VISITED; reallyCount++; break;
                    case DOWN: board[p.x][p.y--] = VISITED; reallyCount++; break;
                }
            }

            break;
        }

        if(board[p.x - 1][p.y] == EMPTY)
        {
            Point pp(p.x - 1, p.y);
            board[p.x - 1][p.y] = LEFT;
            q.push(pp);
        }

        if(board[p.x][p.y - 1] == EMPTY)
        {
            Point pp(p.x, p.y - 1);
            board[p.x][p.y - 1] = UP;
            q.push(pp);
        }

        if(board[p.x + 1][p.y] == EMPTY)
        {
            Point pp(p.x + 1, p.y);
            board[p.x + 1][p.y] = RIGHT;
            q.push(pp);
        }

        if(board[p.x][p.y + 1] == EMPTY)
        {
            Point pp(p.x, p.y + 1);
            board[p.x][p.y + 1] = DOWN;
            q.push(pp);
        }
    }
    return (reallyCount > 0) ? reallyCount : -1;
}

Struktura Point przechowuje współrzędne punktu X i Y.

Proszę o pomoc.

0

BFS, Dijkstra, A*

0

To może inaczej, bo chyba źle zatytułowałem temat - gdy nie mogę znaleźć najkrótszej drogi bez przeszkód muszę wyznaczyć drogę z przeszkodami (tj. mogę przechodzić po przeszkodach jeśli nie można inaczej). Umiem wykorzystać grafy, algorytmu Dijkistry nie chcę używać, bo chcę się czegoś nauczyć. Google przeszukałem wdłuż i wszerz, ale nie znlazłem odpowiedzi. Pewnie jest to banalnie proste, ale ja nie mam żadnego pomysłu na zaprogramowanie tego.

0

Jeśli możesz chodzić po przeszkodach itp, wtedy najkrótsza droga to prosta droga, czyli odcinek od (a,b) do (c,d) ;)

0
kubek3898 napisał(a):

... Google przeszukałem wdłuż i wszerz ...
Chuck Norris? Witamy, witamy.

0

2x UP: tak tylko, że przed i za przeszkodą musi stać wolne pole.

Generalnie nie umiem wyobrazić sobie sprawdzenia tych pól z przeszkodami. Próbowałem coś w stylu:

if(lab[i + 1][j] == PRZESZKODA && lab[i + 2][j] == WOLNE)

Problem w tym, że muszę powtorzyć to dla 4 kierunków, a później jeszcze napisać instrukcję dla zwykłych kroków. Z powodu dużego zagmatwania kodu wydaje mi się, że nie tędy droga.

0

To proste jest droga pomiędzy y1,x1 a y2,x2 jeżeli (map[y1][x1]!=PRZESZKODA)||(map[y2][x2]!=PRZESZKODA)

0

Ehh, chyba wciąż mnie nie rozumiecie, albo to ja nie ogarniam. Ogólnie w skrócie zadanie wygląda tak:

Na planszy o rozmiarze N x M są położone 2 punkty - startowy i końcowy. Teraz poruszając się zgodnie z ruchem na planszy - up, down, left, right muszę przedostać się do pola końcowego. Niestety na planszy występuje też przeszkody lub inaczej pola specjalne, przez które można przejć (przeskoczyć), ale to pole musi stać pomiędzy wolnymi polami :D. Pytanie jest natomiast ile kroków między tymi 2 punktami należy wykonać, wykonując jak najmniej ruchów specjalnych.

Zaplanowałem to tak, by najpierw napisać zwykłe przeszukiwanie grafu. Funkcja ta pokazała by więc czy da się przejść planszę bez przeskakiwania pól specjalnych. Teraz jednak trzeba napisać funkcję, która wyznaczy drogę, gdy występują pola specjalne. I tutaj mam problem, bo nie wiem w jaki sposób sprawdzić kiedy pole jest specjalnym, a kiedy nie.

1

Weź nie udziwniaj, zwykły algorytm Dijkstry przy wstawaniu na pole specjalne koszt =2, dla pozostałych - koszt =1.
Jak chcesz pomasturbować z własnym algorytmem to przynajmniej nie rób tego publicznie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1