Springen naar inhoud

Pacman geest --> kortste route graaf


  • Log in om te kunnen reageren

#1

jorants

    jorants


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 15 december 2008 - 22:11

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 15 december 2008 - 22:19

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.

#3

Raspoetin

    Raspoetin


  • >1k berichten
  • 3514 berichten
  • VIP

Geplaatst op 15 december 2008 - 22:29

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://www.wetenscha...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!!

#4

*_gast_PeterPan_*

  • Gast

Geplaatst op 16 december 2008 - 11:05

Ik denk dat je uitkomt zonder zwaar geschut (zoals Dijkstra's algoritme).
Elk positie kun je weergeven met een paar LaTeX van natuurlijke getallen.
Een eerste poging is als volgt:
Bepaal positie LaTeX van pacman en positie LaTeX van geest 1.
Ik noem de positie links beneden (1,1).
Is LaTeX en kan de geest naar beneden, verplaats dan de geest 1 naar beneden.
Is LaTeX en kan de geest naar boven, verplaats dan de geest 1 naar boven.
Is LaTeX en kan de geest naar links, verplaats dan de geest 1 naar links.
Is LaTeX 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 LaTeX te vervangen door het paar LaTeX ,LaTeX 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.

Veranderd door PeterPan, 16 december 2008 - 11:06


#5

jorants

    jorants


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 18 december 2008 - 10:24

bedankt allemaal, ik heb een oplossing gevonden :D

#6

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 18 december 2008 - 12:25

Bepaal positie LaTeX

van pacman en positie LaTeX van geest 1.
Ik noem de positie links beneden (1,1).
Is LaTeX en kan de geest naar beneden, verplaats dan de geest 1 naar beneden.
Is LaTeX en kan de geest naar boven, verplaats dan de geest 1 naar boven.
Is LaTeX en kan de geest naar links, verplaats dan de geest 1 naar links.
Is LaTeX en kan de geest naar rechts, verplaats dan de geest 1 naar rechts.

Wat zou er gebeuren in de volgende situatie: :D
Geplaatste afbeelding
In theory, there's no difference between theory and practice. In practice, there is.

#7

*_gast_PeterPan_*

  • Gast

Geplaatst op 18 december 2008 - 14:18

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

#8

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 18 december 2008 - 14:55

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.

#9

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 18 december 2008 - 15:08

Je kunt Pacman niet op die plek laten. Hij is altijd in beweging.

Okee zo dan, hij kwam aanlopen van links :D
Geplaatste afbeelding
In theory, there's no difference between theory and practice. In practice, there is.

#10

*_gast_PeterPan_*

  • Gast

Geplaatst op 18 december 2008 - 16:14

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures