Finne raskeste vegen fra A til B på et 2D-kart?

[elbeem]

Hei!

 

Jeg driver med et program som skal finne den raskeste vegen mellom to punkter på et kart. Kartet er svart-hvitt og ligner på et høydekart, bare at fargene angir farten man kan ha der. Altså: Der det er helt svart på kartet er farten lik 0 km/t, og der det er hvitt er farten 100 km/t.

 

Oppgaven: Lag en rute som viser den raskeste vegen man kan ta mellom de to punktene.

 

Jeg har prøvd å søkt på Google etter en algoritme for å løse oppgaven, men jeg vet ikke hva jeg skal søke etter. Vet dere om en algoritme man kan bruke?

[-kristoffer-]

Du kan nok bruke en variant av Dijkstras algoritme

[Mr.Garibaldi]

A* (A star) er en meget effektiv måte å håndtere pathfinding på.

Bruk gråtoneverdien som vekt mellom nodene (f.eks hver 4 pixel er en node (hver pixel vil bli ekstremt tungt)).

 

Ta en tur på biblioteket og lån deg "AI for Game Developers" av O'Reilly. Den har meget gode forklaringer av enkle path-finding algoritmer, samt lett forståelig forklaring av A*.

 

[EDIT]

Hvis du skal kjøre det hele offline, så kan du godt ha hver pixel som en node. Du må bare definere hvilke overganger mellom nodene du skal godta (hver side, eller også på skrå?), så skulle A* passe perfekt

[/EDIT]

Endret 28. februar 2008 av Mr.Garibaldi

[elbeem]

Takker. Skal prøve å lage en implementering av A*.

[Mr.Garibaldi]

Lykke til, det er ganske morsomt

[elbeem]

Ser dette riktig ut? Den eneste feilen (eller mangelen) som er, er at man har kun 8 vinkler å velge mellom. Altså opp, ned, venstre, høyre og på skrå. Jeg skal prøve å få det slik at man kan gå i flere retninger.

[hishadow]

Ser dette riktig ut? Den eneste feilen (eller mangelen) som er, er at man har kun 8 vinkler å velge mellom. Altså opp, ned, venstre, høyre og på skrå. Jeg skal prøve å få det slik at man kan gå i flere retninger.

Tenker du på hva slags metode du bruke for å følge stien?

[elbeem]

Ja, det var det jeg mente. Når programmet lager stien, har det bare 8 himmelretninger å velge mellom, og da får man stier som ikke er optimale om man går de opp i virkeligheten. Hvis du ser på kartet der det er helt hvitt, så ser du at stien går først rett nordover, for deretter å skifte retning til nordøst. I virkeligheten hadde det vært raskere å gå i en retning mellom nord og nordøst.

[hishadow]

Virker som du kanskje har noe feil i søke-algoritmen din når alle naboer har samme vekt?

[elbeem]

Hva mener du med det? Jeg tror ikke det er noe feil med programmet. Det er bare det at programmet kan bare velge mellom 8 retninger, og da blir det den samme avstanden å gå først rett opp, og så nordøst, eller å gå nord-nord-øst. Det blir akkurat like mange piksler. Jeg må lage det slik at hver node er koblet til mer enn 8 andre noder, og så regne avstanden med pytagoras. F.eks. kan noden (10, 10) være koblet til bl.a. (11, 12) selv om de ikke er ved siden av hverandre. Da blir avstanden sqrt(1^2+2^2) = 2,236. Hvis jeg skulle regnet den avstanden når hver node har kun 8 naboer, ville avstanden blitt ca. 1.414 + 1 = 2.414. Tror du dette går?

Endret 2. mars 2008 av elbeem

[Mr.Garibaldi]

Hva mener du med det? Jeg tror ikke det er noe feil med programmet. Det er bare det at programmet kan bare velge mellom 8 retninger, og da blir det den samme avstanden å gå først rett opp, og så nordøst, eller å gå nord-nord-øst. Det blir akkurat like mange piksler. Jeg må lage det slik at hver node er koblet til mer enn 8 andre noder, og så regne avstanden med pytagoras. F.eks. kan noden (10, 10) være koblet til bl.a. (11, 12) selv om de ikke er ved siden av hverandre. Da blir avstanden sqrt(1^2+2^2) = 2,236. Hvis jeg skulle regnet den avstanden når hver node har kun 8 naboer, ville avstanden blitt ca. 1.414 + 1 = 2.414. Tror du dette går?

 

Det er ikke noe problem å ha mer enn 8 retninger, det kommer bare an på hvordan du definerer dem.

Tenk på det som en urettet graf, og ikke som ett 2D bilde, så er det lettere å visualisere/implementere det.