Have we got this right? Topology experts welcome!

This is where we inform about development updates.

Have we got this right? Topology experts welcome!

Postby super_dipsy » 19 Jul 2019, 08:25

OK, so we have a bug in the War in the Americas code. I have a fix, but it is nagging away at me that without a perfect topological brain I may be overlooking something. So I thought why not throw it out to all YOUR brains!

Here is the puzzle. The adjudicator / judge knows about territories on the map, whether they are sea or caost or land-locked territories and what other territories each touches. So for example it knows that North Africa has a coast, touches Tunis which is also a coast, and MAO and Western Med which are seas.

If there is an army in a location, it can move to any non-sea location that it touches. Easy.
If there is a fleet in a location, it is more tricky. Take the North Africa example; North Africa touches Tunis, but can it move there? Answer, yes because it is next to it on the same coastline. But a fleet in Ankara cannot move to Smyrna even though Ankara touches Smyrna because it is not the same coastline. How do you know there is a shared coastline? Easy, look to see if both locations touch the same sea.

OK so far. So now we have the challenge. Look at this part of the War in the Americas map
Capture.PNG
Capture.PNG (30.5 KiB) Viewed 7453 times


As you will see, Para, Caye and Suri are all coastal regions, all touch each other and all touch the same sea. So how do you know whether you can move from one to the other or not? Obviously you can see visually that a fleet in Suri or Para could move to Caye or vice versa, but a fleet in Para could not move to Suri. But how can the dump software know that, based on only knowing about what each territory touches topologically?

My hypothesis is that if you want to move from one location to the other, you need to obviously check to see they touch and they share a sea. But you then
- check to see if there are any more locations that touch both source and destination locations and the same sea
- check to see if this location ONLY touches the other two and the shared sea

So in the example, moving from Para to Suri you would find Caye touching both and sharing the same sea, and you would find Caye only touches Para/Suri and the sea, so it must be locked in and there is no fleet route from Suri to Para.

My belief is this is a pretty rigorous test to see if there is a territory locked in between the other two on the same coastline and therefore preventing movement by a fleet. But I am not totally convinced. I keep wondering about what if a territory is on the edge of the board or something. Could it read as a false locked-in territory or something? Can anyone see scenarios where this solution would fail?
User avatar
super_dipsy
Premium Member
 
Posts: 12406
Joined: 04 Nov 2009, 17:43
Class: Ambassador
Standard rating: 1000
All-game rating: 931
Timezone: GMT

Re: Have we got this right? Topology experts welcome!

Postby Woolgie » 19 Jul 2019, 10:43

Not that it would fail in your map example, but hypothetically it would fail if Para and Suri shared a different coast. Say if the three land regions and only those shared an island. You could move Para to Suri via Caye clockwise but directly from Para to Suri anti-clockwise.

I never realised this was how the alrgorithm worked and it seems like a different method would be more robust. With Link parameters set up between each pair of regions called L (Land), S (Sea) and C (Coast), the algorithm would just check - Oh, you want to move from Para to Suri, well they only have an L Link and you’re a fleet so the answer is no.
I ran Play Diplomacy League for a time and then I set it free
Redesigning my Star Wars variant
Still proud of my solo in Versailles Fog Chaos
WDC 2020 38th place
User avatar
Woolgie
 
Posts: 333
Joined: 15 Feb 2016, 19:43
Location: Chesterfield, UK
Class: Ambassador
Standard rating: 976
All-game rating: 875
Timezone: GMT

Re: Have we got this right? Topology experts welcome!

Postby McCleves » 19 Jul 2019, 10:47

If the Para area did also englobe the territory on the left of Surinam, it would fail.
Because it would prevent you from moving to Para from Surinam, even though it would be technically possible.

What you could do is move the borders from the sea tile.
Right now it's hitting the cape-like extention of the Para province. If you make it hit the middle of the Cayenne province instead, the problem will be resolved as Surinam and Para wouldn't touch the same seatile anymore
McCleves
 
Posts: 5
Joined: 10 Oct 2018, 13:02
Class: Star Ambassador
Standard rating: (700)
All-game rating: (719)
Timezone: GMT

Re: Have we got this right? Topology experts welcome!

Postby Tortellacci » 19 Jul 2019, 12:10

It seems to me that the best option would be to manually include exceptions like this and handle them. The reason for this is because there is no way to know for sure if three adjacent provinces border each other on the same coast. For example: imagine Para, Caye, and Suri are the only three provinces on the map, and there is only one sea province surrounding them. In this case, F Suri -> Paya should be possible, but by looking at the parameters of adjacency and coasts, there is no way for the adjudicator to know why that is possible while moving F Suri -> Paya in the normal WitA map isn't.

Of course the other option would be to add a parameter of "adjacent coasts", but considering this is just now an issue, manually handling the exceptions would likely be the better solution.
Tortellacci
Premium Member
 
Posts: 55
Joined: 04 May 2017, 00:54
Class: Diplomat
Standard rating: (1181)
All-game rating: (1475)
Timezone: GMT-5

Re: Have we got this right? Topology experts welcome!

Postby drillbit » 19 Jul 2019, 13:03

If Surinam and Para were on the edge of the map then from what you've said it would return the result that Surinam is between Cayenne and Para and would not allow fleet moves between Para and Cayenne, so would fail, yes.
drillbit
 
Posts: 55
Joined: 23 Apr 2012, 12:16
Class: Ambassador
Standard rating: (1337)
All-game rating: (1498)
Timezone: GMT

Re: Have we got this right? Topology experts welcome!

Postby drillbit » 19 Jul 2019, 13:14

Would it also fail and allow a fleet to move Para to Georgetown as they do not border the same territories?
drillbit
 
Posts: 55
Joined: 23 Apr 2012, 12:16
Class: Ambassador
Standard rating: (1337)
All-game rating: (1498)
Timezone: GMT

Re: Have we got this right? Topology experts welcome!

Postby super_dipsy » 19 Jul 2019, 16:05

Hmm. Some great thoughts here, but I'm not sure there aren't one or two mistakes too :)

Woolgie wrote:Not that it would fail in your map example, but hypothetically it would fail if Para and Suri shared a different coast.

Which would be correct. That is why for the coastal move to work you have to share a coast.
McCleves wrote:If the Para area did also englobe the territory on the left of Surinam, it would fail.
Because it would prevent you from moving to Para from Surinam, even though it would be technically possible.

No, it is not possible. I don't think this makes any difference. You can move an AMRY from Para to Suri fine, it is a FLEET we are considering. And you cannot move a fleet from Para to Sur no matter how many terrs lie between.
Tortellacci wrote:It seems to me that the best option would be to manually include exceptions like this and handle them.

Agreed, this is always an option. But as a programmer you can't help but look for something more elegant ;) . On a practical level, if you special case it, then in a couple of years when someone puts up a new map and does not realize it has the same issue, you would hit the same bug.
drillbit wrote:If Surinam and Para were on the edge of the map then from what you've said it would return the result that Surinam is between Cayenne and Para and would not allow fleet moves between Para and Cayenne, so would fail, yes.

That is the one I was worried about, but I can't see such an example in my head...
drillbit wrote:Would it also fail and allow a fleet to move Para to Georgetown as they do not border the same territories?

Oh bugger. Yep, that's gonna blow its tiny mind.

Hmmm. Well, if desperate I will juust have to put special case in, or even change the structure so we can have touchpoints for armies and fleets separately, but that is a big change to the design. I'm trying to resist that, but perhaps it can't ever work.
User avatar
super_dipsy
Premium Member
 
Posts: 12406
Joined: 04 Nov 2009, 17:43
Class: Ambassador
Standard rating: 1000
All-game rating: 931
Timezone: GMT

Re: Have we got this right? Topology experts welcome!

Postby Shyvve » 19 Jul 2019, 20:12

Knowing nothing about programming (but having written a wonderful 6-line or so FORTRAN program...once!), I'm wondering how the vanilla game handles the analogous situation of disallowing a F Brest moving to Belgium. Maybe looking at that would be helpful?

EDIT: But maybe my analogy isn't a true one, since Brest and Belgium aren't adjacent by land.
Last edited by Shyvve on 19 Jul 2019, 20:15, edited 1 time in total.
An Oldie and Gold Classicist. Moderator for the Classicist group.
User avatar
Shyvve
 
Posts: 478
Joined: 31 Dec 2016, 20:10
Class: Diplomat
Standard rating: (1313)
All-game rating: (1345)
Timezone: GMT-6

Re: Have we got this right? Topology experts welcome!

Postby super_dipsy » 19 Jul 2019, 20:13

OK, I have got this sorted now. Thanks for the various inputs, it demonstrated clearly that there is no reliable way to do this purely based on the currently supplied data.

What I was trying to avoid was having to redo all the variants and the judge structure because it can screw up our other variants. But I have worked out a way to make it optional, so that for all other variants and even normal terrs in Wita we will change nothing. The optional extra info (where fleets can move) will only need to be added for the affected territories in WitA (and any other map).

Anyway, thanks for helping me get my head straight! :)
User avatar
super_dipsy
Premium Member
 
Posts: 12406
Joined: 04 Nov 2009, 17:43
Class: Ambassador
Standard rating: 1000
All-game rating: 931
Timezone: GMT

Re: Have we got this right? Topology experts welcome!

Postby Custer » 20 Jul 2019, 15:58

Don't forget, there are various substances for that.

;)

LOL

The SHIV
First..........get off my lawn! Second........it's a dashing self portrait! Courtesy of The Craw. Third.....I am still SHIV, Keeper of the Stone Tablets! Go Pack! And behold the power of cheese! And one more thing. Say ya to da U.P. eh!
User avatar
Custer
Premium Member
 
Posts: 3869
Joined: 24 Jan 2009, 20:29
Location: The Minnie Pearl is locked in the ice in Little Bay de Noc til Spring.
Class: Ambassador
Standard rating: 936
All-game rating: 1347
Timezone: GMT-5


Return to Developments

Who is online

Users browsing this forum: No registered users and 2 guests

cron