Sunday, August 21, 2016

Introduction to Adaptive Grids

Adaptive Grids are a procedural generation technique for area and point based topologies that can expand to n-dimensional space.

Although ROAM was a technique that inspired temporal ROAM (Later, VRWorlds), there has been an unresolved question on how to adapt the self-similarity of right triangles to 3 dimensions and above. I’ve been considering a square / cube based approach that exhibits the near-parent properties of ROAM, but have usually run afoul of being unable to conceptualize it into a working model past the main recursive function. A breakthrough in going from 3x3 to 4x4 grids as a starting point has spawned a lot of additional pieces to fall into place.

Realtime Optimally Adaptive Meshes (ROAM) have certain key features when attempting to build procedurally generated content (like terrain).
 - Scaleable depth: ROAM allows one part of the map to be generated more deeply than another part of the map. This is important in terrain generation as a potentially infinite terrain can be generated without infinite memory / storage requirements to generate the entire world at the proposed granularity.
 - Deterministic depth: ROAM can be configured to always return the same division given the same parents. This allows the scaleable depth to continue to generate the same result given a very high level starting parent set, which in turn allows ROAM to roll up and forget previously expanded areas in favour of the currently viewed area.
 - Continuous mesh deformation: Any change made by ROAM continues to keep the mesh cohesive and continuous due to the reliance of splitting pairs of right triangles together based on known parents. This largely removes issues of creasing and tent-poling inherent in many terrain generation techniques.
Adaptive Grids attempt to mimic these traits, but be based off a grid (of squares for 2-dimensional space, cubes for 3-dimensional space, etc).Continuous mesh deformation is currently not retained for the eventual mesh itself, but utilises parental involvement to remove creasing.

Adaptive Grid core algorithm:
(The algorithm is explained for a 2-dimensional surface using squares. Extensions to higher dimensions are trivial, but covered formally later.)
Given a set of parents arranged in a 3x3 grid of squares, the Adaptive Grid generates a 3x3 grid ½ the size centered on the middle square. The new squares rely on the parents that they overlap with. This means that the new middle square is determined solely by the middle parent; the new cardinal squares are determined by the middle square and the adjacent parent (Eg: New square to the north requires the middle parent and the northern parent); and the new corner squares are determined by the middle square and the 3 other parental squares in that diagonal direction (Eg: New square to the NorthEast requires the middle, North, East & NorthEast parents).

 Since the algorithm produces another 3x3 grid at a deeper layer, the algorithm can be recursively applied to create an arbitrary depth.

 Top Layer: 
 If a top layer of 3x3 is used to initiate the algorithm, it can continue to develop infinite depth, but no method of developing breadth of grid when at an arbitrary depth. Any requirement to develop anything other than the centre grid requires the rebuilding of another parent in the previous layer to make the requested square a centre square. The parent would also require a grand-parent in the layer above, and so on, eventually breaking due to the absence of a parent outside of the initial 3x3 layer.

 To allow a defined space for breadth generation, the Adaptive Grid is initiated with a 4x4 grid. This allows the generation of a grid of arbitrary size or arbitrary depth to be generated within a 1x1 size square centred on the midpoint of the 4x4 grid. (Eg: an initial grid of 4x4 squares of 128 unit length can generate a 64x64 grid with 2 unit length inside a 128x128 space centered on the middle of the initial grid)

 4x4 grid layer progression: 
When initiating an Adaptive Grid with a 4x4 layer, the amount of squares in each fully expanded subsequent layer increases with this observed sequence:

Layer 1Layer 2Layer 3Layer 4Layer 5

The calculation for each layer follows the sequence: Layer(n) = Layer(n-1)*2-3

 Proof of defined space:
Since the child 3x3 grid is located centrally over the parent 3x3 grid, the middle child is a direct shrinking of the parent middle square. Continued shrinking makes the centre square reduce the area around the centre point, but never will reduce the centre point to nothingness or deviate from the centrepoint. The sides of the square asymptote to the central point. Since the side length of each square is the same across the entire grid, as the middle square side length reduces toward 0, so too does the outer squares. Therefore the outside of the outer squares also asymptotes toward the central point, which is 1.5 units in from the outside of each outer square. 

Applying this asymptote to a 4x4 grid means that the outside of the outer squares will only ever need to be brought in by 1.5 units when creating a grid of infinite depth. Removing 1.5 units from the borders of the 4x4 grid leaves a 1x1 unit area that cannot be reached, thus leaving the area to be rendered by an arbitrary grid size (Eg: If the requirement for a 1000x1000 grid is needed covering an area of 100 m2 (side 10m), a starting Adaptive Grid of side 40m or larger is required).

Simple Scratch application to help demonstrate Adaptive Grids

Sunday, April 10, 2016

Darkest, Darkest Dungeon - The Hamlet, The Ruins

The Hamlet

Much work to do. Once a bustling hive of activity, the hamlet offered little in service. It, too, had felt the harsh sting of my lineage’s demise. Boarded up and left to time’s grasp. Rising above the rooftops our mansion silhouetted the sky with exposed beams like festering claws. No place to stay anymore.

We need fresh souls to infuse life into this dilapidated estate, and for that, a restoration of the stagecoach network is my first priority. With deeds and crests of sovereignty, the veins of commerce were once again revived.

Canouville was the first to alight into our bleak domain, an aspiring Vestal with judgemental vigor. Raoullin also made the journey, but his proclivity to plague made for an awkward commute. Our assembly is enough to embark upward into the ruinous remains of my bloodline.

The Ruins

With limited provisions we set out to my ancestral home. Gothic architecture rising above once demanded respect, now webbed in neglect it portrayed a more sinister abode. Leading the way through the grandiose entrance, I halted at the sight of candles bracing a raised altar beneath a muralled monk. Lit candles. Apprehensive we scanned the foyer, but skeletal remains adorning the windows only indicated a prior, more murderous occasion.

Ever east through creaking door to a corridor festooned with derelict shelves of vellum and decaying plaster. Still nothing, but the tension eats into Dismas and I as we exchange nervous glances. Of note, an unburned torch held aloft, poised for a task long forgotten. We will give it purpose again.

Up ahead, a strongbox placed proudly in the vaulted chamber drew our gaze while a rabble of bones lurched toward us in animated fits. “To Arms!”

Raullin, silent as ever, reacted first with a puff of emboldening vapours to break my shocked condition and keen the senses. Dismas drew and fired forcefully, splintering bone and exploding whatever foul mastery held its frame together. “Back to the Pit!” He raged. I followed with my own critical smite to blanket the floor with unholy remains. They CAN be fought, they CAN be beaten!

Our attention turned to the reinforced chest. Surely no sober logic leaves this prize so openly on display? A trap? Dismas dared the lock with well-seasoned expertise and proffered up coin, scriven records of land grants and an unlikely shovel. “We’ll be needing that” announced Canouville, scouting the upcoming passageway. True enough, a crude jumble of stones and debris stood tall, defying our advance. Protruding corpses of unknown labourers mocked our attempts to clear the rubble, but with grim determination and spaded steel we overcame the obstacle.

Lying in wait, a brace of skeletons lumbered toward us, backed by a masked cultist. Grapeshot peppered them all as Dismas took command, urging us into the fray. Raoullin let loose a blinding flask of fireworks toward the surprised acolyte while I zealously accused the leading skeletons; “Destroy. Them. All!” My words ripped through what fabric of control bound the bones together, leaving one in a clattering heap and the other wavering. Delivering holy judgement upon the stunned cultist, Canouville’s call boomed bright to rip clear the mask and expire the eyes behind it. The remaining soldier of bone took a grave slash toward our group, catching Canouville off guard. Dismas closed with knife in hand, but skilled execution in bloodletting offered no assistance in felling the calcified corpse, leaving the fatal blow to my own hand. A faint hope blossoms.These creatures seem poorly constructed and easily overpowered by zealous might.

Through the portico into another ruined expanse. No ambush or assault, but a choice of paths for consideration. We head East, more through comforting routine than strategic merit.

The torch, our lifeblood of sanity. Slowly ebbing into shadowy cocoon.

Saturday, April 09, 2016

Darkest, Darkest Dungeon - Reynauld the Crusader

Reynauld the Crusader

As the stagecoach wheels clattered along the cobblestones leading to our venerable house, I held the note loosely, hoping that the pored-over words would shake into a more enlightening alignment. The lanterns held back the darkness, but offered little comfort to my wandering mind. Memories of playing in the cavernous halls of that old house flooded back.

An unearthly howl pierced the night and broke me from my reverie. The startled horses bucked out and couldn’t be contained by the driver’s whip. We left the road to an even bumpier excursion before clattering to a halt minus a wheel and our means of locomotion. Dismas and I were unscathed, but alone as the coach driver scurried after the fleeing mares, a torrent of cursing that trailed into the blackness.

“I guess this means we are on foot?” Queried Dismas. 

We left the luggage for a future return and headed East. Ever East. The hamlet is just ahead.

A grizzled thug stepped out to block our path, but we were in no mood to talk. Dismas, good with a knife, opened his veins while I landed a pommel strike to daze him for a moment. He recovered quickly though and still managed a slashing uppercut that caught my brow. Move quicker or die. Dismas dispatched him with ruthless efficiency to bring the tempo back to an eerie night’s walk. The gold will help, if only to make the tavern that much more enticing upon arrival.

Ever East.

A disheveled tent came into view, but no movement betrayed its owner. Possibly the lowlife bleeding out back on the road? Dismas wasted no time in claiming the additional gold and misappropriated onyx. 

Another ambush! We’ll send them a message that the rightful owner has returned and there is no place for these vermin. Dismas was quick to shoot, but the grapeshot missed both the larger, whip-wielding brigand or the fusiler toward the back. I landed a stunning blow to curtail the bloodletter’s flaying, but couldn’t escape the blanket fire that erupted into the night. Back to the knives for Dismas as we focused on the heavy-set villian to drop him quickly. The whip was our concern, but a point blank shot drove me away before returning with my own justified strike. Prodigious size alone does not dissuade the sharpened blade. 

Pelted with blanket fire, Dismas and I took shelter behind the fallen mass, but the rain of shrapnel didn’t cease. Exploding through the bloodied carcass, we set upon the rifle-clad bandit with steel. As the fiend fell, a faint hope blossomed. 

Portraits, deeds and crests of my heritage lay with the fallen, but I will make something of them in time. More gold to be relieved too, but the hard-won chest held nothing but blight. 

My return was not met with adulation. These squalid lands, these corrupted hovels are mine to rebuild, but the populace remain ambivalent. I, too, fear they may be right. Stress rises when I see their downcast husks.

Darkest, Darkest Dungeon - An Unwelcome Letter

An Unwelcome Letter

“Ruin has come to our family. “
“You remember our venerable house? Opulent and imperial, gazing proudly from its stoic perch above the moor. I lived all my years in that ancient, rumour-shadowed manor, fattened on decadence and luxury”
“And yet I began to tire of conventional extravagance. Singular, unsettling tales suggested the mansion itself was a gateway to some fabulous and unnameable power.”
“With relic and ritual, I bent every effort towards the excavation and recovery of those long buried secrets, exhausting what remained of our family fortune on sworly workmen and sturdy shovels.”   
“At last, in those salt-soaked crags beneath the lowest foundations, we unearthed that damnable portal and a deluded evil. Our every step unsettled the ancient earth, but we were in a realm of death and madness.”
“In the end, I, alone, fled laughing and wailing through those blackened arcades of antiquity until consciousness failed me.”
“You remember our venerable house? Opulent and imperial.”
“It is a festering abomination!”
“I beg you, return home! Claim your birthright and deliver our family from the ravenous, clutching shadows of the darkest dungeon!” 

Monday, March 28, 2016

Kitesurfing Memories

Finally got a woo to measure jumping height, and March delivered a 2 weeks spell of near 20 knot days to test it out. This video was of a particularly clean day in the run-out channel at 1/2 tide. Such a smooth section. Such a lovely day to be out on the water. Such a great time going higher and higher!

TournamentCompare v0.004 - Player Pools

One slight deviation from the old Clarion application is that I have instituted player pools as a starting point for a tournament. All players for a tournament are entered into a sorted list (player pool) that the tournament template draws from. This allows the generation of the player pool to be independent from the tournament template and can therefore be used to test all sorts of varied starting positions and even seeding patterns.

For smaller tournament formats (8 players or less), every possible player pool combination can be generated and used in sequence to eliminate another possible bias. For 8 players this would be 40320 combinations (8 factorial). If a tournament is larger than 8, you could potentially take the top 8 combinations and interleave other random players to give 16, 32, 64, or 128 player pools. This would give a large control set (~40,000 samples), but at least give a somewhat even spread of higher candidates.Unfortunately it would also eliminate the random chance that the most skilled player meets the second most skilled player in round 1 of a 128 player tournament. Since generating a random player pool will be quite easy, I can also test the difference of these two formats and isolate a specific amount of bias due to potential seeding.      

TournamentCompare v0.003 - Validating a tournament template

Because the tournament template system is flexible enough to allow all sorts of formats, it is also flexible enough to bring in all sorts of loops, missing players, unlinked matches, etc, so I'll be making up a validator to vet each tournament template before running thousands of tests on an invalid tournament.

Here's the high level pseudocode:

  1. Start with the final match and work back along the player entry locations until all matches have been processed into a list (vettedMatchList) and all the players are in another list (competitorList). This also sets the match layer (how deep into the tournament that this match represents)
  2. Check to make sure that all TournamentTemplateMatches for this TournamentTemplate have been accounted for.
  3. Check to make sure that all competitors have an entry into the tournament
  4. Build a list (noExitMatchList) for each match that 2nd place continues in the tournament.This is combined with the match layer to evaluate final exit position for 2nd placegetters that do NOT continue.
  5. Mark the tournament as valid and update the database with match layers & exit positions.