Autor Zpráva
hal_sk
Profil
Zdravím.
Chcel by som spraviť simuláciu Langtonovho mravca (Langton's ant), v PHP.
Ide vlastne o 2D priestor, zložený z buniek po ktorom sa pohybuje jedna bunka (mravec) podľa týchto pravidiel:
- Ak mravec príde na bielu bunku, tak zmení jej farbu na čiernu a otočí sa o 90 stupňov vľavo .
- Ak mravec príde na čiernu bunku, tak zmení jej farbu na bielu a otočí sa o 90 stupňov vpravo.
- Na počiatku sú všetky bunky mriežky inicializované na bielu farbu.


Video pre predstavu:
http://www.youtube.com/watch?v=1X-gtr4pEBU

Viem že je sabotáž, použiť na takéto niečo PHP, ale skúsenosti mám zatiaľ len v PHP.
Predstavujem si to, ako nejakú rovinu zloženú z rovnocenných buniek (bielych), za pomoci poľa. Mravca bude predstavovať nejaký SESSION. Ale aj bunky si budú musieť pamätať svoj stav, lebo niektoré sa budú meniť na čierne a naspäť. Jednotlivé kroky mravca, by sa prevádzali pomocou refreshu stránky.
Viete ma nejako naviesť (samozrejme ak by tu niekto vysypal celý kód, bolo by to milé :-) ? Čo použiť, čo nepoužiť? Je moja úvaha v predchodzích vetách správna? Treba voliť iný postup?
Mastodont
Profil
Ano, použij pole a to si taky ukládej do sešny.
Joker
Profil
hal_sk
Asi by na tohle bylo lepší použít Javascript, výpočty by nezatěžovaly server a mravenec by mohl chodit v reálném čase.

Implementace by neměla být tak složitá, alespoň na první pohled-
Podle zadání: mřížka by byla dvourozměrné pole hodnot 0=černá a 1=bílá. Mravenec by měl tři atributy: aktuální souřadnice (X a Y) a aktuální směr (dal bych 0,1,2,3 ~ S,V,J,Z). A jeden krok by udělal:
1. V závislosti na barvě změnit směr mravence. Tak jak jsem definoval směry je změna o 90° vpravo přičtení 1 a vlevo odečtení 1.
2. Invertovat barvu pod mravencem
3. Podle směru upravit souřadnice

Ve složitějších případech, jako jsou na videu, by bylo potřeba přidat mapování barev: pole barev, kde u každé barvy by byla zaznamenaná následující barva a směr otočení. Pokud by směr otočení byl jenom vlevo/vpravo (tj. nešlo "čelem vzad" ani "pokračovat rovně"), dalo by se to i jedním číslem- absolutní hodnota čísla by určovala novou barvu a jeho znaménko směr otočení.
Krok 1 by pak směr otočení bral z mapy barev a krok 2 by místo invertování nastavoval barvu podle mapy.
hal_sk
Profil
Joker
Vďaka za analýzu.

K JavaScriptu sa určite chcem dostať, to by ale trvalo nejaký čas.
V PHP som zatiaľ zosmolil len toto:

Tu som spravil mravca, ktorý chodí cez uhlopriečku mriežky:
http://hal.tym.sk/mravec/01.php

Tu som spravil mravca, ktorý neustále opisuje štvorec:
http://hal.tym.sk/mravec/02.php

Neviem ako mám spraviť to, aby určitá bunka mriežky (SESSION) zmenila/invertovala svoju hodnotu (biela/čierna), podľa toho či sa na nej nachádza mravec (či sa zhoduje index poľa mravca s indexom poľa bunky mriežky). Lebo ako náhle sa dá rehresh, tak my ten cyklus na vykreslenie mriežky, vlastne znuluje všetky SESSION v mriežke.

Zdrojáky:

Mravec ktorý chodí cez uhlopriečku mriežky:
<?php
// narastanie indexov mravca o 1, aby sa dosiahlo pohybu po uhlopriecke
$move_z=$_SESSION['move_z']=$_SESSION['move_z']+1;
$move_x=$_SESSION['move_x']=$_SESSION['move_x']+1;

for($z=1;$z<=10;$z++) // vykreslenie bunkovej mriezky
{
 for($x=1;$x<=10;$x++)
 {
  $_pole[$z][$x]=1; // kazda bunka ma vychodziu hodnotu 1
  $_pole[$move_z][$move_x]="<b style='color:red'>x</b>"; // mravec a jeho indexy pola
  echo $_pole[$z][$x];
 }
 echo "<br>";
}

?>


Mravec ktorý neustále opisuje štvorec:
<?php

$_SESSION['step']=$_SESSION['step']+1; // po kazdom refrese sa zvecsi o 1

if ($_SESSION['cycle']==4) // ak mravec spravy stvrty krok, vynuluje sa mu session
{
 unset($_SESSION['cycle']);
}

$_SESSION['cycle']=$_SESSION['cycle']+1; // cyklus pohybu mravca - zvecuje sa o 1

switch ($_SESSION['cycle']) // pohyb mravca pomocou korekcii indexov pola mravca po kazdom jeho pohybe
{
 case 1;
  $_SESSION['move_z']=$_SESSION['move_z']+0;
  $_SESSION['move_x']=$_SESSION['move_x']+1;
 break;

 case 2;
  $_SESSION['move_z']=$_SESSION['move_z']+1;
  $_SESSION['move_x']=$_SESSION['move_x']+0;
 break;

 case 3;
  $_SESSION['move_z']=$_SESSION['move_z']+0;
  $_SESSION['move_x']=$_SESSION['move_x']-1;
 break;

 case 4;
  $_SESSION['move_z']=$_SESSION['move_z']-1;
  $_SESSION['move_x']=$_SESSION['move_x']+0;
 break;
}

// +5 zabezpeci ze vychodzia poloha mravca bude v strede mriezky
$move_z=$_SESSION['move_z']+5;
$move_x=$_SESSION['move_x']+5;

for($z=1;$z<=10;$z++) // vykreslenie bunkovej mriezky
{
 for($x=1;$x<=10;$x++)
 {
  $_pole[$z][$x]=1; // kazda bunka ma vychodziu hodnotu 1
  $_pole[$move_z][$move_x]="<b style='color:red'>x</b>"; // mravec a jeho indexy pola
  echo $_pole[$z][$x];
 }
 echo "<br>";
}

?>
habendorf
Profil
Hezká úloha, zkusil jsem si ji cvičně udělat v JS. Nejsem žádný skriptař, takže jsem to udělal poněkud dřevorubecky, vlastně jen za pomoci id a class. Za pomoc s časováním děkuji Chamurappimu (chtěl jsem, aby se stopa mravence vykreslovala postupně, bez časování se zobrazí až po výpočtu celá najednou).

V IE trochu vázne začátek, ve FF je to lepší.

http://pokusy.1-webdesign.cz/mravenec/
hal_sk
Profil
habendorf
Pekné. Hneď sa idem učiť JS :-)

PS: Ten tvoj príklad má hypnotizačné účinky. Pozerám sa nehybne do toho viac ako 10 sekúnd a točí sa mi hlava. Skús zvoliť iné farby :-)

Už sa teším ako tam budem skúšať rôzne modely, rôzne druhy pravidiel pre mravca a pozerať sa čo vyvedie. Matika ma nikdy nebavila, lebo mi nešla, ale takto v grafickom podaní je to zaujímavé.
Joker
Profil
habendorf
Vida, nejsem sám, koho lákalo to naprogramovat :)
Až budu mít chvíli, možná zkusím svou verzi :)

Dotaz, jaký je přesně účel následující konstrukce?
  for(var i = 0; i<= 10000; i++)
  {
    (function(i)
    {
      setTimeout(function()
      {

Nějak mi nejde do hlavy, jak to vlastně funguje :)
habendorf
Profil
Joker

První řádek je asi jasný, to je cyklus iterací a to další je přesně to, s čím jsem sám nemohl pohnout - časování, které mi pomohl udělat Chamurappi. Pošlu ho sem, ať to vysvětlí :o)
Chamurappi
Profil
Reaguji na Jokera:
To je lexikální uzávěr, už se to tu párkrát na diskusi objevilo. Anonymní funkce, která se okamžitě vyvolává, má svoji lokální proměnnou „i“ (shodnou s číslem iterace), která přežije ve své podobě do doby vykonání timeoutu. To hlavní cyklové „i“ totiž vyroste k 10 000 dříve, než proběhne první timeout.
Mike8748
Profil
Chamurappi
takze jestli to dobre chapu tak to vytvari 10 tisic najednou bezicich timeoutu?
habendorf
Profil
Mike8748

Taky to tak chápu, už podle toho argumentu i * 10 v timeoutu.
Timy
Profil
Joker
http://diskuse.jakpsatweb.cz/index.php?action=vthread&topic=89699&forum=8&page=-1 :-)
_es
Profil
Joker
Dotaz, jaký je přesně účel následující konstrukce? ...
Miesto kódu:
(function(i)
{ //nejaké príkazy používajúce premennú i
}
)(i);

sa dá použiť aj:
with({i:i})
{ //nejaké príkazy používajúce premennú i
}
habendorf
Profil
S trochu vyladěnou verzí skriptu se mi podařilo dosáhnout toho, čemu v tom videu říkají "highway".

Joker
Profil
takze jestli to dobre chapu tak to vytvari 10 tisic najednou bezicich timeoutu?
Taky jsem to tak pochopil.
Ale není mi jasné, proč nevynechat ten cyklus a neudělat prostě setInterval a krok každých X milisekund.
habendorf
Profil
Joker

Jestli to dobře chápu, tak bys nebyl schopen vyhodit číslo iterace, při které mravenec opustí svůj "výběh".
Joker
Profil
habendorf
Zkusil jsem upravit Tvůj kód ve smyslu mé představy, jak by to mělo fungovat, a funguje to :-)

Můj kód:
var i, x, y, smer, casovac;
i = 0;
smer = 0;
x = y = 25;

function createGate() {
 var string= '';
 for (var x=0; x<= 50; x++) {
  for (var y=0; y <= 50; y++) {
   string += "<span class='green' id='" + x + "-" + y + "' style='top:" + 10*x + "px; left:" + 10*y + "px'> &nbsp;</span> ";
  	}
  }
  document.getElementById('gate').innerHTML = string;
}

function krok(){
  if((x < 0) || (y < 0) || (x > 50) || (y > 50)){
    alert ('Mravenec utekl z pole, počet iterací:' + i);
    clearInterval(casovac);
    return;
  } 
  var policko = document.getElementById(x + '-' + y);
  if(policko.className == 'green')
  {
    policko.className = 'red';
    smer = (smer - 1 == -1 ? 3 : smer-1);
  }
  else
  {
    policko.className='green';
    smer=(smer+1 == 4 ? 0 : smer+1);
  }
  switch(smer)
  {
    case 0 : x-=1; break;
    case 1 : y+=1; break;
    case 2 : x+=1; break;
    case 3 : y-=1; break;
  }
  i++;
}

function goAnt()
{
  casovac = setInterval("krok()",10);
}


Akorát jsem teda udělal pokusný "závod mravenců" :-) a u toho mého kódu běhá mravenec pomaleji.
Udělá se ale stejný počet iterací a vykreslí stejný obrazec.

Taky se to chová jinak při vícenásobném kliknutí na "Vypusť mravence". Zatímco u toho skriptu mravenec začne běhat rychleji (a na konci se pak vyhodí více alertů... ale pořád vykreslý stejný obrazec a udělá 5439 iterací), u toho původního skriptu tam pak běhá více mravenců, což je řekl bych zábavnější :-)
habendorf
Profil
Joker

Jasně. Ten tvůj skript by ale běžel donekonečna, pokud by mravenec nevyběhl ven. A to já dopředu nevěděl, za jak dlouho a zda vůbec vyběhne, proto jsem to chtěl mít omezené tím počtem iterací. Navíc třeba pro ladění jsem začínal s deseti iteracemi.

K té rychlosti, zkus Chamurappiho tuning:

function goAnt()
{
  var x, y, smer = 0, i = 0;
  x = y = 50;

  var timer = setInterval(function()
  {
    i++;
    if(x < 0 || x > 100 || y < 0 || y > 100)
    {
      alert("Mravenec utekl z pole, počet iterací:" + i);
      i = Infinity;
    }
    if(i >= 12000)
    {
      clearInterval(timer);
      return;
    }
    var policko = document.getElementById(x + '-' + y);
    var c = policko.className;
    policko.className = (c == "green") ? "red" : "green";
    smer = (smer + {"red": 1, "green": 3}[c]) % 4;

    x += [-1, 0, 1, 0][smer];
    y += [0, 1, 0, -1][smer];
  }, 1);
}


Edit: zkoušel jsem pak větší matici, takže si musíš přepsat tu startovní pozici a podmínky pro opuštění pole. A nebo zvětšit matici.
Joker
Profil
habendorf
A to já dopředu nevěděl, za jak dlouho a zda vůbec vyběhne, proto jsem to chtěl mít omezené tím počtem iterací. Navíc třeba pro ladění jsem začínal s deseti iteracemi.
Aha, OK. Já naopak vycházel z toho, že by měl běhat prostě dokud to bude pozorovatele bavit :) (resp. dokud nevyběhne pryč).

K té rychlosti, zkus Chamurappiho tuning
Pěkné :) Ale i tak ten mravenec běhá zhruba stejně rychle jako předtím... resp. pomaleji než ten původní kód. Alespoň v Opeře a IE7. Přičemž v IE7 zdá se běhá o maličko rychleji, než v Opeře.

Zajímavé je, že při použití té mé varianty s globálními proměnnými ho sice neurychlí zkrácení intervalu časovače, ale urychlí ho použití více nezávislých časovačů.
Například:
function goAnt()
{
  casovac = setInterval("krok()",30);
  krok();
  casovac2 = setInterval("krok()",30);
  krok();
  casovac3 = setInterval("krok()",30);
}

(tj. teoreticky krok každých 10ms) vyrobí rychlejšího mravence, než:
function goAnt()
{
  casovac = setInterval("krok()",1);
  krok();
  krok();
}

(tj. teoreticky krok každou milisekundu).

Nějak mě nenapadá jiné rozumné vysvětlení.
Dero
Profil
Nějak mě nenapadá jiné rozumné vysvětlení.

Výchozí časovač v mnoha prohlížečích má hrubé rozlišení ~30ms. (často ho přebírají od systému)

Ten krok po milisekundě ti pojede rychleji třeba v Chromu, protože ten používá časovač s jemným rozlišením.
Joker
Profil
Nějak mě nenapadá jiné rozumné vysvětlení "...než že setInterval má nějakou minimální hodnotu intervalu" tam mělo být :), během psaní příspěvku mi to vypadlo :-)
Dero
Díky za vysvětlení.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: