• Over
  • Forummenu
    • Forumregels
    (Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
    Zie eerst de Huiswerkbijsluiter
    Reageer
    jorants
    Artikelen: 0
    Berichten: 2
    Lid geworden op: zo 30 nov 2008, 12:31

    Pacman geest --> kortste route graaf

    hey allemaal,

    ik ben de laatste tijd bezig met een remake van pacman. (niet origineel ik weet het maar ik wil oefenen)

    maar ik ben een beetje vast gelopen... ik kan de geesten niet zo ver krijgen naar pacman te bewegen via de kortste route.

    aangezien een pacman level eigenlijk gewoon een raster is waarvan sommige hokjes betreedbaar zijn en sommige niet dacht ik aan een graaf waarin twee grenzende, betreedbare hokjes twee knopen zijn met een lijn er tussen.

    de vraag wordt dus, hoe kom je achter de kortste route tussen twee knopen in een graaf?

    eigenlijk hoef ik niet de hele route te weten, alleen de eerste richting (links, rechts, boven, beneden), want na eerdere loop (berekeningen van posities ect.) verandert de positie van pacman toch weer en moet het opnieuw uitgerekend worden.

    ik kwam op het Dijkstra algoritme maar dat rekenend de afstand naar ieder punt uit en niet de kortste route naar 1 punt.

    kan iemand mij de stappen uitleggen waarop ik simpel weg kom op de eerste lijn van de kortste route naar een punt?

    waarschijnlijk is mijn verhaal helemaal niet te volgen, deels door mijn belabberde taalgebruik, deels doordat het nogal warrig is :D maar als iemand het toch begrijpt en de oplossing weet, ik ben benieuwd ;)

    alvast tanx, joran

    PS: voor wie pacman niet kent: link
    Gebruikersavatar
    jhnbk
    Artikelen: 0
    Berichten: 6.905
    Lid geworden op: za 16 dec 2006, 09:10

    Re: Pacman geest --> kortste route graaf

    Mogelijk vind je hier links naar het juiste algoritme dat je zoekt.
    Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
    Gebruikersavatar
    Raspoetin
    Artikelen: 0
    Berichten: 3.507
    Lid geworden op: wo 28 sep 2005, 15:46

    Re: Pacman geest --> kortste route graaf

    Ik heb er echt totaal geen verstand van, maar het viel me op dat er onlangs ook een topic is geopend over een graaf: http://sciencetalk.nl/forum/index.php?s...71&hl=graaf

    Een week geleden had ik nog nooit van een graaf gehoord (in deze context dan) en nu twee topics binnen een paar dagen. Misschien heb je iets aan de link, of kun je de topicstarter aldaar een bericht sturen. Volgens mij hebben jullie het over twee verschillende typen grafen, maar wie weet vind je daar iets wat je zoekt. Nogmaals, ik weet er echt niks van maar ik wilde je de link naar het andere topic niet onthouden (hoewel je hem met de zoekfunctie ook wel had kunnen vinden).
    I'm not suffering from insanity - I'm enjoying every minute of it!!
    PeterPan
    Artikelen: 0

    Re: Pacman geest --> kortste route graaf

    Ik denk dat je uitkomt zonder zwaar geschut (zoals Dijkstra's algoritme).

    Elk positie kun je weergeven met een paar
    \((x,y)\)
    van natuurlijke getallen.

    Een eerste poging is als volgt:

    Bepaal positie
    \((x,y)\)
    van pacman en positie
    \((x_1,y_1)\)
    van geest 1.

    Ik noem de positie links beneden (1,1).

    Is
    \(y_1>y\)
    en kan de geest naar beneden, verplaats dan de geest 1 naar beneden.

    Is
    \(y_1<y\)
    en kan de geest naar boven, verplaats dan de geest 1 naar boven.

    Is
    \(x_1>x\)
    en kan de geest naar links, verplaats dan de geest 1 naar links.

    Is
    \(x_1<x\)
    en kan de geest naar rechts, verplaats dan de geest 1 naar rechts.

    Dit kan als je wilt nog iets verfijnd worden (indien nodig) door positie
    \((x,y)\)
    te vervangen door het paar
    \((x^1,y^1)\)
    ,
    \((x^2,y^2)\)
    van posities van de uiteinden van het segment waarbinnen pacman zich op dat moment bevindt. De geest gaat richting die positie waarvan de coordinaten het minst verschillen van die van de geest.
    jorants
    Artikelen: 0
    Berichten: 2
    Lid geworden op: zo 30 nov 2008, 12:31

    Re: Pacman geest --> kortste route graaf

    bedankt allemaal, ik heb een oplossing gevonden :D
    Gebruikersavatar
    Rogier
    Artikelen: 0
    Berichten: 5.679
    Lid geworden op: di 27 apr 2004, 13:40

    Re: Pacman geest --> kortste route graaf

    PeterPan schreef:Bepaal positie
    \((x,y)\)
    van pacman en positie
    \((x_1,y_1)\)
    van geest 1.

    Ik noem de positie links beneden (1,1).

    Is
    \(y_1>y\)
    en kan de geest naar beneden, verplaats dan de geest 1 naar beneden.

    Is
    \(y_1<y\)
    en kan de geest naar boven, verplaats dan de geest 1 naar boven.

    Is
    \(x_1>x\)
    en kan de geest naar links, verplaats dan de geest 1 naar links.

    Is
    \(x_1<x\)
    en kan de geest naar rechts, verplaats dan de geest 1 naar rechts.
    Wat zou er gebeuren in de volgende situatie: :D

    Afbeelding
    In theory, there's no difference between theory and practice. In practice, there is.
    PeterPan
    Artikelen: 0

    Re: Pacman geest --> kortste route graaf

    Wat zou er gebeuren in de volgende situatie: :P
    Je kunt Pacman niet op die plek laten. Hij is altijd in beweging.

    Als hij in een beweging naar boven is, gaat de geest ook die kant op en vieze verza. :P :D
    EvilBro
    Artikelen: 0
    Berichten: 7.081
    Lid geworden op: vr 30 dec 2005, 09:45

    Re: Pacman geest --> kortste route graaf

    ls hij in een beweging naar boven is, gaat de geest ook die kant op en vieze verza. :D :P
    En zodra ze dan allebei uit het midden zijn, is de kortste route boven- of onderlangs. Jouw algoritme doet hiet niks mee. Je wijkt dus af van hetgeen de oorspronkelijke poster denkt te willen.

    Dat hoeft op zich natuurlijk geen probleem te zijn, maar bij pac-man is het zo dat de spookjes net iets sneller bewegen dan pac-man. In het voorbeeld van Rogier en jouw algoritme kun je eeuwig blijven leven. Je kan echter nooit alle puntjes te pakken krijgen (die onder het rode spookje zal je nooit te pakken krijgen). Bij de 'kortste weg'-variant zal je uiteindelijk gepakt worden door het spookje, maar is het afhankelijk van de snelheid wel mogelijk om alle punten te krijgen.

    Gezien het geringe aantal punten dat mogelijk is bij pac-man zie ik trouwens weinig problemen met een simpele brute-force aanpak om het korste pad te bepalen.
    Gebruikersavatar
    Rogier
    Artikelen: 0
    Berichten: 5.679
    Lid geworden op: di 27 apr 2004, 13:40

    Re: Pacman geest --> kortste route graaf

    Je kunt Pacman niet op die plek laten. Hij is altijd in beweging.
    Okee zo dan, hij kwam aanlopen van links :D

    Afbeelding
    In theory, there's no difference between theory and practice. In practice, there is.
    PeterPan
    Artikelen: 0

    Re: Pacman geest --> kortste route graaf

    Pacman kan stilstaan, maar de geesten staan nooit stil. Een geest keert nooit terug op zijn schreden.

    Dus als een geest zich b.v. naar boven beweegt, dan vervalt de optie "ga naar beneden", en als ook aan de andere voorwaarden niet is voldaan, zet hij zijn pad voort in de ingeslagen weg.

    Ik heb even pacman gespeeld en gezien dat als je je pacman stilzet, de geesten niet goed meer weten welke weg ze nemen om je aan te vallen. Zie kiezen dan niet telkens de kortste weg.
    Reageer

    Terug naar “Wiskunde”

    Sciencetalk

    Hét onafhankelijke platform voor het delen van wetenschappelijke kennis en informatie

    • info@sciencetalk.nl
    • 0648478721