Miután már egy működő, és valamennyire elviselhető városgenerátort sikerült összedobni, nekiálltam a telekbányásznak. Ez a kis modul felelős azért, hogy a városgenerátor által kiköpött gráfból kiszedjem a telkeket, vagyis azokat a területeket, amiket minden oldalról út határol. A tőlem megszokott elméleti fejtegetés következik.

Adott egy gráf, ami úgy van reprezentálva, hogy tudjuk az összes pont koordinátáját, meg, hogy mi mivel van összekötve. Namármost a kérdés, hogy ebből hogyan kapunk egy olyan adatszerkezetet, ami mondjuk hasonlít egy poligontömbhöz. Először is, mi a poligon? Hát az simán pontok (illetve pontosabban: pozíciók) tömbje. Vagyis a poligontömb nem más, mint pozíciók tömbjének tömbje. Szeretjük az adatszerkezeteket, ugye? :D

Viszont az sem árt, ha nem csak random pontokat rakunk bele egy tömbbe, hanem azok csatlakoznak egymáshoz utakon keresztül. Oké, ezt még meg tudjuk oldani, egyszerűen fogunk egy tetszőleges pontot, kiválasztunk egy tetszőleges szomszédot, és máris van két pontunk, ami össze van kötve. Aztán a következő pontnál is kiválasztunk egy szomszédot (ami szerencsés esetben különbözik az első ponttól), és így tovább. Tulajdonképpen a telek kiszedése hasonló ehhez, csak nem véletlenszerűen választjuk a szomszédokat.

Amikor a városban vagyunk, és programozók egy csoportja odaszegezi az uzit a homlokunkhoz, hogy sétáljunk körbe egy telket, hogyan abszolváljuk a feladatot? Elindulunk egy kereszteződésből, és minden kereszteződésnél az ISO-szabvány szerint megjelölt irányba (esetünkben ez most legyen a bal oldal, mert az a jobb :D), majd a következő kereszteződésnél is elsétálunk balra. Ámde nemcsak akármelyik bal oldali elágazásba sétálunk bele, hanem amelyik legközelebb van az előző utcához. Ezt úgy tudnánk szépen leírni, hogy amikor elérünk egy kereszteződéshez, akkor szembefordulunk azzal az úttal, amerre jöttünk, majd elkezdünk jobbra forogni, és az első út, amit meglátunk, az lesz a "legbalabbik" út.

Példa.

Itt egy ábra. Az "A" jelű pontból indultunk, és megérkeztünk a "B" jelű pontba. Megfordulunk, úgy, hogy "A"-val szembe nézünk, ekkor a narancssárga vonal mutatja az irányunkat. Majd a pirossal jelölt nyíl irányában megfordulunk jobbra, és az első út lesz a keresett út.

No, ha ez megvan, akkor már csak azt kell megoldani, hogy ne járjunk be olyan poligont, amit már egyszer bejártunk. Kis belegondolással belátható, hogy minden utat pontosan kétszer fogunk bejárni (egyszer oda, egyszer vissza), mivel minden útnak két oldala van, tehát minden út két telekkel lesz "szomszédos". Tehát jelölni kell valamivel, hogy ezt az utat ilyen irányban már egyszer bejártuk-e. Én egy egyszerű megoldást választottam: mivel már nem lesz szükségem a gráfra, és mivel egy út mindkét végpontjában tárolva van az út, egyszerűen kitörlöm az utat abból a pontból, amiből épp kiindultam. Visszafelé még vissza tudok jönni egyszer, mivel a másik végpontban még benne van. Íme, egy példa az eredményből:

Persze jogosan veti fel valaki, hogy mi van a szélekkel? Nos, igen, a mostani rendszer azokat is bejárja, szóval ezzel majd kezdeni kell valamit. Több ötletem is van erre, például megadom, hogy egy poligon maximum "n" pontot tartalmazzon. Vagy, mivel ez az egyetlen ilyen invalid telek, elég, ha megkeresem azt a telket, ami rengeteg pontból áll, és kitörlöm. De biztosabb, ha megnézem a külső szögek összegét. A belső (elfogadható) telkeknél ez 360 fok lesz, míg a telekhatárnál -360 fok.

És most, hogy megvannak a telkek, jöhet a következő napirendi pont: a lakások legenerálása. Hallelujah!