Algoritme om een vrije weg te berekenen

[ChaosZ0ne]

Heren,

Ik ben bezig met mijn eerste Android spelletje.
Het is een soort kloon van Auchtung die Kurve/IPcurve.
Voor degenen die het niet kennen:
Het is een spelletje waar er met constante snelheid een lijn getekend wordt. Deze lijn kan je links en rechts sturen. Tevens zijn er een aantal vijanden, die ook zo lang mogelijk willen leven. Jijzelf(en de vijanden) moeten dus elkaar ontwijken. Als je jezelf of een ander raakt ben je dood.
http://www.achtungdiekurve.net/ is een voorbeeld van het spel in flash.

Ik loop echter vast bij het bedenken van een zo efficient mogelijk algoritme om een van de bot's die er in komen, een juiste weg te laten bedenken. Ik heb al wat methoden geschreven die de bot besturen en een bepaald punt op laten zoeken, maar ik kom niet verder.

Wat heb ik:
-een ArrayList met alle punten er in van de lijn van de gebruiker
-Collisiondetection. Zodra een lijn een ander raakt, zal er een collision-afhandeling plaatsvinden (a.k.a. je bent dood). Dit gebeurt door alle punten van elke lijn met elk punt van een andere lijn te vergelijken.
-Muren. Dit zijn in feite gewoon lijnen, maar zijn statisch. Dit is om het spel wat moeilijker te maken (de muren bevinden zich midden in het speelveld). Ook hier wordt collisiondetection op toegepast.

Waar loop ik op vast:
De vijand wil graag zo lang mogelijk blijven leven. Hiervoor dient hij het beste pad te kiezen. Dit is niet per sé zo ver mogelijk van andere lijnen weg, dit kan ook best langs een andere lijn gaan, om zo bijvoorbeeld op een groot open stuk te komen, waar hij op zijn gemak rondjes kan tekenen.
Echter, om te berekenen wat ófwel de grootste afstand tot een ander is, ófwel een ander uit de weg gaan, als die op hem af komt, is voor mij nogal een grote opgave. Niet enkel omdat mijn ervaring niet erg groot is, maar vooral meer omdat de resources op een android telefoon nogal beperkt zijn.

Ik ben niet direct op zoek naar een volledig werkend algoritme, maar een hint in welke richting ik moet zoeken zou ik erg op prijs stellen.
Overigens werk ik met Android 2.1

[RobIII]

ChaosZ0ne schreef op dinsdag 21 juni 2011 @ 19:57:
Het is een soort kloon van Auchtung die Kurve/IPcurve.
Voor degenen die het niet kennen:
Het is een spelletje waar er met constante snelheid een lijn getekend wordt. Deze lijn kan je links en rechts sturen. Tevens zijn er een aantal vijanden, die ook zo lang mogelijk willen leven. Jijzelf(en de vijanden) moeten dus elkaar ontwijken. Als je jezelf of een ander raakt ben je dood.
http://www.achtungdiekurve.net/ is een voorbeeld van het spel in flash.

Zeg gewoon Tron (clone). Als je die niet kent: ga je schamen!

ChaosZ0ne schreef op dinsdag 21 juni 2011 @ 19:57:
Ik ben niet direct op zoek naar een volledig werkend algoritme, maar een hint in welke richting ik moet zoeken zou ik erg op prijs stellen.

Met de juiste naam ( ) kom je een heel eind [google=tron algorithm] of [google=tron light cycle algorithm]

[Soultaker]

Ha, dat heb ik ook al eens gedaan, maar ik gebruik de naam Zatacka:

• http://hell.student.utwente.nl/gitweb.cgi?p=zatacka;a=tree (source code)
• http://hell.student.utwente.nl/zatacka/ (binaries)

Hier zitten ook al bots bij. Misschien kun je er wat inspiratie uit halen.

RobIII schreef op dinsdag 21 juni 2011 @ 20:51:
Zeg gewoon Tron (clone). Als je die niet kent: ga je schamen!

Tron is ook leuk, maar Zatacka geeft spelers wel fundamenteel méér vrijheid, doordat je vrij kunt draaien, niet aan een grid gebonden bent, je geen ononderbroken spoor achterlaat, en je een beperkte draaicirkel hebt (waardoor je niet per se door elke hoek kunt manouvreren). Tron is aanzienlijk simpeler om een goede AI voor te coden.

In mijn AI doe ik praktisch geen planning; ik doe alleen een vrij ondiepe depth-first search om het pad voor de komende seconde ofzo te plannen. Dat levert al een AI op die sterker is dan de gemidelde menselijke speler. Als het doel is om een AI te maken die leuk is om tegen te spelen, zou ik dus eenvoudig beginnen en 'm dus vooral niet té slim proberen te maken.

[ Voor 14% gewijzigd door Soultaker op 22-06-2011 05:53 ]

[Verwijderd]

Bestaat trouwens al in de market he https://market.android.co...rve&feature=search_result

[ocf81]

Het A* algoritme is voor pathfinding wel redelijk standaard geloof ik.

[ChaosZ0ne]

Ik heb inderdaad nog eens flink zitten zoeken naar algoritmen (bedankt voor die links, Soultaker), maar veelal is het algoritme (zoals het A*) simpelweg te zwaar. We willen namelijk graag dat ook op de wat oudere, tragere devices (denk G1, of Wildfire), het spel nog enigzins speelbaar is.

@altrincham: Klopt, maar die heeft ook geen bots helaas.

[MSalters]

A* traag? Da's onzin; het is een behoorlijk snel algoritme. Tenminste, als je de heuristische functie goed hebt, anders krijg je gewoon Dijkstra.

[Verwijderd]

MSalters schreef op maandag 27 juni 2011 @ 11:11:
A* traag? Da's onzin; het is een behoorlijk snel algoritme. Tenminste, als je de heuristische functie goed hebt, anders krijg je gewoon Dijkstra.

Inderdaad, met wat net programmeerwerk is het best een prima algoritme.

[Brad Pitt]

Verwijderd schreef op vrijdag 24 juni 2011 @ 11:59:
Bestaat trouwens al in de market he https://market.android.co...rve&feature=search_result

Bij deze versie kan je alleen spelen tegen een menselijke tegenstander. No bot to be found

[Janoz]

ChaosZ0ne schreef op zondag 26 juni 2011 @ 16:06:
Ik heb inderdaad nog eens flink zitten zoeken naar algoritmen (bedankt voor die links, Soultaker), maar veelal is het algoritme (zoals het A*) simpelweg te zwaar.

A* is niet echt toepasselijk aangezien we het hier niet echt over een graaf achtig probleem hebben. Spelers bewegen niet echt op een grid en hebben restricties in hun bewegingsvrijheid (minimale draaicircel ed).

Persoonlijk denk ik dat er veel meer winst te halen is uit de manier waarop je alles bijhoudt. Alle getekende punten in een arraylist op slaan vult die lijst behoorlijk. Je kunt beter een wiskundigere benadering zoeken. Het is waarschijnlijk een stuk efficienter om verschillende lijnstukjes met elkaar te vergelijken.

[Soultaker]

ChaosZ0ne schreef op zondag 26 juni 2011 @ 16:06:
Ik heb inderdaad nog eens flink zitten zoeken naar algoritmen (bedankt voor die links, Soultaker), maar veelal is het algoritme (zoals het A*) simpelweg te zwaar.

Zoals ik zei, heb je helemaal geen heel geavanceerde AI nodig om een beetje interessante tegenstander te maken. Mijn bot gebruikt 1-2% CPU ofzo op m'n desktop met een zoekdiepte van 7; dat moet zelfs op een smartphone CPU nog wel te doen zijn.

Janoz schreef op maandag 27 juni 2011 @ 12:07:
Je kunt beter een wiskundigere benadering zoeken. Het is waarschijnlijk een stuk efficienter om verschillende lijnstukjes met elkaar te vergelijken.

Misschien, maar je kunt ook veel lijnstukken krijgen, en het geheel is een stuk lastiger te implementeren. Ik zou gewoon zo simpel mogelijk beginnen. Je kunt het altijd ingewikkelder maken als je eenvoudige aanpak niet volstaat, maar het is jammer als je meteen een aanpak kiest die zo ingewikkeld is dat je er niet uitkomt.

[Janoz]

Ik heb het dan vooral over:

Dit gebeurt door alle punten van elke lijn met elk punt van een andere lijn te vergelijken.

Je hoeft niet alles met alles te vergelijken. Enkel het laatste stukje met alles is genoeg. Daarnaast kun je sneller 2 lijnstukken met elkaar testen dan dat je dat punt voor punt doet.

Uiteraard is het wel wat ingewikkelder.

[ocf81]

A* kan ook worden toegepast door een obstructionmap/graaf te genereren van de hoekpunten van de bounding boxes van obstakels i.c.m. precalculated routing met behulp van vooraf gedefinieerde waypoints. Indien het einde dichter bij je eerste kandidaat waypoint ligt dan bij andere waypoints, skip je de waypoint fase.
Je maakt een obstructionmap/graaf van de situatie naar het dichtsbijzijnde waypoint en van daar ga je over de vooraf berekende route naar het knooppunt wat het dichtst bij de bestemming ligt. vervolgens bereken je de obstruction map voor de route naar het eindpunt vanaf het laatste knooppunt. die map kan ook al gedeeltelijk vooraf worden gegenereerd en ingevuld als er statische objecten in de scene aanwezig zijn. Door het probleem op te delen in delen die kleine afstanden dynamisch doen (duur) en grote afstanden statisch afhandelen (zeer goedkoop) moet het ook op een mobiel nog te doen zijn. je zou knoopunten ook kunnen enablen en disablen om de beschikbaarheid van gebieden dynamisch te maken. Het kost wel wat extra geheugen om de paden van te voren te beschrijven of van flash te laden.

[ Voor 5% gewijzigd door ocf81 op 14-07-2011 13:20 ]

[Verwijderd]

zeg dan ook gewoon niets, je hoeft niet te posten

[ Voor 211% gewijzigd door RobIII op 26-07-2011 01:08 ]

[joppybt]

Er is een Google AI Challange voor Tron Light Cycles (Winter 2010) geweest.
Er is een apart topic waar mensen uitleggen hoe hun bots werken.