Dark Voice Posted December 13, 2011 Report Share Posted December 13, 2011 (edited) Predstavljam vam svoju master tezu. Radi se o 2D RTS engine-u napisanom from the scratch za Java 7 platformu. Naglasak je na jednom primeru pathfinding-a za strateske igre (ili slicne interaktivne sisteme). Kao sto se moze videti, engine je napisan sa mogucnoscu render-ovanja Starcraft multimedijalnih resursa. Resenje je hibridno. Zasnovano je na tzv. potencijalnim poljima, odnosno kontinualnom modelu, uz niz optimizacija (odnosno pojednostavljenja) da bi ono bilo primenljivo na interaktivne sisteme (RTS igre), izvrsivo samo na CPU-u i izvodljivo na Java-i. Motivaciju sam dobio iz http://www.youtube.com/watch?v=jA2epda-RkM. Sam kontinualni model je definisan ovde i to za sasvim drugu primenu - za crowd simulation. Poenta cele price je da se za zadani cilj, za ceo prostor generise potencijalno polje realnih vrednosti koje obrazuju opadajuci gradijent do samog cilja u kome je vrednost 0. Jedinice iz bilo koje tacke u prostoru mogu da odrede optimalnu putanju do cilja prateci opadajuce vrednosti potencijalnog polja i ne moraju imati fiksnu putanju ka cilju odredjenu nekom pretragom (kao sto je A* algoritam). Dinamicke prepreke (ostale jedinice i sl.) mogu da projektuju porast vrednosti potencijalnog polja sto prouzrokuje njihovo izbegavanje. U fizickom smislu, potencijalno polje je skalarna vremenska slika monotono sireceg talasa koji se siri iz ciljne tacke u prostoru, sto je definisano eikonal jednacinom. Potencijalno polje je u svakoj tacki jednako vremenskom trenutku u kome je talasni front dostigao tu tacku. Za numericku diskretizaciju eikonal jednacine koristi se upwind sema, a za sinlge-threaded procesorsku konstrukciju potencijalnog polja fast marching metoda. Za razresavanje kolizije korisitio sam pojednostavljeni flocking mehanizam. Nisam previse eksperimentisao sa razlicitim kolizionim radijusima, ali sam primetio izvesne probleme ako su oni dovoljno veliki (jer kolizioni mehanizam nije dovoljno sofisticiran). Ogromna prednost primene potencijalnih polja je cinjenica da jedinice ne moraju posedovati unapred isplaniranu putanju do cilja, vec planiraju samo jedan korak unapred, te pri otkrivanju kolizije ne moraju da skupo odredjuju alternativnu putanju. Mana je naravno hardverska zahtevnost, jer proracunavanje vrednosti potencijala za svako polje u grid-u nije nimalo naivno. Implementacija broji blizu 200 klasa (odnosno interfejsa). Kod sebe imam AMD Athlon X2 6000+ CPU. Proces zauzima do 500MB RAM-a i trpi do 1500 jedinica na mrezi rezolucije 512x512 sa 30+ fps. Konstrukcija potencijalnog polja traje oko 100ms. AMD je sa Radeon HD4xxx serijom predstavio GPGPU optimizovanu implementaciju za crowd simulation probleme, sto svakao planiram da istrazim, ali onda cela prica ide na odgovarajucu C++ platformu (gde joj je i mesto). Edited September 15, 2012 by Death Egg 2 Quote MSc Link to comment Share on other sites More sharing options...
voodoo_ Posted December 13, 2011 Report Share Posted December 13, 2011 Bogami alal vera! Quote Link to comment Share on other sites More sharing options...
cali Posted December 13, 2011 Report Share Posted December 13, 2011 Impresivno, svaka čast! Quote Link to comment Share on other sites More sharing options...
GOd Posted December 13, 2011 Report Share Posted December 13, 2011 Gz matori sabio si. Quote Link to comment Share on other sites More sharing options...
Sa1Nt Posted December 13, 2011 Report Share Posted December 13, 2011 gotivno! Quote Link to comment Share on other sites More sharing options...
ZerBah Posted December 13, 2011 Report Share Posted December 13, 2011 Izgleda do jaja, pogotovo ovo pred kraj gde si pustio zergling swarm :P Quote А в чем сила, брат? Link to comment Share on other sites More sharing options...
reiser Posted December 13, 2011 Report Share Posted December 13, 2011 svaka cast :) Quote Link to comment Share on other sites More sharing options...
Dark Voice Posted December 14, 2011 Author Report Share Posted December 14, 2011 Zahvaljujem na komplimentima. Quote MSc Link to comment Share on other sites More sharing options...
BarcaS take 2 Posted December 14, 2011 Report Share Posted December 14, 2011 Kakav cheat - ne moze toliko jedinica da se zaokruzi u scu! :D Salu na stranu - izvrsno! :))) A+? Quote https://www.g2a.com/r/barcas Link to comment Share on other sites More sharing options...
Lucky Posted December 14, 2011 Report Share Posted December 14, 2011 Stvarno svaka čast. Quote Link to comment Share on other sites More sharing options...
Trooper Posted December 14, 2011 Report Share Posted December 14, 2011 vrh! daj malo tehnickih detalja :) ako dobro vidim radi pathfinding i za dinamicke prepreke (ie. ostale jedinice na terenu). Koje algoritme si koristio, kako radis collision detection, koja su ogranicejna (jesi probao neke stress testove sa brdom jedinica), etc Quote Link to comment Share on other sites More sharing options...
StormScion Posted December 14, 2011 Report Share Posted December 14, 2011 kako utice velicina samih jedinica ? Recimo 6 puta veca jedinica nego ostale da li ima isti pathing kao najmanja jedinica ? Quote Is the destiny of mankind controlled by some transcendental entity or law? Is it like the Hand of God hovering above? At least it is true that man has no control, even over his own will Link to comment Share on other sites More sharing options...
Dark Voice Posted December 14, 2011 Author Report Share Posted December 14, 2011 (edited) Resenje je hibridno. Zasnovano je na tzv. potencijalnim poljima, odnosno kontinualnom modelu, uz niz optimizacija (odnosno pojednostavljenja) da bi ono bilo primenljivo na interaktivne sisteme (RTS igre), izvrsivo samo na CPU-u i izvodljivo na Java-i. Motivaciju sam dobio iz Supreme Commander 2 pathfinding-a. Sam kontinualni model je definisan ovde i to za sasvim drugu primenu - za crowd simulation. Poenta cele price je da se za zadani cilj, za ceo prostor generise potencijalno polje realnih vrednosti koje obrazuju opadajuci gradijent do samog cilja u kome je vrednost 0. Jedinice iz bilo koje tacke u prostoru mogu da odrede optimalnu putanju do cilja prateci opadajuce vrednosti potencijalnog polja i ne moraju imati fiksnu putanju ka cilju odredjenu nekom pretragom (kao sto je A* algoritam). Dinamicke prepreke (ostale jedinice i sl.) mogu da projektuju porast vrednosti potencijalnog polja sto prouzrokuje njihovo izbegavanje. U fizickom smislu, potencijalno polje je skalarna vremenska slika monotono sireceg talasa koji se siri iz ciljne tacke u prostoru, sto je definisano eikonal jednacinom. Potencijalno polje je u svakoj tacki jednako vremenskom trenutku u kome je talasni front dostigao tu tacku. Za numericku diskretizaciju eikonal jednacine koristi se upwind sema, a za sinlge-threaded procesorsku konstrukciju potencijalnog polja fast marching metoda. Za razresavanje kolizije korisitio sam pojednostavljeni flocking mehanizam. Nisam previse eksperimentisao sa razlicitim kolizionim radijusima, ali sam primetio izvesne probleme ako su oni dovoljno veliki (jer kolizioni mehanizam nije dovoljno sofisticiran). Ogromna prednost primene potencijalnih polja je cinjenica da jedinice ne moraju posedovati unapred isplaniranu putanju do cilja, vec planiraju samo jedan korak unapred, te pri otkrivanju kolizije ne moraju da skupo odredjuju alternativnu putanju. Mana je naravno hardverska zahtevnost, jer proracunavanje vrednosti potencijala za svako polje u grid-u nije nimalo naivno. Implementacija broji blizu 200 klasa (odnosno interfejsa). Kod sebe imam AMD Athlon X2 6000+ CPU. Proces zauzima do 500MB RAM-a i trpi do 1500 jedinica na mrezi rezolucije 512x512 sa 30+ fps. Konstrukcija potencijalnog polja traje oko 100ms. AMD je sa Radeon HD4xxx serijom predstavio GPGPU optimizovanu implementaciju za crowd simulation probleme, sto svakao planiram da istrazim, ali onda cela prica ide na odgovarajucu C++ platformu (gde joj je i mesto). Edited December 15, 2011 by Death Egg 1 Quote MSc Link to comment Share on other sites More sharing options...
Shekk Posted December 14, 2011 Report Share Posted December 14, 2011 Svaka čast. Quote jebote, smorio si sa kukanjem vise :D Link to comment Share on other sites More sharing options...
koshuta Posted December 16, 2011 Report Share Posted December 16, 2011 Stvarno Milose, svaka cast. Bas si masterovao . Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.