Kun nyt vihdoinkin älysin tuon lyhimmän reitin etsimisen salat, päätin lisätä siitä koodivinkin tänne, kun täällä ei sellaista vielä näytä olevan.
Idea saattaa olla sama, kuin A-star:ssa, mutta en ole varma, sillä en ymmärtänyt esimerkkikoodia.
Joka tapauksessa idea menee siten, että merkataan kaikki lähtöpisteen ympärillä olevat ruudut(ei kuitenkaan seiniä ja muita esteitä) yhtä suuremmalla, kuin lähtöpiste. Sitten käydään karttaa läpi etsien äsken merkattuja ruutuja ja merkataan niiden ympärillä olevat ruudut (ei seiniä, esteitä eikä jo merkattuja ruutuja). Tätä jatketaan, kunnes tullaan päätepisteeseen.
Sitten lähdetään tulemaan takaisin päin siten, että merkataan päätepiste reitin viimeiseksi etapiksi. Ja sitten etsitään päätepisteen ympäriltä yhtä pienemmällä arvolla merkattu ruutu ja merkataan se reitin toiseksi viimeiseksi etapiksi ja jatketaan näin, kunnes tullaan alkupisteeseen(S), mutta ei merkata kuitenkaan alkupistettä(S) etapiksi.
Ja kuten huomanette, algorithmi olettaa, että kaikki kuljettava alue on yhtä helppokulkuista.
Merkattuja ruutuja ei myöskään etsitä, kuin siltä neliöltä, johon merkatut ruudut mahtuvat. Tämä tekee etsimisen nopeammaksi erityisesti isoissa kentissä.
Sitten vielä parametreista:
**map(huom! map[leveys][korkeus]):
- Maastokartta, jossa kulkukelpoinen alue on merkattu 0:lla
ja kulku kelvoton alue nollasta poikkeavalla luvulla.
int width, height:
-Kentän leveys ja korkeus
int sx, sy:
-Alku koordinaatit
int ex, ey:
-Loppu koordinaatit
int maxlen:
-Reitin maksimipituus ruutuina. Jos reitistä tulisi pidempi, etsintä lopetetaan.
Funktio palauttaa reitin Path tyyppisenä alkaen 1:stä. Jos reittiä ei löydy, funktio palauttaa NULL:n.
Lisäksi mukana on myös ohjelman pätkä, jolla voi helposti todentaa funktion toimivuutta. Tällöin tarvitset myös map.txt:n, sillä se sisältää esimerkkikartan.
typedef struct Path {
int short x, y;
bool last;
};
Path *FindPath(short int **map, int width, int height, int sx, int sy, int ex, int ey, int maxlen) {
Path *path = NULL; // reitin palautus formaatti
short int **pathmap; // reittikartta
short int distance = 1; // etäisyys
short int pathindex; // reittialkion indexi
short int leftside, rightside, upside, downside; // etsittävän alueen reunat
bool distancefound = true; // uusi alkio löydetty reitillä
bool pathfound = false; // reitti löydetty alusta loppuun
// Jos alkupiste on sama kuin loppupiste
if(sx == ex && sy == ey)
return NULL;
// Varataan muistia reittikartalle
pathmap = new short int* [width+2];
for(int i = 0; i < width+2; i++)
pathmap[i] = new short int [height+2];
// Kopioidaan maastokartta reittikartan pohjaksi ja jätetään reunoille
// yksi ruutu tyhjää, jotta ei osoitella myöhemmin taulukon ulkopuolelle
for(int y = 0; y < height; y++) {
for(int x = 0; x < width; x++) {
if(map[x][y] <= 0)
pathmap[x+1][y+1] = map[x][y];
else
pathmap[x+1][y+1] = -map[x][y];
}
}
// Luodaan ympärille seinät
for(int i = 0; i < width; i++) {
pathmap[i][0] = 0;
pathmap[i][height+1] = 0;
}
for(int i = 0; i < height; i++) {
pathmap[0][i] = 0;
pathmap[width+1][i] = 0;
}
// Myös alku- ja loppupiste täytyy asettaa pathmap-yhteensopivaksi
sx++; sy++;
ex++; ey++;
// Lähtöpiste merkataan 1:llä
pathmap[sx][sy] = 1;
// alussa etsitään vain lähtöpisteen ympäriltä
leftside = sx-1;
rightside = sx+1;
upside = sy-1;
downside = sy+1;
// Sitten merkataan kaikki distance muuttujan arvoiset alkiot
// distance+1:n arvoisiksi, lisätään distanceen yksi ja jatketaan
// kunnes loppupiste löytyy
distance = 1;
while(!pathfound && distancefound && distance < maxlen) {
distancefound = false;
for(int y = upside; y <= downside; y++) {
for(int x = leftside; x <= rightside; x++) {
// Jos alkio on ympärimerkattavan arvoinen
if(pathmap[x][y] == distance) {
distancefound = true; // yksikin alkio löydetty
// Jos piste on loppupiste, siirrytään suraavaan vaiheeseen
if(ex == x && ey == y) {
y = height+1; // Jotta päästään pois koko looppirakenteeta
pathfound = true;
distance--;
break;
}
// Muussa tapauksessa merkataan ympärillä olevat vapaat alkiot
// Samalla tarkistetaan, josko etsintäaluetta tulisi laajentaa
for(int j = y-1; j <= y+1; j++) {
for(int i = x-1; i <= x+1; i++) {
if(pathmap[i][j] == 0) { // Jos vapaa ruutu
pathmap[i][j] = distance+1; // Merkataan
// Mahdollisen etsintäalueen laajentamisen tarkistukset
if(upside > y-1) upside = y-1;
if(downside < y+1) downside = y+1;
if(leftside > x-1) leftside = x-1;
if(rightside < x+1) rightside = x+1;
}
}
}
}
}
}
// Seuraavalla kierroksella etsitään tällä
// kierroksella merkattuja alkioita
distance++;
}
// Jos reitti löydettiin alusta loppuun
if(pathfound == true) {
// Varataan muistia reitille
path = new Path [distance];
// asetetaan loppupiste apulaisiin ja viimeisen merkki viimeiseen
int x = ex, y = ey; // reitinhaku apulaiset
path[distance].last = true; // loppupiste on viimeinen
// Etsitään reitti alusta loppun siten, että loppupisteen ympäriltä etsitään
// seuraavaa alempiarvoista alkiota ja sitten taas löydetyn ympäriltä jne.
for(int a = distance-1; a > 0; a--) {
// -1, jotta sijainti olisi oikein parametrina annetussa kartassa
path[a].x = x-1;
path[a].y = y-1;
path[a].last = false; // ei ole viimeinen
// On tärkeää, että etsitään reittiä ensin pysty- ja vaakasunnista
// ja sitten vasta vinosuunnista, jotta reitistä tulee järkevän oloinen.
// Muuten reittiin voi tulla outoja koukkauksia.
if(pathmap[x][y-1] == a) // yläpuoli
{y--; continue;}
if(pathmap[x][y+1] == a) // alapuoli
{y++; continue;}
if(pathmap[x-1][y] == a) // vasen
{x--; continue;}
if(pathmap[x+1][y] == a) // oikea
{x++; continue;}
if(pathmap[x-1][y-1] == a) // vasen yläkulma
{x--; y--; continue;}
if(pathmap[x+1][y-1] == a) // oikea yläkulma
{x++; y--; continue;}
if(pathmap[x-1][y+1] == a) // vasen alakulma
{x--; y++; continue;}
if(pathmap[x+1][y+1] == a) // oikea alakulma
{x++; y++; continue;}
}
}
return path;
}#include <stdlib.h>
#include <stdio.h>
typedef struct Path {
int short x, y;
bool last;
};
// alku(S) ja loppu(E) koordinaatit
const short int SX = 1;
const short int SY = 1;
const short int EX = 29;
const short int EY = 1;
Path *FindPath(short int **map, int width, int height, int sx, int sy, int ex, int ey, int maxlen);
int main(int argc, char *argv[])
{
Path *path; // Reitti tallennetaan Path-muotoon
// Ladataan kertta
short int **map;
map = new short int* [80];
for(int i = 0; i < 80; i++)
map[i] = new short int [23];
FILE *file = fopen("map.txt", "rb");
for(int y = 0; y < 23; y++) {
for(int x = 0; x < 80; x++) {
fread(&map[x][y], sizeof(short int), 1, file);
}
}
fclose(file);
// Etsitään reitti
path = FindPath(map, 80, 23, SX, SY, EX, EY, 256);
// Jos reitti löytyi
if(path != NULL) {
// Merkataan se kartalle
int calc = 1;
do {
map[path[calc].x][path[calc].y] = 1;
calc++;
}while(!path[calc].last);
}
map[SX][SY] = 2; // alkupiste
map[EX][EY] = 3; // loppupiste
// Tulostetaan kartta
for(int y = 0; y < 23; y++) {
for(int x = 0; x < 80; x++) {
if(map[x][y] == -1)
printf("#");
if(map[x][y] == 0)
printf("0");
if(map[x][y] == 1)
printf(" ");
if(map[x][y] == 2)
printf("S");
if(map[x][y] == 3)
printf("E");
}
}
system("PAUSE");
return 0;
}Kiitos kun julkaisit tämän. On nimittäin aiheuttanut päänvaivaa ainakin minulle. Nyt sitte joukolla koodaamaan reaaliaikanaksuja. :)
Kysymys kuuluu, olisiko mahdollisten suuntien läpikäyntiin voinut käyttää jonkinsortin silmukkaa? (olisi mahdollista, jolloin koodi selkeytysi ja lyhenisi)
Nythän jokainen "seuraava siirto" on syötetty käsin, ja tulos näyttää melkeinpä kaamealta.
====
Seuraavaksi koodivinkkiä käyttäneet voisivat tehdä version, jossa maastossa on eri nopeuksisia maastoja, sekä seiniä joihin ei voi astua.
Muutoksia ei tarvitse tehdä paljoa.
Muuten tämä koodivinkki opastaa erittäin hyvin reitinhaun periaatteisiin.
Eikös tämä olisi helpompi toteuttaa rekursiolla?
lainaus:
Kysymys kuuluu, olisiko mahdollisten suuntien läpikäyntiin voinut käyttää jonkinsortin silmukkaa? (olisi mahdollista, jolloin koodi selkeytysi ja lyhenisi)
Hyvin totta ja teinkin heti muutoksen alkioiden merkkaamiseen. Lopullisten reittialkioiden etsimiseen en kuitenkaan keksinyt mitään selkeämpää tapaa, sillä alkiot pitää etsi siten, että ensin tarkistetaan pysty- ja vaakasuunnassa olevat ja sitten vinoittain, jotta reitin visuaalisuus pysyisi hyvänä.
Tein tämän alunperin kuusisuuntaiselle liikkumiselle, joten siinä silmukan käyttö olisi ollut hieman kyseenalaista. Sitten tein tämän melkein suoraan edellämainitun pohjalta.
Kuvauksen perusteella sanoisin, että tämä on Dijkstran algoritmi. A* on tätä kehittyneempi idea.
lainaus:
Kuvauksen perusteella sanoisin, että tämä on Dijkstran algoritmi. A* on tätä kehittyneempi idea.
Ei tämä ole edes djikstra vaan perus BFS (Breadth-First search, leveyshaku), jossa on lisäksi aika tehoton tapa etsiä tällä hetkellä reunassa olevat solmut. Ehdottaisin, että kullakin kierroksella merkattujen solmujen indeksit laitettaisiin vaikka taulukkoon ja sitten seuraavalla kierroksella käytäisiin vain tämä taulukko läpi ja luotaisiin uusista reunasolmuista toinen taulukko.
Djikstraa tarvitaan muuten vasta sitten, kun polkujen väliset painoarvot vaihtelevat.
teinpä huvikseni ja c++ harjotukseksi poluetsintä sydeemin jossa poluilla on painoarvot ja ukko osaa kävellä vinottain (painoarvo * 1,4) :P
nyt selkeyden vuoksi olen käyttänyt näköään 9? filua, jos vaikka laittais kaikki yhteen, komentois ja laittaisi tänne :)
Tein tälläisen pythonilla. Pistän tähän kommentiks ku sitä ei näköjää hyväksytty koodivinkiks eli: http://tauri.nikkeli.net/~kimble/route/
ohje testaamiseen:
http://tauri.nikkeli.net/~kimble/route/ohje
Aihe on jo aika vanha, joten et voi enää vastata siihen.