[1.10.2][Project] Designing/defining Regions, drawing visible world in 2d.

[Ernio]

Hey,

 

At this point everything I do pretty much converges to defining regions (regions - e.g: cities, guilds zones or non-/pvp zones and zone-based mob-spawning which is pretty much key in MMO Engines.)

 

I am here for brainstorming and maybe even finding someone in doing mod/api with me

 

1. Let's define some stuff:

* Regions are defined in X/Y coords with bottom and top (y1,y2) creating prism.

* Rectangle ((x1,y1),(x2,y2)) - self explanatory.

* Polygon (List<xi,yi>) - where polygon is only viable if its area is not 0 (which ensures that it has 3+ vertexes) and its sides don't intersect (those prerequisites will be handled internally on creation).

* Circle - in future, so i'll skip it.

 

2. Let's bring idea into play:

* Most of you probably know WorldGuard and unless something changed there, I don't want to do it like they do - running with wand around, but with a nice GUI (admin only tool).

* Basic idea is to open editor GUI which will display currently loaded world and will request all visible (in range) regions and draw them using simple vertex based GL.

* GUI will have creation and edition tools and will send update packets to server on demand (on change).

* Regions will be saved mostly server side, unless needed otherwise - e.g (again admin tool) - we would want to render their sides inside world.

 

3. Let's bring image into play:

 

...and define some stuff:

* GLOBAL will be region of world.

* Regions will be tree based (I think).

In image above we have:

// Obvious tree structure:
GLOBAL
DESERT 1 (orange)
FOREST (purple)
	RIVER (blue)
		LAGOON (brown)
	STRUCTURE (dark red)
DESERT 2 (dark orange)
// Not so obvious:
CITY (red)
LAKE (yellow)

 

Okay so: "obvious tree" (B+ tree maybe) can be created because we have direct parent-child relations.

* Note: We assume that RIVER is fully contained in FOREST (because on image it is not visible).

 

The "not so obvious" refers to regions which are harder to assign.

Now - how would one assign them?

3.1. Extend parent - region will have one assigned parent and will extends parent reach to borders of itself.

* Problem - what if we want city to be partially in forest and desert, not just extend one of them?

Here comes 3.2:

3.2. Have one parent region (the one drawn) and then internally split region into split-regions and assign them to proper parents.

* Well, everything seems nice, we could have:

// Obvious tree structure:
GLOBAL
DESERT 1 (orange)
FOREST (purple)
	RIVER (blue)
		LAGOON (brown)
	STRUCTURE (dark red)
	CITY 1
	LAKE 1
DESERT 2 (dark orange)
	CITY 2
	LAKE 2
CITY (red)
	CITY 1
	CITY 2
LAKE (yellow)
	LAKE 1
	LAKE 2

...but we kinda lose parent-child structure as split-region would have 2 parent.

Okay so 3.3:

3.3. How about make it like 3.2. but also add "SplitRegion extends Region" that would be that "internal structure" and would have Region#parent and SplitRegion#parentInternal

LAKE (yellow)
LAKE 1 // parent = FOREST, parentInternal = LAKE
LAKE 2 // parent = DESERT 2, parentInternal = LAKE

...which seems like we got it?

In case of finding where we are, we would recursively climb by Region#parent so e.g: (LAKE 1, FOREST, GLOBAL}, while LAKE 1 could have #getName=LAKE.getName (fallback to parentInternal).

 

4. Algorithms and tracking:

Okay so regions exist for us to know where we are (naming) and for all sorts of checks like spawning specific mobs with specific stats and in specific numbers.

4.1. Entity containment: (everything would be server side, and client would receive final form like one mentioned: (LAKE 1, FOREST, GLOBAL})

@Capability would hold current Region.

4.1.1. On 1st assign we would have to scan all regions in world to find ourselves, so basically big recursion.

4.1.2 On tick we would check if Entity#pos changed and then make all sorts of checks:

* Entity leaves sub-region into parent-region.

* Entity leaves sub-region and number of parent regions (number because we can have many recursive regions on border of something big).

* Entity joins adjacent region or internal region.

* Other shit that we have to account for...

Note: Holy shit, we are closing in to big-ass data structures (if we want to have some speed).

 

4.2 Other shit I will probably mention in posts to come.

 

5. Minecraft problems:

* How do you render visible world in a smart way? How could one make leveled rendering? (display everything from Y to 0, so I can e.g see cross section of high-ass tower and define floor sub-regions).

* How do you render borders in world (vanilla does it, so easy to find, yet - ideas are appreciated).

* How know what Regions to send to display on GUI? Heck, check all the Regions!

* Other shit, idk.

 

Okay - why does this thread even exist?

The hell if I know... I kinda of started designing some of this and then even re-thought while writing this post.

Basically - if anyone has some ideas (as to not only how to write, but what to write), some references, some algorithms (well, I know most), some polygonal smart-conversions (e.g converting self-intersecting polygon to a closed one, which will be used on poly creation), or anything of sorts - post it, right here!

 

Also as mentioned before - if someone would be interested in coding it with me - feel free to say so and I will make open repo.

 

Thanks for input

 

P.S: Seriously - ANYTHING that comes to your mind, MC source is big and its easy to overlook some stuff.

 

EDIT 1:

Note - image shows 2 regions have shared border - I plan on writing algorithm that will auto expand region to adjacent ones (if possible) and also bucket tool for defining regions that are surrounded by others.

 

EDIT 2:

If you look at LAKE - it will obviously have more internal splits than {1,2} as it is being split multiple times.

 

EDIT 3:

5.1. What if visible world is not covering the region we want to create? How could one force sending to client? How to prevent chunks to auto-unload? Maybe generate simple image on server and send it to client?