[DGD] the building blocks of grandiose worlds: geometry

Tue Aug 27 20:39:01 CEST 2013

It's been a couple months since I was able to dive into code, but I've been
trying to work out geometry based relationships rather than simple
environment containment.

I have a few blog posts on the subject:

http://www.second-contract.com/2013/02/scenes-and-settings/
http://www.second-contract.com/2013/03/scenes-and-settings-part-2/
http://www.second-contract.com/2013/03/proximity-and-movement/
http://www.second-contract.com/2013/07/describing-scenes-paths-and-terrains/

Some code is available on github: https://github.com/jgsmith/second-contract

If those might be helpful.

-- Jim

On Tue, Aug 27, 2013 at 2:19 PM, Raymond Jennings <shentino at gmail.com>wrote:

> So the gist of veiling is that insider and outsider is inherently
> transitive, which is why it can be implied.
>
> If object A is outside object B, and B is outside C, then we already know A
> is outside C and we don't even have to ask.
>
>
> On Tue, Aug 27, 2013 at 11:08 AM, Raymond Jennings <shentino at gmail.com
> >wrote:
>
> > I should probably point out that in this process I'm trusting geometry
> > queries to be honest.  Real geometry is consistent and allows for this to
> > work.  This scheme will fail in a hurry if geometry handlers lie to the
> > relation processing.
> >
> >
> > On Tue, Aug 27, 2013 at 11:07 AM, Raymond Jennings <shentino at gmail.com
> >wrote:
> >
> >> I agree, it's vague ^^  I'm still trying to come up with the terminology
> >> too.
> >>
> >> The basic idea is that I keep track of geometric (topologic?) relations
> >> between neighboring objects.
> >>
> >> WRT one object that holds the relation mapping, another object can be:
> >>
> >> 1.  An insider (completely contained by us)
> >> 2.  An intersecter (our boundaries criss cross)
> >> 3.  An outsider (completely containing us)
> >> 4.  An overlapper (our boundaries are perfectly congruent)
> >> 0.  No relation at all
> >>
> >> The default is 0, which as a nil is not even tracked, and any object not
> >> in our relation map is assumed to be 0.
> >>
> >> Now the immediately useful part:
> >>
> >> First, direct neighbors:
> >>
> >> Objects in sets 1, 2, or 4 have parts of themselves inside us, and
> >> qualify for internal actions.
> >> Objects in sets 2, 3, or 4 have parts of themselves outside us, and
> >> qualify for external actions.
> >>
> >> Second, indirect neighbors:
> >>
> >> Additionally, objects in sets 2, 3, or 4 may have objects of their own
> >> inside them, or in their own 1-, 2-, or 4- set.
> >>
> >> The 1's, 2's, and 4's of our 2's, 3's, and 4's are external neighbors.
> >>
> >> The 2's, 3's, and 4's of our 1's, 2,s and 4's are our internal
> neighbors,
> >> and the rules of geometry (I think anyway) imply that those indirect
> >> relations will also show up in our own 1's, 2's, or 4's
> >>
> >> By querying these lists, I can find neighbors.  This collection of
> >> neighbors is the list of candidates for things like visibility,
> >> interaction, targeting by nouns, and so on.
> >>
> >> That is the immediate usefulness.
> >>
> >> The second intended benefit:  Any outsider or insider acts as a veil
> >> which hides everything behind it from processing, which in a sizable
> world
> >> can obviously cut way down on the O(N^2) potentials, since anything
> >> affecting us from beyond that veil (no sirius black jokes please) has
> to go
> >> through the veil to get to us, and since the outsider or insider is
> already
> >> keeping track of us in its own relation list, anything that cares to
> find
> >> us can do so easily once it hits the veil and peeks behind it.
> >>
> >> This veiling effect also helps save on processing time when geometry
> >> relations need to be checked for updating after an object moves.  I
> don't
> >> have to do a nasty O(N^2) check against everything else.  If I change
> from
> >> a 1 to a 2 for object B, I only have to look at object B's 1's and 2's
> and
> >> 4's to see who my new relations might be.  Similiarly, if I become a 1
> of
> >> object B, I never have to look outside object B again to check anything.
> >>
> >> This is all theoretical so far, but my prototype is working well enough
> >> even now for the time being.
> >>
> >> As a quick and dirty example, let's say you have a few objects:
> >>
> >> object A is Fort Providence, and is a municipal zone.
> >> object B is the county of Kolechistan
> >> object C is Kolechistan's first police precinct
> >> object D is Kolechistan's fourth fire district
> >> object E is the state of Imporiton
> >> object F is the great and glorious nation of Triskellia
> >> object G is the state of Oregon.
> >>
> >> A is completely inside B, and also completely inside C and D
> >> B is completely inside E, and contains C and D
> >> C and D, being under different departments of Kolechistan, are
> >> intersecting each other, completely contain A, and are completely
> inside B
> >> E contains A
> >> F contains E
> >> F contains G
> >>
> >> Now, I have some optimizations already.
> >>
> >> Because E completely surrounds B, it doesn't even show up as a relation
> >> at all for A, C, or D.  A, C, and D list B as their ousider, and can
> safely
> >> ignore anything outside of B.  Which means that anything inside
> Kolechistan
> >> doesn't have to worry about the rest of Imporiton, or for that matter,
> >> anything outside it such as F (Triskellia) and G (oregon).  Object B
> acts
> >> as a veil that hides objects E, F, and G from objects B and C, and
> >> therefore from object A.
> >>
> >> Additinally, anything outside of Kolechistan doesn't need to worry about
> >> anything inside of it.  Objects E, F, and G can completely ignore object
> >> B's contents, since object E acts as a veil.
> >>
> >> Now if due to political events, the borders change, I can run a geometry
> >> check on any objects.  If the check brings in new neighbors, I can check
> >> against them as well, and if relations change I can then look for more
> >> candidates.
> >>
> >> However, I only have to check my neighbors.  If after checking them, no
> >> new candidates pop up, I can stop.  Anything that remains an outsider
> >> cannot possibly have anything interesting outside itself, and likewise
> for
> >> insiders.
> >>
> >> Now, if something happened outside that needed our attention, that
> >> something would first have to pierce the borders of our outsiders, and
> if
> >> it did that, it would then check our outsider's relations (including
> us).
> >>
> >> or, to put it back in the example, if a rocket was launched from China
> >> and made its way to Fort Providence, you can bet your bones that
> >> Triskellia's air force radar would find out about it and the air force
> >> would warn Imporiton's governor.  Imporiton's governor, in turn would
> >> probably put the police precinct and fire district on high alert by the
> >> time the rocket impacted.  Which is to say, that the rocket would have
> to
> >> go through Triskellia's borders before Imporiton even saw it, and
> likewise
> >> through Imporiton's borders before the police and fire districts saw it,
> >> and then likewise for Fort Providence itself.  Each penetration of a
> veil
> >> brings up new objects to check for relations, and this process can
> recurse
> >> as needed until everything resolves.
> >>
> >> Since the police and fire zones intersect though, Fort Providence still
> >> has to put up with jurisdictional squabbles.
> >>
> >> I hope this clarifies my idea better.
> >>
> >>
> >> On Mon, Aug 26, 2013 at 11:08 AM, Natasha Koroleva <
> >> natasha.i.koroleva at gmail.com> wrote:
> >>
> >>> Kind of vague description. I wonder there is a direction attribute for
> >>> the relation (I assume this will be used for to handle exits)? Overlap
> >>> includes some sort of index so that you know what is above and below
> >>> the object?
> >>>
> >>> On Mon, Aug 26, 2013 at 10:51 AM, Raymond Jennings <shentino at gmail.com
> >
> >>> wrote:
> >>> > Ok, so I just implemented very basic geometry processing, that makes
> >>> sets
> >>> > of objects that are inside, outside, intersecting, overlapping, or
> not
> >>> > related at all.
> >>> >
> >>> > This is the foundation for delegation and object hiding in my
> "colossal
> >>> > galaxy with detail down to the room" scheme.
> >>> >
> >>> > The gist is that for any two objects, object B can be inside object
> A,
> >>> > outside it, intersecting it, or overlapping it (same position and
> >>> shape)
> >>> >
> >>> > Ultimately, the relation list will seed the candidate list when
> >>> checking
> >>> > for neighbors.
> >>> >
> >>> > Can anyone see any flaws in this design?
> >>> > ____________________________________________
> >>> > https://mail.dworkin.nl/mailman/listinfo/dgd
> >>> ____________________________________________
> >>> https://mail.dworkin.nl/mailman/listinfo/dgd
> >>>
> >>
> >>
> >
> ____________________________________________
> https://mail.dworkin.nl/mailman/listinfo/dgd
>