Unnecessary borders displayed

[bob0809]

I hope this will be fixed with the next patch? For some reason this is bugging me way more than it should.

[s_nkarp]

We do need a different border drawing algorithm. The current one has 2^93 distinct possible error conditions...

[bob0809]

I got to ask how you draw your borders? I have of course no idea how your game works, but isn't drawing a border or not simply determiner by the question if two adjacent provinces have the same side controlling it or not?

[Pat]

Miguel wrote this post about it last year ..

http://www.shenandoah-studio.com/improv ... ng-part-1/

[Miguel_TSS]

I got to ask how you draw your borders? I have of course no idea how your game works, but isn't drawing a border or not simply determiner by the question if two adjacent provinces have the same side controlling it or not?

It seems super simple because, for humans, it is. As natural pattern recognizers, mentally grouping and outlining a give set is pretty trivial. Not so much for our computer counterparts. This problem is compounded by the need to have it visually displayed, very quickly for human consumption. The pipeline must also allow for early quick iteration, since the map borders change during development.

<troll challenge>Play connect the dots. Now with ~2500 Dots. Now with on a shape you've never seen before. Now with no numbers. You may not need all the dots. Now create your own paper. Don't forget to create your own marker. You have a 60th of a second. GO!</troll challenge>

The errors come from two places:

Input error
We re-use raster (Sprite) data to automatically determine the polygon vertices. All of the sprites are separated by 1-5 pixels of antialiasing and/or transparency so verts generated may not actually touch. The algorithm attempts to compensate for this, most of the time successfully. When it fails, vertex data requires manual tweaking.

Optimization Error
More vertices = more computation = more time = NO GOOD! Each space generally has between 25-65 vertices so we can't just start with an intersection test. We using bounding boxes to create a cascading union of spaces and remove interior polygons quickly. When a polygon is added to the union the new shape is optimized. This does however have the potential for moving a vertex. When identified, these can also be fixed by manual tweaking the input file.

I can go into more detail in a blog post if you are super interested at each step. Though there's lots I'd like to do in this area (Threading, VBO optimization, new algorithm), it becomes a bit of a "The devil you know" sort of situation. 2^93 is a big number (Though it's more like ~40^93 if you think at the intersection level) it's a lot to test, so even though I hate having you experience a fail case, I really appreciate the bug report. The Screen shot and save file gets us right there for the fix.

For Further reading on Polygon Union:
http://lin-ear-th-inking.blogspot.dk/20 ... using.html
http://stackoverflow.com/questions/6844 ... hout-holes
http://www.cs.man.ac.uk/~toby/alan/software/

[s_Titus_Tears]

My biggest gripe about the border definition with the heavy white line around it hides all the detail about the specific crossing.
The rivers become hidden and other natural obstacles, this was more evident for me in Battle of the Bulge…
But does also live within Drive on Moscow.

Regards

[daviddunham]

As in Bulge, you can press and hold on the map to hide the borders (revealing the rivers).

[bob0809]

Miguel, thanks for the great answer! I just want to mention how much I appreciate your (and the rest of the team's, obviously) blog posts, especially the technical ones!
You are the only developer I know that actually explains the technical intricacies of his game in so much detail. As someone who is taking some baby steps in 2D engines, I find them especially interesting.