Jeg holder på å skrive en stifinner-algoritme til et dataspill. Først litt kort om spillet: Man starter på et flatt område og skal bevege seg fra start til mål. Motstanderne skal plassere hindringer på banen, slik at det er vanskeligst mulig å komme seg til mål; litt som en labyrint.
Det skal ikke være mulig å ødelegge hindringene, og derfor trenger jeg åpenbart en algoritme som kan sjekke at det finnes en gyldig vei fra start til mål, ellers kan jo motstanderen bare mure igjen målområdet, og vinne spillet.
Jeg har lenge lett etter effektive måter å gjøre dette på, uten særlig hell. Det skal skje i realtid, så det kan nesten ikke være en veldig tung algoritme.
Det eneste jeg har klart å komme opp med selv er å sjekke hver celle på brettet, og se om den er ledig eller blokkert (av en hindring). Da får jeg et rutenett med alle de tilgjengelige cellene, og kan starte en kjempelang "loop" for å se start-cellen er i kontakt med mål-cellen. Denne loopen er veldig tung å kjøre, ettersom den må sjekke absolutt alle mulige veier gjennom labyrinten.
Det jeg leter etter er altså bare ren logikk for hvordan dette kan fungere mest effektivt. Det blir ekstra komplisert av at spillet er i 3D, og man kan hoppe opp på hindringer som er lave nok, og deretter klatre over hindringer som er ett hakk høyere enn det igjen.
Er det noen som har noen tips?
Her er et dataspill som har det jeg leter etter; du kan plassere tårn på spillbrettet, og monstrene som kommer finner av seg selv raskeste vei gjennom hindringene - og du kan ikke blokkere målområdet.
Det skal ikke være mulig å ødelegge hindringene, og derfor trenger jeg åpenbart en algoritme som kan sjekke at det finnes en gyldig vei fra start til mål, ellers kan jo motstanderen bare mure igjen målområdet, og vinne spillet.
Jeg har lenge lett etter effektive måter å gjøre dette på, uten særlig hell. Det skal skje i realtid, så det kan nesten ikke være en veldig tung algoritme.
Det eneste jeg har klart å komme opp med selv er å sjekke hver celle på brettet, og se om den er ledig eller blokkert (av en hindring). Da får jeg et rutenett med alle de tilgjengelige cellene, og kan starte en kjempelang "loop" for å se start-cellen er i kontakt med mål-cellen. Denne loopen er veldig tung å kjøre, ettersom den må sjekke absolutt alle mulige veier gjennom labyrinten.
Det jeg leter etter er altså bare ren logikk for hvordan dette kan fungere mest effektivt. Det blir ekstra komplisert av at spillet er i 3D, og man kan hoppe opp på hindringer som er lave nok, og deretter klatre over hindringer som er ett hakk høyere enn det igjen.
Er det noen som har noen tips?
Her er et dataspill som har det jeg leter etter; du kan plassere tårn på spillbrettet, og monstrene som kommer finner av seg selv raskeste vei gjennom hindringene - og du kan ikke blokkere målområdet.
