[PHP] Spelmap maken

[Hans1990]

Hey,

Ik ben sindskort bezig met een spel. Het is een adventure spel, en dat kan niet worden gespeelt zonder map. Een aangezien me kennis niet erg veel verder is ontwikkelt dan PHP ben ik wel verplicht voor mezelf om PHP te gebruiken.

Nouja, laten we ter zake komen. Wat ik dus wil is een spelmap maken. Waar je dus ook in kan lopen en kan zien waar andere spelers zijn. Nu is het maken van een map, dus dat je alle objecten ziet niet zo moeilijk. Maar dat je kan lopen kom ik echt niet uit. Nu heb ik ook niet echt het gevoel dat mijn map systeem erg perfect is en dus zoek ik naar een oplossing.

Nu doe ik het nogal onhandig, ik heb nu een ini file (als test) waar ik alle textures (lees: image) heb en daarachter cordinaten zet. Dus bv:

code:

[background]
gras=1:1:10:10

Dan zal de vakje's 1,1 tot en met 10,10 (een vierkant dus) opgevult moeten worden met gras. Nou, als je dat met een gehele wereld map doet is het niet meer zo snel (ik heb nu een test gemaakt, die komt al op 0,1 seconden uit met een map van 30x30 vakje's. Vrij traag dus ).

Nu zoek ik dus een oplossing voor een map maken wat een beetje snel is en dat ook efficient werkt. Dus dat alleen de dingen genereert die wat je ziet.

En dan ook nog het lopen, dus dat je op een ander vakje klikt en je daar naartoe gaat. Opzich is dat simpel, een kwestie van de speler cordinaten wijzigen. Maar nu moet het wel bugvrij zijn, dus dat je niet zomaar kan afsnijden als er bijvoorbeeld een grote muur staat waar je niet omheen kan. Dus moet ik iets maken wat uitpuzzelt of de speler daar wel kan komen.

Ik heb ooit iets gehoort dat je vakje voor vakje het script verder moest laten gaan, elke kant op. En vanaf die kant weer vakje voor vakje verder totdat het punt is bereikt. Lukt het niet vanwege muren oid kan je er niet komen. Maar nu heb ik dus in godsnaam geen id hoe je dat moet scripten, en ook hoe je het snel kan doen (qua parse tijden).

Nu hoef ik geen kant en klare codes. Alleen duidelijke uitleg met eventueel kleine voorbeeldje's hoe je dit zal kunnen oplossen.

Hopelijk kan iemand me helpen, anders kan ik nu al stoppen.

[ Voor 7% gewijzigd door Hans1990 op 01-08-2004 19:46 ]

[GlowMouse]

Hans1990 schreef op 01 augustus 2004 @ 19:42:
Ik heb ooit iets gehoort dat je vakje voor vakje het script verder moest laten gaan, elke kant op. En vanaf die kant weer vakje voor vakje verder totdat het punt is bereikt. Lukt het niet vanwege muren oid kan je er niet komen. Maar nu heb ik dus in godsnaam geen id hoe je dat moet scripten, en ook hoe je het snel kan doen.

x(nieuw)-x(oud)=1 of -1
y(nieuw)-y(oud)=1 of -1
Als je diagonaal mag verplaatsen, is het de ene of de andere mogelijkheid. Als je niet diagonaal mag verplaatsen, is 1 van de 2 nul in plaats van 1 of -1.

[Grijze Vos]

Volgens mij wil hij een kortste pad algoritme van plek 1 naar plek 2. Kheb wel eens een doolhof gemaakt voor school, als je in de source ervan (delphi) geinterreseerd bent, hoor ik het wel.

De ideene eruit zijn aardig eenvoudig.

[edit]

Omdat ik in een goeie bui ben, een aanzet voor je.

Je hebt je multidimensioneel array, ik raad je aan om een class te maken voor Hokje. Elk hokje krijgt properties, coordinaten (eventueel, zou je ook buiten het hokje om kunnen laten doen, maar tis netter als het object het zelf ook weet). Dan soort grond, gras, muur, whatever. Dan moet je een functie hebben die zegt of je erover kan lopen of niet, das natuurlijk afhankelijk van de soort grond van het hokje.

En dan moet je even kijken naar die doolhof executable, en het hand to wall algoritme bekijken, evt googlen.

[ Voor 51% gewijzigd door Grijze Vos op 01-08-2004 19:57 ]

[Johnny]

Watvoor manier gebruik je nu dan precies, heb je code of een online voorbeeld?

Wat je zou kunnen doen is iedere omgeving/vakje een aantal eigenschappen geven, je gefet bijvoorbeeld omgeving 1-1 de eigenschap (regels) dat er naar 1-2 en 2-1 mag worden gegaan, en geen enkele andere, die vakjes geef je dan weer andere eigenschappen waardoor je niet zomaar van ieder vakje overal heen kan gaan.

[Grijze Vos]

Johnny schreef op 01 augustus 2004 @ 19:56:
Watvoor manier gebruik je nu dan precies, heb je code of een online voorbeeld?

Wat je zou kunnen doen is iedere omgeving/vakje een aantal eigenschappen geven, je gefet bijvoorbeeld omgeving 1-1 de eigenschap (regels) dat er naar 1-2 en 2-1 mag worden gegaan, en geen enkele andere, die vakjes geef je dan weer andere eigenschappen waardoor je niet zomaar van ieder vakje overal heen kan gaan.

Dat is een lelijke methode, naar welke buren je kan gaan hangt af van de properties van die buren, die properties set je dus niet op het huidige blokje.

Verder bedoelt ie volgens mij dat ie wil dat je ergens random klikt, en dat het poppetje dan erheen gaat lopen..

[Hans1990]

Nouja, ik heb hier een voorbeeld met wat bv niet mag:



Je mag dan dus niet naar de middelste lopen en het dus de bedoeling dat je meerdere tiles tegelijk kan verplaatsen zodat het lopen een beetje makkelijk en snel blijft. Enneh Grijze Vos, ik ben wel geinterreseerd in je code van delphi. Alhoewel ik de taal niet ken kan ik vast wel ontcijferen wat je doet. Als je me pb't kan ik je MSN geven als je zo wilt communiceren.

[Soultaker]

Grijze Vos schreef op 01 augustus 2004 @ 19:53:
En dan moet je even kijken naar die doolhof executable, en het hand to wall algoritme bekijken, evt googlen.

Die hand-to-wall-methode werkt uitsluitend als het begin en eindpunt aan dezelfde muur liggen. Als je begin- en eindpunt niet per se in de hoek hoeven liggen (zoals jouw programma) dan is het niet gegarandeerd dat je een oplossing vindt. (Overigens werkt het algoritme ook alleen in 2D: ik heb 'm op het drielandenpunt proberen toe te passen op dat doolhof daar maar dat werkte niet omdat er bruggen in voor kwamen, waar je zoveel overheen als onderdoor kan).

Van die least visited methode ben ik niet helemaal zeker of 'ie werkt. Ik zie er in ieder geval niet echt een voordeel in; hij produceert aanzienlijk slechtere oplossingen dan een simpel flooding algoritme en gebruik grofweg evenveel geheugen.

[Soultaker]

Hans1990 schreef op 01 augustus 2004 @ 20:06:
Nouja, ik heb hier een voorbeeld met wat bv niet mag:

[afbeelding]

Daarvoor is het nuttig om een pathfinding algoritme te gebruiken om te bepalen uit welke afgescheiden delen de kaart bestaat. Een aardige inleiding staat wel op AI Depot: Beginners Guide to Pathfinding Algorithms. De tutorial gaat uit van een willekeurige graaf, wat wat algemener is dan jouw kaart met vierkantjes, maar de principes zijn even goed toepasbaar. Eventueel wil ik wel het een en ander toelichten als het niet duidelijk is.

Overigens hoef je per kaart maar een keer elk vakje aan een groep te koppelen en kun je daarna direct zien of twee vakjes in verschillende groepen zitten en dus niet verbonden zijn.

[Grijze Vos]

Je kunt ook een DFS of een BFS gebruiken uiteraard. Doolhofje mochten we zelf kiezen wat we implementeerden, en ik had niet bijster veel zin en tijd. Maar ik denk dat TS wel wat heeft aan de opzet van de klassen.

Overigens lijken me niet-bereikbare plekken in een RPG nogal zinloos, TS.

edit:
hmz, die source is onvindbaar. Sorry.

[ Voor 30% gewijzigd door Grijze Vos op 01-08-2004 20:24 ]

[Verwijderd]

Voor de representatie van je map lijkt een klassiek "tiles-palet" me een goede oplossing. Je hebt dan een verzameling tiles die aangegeven worden met een nummer, bijvoorbeeld 0=water, 1=gras, 2=zand, 3=boom, 4=muur, etc. Om de kaart te beschrijven gebruik je dan een matrix, die elke tile op de kaart mapt naar een tile uit de set.

Voor jouw voorbeeld zou je bijvoorbeeld de volgende gegevens krijgen:

code:

00000000000000000
01111111111111110
01111111111111110
01133333333333110
01130000000003110
...etc...

Als je dit niet fijn vindt ontwerpen, kun je altijd nog een script schrijven dat uit een stel teken-primitieven (zoals rechthoeken, lijnen, vlakken, en meer van dat soort dingen, net zoiets als wat je nu hebt) zo'n map-bestandje genereert.

Als het gaat over "doorloopbaarheid" coderen, heb je een paar keuzes: je kunt ervoor kiezen om de doorloopbaarheid van een vakje aan de tile verbinden. Dat wil zeggen dat je hard instelt dat je door bijvoorbeeld een boom of een muur niet heen kunt lopen. Je kunt dit coderen door regels op te stellen als "door tiles met een nummer hoger dan 1000 kun je niet heenlopen", of "door tiles met een oneven nummer kun je niet heenlopen", of wat dan ook.

Wat je ook kunt doen is de doorloopbaarheid (en eventueel andere eigenschappen) in een aparte "layer" stoppen. Je hebt dan een tweede matrix met dezelfde grootte als de eerste, en op elke positie geef je met een 0 of 1 aan of je wel of niet over dat vakje heen kan lopen. Het voordeel hiervan is dat het feit of je wel of niet over een tile kunt lopen, los staat van hoe de tile eruit ziet. Zo kun je gras maken waar je niet over heen kan lopen (niet echt logisch), of een stukje boom waar je wel doorheen kan lopen (geheime gang!).

Het hangt er maar net van af of je hier nut in ziet of je dat wil gaan doen. Ook andere eigenschappen (bijvoorbeeld, als je op een vakje gaat staan verschijnt er een monster) kun je door middel van extra layers met weinig moeite incoderen.

[ Voor 13% gewijzigd door Verwijderd op 01-08-2004 20:43 ]

[crisp]

voor lemmings heb ik precies de opzet die OneOfBorg beschrijft genomen. Nu zijn lemmings ook weinig intelligent, dus dat is ook wel weer makkelijk want je hoeft geen IA in te bouwen
De map staat ook los van het speelveld (wat uiteindelijk gewoon een achtergrondplaatje is).
Het is welliswaar geen PHP maar javascript (dat is voor een interactiegame ook een stuk handiger), maar de source is op mijn site te vinden: http://www.xs4all.nl/~crisp/lemmings/lemmings.zip (dit is de source zonder plaatjes of muziek ivm copyrights)

[Hans1990]

Grijze Vos schreef op 01 augustus 2004 @ 19:53:

Je hebt je multidimensioneel array, ik raad je aan om een class te maken voor Hokje. Elk hokje krijgt properties, coordinaten (eventueel, zou je ook buiten het hokje om kunnen laten doen, maar tis netter als het object het zelf ook weet). Dan soort grond, gras, muur, whatever. Dan moet je een functie hebben die zegt of je erover kan lopen of niet, das natuurlijk afhankelijk van de soort grond van het hokje.

Ehm, bedoel je een class maken voor elk hokje ? Dan krijg je volgens mij erg veel classes (volgens mij over de 20K want de map word niet erg klein, gaat PHP niet erg fijn vinden).

Nu vraag ik me dus nog steeds af hoe ik het beste de data kan opslaan. Ik weet uit ervaring dat serialize niet erg snel is, maar in ini files kan je ook niet alles kwijt. En in MySQL lijkt me ook niet erg verstandig. En het verandert niet erg vaak, dus lijkt het me een beetje overbodig

[Apache]

In een database opslaan lijkt me vrij nuttig, als je nog wat meta info erbij wilt gaat dat ook erg praktisch en als je het goed aapakt kunt je stukken map met een query ophalen en ook joinen op een tabel met bijvoorbeeld de huidige spelers met hun posities.

[flashin]

Hans1990 schreef op 01 augustus 2004 @ 21:47:
[...]


Ehm, bedoel je een class maken voor elk hokje ? Dan krijg je volgens mij erg veel classes (volgens mij over de 20K want de map word niet erg klein, gaat PHP niet erg fijn vinden).

Nu vraag ik me dus nog steeds af hoe ik het beste de data kan opslaan. Ik weet uit ervaring dat serialize niet erg snel is, maar in ini files kan je ook niet alles kwijt. En in MySQL lijkt me ook niet erg verstandig. En het verandert niet erg vaak, dus lijkt het me een beetje overbodig

Hij heeft het over je klasse "hokje" instantieren.

Hoezo lijkt MySQL niet verstandig? Heb je voor dit spel maar een hostje van 100mb waarvan in de av staat dat je maar zoveel cpu-power mag gebruiken ofzo? Als je een webbased game wilt maken, zul je altijd goede hosting nodig hebben en hoge parsetimes. Sponsoring gaat vaak ook makkelijk als je game ambities heeft

edit:
ook nog wat voor opslag: xml

[ Voor 4% gewijzigd door flashin op 02-08-2004 00:14 ]

[Soultaker]

Grijze Vos schreef op 01 augustus 2004 @ 20:13:
Overigens lijken me niet-bereikbare plekken in een RPG nogal zinloos, TS.

Niet als je je op een andere manier ook kunt transporteren, bijvoorbeeld door te vliegen of te teleporteren.

Dat is trouwens ook relevant in deze situatie:

Verwijderd schreef op 01 augustus 2004 @ 20:42:
Wat je ook kunt doen is de doorloopbaarheid (en eventueel andere eigenschappen) in een aparte "layer" stoppen. Je hebt dan een tweede matrix met dezelfde grootte als de eerste, en op elke positie geef je met een 0 of 1 aan of je wel of niet over dat vakje heen kan lopen. Het voordeel hiervan is dat het feit of je wel of niet over een tile kunt lopen, los staat van hoe de tile eruit ziet. Zo kun je gras maken waar je niet over heen kan lopen (niet echt logisch), of een stukje boom waar je wel doorheen kan lopen (geheime gang!).

Als je kunt teleporteren, is het wel prettig als je bepaalde delen af kunt schermen. Het biedt sowieso wel voordelen om hoe een vakje werkt (of je er wel of niet door heen kunt lopen, bijvoorbeeld) te scheiden van hoe een vakje er uit ziet, wat een heel ander aspect van een vakje is.

off-topic:

crisp schreef op 01 augustus 2004 @ 20:49:
voor lemmings heb ik precies de opzet die OneOfBorg beschrijft genomen. [..]
De map staat ook los van het speelveld (wat uiteindelijk gewoon een achtergrondplaatje is).

Hoe kreeg je het eigenlijk voor elkaar om gaten te maken in de voorgrond? (Als er een digger of een explosie langskomt, bijvoorbeeld).

[ Voor 18% gewijzigd door Soultaker op 02-08-2004 00:19 ]

[Soultaker]

flashin schreef op 02 augustus 2004 @ 00:13:
Hoezo lijkt MySQL niet verstandig?

Het is niet altijd zinnig om in principe statische data in een database te stoppen. Sowieso kan een database als MySQL vrij weinig met het soort informatie dat de TS wil opslaan. Het enige waar je MySQL dan nog voor kunt gebruiken is je mapgegevens elke keer uitlezen maar dan moet je ze nog steeds converteren naar een voor PHP handig formaat. Dan kun je ze naar mijn mening net zo goed van/uit een bestand serializen (in welk formaat dan ook).

[coubertin119]

Hans1990 schreef op 01 augustus 2004 @ 21:47:
[...]


Ehm, bedoel je een class maken voor elk hokje ? Dan krijg je volgens mij erg veel classes (volgens mij over de 20K want de map word niet erg klein, gaat PHP niet erg fijn vinden).

Nu vraag ik me dus nog steeds af hoe ik het beste de data kan opslaan. Ik weet uit ervaring dat serialize niet erg snel is, maar in ini files kan je ook niet alles kwijt. En in MySQL lijkt me ook niet erg verstandig. En het verandert niet erg vaak, dus lijkt het me een beetje overbodig

1 class, 20000 instanties. Die class heeft dan alle properties die een hokje nodig heeft, informatie over de locatie, over het uitzicht, over de behaviour. Heb je al ooit met objecten gewerkt in PHP?

[Verwijderd]

Hoewel object-georiënteerd natuurlijk heel mooi is, vraag ik me af of dat hier niet te geheugenintensief wordt (en traag, vergeet niet dat je bij elke pagina-aanroep alle gegevens opnieuw moet instantiëren en ook weer weggooien). Een paar multidimensionale integer-arrays doen het net zo goed, maar zijn sneller.

Bovendien is een DBMS net wel goed, om conflicten te voorkomen als meerdere clients tegelijk gegevens aan het wijzigen zijn, en om informatie te cachen en die zo sneller op te kunnen hoesten.

[Hans1990]

coubertin119 schreef op 02 augustus 2004 @ 09:28:
[...]
1 class, 20000 instanties. Die class heeft dan alle properties die een hokje nodig heeft, informatie over de locatie, over het uitzicht, over de behaviour. Heb je al ooit met objecten gewerkt in PHP?

Jawel, maar met objecten nog niet erg diepgaande classes (dus dat PHP eerst 5 functie's doorloopt voordat ie echt iets gaat doen ofzo).

Nu het echter wel handig zal zijn begin ik nu dus aan het lopen. Ik heb vannacht een ideetje (in bed nog wel ) uitgedacht maar ik denk dat het nu niet meer echt gaat werken, even me theorie uitleggen:

Ik ben van plan om een soort pinball modus te maken. Het script gaat eerst links en rechts kijken of hij in de zelfde kolom kan kopen van de eind locatie. Kan die dat niet, dan gaat hij de splitsingen op (die hij onderweg heeft gevonden ?) en gaat hij verder met zoeken naar de juiste kolom, als hij die een keer heeft gevonden gaat hij kijken of hij naar beneden of boven moet en gaat die kant op, kan hij dan er niet komen (vanwege een muur oid) gaat hij de andere kant op en zoekt weer op splitsingen (doet ie altijd) ect. Netzolang totdat alle splitsingen op zijn en zal het einddoel wel bereikt moeten zijn.. Maarja, of het werkt weet ik zelf niet (ik denk het wel) maar hoe ik het werkend in een PHP file krijg word wel een dagje proberen, komt eigenlijk op PathFinding Algoritme neer (dankzij die methode dus), maar dan worden de points zelf aangemaakt.

Denken jullie dat dit goed zal werken ? Of weet je iets beters ?

edit:

Ik heb trouwens al wel een array met elke tile en informatie ervan, dus van het object zelf. Dus of je er doorheen kan lopen ect.

[ Voor 6% gewijzigd door Hans1990 op 02-08-2004 11:00 ]

[Verwijderd]

Klinkts als DFS met heuristics.

Het zal best werken. Of het het beste is weet ik niet, en daar durf ik ook niks over te zeggen want ik heb armzalig weinig ervaring met pathfinding algorithms

[Soultaker]

Als je alle vakjes wil indelen in samenhangende gebieden dan maakt het niet uit hoe je zoekt; je bezoekt elk vakje toch exact 1 keer. Ik zou dus voorstellen om de meest eenvoudige manier te kiezen; gewoon depth first search en geen heuristics. Maar ergens heb ik het idee dat de TS helemaal geen ervaring heeft met zoekalgoritmen.

[ Voor 22% gewijzigd door Soultaker op 02-08-2004 15:35 ]

[Grijze Vos]

Hans1990 schreef op 01 augustus 2004 @ 21:47:
[...]


Ehm, bedoel je een class maken voor elk hokje ? Dan krijg je volgens mij erg veel classes (volgens mij over de 20K want de map word niet erg klein, gaat PHP niet erg fijn vinden).

Nee, 1 class die je 20K keer instantieert uiteraard.

[hemaworst]

Hoi!

Wat jij zoekt is een pathfinding routine.
Een hele bekende is a*:
http://www.policyalmanac.org/games/aStarTutorial.htm

Hier een java applet die de theorie laat zien:
http://www.ccg.leeds.ac.uk/james/aStar/

Als je zoekt op A* op google dan komen er zat tutorials en sources

[crisp]

Soultaker schreef op 02 augustus 2004 @ 00:15:
[...]
off-topic:

[...]

Hoe kreeg je het eigenlijk voor elkaar om gaten te maken in de voorgrond? (Als er een digger of een explosie langskomt, bijvoorbeeld).

off-topic
simpel; een zwart plaatje op de voorgrond plaatsen in de vorm van het gat (de rest transparant), maar wel met een lagere z-index als de lemmings zelf