Hra ve stylu Untangle

Dnes se pokusíme využít znalosti z předchozích článků a vytvořit hru. Jedná se o typ hry, kde posouváme vrcholy rovinného grafu ve snaze nalézt jeho rovinné nakreslení. Zní to složitě, ale čtěte dál a hned bude vše jasné.

Postup práce

Stanovme si, co vše potřebujeme a jak to budeme dělat.

Kde vzít grafy

Ve hře se pracuje s rovinnými grafy, tedy grafy, které lze nakreslit tak, aniž by se nějaké hrany protínaly. Pokud uděláme náhodný graf, nemusí být rovinný (třeba $K_{3,3}$ není rovinný).

Vstupní grafy je možné zadat ručně, ale musíme nejdříve nějaké hezké vymyslet. Další možností je nechat si je náhodně vygenerovat počítačem.

Rovinným grafem by mohla být např. triangulace (mezi body v rovině dáme hrany tak, že každá stěna je trojúhelník). V minulém článku o Voroného diagramu jsme při výpočtu diagramu dostali vedlejší produkt, Delaunayho triangulaci. Tu můžeme použít, případně z ní odstranit nějaké hrany, aby graf nebyl tak komplikovaný.

V grafu také potřebujeme kontrolovat protínání hran a podle toho je správně vykreslovat. Kontrolu protínání lze použít z předchozího článku.

Postup tedy je:

• vytvořit v rovině vrcholy
• vypočítat na nich triangulaci - správný seznam hran
• vyhodit některé hrany pro zjednodušení grafu
• zamíchat vrcholy (my je dáme do kružnice)
• nechat uživatele hýbat vrcholy, podle toho překreslovat graf

Kód

/*
   Vrcholy jsou třídy Point, graficky je reprezentuje
   třída Dot. Dot má pointer na svůj vrchol (Dot.p) 
*/

import net.ivank.voronoi.*;
import net.ivank.Geometry;

var i:int;
const n:int = 10;   // počet vrcholů
// rozměry scény
const w:int = stage.stageWidth;
const h:int = stage.stageHeight;
var dDot:Dot;       // vrchol, kterým se táhne
var edges:Vector.< VEdge >; 
var v:Voronoi = new Voronoi();
var vertices:Vector.< Point> = new Vector.< Point >();

Vytvoření grafu

// náhodné vrcholy
for(i = 0; i< n; i++)
   vertices.push(new Point(150 + Math.random()*300, 120 + Math.random()*240 ));

// generujeme pro ně hrany (voronoi a delaunay)
edges = v.GetEdges(vertices, stage.stageWidth, stage.stageHeight);

// umístíme vrcholy do kružnice
for(i=0; i< n; i++)
{
   vertices[i].x = w/2 + 170 * Math.cos(Math.PI*2*i/n);
   vertices[i].y = h/2 + 170 * Math.sin(Math.PI*2*i/n);
}

// přidáme na scénu DOTy
for(i = 0; i< n; i++)
{   
   var d:Dot = new Dot();
   d.addEventListener(MouseEvent.MOUSE_DOWN, onDown );
   d.addEventListener(MouseEvent.MOUSE_UP,   onUp   );
   d.p = vertices[i];
   d.x = vertices[i].x; d.y = vertices[i].y;
   d.buttonMode = true;
   addChild(d);
}

Už jen zbývá napsat vykreslování čar a také kontrolu, zda se nějaké dvě protínají (-> kontrola, zda se žádné neprotínají). To jde napsat různými způsoby a konkrétní kód nechám na vás.

Vylepšení hry

Pokud do hry přidáme pěknou grafiku, případně nějaké další extra funkce, bude hra mnohem pestřejší a pro určité procento populace i zábavná :) V tomto duchu jsem vytvořil hru FlyTangle. Pokud by vás bavila a máte Google Chrome, můžete si ji nainstalovat jako Chrome aplikaci.