Vektorer, finne berørte posisjoner

[Gjest]

Hei godtfolk

 

(Ikke noe QT denne gangen, jeg har droppet QT manien min for en liten stund )

 

Driver å koder grunnleggende funksjoner for et top-down 2D spill i C++ og jobber litt med kart og kartgenerering, i den forbindelse lurer jeg på om jeg gjør ting optimalt i møte med følgende problemstilling:

 

Kartet er representert av en todimensjonal vektor "map" (som jeg har typedefinert som TwoDimIntegerVector) og postene her kan ha verdien 0 eller 1 (så langt) hvor 0 er åpen flate og 1 er en vegg. For å tegne korrekt vegg må jeg jo vite hva slags flate gjeldende post har ved siden, over og under. Følgende funksjon gjør dette:

 

wallType OurMap::getAdjecentTiles(int tileXPos, int tileYPos) {
 std::vector<int> adjecent;
 wallType wall;

 adjecent[0] = map[tileXPos][tileYPos--];
 adjecent[1] = map[tileXPos][tileYPos++];
 adjecent[2] = map[tileXPos--][tileYPos];
 adjecent[3] = map[tileXPos++][tileYPos];


 if (adjecent[0] == 0 && adjecent[1] == 0) {
   if (adjecent[2] == 1 && adjecent[3] == 1) {
	wall = vertical;
   }
 }

 return wall;
}

 

Koden over finner jo bare ut om jeg skal tegne en vertikal vegg så langt, jeg har ikke lagt til en sjekk for alle typer:

 

enum wallType { horizontal, vertical, lowerCornerToLeft, lowerCornerToRight, upperCornerToLeft, upperCornerToRight };

 

Så spørsmålet er, finnes det en mer "grasiøs" måte å kode dette på (den if implementeringen blir jo skikkelig spaghetti når den er ferdig) og i så tilfelle hvordan ville du implementert denne løsningen?

 

Koden til hele spillet kan du se på github:

 

https://github.com/f...pheap-Starships

 

Dette er spillet så langt

 

http://www.youtube.com/watch?v=yLXQmv8JK0k

 

Ikke mye å skryte av og de som skulle bidra med ting og tang (grafikk og lyd) har mer eller mindre mistet interessen virker det som. Så jeg kommer antageligvis til å fullføre en plattform hvor jeg kan bruke koden til å lage mitt eget spill etterhvert. Hvis noen har lyst til å hoppe ombord "team vonfaff" og lage et spill, si ifra

[Lycantrophe]

Så spørsmålet er, finnes det en mer "grasiøs" måte å kode dette på (den if implementeringen blir jo skikkelig spaghetti når den er ferdig) og i så tilfelle

Tjah, ville startet med:

 

if (adjecent[0] =! 0 || adjecent[1] != 0)
return wall;
if (adjecent[2] == 1 && adjecent[3] == 1)
return vertical;
return wall;

 

Forøvrig ville jeg renamet funksjonen, den beskriver noe annet enn det den gjør.

 

Det er ingen grunn til å drive med inkrementering av indeksene som du gjør. Spesielt de i den siste linjen der du henter ut koordinater er verdiløs.

 

Jeg ville også vurdert å lagret enumene direkte i map-et, med mindre du har en veldig god grunn til å gjøre det sånn som du gjør nå. Sparer deg mye regning (og kompleksitet!)

 

Siden du alltid sjekker konstant størrelse ville jeg brukt array i stedet for vektor for mellomlagring. Et alternativ er jo å bruke indeksene direkte.

 

Siden verdiene du skal sjekke mot er typiske edge cases (pun intended) ville jeg heller sjekket for disse eksplisitt enn å hente ut fra arrayen din. Siden du vet hvor stort kartet er kan du også regne det frem til hvilke koordinater som vil være hjørner.

 

Men, om jeg hadde måttet bruke stilen din ville gjort noe á

/* corners */
if( x == 0 && y == 0 )
	return lowerCornerToLeft;
if( x == length && y == 0 )
	return lowerCornerToRight;
if( x == 0 && y == height )
	return upperCornerToLeft;
if( x == length && y == height )
	return upperCornerToRight;

if( map[ x ][ y ] != 0 || map[ x ][ y + 1 ] != 0 )
	return horizontal;

return vertical;

Endret 13. mai 2013 av Lycantrophe

[Gjest Gjest slettet-ld9eg7s96q]

Forøvrig ville jeg renamet funksjonen, den beskriver noe annet enn det den gjør.

 

Ja du sier noe, opprinnelig returnerte jeg adjecent, har glemt å rename funksjonen

 

 

Det er ingen grunn til å drive med inkrementering av indeksene som du gjør. Spesielt de i den siste linjen der du henter ut koordinater er verdiløs.

 

Hø? Jeg henter ut verdiene fra fire steder: over, under, høyre og venstre for å vite om jeg skal tegne en vegg med tilknytning til neste vegg, hjørne osv. Hvorfor er koordinatene jeg henter ut i de siste linjene verdiløse?

 

Den første linjen trekker en verdi fra den "ytterste" vektoren, altså den til "venstre", samme med neste bare da inkrementerer jeg så det blir til "høyre" for verdien i vektoren. De to neste linjene gjør det samme bare i den "innerste" vektoren så da flytter jeg indeksen i praksis "over" og "under" og får ut verdiene av disse. Eller gjør jeg det feil her? Hva er feil i så tilfelle?

 

Takker for svar og tips som har vært informativt. Jeg skal leke meg mer rundt med dette

[Lycantrophe]

Koordinatene du henter ut er ikke verdiløse, men det er meningsløst å inkrementere telleren etter du har gjort oppslaget (på den siste verdien). Den brukes jo ikke igjen.

 

Du inkrementerer verdien opp og ned (og inline). Da kan du gjerne spare deg, og alle andre, hodepinen og heller bruke +/- 1, som i eksempelet mitt. Det er ikke feil, det er bare unødvendig.

[Gjest Gjest slettet-ld9eg7s96q]

Derp, jeg skjønner hvor du vil nå. Takker så mye! Ser at jeg får en mye renere kode med metoden din

Endret 13. mai 2013 av Gjest slettet-ld9eg7s96q

[Lycantrophe]

Tror fortsatt det kan lønne seg å lagre enumen rett i map-et.

[Gjest Gjest slettet-ld9eg7s96q]

Mener du f.eks noe ala:

 

typedef std::vector<std::vector<wallType>> map;

 

og så implementere map i OurMap objektet?

Endret 13. mai 2013 av Gjest slettet-ld9eg7s96q

[Lycantrophe]

Jepp. Da slipper du å gjennomføre sjekken i det hele tatt og får enkodet mer informasjon inn på samme plass. Med enum classes i C++11 blir det fint og typesafe og.

[Gjest Gjest slettet-ld9eg7s96q]

Genialt, heh. Det var en fiffig løsning du

 

Må innrømme at jeg ikke er så altfor up to date med C++ 11, men dette er noe jeg skal forfølge

Endret 13. mai 2013 av Gjest slettet-ld9eg7s96q

[Lycantrophe]

C++11 innfører det som kalles enum classes som er en sterker enum; den kan ikke implisitt castes til int. Dette gjør også at man ikke lenger kan sammenligne to forskjellige typer enumes.

 

http://en.wikipedia....ed_enumerations

 

In C++03, enumerations are not type-safe. They are effectively integers, even when the enumeration types are distinct. This allows the comparison between two enum values of different enumeration types. The only safety that C++03 provides is that an integer or a value of one enum type does not convert implicitly to another enum type. Additionally, the underlying integral type is implementation-defined; code that depends on the size of the enumeration is therefore non-portable. Lastly, enumeration values are scoped to the enclosing scope. Thus, it is not possible for two separate enumerations to have matching member names.

 

enum type1 { foo, bar, baz };
enum type2 { zab, rab, oof };

zab == bar

vil da gi compiler error.

Endret 13. mai 2013 av Lycantrophe

[Gjest Gjest slettet-ld9eg7s96q]

Godt jeg postet dette så tidlig i stadiet av kodingen da

 

Bruker MSVC hestepress 2010 og siste versjon av xcode på mac for å kompilere dette, går ut ifra at nmake under windows i dette utviklingsmiljøet og kompilatoren til xcode støtter C++ 11?

[Lycantrophe]

xcode bruker vel clang/llvm, så såfremt du har en ny versjon (>= 3.2) bør du være good-to-go. MSVC er det litt verre med, men gud hjelpe meg du burde styre unna uansett. Lurer på om MSVC omsider skal kunne kompilere noe C++11-kode, men jeg ville IKKE tatt det for gitt. Test godt om du velger å bruke standarden for MSVC.

 

C++11 er forøvrig ikke noe krav for at løsningen med å bruke enums direkte i vektoren skal kunne brukes; det eneste C++11 vil gi deg i så måte er strongly typed.

 

That being said har C++11 VELDIG mange fine features, så det er absolutt verdt en titt. Men, MSVC da gitt. :--/

 

http://gcc.gnu.org/

 

edit: om du har xcode 4.6 ser det ut til at du har tilgang på llvm3.2

http://en.wikipedia.org/wiki/Xcode#4.6

Endret 13. mai 2013 av Lycantrophe

[Gjest Gjest slettet-ld9eg7s96q]

Ja jeg startet med å kode dette i xcode og når jeg skulle kompilere dette i windows tok jeg tak i det første og beste. Eller, det var kanskje litt mer bevisst en som så, du snakker med en som lærte seg C++ i MSVC 2.0 under windows 3.11 så det utviklingsmiljøet har vært default for meg egentlig når jeg skulle kompilere det lille jeg lager under windows ....

 

Av kuriositet, hva hadde du valgt under windows?

[Lycantrophe]

MinGW. Hver gang. http://www.mingw.org/

Endret 13. mai 2013 av Lycantrophe

[Gjest Gjest slettet-ld9eg7s96q]

Skal prøve å få dette til å samarbeide med MinGW og qmake/QT, da slipper jeg å stresse med xcode også. Kjekt å ha identisk utviklingsmiljø over flere plattformer.

 

Edit: Og så lang tid tok det før QT manien tok over igjen :V

Endret 13. mai 2013 av Gjest slettet-ld9eg7s96q

[Lycantrophe]

Enda et tips om du skal få til det: CMake.

 

http://www.cmake.org/

 

Jeg finner dokumentasjonen forferdelig forvirrende, men du finner sikkert noen eksempler. Om du har tilgang på linux kan kdevelop lage en kurant cmake for deg.

 

Also, og dette har irritert meg lenge: det heter Qt, ikke QT. qt kan gå, men QT er bare ille.

[Gjest Gjest slettet-ld9eg7s96q]

Den opprinnelige logoen til Trolltech hadde Q og T i uppercase, så det så :V

 

Men la gå: qT

 

 

> : )

Endret 13. mai 2013 av Gjest slettet-ld9eg7s96q

[Lycantrophe]

Psh, bare en dårlig font.

[GeirGrusom]

Mulig jeg har missforstått, men kan det ikke skrives slik?

enum sides
{
 top = 1,
 bottom = 2,
 left = 4,
 right = 8,
 topLeft = top | left,
 topRight = top | right,
 bottomLeft = bottom | left,
 bottomRight = bottom | right,
 vertical = left | right,
 horizontal = top | bottom
};

return adjacent[0]
   | adjacent[1] << 1
   | adjacent[2] << 2
   | adjacent[3] << 3;

Endret 14. mai 2013 av GeirGrusom

[Lycantrophe]

Det ser riktig ut så langt jeg ser det, men det har to "ulemper", om en skal si det slik.

 

Den første er naturligvis at bit"magi" får en del til å få panikk. Den andre er at det er betydelig tregere enn den egentlig gode løsningen, nemlig å representere enhetene i map-et direkte. Da kreves ingen lookup i det hele tatt.

 

Det å bruke adjacent[n] krever i tillegg at du henter ut verdiene fra map-et, som tross alt gir deg fire linjer ekstra.

 

Hastighetsmessig spørs det også om det er kjappere. Ja, bitshifts og or er lynkjapt, men her er du antagelig "avhengig" av RAM access, som er en betydelig timesink. Såfremt ikke alt ligger cachet, men spørs om det går hvis map-et blir stort nok.*

 

tl;dr det er en pen løsning, men vet ikke om det er verdt det.

 

* this I base on absolutely nothing. Det må selvfølgelig profileres for å være verdt noe, jeg presenterer bare synsing.

Endret 15. mai 2013 av Lycantrophe