VRIEN: Algoritme som jobber seg ut fra et punkt på et sjakkbrett etter 'klynger'

[TheClown]

Må nok spørre dere om hjelp igjen, og denne gangen er det litt vrient. Jeg sliter i allefall litt selv.

 

Jeg har et brett, som kan ligne på et sjakkbrett i et multidimensjonalt array som jeg kaller $map. $map[x-koordinat][y-koordinat]. Si at man tar utgangspunkt i $map[5][5]. Dette feltet består av "gull". Jeg skulle gjerne hatt en funksjon som jobber seg ut i fra dette punktet og finner alle punkter av samme type (gull altså) som ligger i nærheten av dette, og returnerer antall treff. Det vil si at hvis $map[4][5] også er gull så vil algoritmen sjekke om felter rundt $map[4][5] også er gull.

 

Se vedlagt bilde. Der er det en rød sirkel, tallet algoritmen skal returnere her skal være 9. Punktene jeg leter etter trenger ikke ligge direkte over eller på sidene av utgangpunktet, men på en eller annen måte være tilkoblet dette "feltet".

 

Er det noen som har en funksjon som kan gjøre dette?

Endret 5. august 2011 av TheClown

[BlueEAGLE]

Det du trenger her er nok en rekursiv funksjon som sjekker feltene over, under til venstre og til høyre for gjeldende felt men ikke felt som har vært sjekket tidligere.

 

function ConnectedMatches($type, $Xcoord, $Ycoord, $Map)
{
 if($Xcoord + 1) >= $Map->Columns) //Check if we're at the right most boundry
 {
   if($Map->grid[Xcoord+1][YCoord]).Type == $type) 
     $Matches += 1 + ConnectedMatches($type, $Xcoord+1, $Ycoord, $Map)
 }
 //Repeat for x-1, y+1 and y-1
}

 

Det som er litt tricky her er at du må passe på at funksjonen ikke teller samme felt to ganger. Derfor mistenker jeg at du trenger en egen matrise som angir hvilke felt som er talt i denne kjøringen av funksjonen og setter koordinatene til "sjekket" etterhvert som du treffer.

 

Jeg har her utvidet $Map til å være en klasse som inneholder matrisen samt antall kolonner og rader ca slik:

 

class Map
var $Columns = 5
var $Rows = 5
var $Map = array(Columns, $Rows);

 

Det finnes mest sannsynlig noen geniale funksjoner som bruker en mindre "brute force" tenkemåte som gjør dette bedre, men det er nå iallfall slik jeg ville gått frem.

 

 

Edit: En ting som er verdt å merke seg er at "Mine field" er et minefelt og ikke et gruveområde.

Endret 5. august 2011 av BlueEAGLE

[TheClown]

Flott! Men dette er allerede i en class, du kunne ikke vært så grei å skrive om til en normal funksjon, eller lar det seg ikke gjøre?

 

Kan jo legge inn treffene i et array og loope gjennom det, luke ut dobbeltgjengere og summere til slutt. men vil funksjonen din fortsette til sidene og oppover?

 

+1 og -1 forvirrer meg litt

Endret 5. august 2011 av TheClown

[FraXinuS]

Jeg er ikke noe algoritme-expert, men her er i hvertfall en funksjon som jeg tror fungerer:

 

 

 

<?php


$map = array(
   array('water', 'water', 'water', 'water', 'water', 'water', 'water', 'water', 'water', 'water'),
   array(null, null, null, null, null, null, null, 'gras', null, null),
   array('gold', null, 'gold', null, null, null, null, null, null, null),
   array(null, null, 'gold', 'gold', null, null, null, null, null, null),
   array(null, null, null, null, null, null, null, 'gold', 'gold', null),
   array(null, null, null, null, null, null, null, 'gold', null, null),
   array(null, null, null, null, null, null, null, 'gold', 'gold', null),
   array(null, null, null, null, null, null, null, 'gold', 'gold', null),
   array(null, null, null, null, null, null, null, null, 'gold', null),
   array(null, null, null, null, null, null, null, null, 'gold', null),
);




function count_matches($haystack, $needle, $x=0, $y=0, &$_matches=array()){

   if(!isset($haystack[$x][$y]) || $haystack[$x][$y] !== $needle || isset($_matches[$x.$y]))
       return 0;

   $_matches[$x.$y] = true;

   count_matches($haystack, $needle, $x+1, $y, $_matches);
   count_matches($haystack, $needle, $x-1, $y, $_matches);
   count_matches($haystack, $needle, $x, $y+1, $_matches);
   count_matches($haystack, $needle, $x, $y-1, $_matches);

   return count($_matches);

}

var_dump(count_matches($map, 'gold', 6, 7));


?>

 

 

 

Denne søker bare opp, ned og til sidene, ikke på skrå.

Endret 5. august 2011 av FraXinuS

[BlueEAGLE]

+1 og -1 forvirrer meg litt

+1 betyr enten ruten til høyre for eller under denne.

-1 betyr enten ruten til venstre for eller over denne.

 

Det jeg har skrevet er langt fra noen komplett funksjon, men en pekepinn på hvordan jeg ser for meg algoritmen.

 

Cluet her er at hver gang du finner en nabocelle med riktig type så kaller du den samme funksjonen med koordinatene til denne cellen og lar den sjekke hvor mange naboer den har av riktig type og svare det tilbake.

[TheClown]

Takk for svar, men jeg sliter litt med funksjonen din. Har skrevet den om litt, så den ser slik ut:

 

function mapChunckSize ($haystack, $x, $y, $t, $needle, &$_matches=array())
{

	if(!isset($haystack[$x][$y][$t]))
		return 0;

	if ($haystack[$x][$y][$t] !== $needle)
		return 0;

	if (isset($_matches[$x.$y]))
		return 0;

	$_matches[$x.$y] = true;

	mapChunckSize($haystack, $needle, $x+1, $y, $_matches);
	mapChunckSize($haystack, $needle, $x-1, $y, $_matches);
	mapChunckSize($haystack, $needle, $x, $y+1, $_matches);
	mapChunckSize($haystack, $needle, $x, $y-1, $_matches);

	return count($_matches);
}

 

Jeg caller den slik:

$this->mapChunckSize($map, $i, $ii, 'type', 'minefield')

 

Og arrayet er bygget opp slik:

Array
(
...
    [6] => Array
       (
           [0] => Array
               (
                   [coordinates] => 6-0
                   [type] => grass
               )

           [1] => Array
               (
                   [coordinates] => 6-1
                   [type] => grass
               )

           [2] => Array
               (
                   [coordinates] => 6-2
                   [type] => grass
               )

           [3] => Array
               (
                   [coordinates] => 6-3
                   [type] => grass
                   [resources] => stone
                   [amount] => 23
               )

           [4] => Array
               (
                   [coordinates] => 6-4
                   [type] => minefield
                   [resources] => gold
                   [chunk] => 
                   [amount] => 76%
               )

           [5] => Array
               (
                   [coordinates] => 6-5
                   [type] => grass
                   [resources] => tree
                   [amount] => 37
               )

           [6] => Array
               (
                   [coordinates] => 6-6
                   [type] => grass
               )

           [7] => Array
               (
                   [coordinates] => 6-7
                   [type] => minefield
                   [resources] => gold
                   [amount] => 51%
               )

           [8] => Array
               (
                   [coordinates] => 6-8
                   [type] => grass
               )

           [9] => Array
               (
                   [coordinates] => 6-9
                   [type] => grass
               )

       )
...
)

 

Og jeg får erroren:

Fatal error: Call to undefined function mapChunckSize() in ... på linja hvor:

mapChunckSize($haystack, $needle, $x+1, $y, $_matches); står

 

Hvorfor det?

 

EDIT

 

Funker hvis jeg fjerner ! i linja

if ($haystack[$x][$y][$t] !== $needle)

 

Men da returnerer funksjonen bare 1

Endret 5. august 2011 av TheClown

[FraXinuS]

Du må legge til $this->mapChunckSize og du må legge til $t og flytte $needle til riktig posisjon.

[BlueEAGLE]

Jeg håper for guds skyld at du leser inn kartet fra en datafil og ikke har hele den arrayen der definert i kode.

 

Nøkkelen i funksjonen er som du sikkert har fattet at alle tilliggende celler i en matrise enten har verdien X +/- 1 eller Y +/- 1 og at en rekursiv funksjon som returnerer 1 + antallet mottatt fra hver underkall til tilliggende celler bortsett fra de som allerede har blitt talt vil løse problemet.

[TheClown]

Arrayet er definert i koden fordi jeg "produserer" dette her med scriptet. Seinere vil jeg lagre resultatet i database, ye