Take the 2-minute tour ×
Arqade is a question and answer site for passionate videogamers on all platforms. It's 100% free, no registration required.

What's the per-opponent vulnerability of a given territory in the online Risk-like game http://www.conquerclub.com? Is there an existing tool that solves this problem, albeit in a different context? Details:

I define vulnerability(t,x) as "the minimum number of troops opponent x must defeat in order to reach and conquer territory t". This calculation is non-trivial when x has no troops adjacent to t.

Sample JSON input data below (hideous), with a following explanation. The goal is to take JSON data in this format, and return per-territory per-opponent vulnerability.

map = {"killers":[],"countries":[{"name":"Baie de Henne","xS":240,"yS":86,"xL":304,"yL":108,"neutral":0,"bonus":0,"borders":[1,23],"bombardments":[]},{"name":"Port-de-Paix","xS":288,"yS":84,"xL":367,"yL":102,"neutral":0,"bonus":0,"borders":[0,2,8,7],"bombardments":[]},{"name":"Ile de la Tortue","xS":317,"yS":44,"xL":404,"yL":50,"neutral":0,"bonus":0,"borders":[1,4],"bombardments":[]},{"name":"Le Borgne","xS":337,"yS":78,"xL":434,"yL":96,"neutral":0,"bonus":0,"borders":[4],"bombardments":[]},{"name":"Cap-Haiten","xS":408,"yS":113,"xL":519,"yL":139,"neutral":0,"bonus":0,"borders":[3,2,5,9,6],"bombardments":[]},{"name":"Fort-Liberte","xS":462,"yS":126,"xL":587,"yL":156,"neutral":0,"bonus":0,"borders":[4,6],"bombardments":[]},{"name":"La Victoire","xS":434,"yS":146,"xL":555,"yL":186,"neutral":0,"bonus":0,"borders":[4,12,5],"bombardments":[]},{"name":"Gonaives","xS":302,"yS":119,"xL":385,"yL":146,"neutral":0,"bonus":0,"borders":[1,8,9],"bombardments":[]},{"name":"Cammon","xS":346,"yS":130,"xL":440,"yL":160,"neutral":0,"bonus":0,"borders":[1,7,9],"bombardments":[]},{"name":"Paul","xS":396,"yS":152,"xL":476,"yL":178,"neutral":0,"bonus":0,"borders":[7,8,4,10,11],"bombardments":[]},{"name":"Desdunes","xS":369,"yS":185,"xL":470,"yL":229,"neutral":0,"bonus":0,"borders":[9,11,15,16],"bombardments":[]},{"name":"Bouli","xS":421,"yS":214,"xL":535,"yL":266,"neutral":0,"bonus":0,"borders":[9,10,17,13],"bombardments":[]},{"name":"Los Posos","xS":483,"yS":207,"xL":576,"yL":230,"neutral":0,"bonus":0,"borders":[13,6],"bombardments":[]},{"name":"Hinche","xS":451,"yS":213,"xL":576,"yL":269,"neutral":0,"bonus":0,"borders":[11,12,14],"bombardments":[]},{"name":"Roseau","xS":480,"yS":255,"xL":606,"yL":318,"neutral":0,"bonus":0,"borders":[13],"bombardments":[]},{"name":"Ile de la Gonave","xS":278,"yS":250,"xL":354,"yL":311,"neutral":0,"bonus":0,"borders":[16,10,19,23],"bombardments":[]},{"name":"Saint-Marc","xS":365,"yS":241,"xL":465,"yL":299,"neutral":0,"bonus":0,"borders":[15,17,10],"bombardments":[]},{"name":"Monet","xS":411,"yS":279,"xL":523,"yL":346,"neutral":0,"bonus":0,"borders":[16,11,19,20,18],"bombardments":[]},{"name":"La Toison","xS":453,"yS":278,"xL":577,"yL":346,"neutral":0,"bonus":0,"borders":[17,20],"bombardments":[]},{"name":"Port-au-Prince","xS":395,"yS":308,"xL":503,"yL":387,"neutral":0,"bonus":0,"borders":[17,20,15],"bombardments":[]},{"name":"Kenscoff","xS":432,"yS":315,"xL":549,"yL":395,"neutral":0,"bonus":0,"borders":[17,19,28,29,18],"bombardments":[]},{"name":"Jeremie","xS":109,"yS":312,"xL":140,"yL":390,"neutral":0,"bonus":0,"borders":[23,22],"bombardments":[]},{"name":"Les Cayes","xS":141,"yS":359,"xL":180,"yL":450,"neutral":0,"bonus":0,"borders":[21,23,24],"bombardments":[]},{"name":"Pestel","xS":154,"yS":310,"xL":197,"yL":388,"neutral":0,"bonus":0,"borders":[21,22,24,15,0],"bombardments":[]},{"name":"Aquin","xS":177,"yS":341,"xL":220,"yL":422,"neutral":0,"bonus":0,"borders":[23,22,25],"bombardments":[]},{"name":"Cotes de Fer","xS":262,"yS":325,"xL":334,"yL":413,"neutral":0,"bonus":0,"borders":[24,26,27],"bombardments":[]},{"name":"Leogane","xS":344,"yS":326,"xL":438,"yL":408,"neutral":0,"bonus":0,"borders":[25,27,28],"bombardments":[]},{"name":"Bainet","xS":338,"yS":355,"xL":430,"yL":445,"neutral":0,"bonus":0,"borders":[25,26,28],"bombardments":[]},{"name":"Jacmel","xS":374,"yS":341,"xL":475,"yL":428,"neutral":0,"bonus":0,"borders":[29,20,26,27],"bombardments":[]},{"name":"Belle-Anse","xS":478,"yS":364,"xL":608,"yL":457,"neutral":0,"bonus":0,"borders":[28,20],"bombardments":[]}],"continents":[{"name":"Nord","bonus":4,"required":0,"territories":[0,1,2,3,4,6,5],"subcontinents":[],"overrides":[]},{"name":"Artibonite","bonus":3,"required":0,"territories":[7,8,9,10],"subcontinents":[],"overrides":[]},{"name":"Centre","bonus":2,"required":0,"territories":[11,12,13,14],"subcontinents":[],"overrides":[]},{"name":"Ouest","bonus":5,"required":0,"territories":[15,16,17,19,20,18],"subcontinents":[],"overrides":[]},{"name":"Sud","bonus":2,"required":0,"territories":[21,22,23,24],"subcontinents":[],"overrides":[]},{"name":"Sud-Est","bonus":3,"required":0,"territories":[25,26,27,28,29],"subcontinents":[],"overrides":[]}],"requirements":[],"objectives":[],"reinforcements":[],"positions":[],"title":"Haiti","large":"Haiti.L.jpg","small":"Haiti.S.jpg","widthS":"550","heightS":"407","widthL":"698","heightL":"517","min_reinforcement":0,"country_counter":30};

armies = [{"player":"4","quantity":1},{"player":"1","quantity":1},{"player":"1","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"1","quantity":5},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"2","quantity":3},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"2","quantity":1},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1},{"player":"0","quantity":3},{"player":"4","quantity":1},{"player":"4","quantity":1},{"player":"4","quantity":3},{"player":"1","quantity":3},{"player":"1","quantity":1},{"player":"1","quantity":1},{"player":"3","quantity":1},{"player":"3","quantity":1}];
  • "map =" defines the fixed map. Each entry in "countries" represents a territory. For example, "Baie de Henne" is territory 0, "Port-de-Paix" is territory 1, "Ile de la Tortue" is territory 2, and so on.

  • The "borders" field tells which territories can attack each other. In more complex maps, some attacks are 1-way, but not here. For this map, if s can attack t, then t can attack s.

  • The "map =" line has lots more info, but nothing useful for this question.

  • The "armies =" line gives the owner and number of troops for each territory (changes each turn). For example, player 4 has 1 troop on territory 0 (which we know from above is "Baie de Henne"), player 1 has 1 troop on territory 1 ("Port-de-Paix"), and player 1 also has 1 troop on territory 2 ("Ile de la Tortue").

    This information should be sufficient to calculate per-territory per-opponent vulnerability.

Note: a player may not attack his own troops. Example:

  • Opponent x has 1 troop on s, adjacent to t.

  • Opponent x has 100 troops on r, adjacent to s, but not adjacent to t.

  • The 100 troops or r cannot attack the 1 troop on s to get to t.

  • On the map below, player 1 is red, 2 is green, 3 is blue, and 4 is yellow. As with many conquerclub.com maps, it's not trivially obvious which territories border which: that's one reason I want this program.

Risk map

This program (written for a completely different reason) may be helpful and/or confusing.

Even if no one's written a program specifically for conquerclub.com, is there a general tool that solves these kinds of problem?

I realize I could use networkx, treat this as a digraph, and use shortest paths, but is there something "higher level" I could use?

share|improve this question
1  
Darn it, now I'm going to spend the whole day tomorrow thinking about this. –  Steve V. Dec 24 '10 at 6:02
    
Belongs on gamedev? –  Mechko Dec 24 '10 at 7:20
1  
I think this question belongs on this site. It's just a particularly mathy/programming-related way of breaking down a game mechanic that needs to be determined. –  Mana Dec 24 '10 at 7:39
1  
@Mechko - this is about the mechanics behind an existing game which help the gamer do better - and not something needed for the development of any new game. All that said, barrycarter, I'm not entirely sure our website is the best place to get an answer for this type of question - good luck anyway. –  Oak Dec 25 '10 at 16:34
    
Thanks. I might modify it + post it to math or programming too. But I'm pretty sure the people here are mathematicians and programmers too. –  barrycarter Dec 25 '10 at 17:16
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.