B Info Other Efficiently storing and accessing complex data types 1.153

[Zsar]

I intend to code some graph based algorithms into the game. How could I efficiently (in terms of ingame computation) represent graphs with bidirectional edges and variable number of edges per node?

Example:

Distance weighted adjacency graph for walled centers, directional path between two centers

#script_is_adjacent_to
# INPUT : arg0 = center1, arg1 = center2
# OUTPUT: reg0 = weight / -1 if not adjacent

desired complexity O(1)

Spoiler: Solved in O(#adjacencies of center1).

  ("cf_is_adjacent_to",[
    (store_script_param_1, ":center1"),
    (store_script_param_2, ":center2"),

    (party_get_slot, ":adjacencies" ":center1", slot_center_adjacencies),
    (party_get_num_companion_stacks, ":size", ":adjacencies"),
    (try_for_range, ":index", 0, ":size"),
      (party_stack_get_troop_id, reg0, ":adjacencies", ":index"),
      (party_get_slot, reg0, reg0, slot_node_content),
      (eq, reg0, ":center2"),
        (party_stack_get_size, reg0, ":adjacencies", ":index"),
        (assign, ":size", 0),
    (try_end),
    (neq, ":size", 0), # center2 not found in adjacencies
  ])

#script_get_adjacent_centers
# INPUT : arg0 = center
# OUTPUT: reg0 = adjacent centers

desired complexity O(#adjacent centers)

Spoiler: Solved in O(1).

(party_get_slot, reg0, ":center", slot_center_adjacencies)

#script_get_path_from_to
# INPUT : arg0 = center1, arg1 = center2
# OUTPUT: reg0 = path

some variant of Dijstra's shortest path algorithm
Solved in O(|Graph|).

#script_get_next_in_path
# INPUT : arg0 = path, arg1 = center
# OUTPUT: reg0 = next center / -1 if center is end

desired complexity O(1)

Spoiler: Solved in O(|Path|)

  ("get_next_in_path",[
    (store_script_param_1, ":path"),
    (store_script_param_2, ":center"),

    (party_get_helpfulness, ":size", ":path"),
    # find center
    (try_for_range, ":index", 0, ":size"),
      (party_get_slot, reg0, ":path", ":index"),
      (party_get_slot, reg0, reg0, slot_node_content),
      (eq, reg0, ":center"),
        (assign, ":size", 0),
    (try_end),
    (try_begin),
      (eq, ":size", 0), # center found
        (val_add, ":index", 1),
        (party_get_helpfulness, ":size", ":path"),
        (lt, ":index", ":size"), # center not end of path
          (party_get_slot, reg0, ":path", ":index"),
          (party_get_slot, reg0, reg0, slot_node_content),
    (else_try),
      (assign, reg0, -1), # no next center
    (try_end),
  ]),

I might want to make the weight complex too, a distance/time tuple mayhap, to account for forests, rivers, cliffs...
For a start, even an unweighted graph would be nice, but neither do I want to reserve a dozen entries per node when most would have three to five adjacents nor do I wish to clutter my troops file with one data trooper per node.

Idea:

Use bitmask entries to accumulate edge information into one value.
-> Nodes
... Dismissed. - Turned out to be too many values. Graphs and nodes are now both datastructs.
Spawn inactive parties from a template to provide vectors.
-> Set of Nodes
... Implemented.
Interpret as set of adjacents or as path depending on called script.
-> Neighbors and Paths
... Dismissed. As graphs already are lists of nodes, paths are just differently ordered lists of nodes, whereas neighbors are stored as a set of edges.

 

[Zsar]

An expanded use case:

Spoiler: hand-crafted adjacency graph for walled centers on vanilla map

    (assign, ":center", "p_town_1"),    # Sargoth
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_2",    1), # Tihr
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_5",  1), # Tehlrog    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_11", 1), # Curin      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_18", 1), # Ismirala   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_36", 1), # Jelbegi    Castle
    # 5 edges

    (assign, ":center", "p_town_2"),    # Tihr
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_5",  1), # Tehlrog    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_11", 1), # Curin      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_12", 1), # Chalbek    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_34", 1), # Hrus       Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_36", 1), # Jelbegi    Castle
    # 6 edges

    (assign, ":center", "p_town_3"),    # Veluca
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_5",    1), # Jelkala
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_15",   1), # Yalen
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_1",  1), # Culmarr    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_15", 1), # Ergellon   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_28", 1), # Grunwalder Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_33", 1), # Etrosq     Castle
    # 6 edges

    (assign, ":center", "p_town_4"),    # Suno
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_6",    1), # Praven
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_7",    1), # Uxkhal
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_13", 1), # Kelredan   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_25", 1), # Ryibelet   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_31", 1), # Vyincourd  Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_35", 1), # Haringoth  Castle
    # 6 edges

    (assign, ":center", "p_town_5"),    # Jelkala
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_21", 1), # Ibdeles    Castle
    # 2 edges

    (assign, ":center", "p_town_6"),    # Praven
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_1",  1), # Culmarr    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_23", 1), # Tevarin    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_25", 1), # Ryibelet   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_35", 1), # Haringoth  Castle
    # 5 edges

    (assign, ":center", "p_town_7"),    # Uxkhal
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_16",   1), # Dhirim
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_13", 1), # Kelredan   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_15", 1), # Ergellon   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_24", 1), # Reindi     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_28", 1), # Grunwalder Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_31", 1), # Vyincourd  Castle
    # 7 edges

    (assign, ":center", "p_town_8"),    # Reyvadin
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_11",   1), # Curaw
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_4",  1), # Radoghir   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_6",  1), # Tilbaut    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_19", 1), # Yruma      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_37", 1), # Dramug     Castle
    # 5 edges

    (assign, ":center", "p_town_9"),    # Khudan
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_11",   1), # Curaw
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_13",   1), # Rivacheg
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_7",  1), # Sungetche  Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_19", 1), # Yruma      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_29", 1), # Nelag      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_39", 1), # Slezkh     Castle
    # 6 edges

    (assign, ":center", "p_town_10"),   # Tulga
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_17",   1), # Ichamur
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_18",   1), # Narra
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_2",  1), # Malayurg   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_17", 1), # Distar     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_30", 1), # Asugan     Castle
    # 5 edges

    (assign, ":center", "p_town_11"),   # Curaw
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_4",  1), # Radoghir   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_18", 1), # Ismirala   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_19", 1), # Yruma      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_39", 1), # Slezkh     Castle
    # 6 edges

    (assign, ":center", "p_town_12"),   # Wercheg
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_3",  1), # Bulugha    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_10", 1), # Alburq     Castle
    # 2 edges

    (assign, ":center", "p_town_13"),   # Rivacheg
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_3",  1), # Bulugha    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_8",  1), # Jeirbe     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_39", 1), # Slezkh     Castle
    # 4 edges

    (assign, ":center", "p_town_14"),   # Halmar
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_18",   1), # Narra
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_22", 1), # Unuzdaq    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_24", 1), # Reindi     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_40", 1), # Uhhun      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_41", 1), # Jameyyed   Castle
    # 5 edges

    (assign, ":center", "p_town_15"),   # Yalen
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_14", 1), # Maras      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_33", 1), # Etrosq     Castle
    # 3 edges

    (assign, ":center", "p_town_16"),   # Dhirim
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_20", 1), # Derchios   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_24", 1), # Reindi     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_26", 1), # Senuzgda   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_27", 1), # Rindyar    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_28", 1), # Grunwalder Castle
    # 6 edges

    (assign, ":center", "p_town_17"),   # Ichamur
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_18",   1), # Narra
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_2",  1), # Malayurg   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_7",  1), # Sungetche  Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_38", 1), # Tulbuk     Castle
    # 5 edges

    (assign, ":center", "p_town_18"),   # Narra
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_2",  1), # Malayurg   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_27", 1), # Rindyar    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_40", 1), # Uhhun      Castle
    # 6 edges

    (assign, ":center", "p_town_19"),   # Shariz
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_9",  1), # Jamiche    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_45", 1), # Caraf      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_46", 1), # Weyyah     Castle
    # 3 edges

    (assign, ":center", "p_town_20"),   # Durquba
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_21",   1), # Ahmerrad
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_41", 1), # Jameyyed   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_42", 1), # Teramma    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_44", 1), # Durrin     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_47", 1), # Samarra    Castle
    # 5 edges

    (assign, ":center", "p_town_21"),   # Ahmerrad
    (call_script, "script_set_adjacency_between_centers", ":center", "p_town_22",   1), # Bariyye
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_43", 1), # Sharwa     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_44", 1), # Durrin     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_47", 1), # Samarra    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_48", 1), # Bardaq     Castle
    # 6 edges

    (assign, ":center", "p_town_22"),   # Bariyye
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_43", 1), # Sharwa     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_44", 1), # Durrin     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_48", 1), # Bardaq     Castle
    # 4 edges

    (assign, ":center", "p_castle_1"),  # Culmarr    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_31", 1), # Vyincourd  Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_33", 1), # Etrosq     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_35", 1), # Haringoth  Castle
    # 5 edges

    (assign, ":center", "p_castle_2"),  # Malayurg   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_27", 1), # Rindyar    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_40", 1), # Uhhun      Castle
    # 5 edges

    (assign, ":center", "p_castle_3"),  # Bulugha    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_8",  1), # Jeirbe     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_10", 1), # Alburq     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_39", 1), # Slezkh     Castle
    # 5 edges

    (assign, ":center", "p_castle_4"),  # Radoghir   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_5",  1), # Tehlrog    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_18", 1), # Ismirala   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_19", 1), # Yruma      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_32", 1), # Knudarr    Castle
    # 6 edges

    (assign, ":center", "p_castle_5"),  # Tehlrog    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_18", 1), # Ismirala   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_32", 1), # Knudarr    Castle
    # 5 edges

    (assign, ":center", "p_castle_6"),  # Tilbaut    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_20", 1), # Derchios   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_27", 1), # Rindyar    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_32", 1), # Knudarr    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_37", 1), # Dramug     Castle
    # 5 edges

    (assign, ":center", "p_castle_7"),  # Sungetche  Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_19", 1), # Yruma      Castle
    # 3 edges

    (assign, ":center", "p_castle_8"),  # Jeirbe     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_10", 1), # Alburq     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_18", 1), # Ismirala   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_39", 1), # Slezkh     Castle
    # 5 edges

    (assign, ":center", "p_castle_9"),  # Jamiche    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_16", 1), # Almerra    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_21", 1), # Ibdeles    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_46", 1), # Weyyah     Castle
    # 4 edges

    (assign, ":center", "p_castle_10"), # Alburq     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_18", 1), # Ismirala   Castle
    # 4 edges

#   (assign, ":center", "p_castle_11"), # Curin      Castle
    # 2 edges

    (assign, ":center", "p_castle_12"), # Chalbek    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_34", 1), # Hrus       Castle
    # 2 edges

    (assign, ":center", "p_castle_13"), # Kelredan   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_25", 1), # Ryibelet   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_32", 1), # Knudarr    Castle
    # 4 edges

    (assign, ":center", "p_castle_14"), # Maras      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_35", 1), # Haringoth  Castle
    # 2 edges

    (assign, ":center", "p_castle_15"), # Ergellon   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_28", 1), # Grunwalder Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_31", 1), # Vyincourd  Castle
    # 4 edges

    (assign, ":center", "p_castle_16"), # Almerra    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_21", 1), # Ibdeles    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_22", 1), # Unuzdaq    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_24", 1), # Reindi     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_28", 1), # Grunwalder Castle
    # 5 edges

#   (assign, ":center", "p_castle_17"), # Distar     Castle
    # 1 edge
#   (assign, ":center", "p_castle_18"), # Ismirala   Castle
    # 6 edges

    (assign, ":center", "p_castle_19"), # Yruma      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_39", 1), # Slezkh     Castle
    # 6 edges

    (assign, ":center", "p_castle_20"), # Derchios   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_32", 1), # Knudarr    Castle
    # 3 edges

#   (assign, ":center", "p_castle_21"), # Ibdeles    Castle
    # 3 edges

    (assign, ":center", "p_castle_22"), # Unuzdaq    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_24", 1), # Reindi     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_46", 1), # Weyyah     Castle
    # 4 edges

#   (assign, ":center", "p_castle_23"), # Tevarin    Castle
    # 1 edge

    (assign, ":center", "p_castle_24"), # Reindi     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_26", 1), # Senuzgda   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_28", 1), # Grunwalder Castle
    # 7 edges

    (assign, ":center", "p_castle_25"), # Ryibelet   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_36", 1), # Jelbegi    Castle
    # 4 edges

#   (assign, ":center", "p_castle_26"), # Senuzgda   Castle
    # 2 edges

    (assign, ":center", "p_castle_27"), # Rindyar    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_37", 1), # Dramug     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_40", 1), # Uhhun      Castle
    # 6 edges

#   (assign, ":center", "p_castle_28"), # Grunwalder Castle
    # 6 edges

    (assign, ":center", "p_castle_29"), # Nelag      Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_38", 1), # Tulbuk     Castle
    # 2 edges

    (assign, ":center", "p_castle_30"), # Asugan     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_43", 1), # Sharwa     Castle
    # 2 edges

#   (assign, ":center", "p_castle_31"), # Vyincourd  Castle
    # 4 edges
#   (assign, ":center", "p_castle_32"), # Knudarr    Castle
    # 5 edges
#   (assign, ":center", "p_castle_33"), # Etrosq     Castle
    # 3 edges
#   (assign, ":center", "p_castle_34"), # Hrus       Castle
    # 2 edges
#   (assign, ":center", "p_castle_35"), # Haringoth  Castle
    # 4 edges
#   (assign, ":center", "p_castle_36"), # Jelbegi    Castle
    # 3 edges
#   (assign, ":center", "p_castle_37"), # Dramug     Castle
    # 3 edges
#   (assign, ":center", "p_castle_38"), # Tulbuk     Castle
    # 2 edges
#   (assign, ":center", "p_castle_39"), # Slezkh     Castle
    # 6 edges
#   (assign, ":center", "p_castle_40"), # Uhhun      Castle
    # 4 edges

    (assign, ":center", "p_castle_41"), # Jameyyed   Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_42", 1), # Teramma    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_47", 1), # Samarra    Castle
    # 4 edges

    (assign, ":center", "p_castle_42"), # Teramma    Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_45", 1), # Caraf      Castle
    # 3 edges

    (assign, ":center", "p_castle_43"), # Sharwa     Castle
    (call_script, "script_set_adjacency_between_centers", ":center", "p_castle_48", 1), # Bardaq     Castle
    # 4 edges

#   (assign, ":center", "p_castle_44"), # Durrin     Castle
    # 3 edges
#   (assign, ":center", "p_castle_45"), # Caraf      Castle
    # 2 edges
#   (assign, ":center", "p_castle_46"), # Weyyah     Castle
    # 3 edges
#   (assign, ":center", "p_castle_47"), # Samarra    Castle
    # 3 edges
#   (assign, ":center", "p_castle_48"), # Bardaq     Castle
    # 3 edges

#nodes =  48
#edges = 145

max edges per node     = 7
min edges per node     = 1
average edges per node = 6

most  common edges per node = 5
least common edges per node = 1, 7

Edge occurences: 2 11 13 13 15 14 2

And of course they are all subject to change.

 

[Dawiduh]

Man, quite oftopic, you're some serious coder. Congrats. When i'm off shlivovitsa I'll take a better look at what it's here. Respect!

 

[Zsar]

But... I did not even do anything! ... visible. Yet.
On it, of course, but struggling with such basic things as control outputs. Not quite qualifying, is it?

 

[Zsar]

Another prototype of graph API with Dijkstra's algorithm and stack-pathes.
This time, it actually has a chance to work. Having changed the node definition also means that a node is now thoroughly artificial and thus may hold additional data as a list - saves three lists and associated concurrency overhead from Dijkstra's algorithm.

... Last updated 22:27, 26.02.2013: handles start node separately to reduce an average half graph iteration into a maximal log(2, |graph|) operation

Spoiler: dependencies

##################
##  NODE SLOTS  ##
##################
slot_node_content     = 0
slot_node_distance    = 1
slot_node_predecessor = 2

  #script_create_datastruct
  # INPUT : none
  # OUTPUT: reg0 = new empty struct
  ("create_datastruct",[
    (spawn_around_party, "p_main_party", "pt_datastruct"),
    # move offmap
    (party_relocate_near_party, reg0, "p_temp_party", 1), # to prevent overwriting the spawn radius
    # initialise list size
    (party_set_helpfulness, reg0, 0) # default is 100
  ]),

  #script_copy_list
  # INPUT : arg0 = list-struct
  # OUTPUT: reg0 = new list-struct with same content
  ("copy_list",[
    (store_script_param_1, ":oldList"),

    (call_script, "script_create_datastruct"),
    # adopt size
    (party_get_helpfulness, ":size", ":oldList"),
    (party_set_helpfulness, reg0, ":size"),
    # adopt elements
    (try_for_range, ":index", 0, ":size"),
      (party_get_slot, ":element", ":oldList", ":index"),
      (party_set_slot, reg0, ":index", ":element"),
    (try_end)
  ]),

  #script_find_in_ascending_list
  # INPUT : arg0 = list-struct, arg1= element
  # OUTPUT: index, -1 if not found
  ("find_in_ascending_list",[
    (store_script_param_1, ":list"),
    (store_script_param_2, ":element"),

    (assign, ":left", 0),
    (party_get_helpfulness, ":size", ":list"),
    (assign, ":right", ":size"),
    (val_sub, ":right", 1),
    (try_for_range, ":unused", 0, ":size"), # unused will never reach more than log(2, size)
      (try_begin),
        (ge, ":right", ":left"),
          (store_add, reg0, ":left", ":right"),
          (val_div, reg0, 2),
          (party_get_slot, ":entry", ":list", reg0),
          (try_begin),
            (eq, ":element", ":entry"),
              # element found
              (assign, ":size", 0),
          (else_try),
            (gt, ":element", ":entry"),
              # index right of middle
              (store_add, ":left", reg0, 1),
          (else_try),
            # index left of middle
            (store_sub, ":right", reg0, 1),
          (try_end),
      (else_try),
        (assign, ":size", 0),
        (assign, reg0, -1),   # element not found
      (try_end),
    (try_end)
  ]),

  #script_find_smallest_in_list
  # INPUT : arg0 = list-struct, arg1 = relational operator script, arg2 = additional RO script data
  # OUTPUT: reg0 = smallest element, reg1 = index of smallest element
  ("find_smallest_in_list",[
    (store_script_param_1, ":list"),
    (store_script_param_2, ":betterThan"),
    (store_script_param, ":btParam", 3),

    (party_get_helpfulness, ":size", ":list"),
    (assign, reg1, 0),
    (party_get_slot, reg0, ":list", reg1),
    (try_for_range, ":index", 1, ":size"),
      (party_get_slot, ":nextElement", ":list", ":index"),
      (call_script, ":betterThan", reg0, ":nextElement", ":btParam"),
        # smaller element found
        (assign, reg0, ":nextElement"),
        (assign, reg1, ":index"),
    (try_end)
  ]),

  #script_remove_from_list_by_index
  # INPUT : arg0 = list-struct, arg1 = index
  # OUTPUT: none
  ("remove_from_list_by_index",[
    (store_script_param_1, ":list"),
    (store_script_param_2, ":begin"),

    (val_add, ":begin", 1),
    (party_get_helpfulness, ":size", ":list"),
    (try_for_range, ":index", ":begin", ":size"),
      (party_get_slot, ":element", ":list", ":index"),
      (val_sub, ":index", 1),
      (party_set_slot, ":list", ":index", ":element"),
    (try_end),
    (val_sub, ":size", 1),
    (party_set_helpfulness, ":list", ":size")
  ]),

  #script_pop_from_stack
  # INPUT : arg0 = list-struct
  # OUTPUT: reg0 = element
  ("pop_from_stack",[
    (store_script_param_1, ":list"),

    (party_get_helpfulness, reg0, ":list"),
    (val_sub, reg0, 1),
    (party_set_helpfulness, ":list", reg0),
    (party_get_slot, reg0, ":list", reg0)
  ])

# DEFINITIONS:
# a  graph is a list of nodes ascending by ID
# a  path  is a list of connected nodes in [destination, start[
# a  node  is a set  of edges
# an edge  is a 2-tuple of (node, weight)

# TECHNICALITIES:
# a node's content is stored in slot_node_content
# a node's slot_node_distance and slot_node_predecessor are used in script_find_shortest_path_between_nodes and should never be directly accessed
# nodes are stored in graph slots from [0, #nodes]
# use script_pop_from_stack to obtain the next destination from a path

scripts.extend([
  #script_cf_distance_greater_than
  # INPUT : arg0 = node1, arg1 = node2
  # OUTPUT: none
  # FAIL  : if node1(slot_node_distance) <= node2(slot_node_distance)
  ("cf_distance_greater_than",[
    (store_script_param_1, ":node1"),
    (store_script_param_2, ":node2"),

    (party_get_slot, ":node1", ":node1", slot_node_distance),
    (party_get_slot, ":node2", ":node2", slot_node_distance),
    (gt, ":node1", ":node2")
  ]),

  #script_find_shortest_path_between_nodes
  # INPUT : arg0 = graph, arg1 = node1, arg2 = node2
  # OUTPUT: reg0 = path from node1 to node
  # Dijkstra's algorithm
  ("find_shortest_path_between_nodes",[
    (store_script_param_1, ":graph"),
    (store_script_param_2, ":node1"),
    (store_script_param, ":node2", 3),

    # handle start node separately
    (call_script, "script_find_in_ascending_list", ":graph", ":node1"), # O(log(2, |graph|)) vs O(|graph|) via script_find_smallest_in_list
    (party_set_slot, ":node1", slot_node_distance, 0),
    (assign, ":node", ":node1"),
    # list of unreached nodes
    (call_script, "script_copy_list_without", ":graph", reg0),
    (assign, ":restNodes", reg0),
    # initialise distances
    (party_get_helpfulness, ":size", ":restNodes"),
    (try_for_range, ":index", 0, ":size"),
      (party_get_slot, ":index", ":restNodes", ":index"),
      (party_set_slot, ":index", slot_node_distance, 0x7FFFFFFF), # not quite infinity, but close enough
    (try_end),
    # hack a while-loop
    (assign, ":more", 1),
    (try_for_range, ":unused", 0, ":more"),
      (party_get_slot, ":distanceSoFar", ":node", slot_node_distance),
      (party_get_num_companion_stacks, ":size", ":node"),
      # process neighbors
      (try_for_range, ":index", 0, ":size"),
        (party_stack_get_troop_id, ":neighbor", ":node", ":index"),
        (call_script, "script_find_in_ascending_list", ":restNodes", ":neighbor"),
        (neq, reg0, -1), # neighbor not of interest
          (party_stack_get_size, ":weight", ":node", ":index"),
          (store_add, ":distance", ":distanceSoFar", ":weight"),
          (party_get_slot, ":weight", ":neighbor", slot_node_distance),
          (lt, ":distance", ":weight"), # shorter path to this node found
            (party_set_slot, ":neighbor", slot_node_distance, ":distance"),
            (party_set_slot, ":neighbor", slot_node_predecessor, ":node"),
      (try_end),
      # fetch next node
      (call_script, "script_find_smallest_in_list", ":restNodes", "script_cf_distance_greater_than"),
      (neq, reg0, ":node2"), # not there yet
        (call_script, "script_remove_from_list_by_index", ":restNodes", reg1),
        (assign, ":node", reg0),
        (val_add, ":more", 1), # always one step ahead of you
    (try_end),
    # construct the path
    (assign, reg0, ":restNodes"), # reutilise that datastruct
    (assign, ":more", 1),
    (try_for_range, ":index", 0, ":more"),
      # iterate through predecessors until node1 is reached
      (party_set_slot, reg0, ":index", ":node2"),
      (party_get_slot, ":node2", ":node2", slot_node_predecessor),
      (neq, ":node2", ":node1"),
        (val_add, ":more", 1),
    (try_end),
    (party_set_helpfulness, reg0, ":more")
  ])
])

... Has anyone ever written an inlining tool for scripts? Would have a huge application potential for this kind of stuff.

 

[Zsar]

(Originally contained incomplete and now obsolete code. May hold spill from above post in the future.)

 

[Mad Vader]

I have a feeling (again) you are using a modern carrier task force to kill a rabbit and over-engineering solutions to ordinary problems. The KISS principle would get you the same results with much less pain.

Spoiler: Rant

I've seen this a lot in good engineers. Their thinking is not result-oriented, their challenge is to design complex mechanisms as an end to itself. Case in point: you didn't even present possible uses - caravan trading? strategic AI improvements? How?
What can be done with a carrier task force that you can't do with a hunting rifle? Do you want to kill the rabbit or just build a shiny new task force?

But in the end, you do what you feel needs doing.

Other comments:
- Storing center data like adjacent centers, distances and such is best done in new center slots, not global arrays like dummy parties, which I assume you are doing.
- Never tried call_script with a variable script name, but it should work. Surprised that you didn't  test it before posting code? Seems crucial. Anyway, it's easily replaced by conditional blocks depending on a boolean input parameter, and less room for bugs that way.
- Note that party_force_add_members has a bug in the current Warband engine - don't know if they are fixing that for 1.155. Force-adding a new troop in a party with more than 32 troop types will wipe out the "excess" troops.

 

[cmpxchg8b]

- Never tried call_script with a variable script name, but it should work. Surprised that you didn't  test it before posting code? Seems crucial. Anyway, it's easily replaced by conditional blocks depending on a boolean input parameter, and less room for bugs that way.

It works.

 

[Zsar]

- Note that party_force_add_members has a bug in the current Warband engine - don't know if they are fixing that for 1.155. Force-adding a new troop in a party with more than 32 troop types will wipe out the "excess" troops.

Crucial information.
It would be really, really great if such unexpected behaviour were documented. But where is it?
Thank you in any case, now I know; not like with the message system.

It works.

Now that be honeyed words in my eyes... ew. Great news, thank you.

[Y]ou didn't even present possible uses - caravan trading? strategic AI improvements? How?

See, you instinctively found the obvious answer, already.
Without knowing whether it can be done and whether it then be performant enough to be employed, I wished not to promise apples I could mayhap not actually pluck, but here we go:

• Parties shall travel in natural ways and paths.
  • Rest at night.
  • Prefer to rest in walls.
  • Travel in steps from one walled center to the next.
    • for lords: Travelling Salesman problem for recruitment path on subgraph of owned centers; might want to stop at not-owned ones for other business
    • for caravans: try trade along the way, abort if intent has been fulfilled before target reached
  • If dusk imminent, wait at the current center and resume travel at dawn.
  This is a graph traversal problem. All algorithms of relevance are older than I am.

• Factions shall weight strategic position of a center into their target selection. Possible questions:
  • Is faction territory connected?
    • Which centers of whom lie between our connected subgraphs?
    • How many centers does the shortest path between our connected subgraphs contain?
  • For all targets: How many own centers border it? (inner line)
  • For all targets: How many other targets border it? (outer line)
  • Special case: Do only <threshold> own and other's centers border it? (bottleneck)
  • Is there a border to others? (before bothering to do expensive calculations; update on center-owner change)
  • How many third's centers lie on shortest path between our's and their centers? (wedge)
  These are ALL graph traversal problems, so to solve them ALL AT ONCE I want my graph!

... But I am indeed minorly flexible, so if you proposed a more efficient solution to deal with mountains, bridges, forests, I might just try it.

This draft raises the following requirements:

• A center must know its adjacent centers.
• A center is adjacent to another center, if travel between them would not sensibly include a third center.
• An operation must exist to split the center graph into several connected graphs per faction.
  • The number of connected graphs per faction must be variable.
• An operation must exist to plot a shortest path between two arbitrary centers.
  • A path may contain only centers of a certain type (only towns, only walled centers, only towns and villages, only castles) and thus be not a subgraph of the original graph.
  • An edge must be weighted to account for terrain and not-time related modifiers (risk...)
• An operation must exist to check for a given path and center whether the path could be prolonged or redirected to include the center with only <threshold> added weight and return the new path.

There you got your specification; show me how it's done.

Spoiler: Rant of my own

Well, you know, when I started scripting for Warcraft 3, all kinds of people had already established all kinds of ways to implement traditional high-level data structures into the local scripting language.
There was a singly-linked list, a stack... These were implemented by abusing the native datatype Location, a 2-tuple of integer values by virtue of the infamous "return bug": the ability to pass every data object as an untyped pointer by writing two return statements in a row.

... This allowed to deploy algorithms with JASS as one would with Java, Python, C - made life easier and allowed for the efficient execution of weird and weirdest stuff.

Truth be told, after almost four years I had kind of expected to meet a similarly advanced coder crowd for M&B. People who know and tell how to get the most out of the script engine at hand. Instead I meet with what seems like a corporative attitude: "I have not profitted yet, it must be bad." It is a game! There are First Person Shooter maps for Wc3! Why would anyone do something so unefficient - a dedicated shooter would surely be much better!? Well, someone wanted to see if he could. And had a crow that cheered him on. ... I seem a nostalgic dodderer by now, eh? Or, what, a "troll"? Most basic courtesies seem to belong to "lost knowledge of the glorious past" nowadays.

Somewhen in the last half-decade it became damn hard to find nice places on the net in general. Everywhere I go nowadays appears like... small secluded villages full of reactionary old people. Wary of outsiders, proud of tradition, generally unenthusiastic.
- Slowly, I start to become more like that myself. Jaded. Callous. It seems to be the new trend.

It would all be justified, if a hundred people had asked the same questions, proposed the same ideas before and this had been well documented and a central place for such knowledge well sorted and filed existed. I have asked for directions to such a place and received no answer, so I feel my own patience wane.

... I kind of expect a solution now, by the way. You have been around for a long time, you have involved yourself into complex projects in the past. You have the experience, you have the knowledge and I am eager to listen. All you have to do is talk...

There are other applications, of course: Task stacks. Limited information for everyone. Information propagation. Emergency solution trees.
None can I assess easily enough to just tell whether it be feasible or not.

 

[Mad Vader]

I'm sorry there's no documentation in one place. On the behalf of the community and Taleworlds, I apologize we are not up to WC3 standards.

Whatever I know, I found out by black box testing, and some useful gems here in the Forge. I assume everyone else does or should do the same. It's the only thing you can do, really, once you get into advanced scripting. There are no advanced scripting tutorials and very little user documentation, not that there weren't several attempts at creating a central repository of knowledge.
I found this one helpful though: http://forums.taleworlds.com/index.php/topic,213060.0.html.

Now some comments:
- Parties shall travel in natural ways and paths; rest at night; prefer to rest in walls...
This is a flavor-only feature, not really useful, but it supports your case.
It does lower the gameplay possibilities at night, so it's not all good. Some map parts may become empty and unpopulated by regular parties. Maybe it means we won't be able to fight lords or caravans in woods or other "unnatural" terrain.
It also adds a strain on the CPU, as your party dispatcher simple trigger must frequently oversee all the parties, except maybe some bandits.
Besides, there are map design tricks like bridges and mountain passes to direct the traffic in a certain way.
- Factions shall weight strategic position of a center into their target selection...
This is more interesting and useful. The strategic AI does take into account how close some center is, but giving priority to connecting "unconnected" centers would improve the strategic AI.
As for the solution, you can check if an enemy center is sufficiently "between" some of yours (the distance between them is at most slightly less than the sum of distances between each of them and the enemy center). Simpler and without graphs too.
Simple graphs of adjacent centers can be useful to establish bordering centers and have some more complex AI decision-making, but I can't see much use for graph manipulation operations.

The problem I raised is that you should start with a particular gameplay-related problem, and work your way to a solution, not the other way around. Otherwise, you risk ending up with a general purpose library that no one uses - and we don't want that, right? You can make complex, useless libraries just for the fun of it, of course, there's nothing too wrong about it.

There are not many advanced modders here (if any) that would appreciate the glory of a general purpose graph manipulating library for their more advanced projects. In fact, many of them would prefer to code their own custom and more compact solution, as others like coding challenges too.

The best you can do, in my opinion, is to make a desirable gameplay feature (released as OSP code) that the newbies (and Floris ) could then stuff into their mods. For example, the strategic AI is a somewhat unexplored area, so improving it would be beneficial to the community and the players. And you can develop your own set of libraries to support your feature, if that's what you find most fun.

 

[Zsar]

Eh, I quit the scene years ago, when the site I had frequented was integrated into the Hive Workshop. That was... ugh... no idea when, but Blizzard put out three more patches thereafter.
There was no such thing as a central documentation (say: a Wiki) there either. Just people who knew and who shared, lively enough that it was not missed... much.
... Apropos Wiki, what about this one? It looks pitiful, but that is no inherent trait.

Now, we have to establish a common ground on the concept of usefulness, desirability et al. as it is obvious our understandings differ.
Game mechanics dictate both the set of possible actions as well as the quality of any given action within the game world. Quality of an action, that is of course the added wealth it promises to the actor (diminished by the chance of this wealth to actually be added and the chance of outside intervention causing instead a net loss of wealth) divided through the amount of time necessary to cause the addition.

If entities in the game act blatantly unqualitative, the game grow unappealing: The world work badly without a player already, no need to introduce one and make matters worse.

Spoiler: example

In the M&B:W world, trading promises only money, which is therefore the wealth in question to judge its quality.
Wished one to trade, one would surely pick a place to start - conveniently where one is right now or somewhere nearby if no profit seems likely with the goods at hand - and a place to finish, where the goods attained fetch the greatest price attainable.
However, there are several factors that make this plan alone look like a bad idea:

• There are usually not enough trade goods available to fill up and yet sell with considerable profit at the destination. Causes are:
  • quantitative lack of one good
  • lack in diversity of goods that actually fetch a win on this route
  • value loss due to shipment size
• The trade run can thus be improved by visiting additional centers:
  • to compensate value loss of too large shipments
  • to acquire additional goods for too small shipments
  but as both directions are possible, it is obviously still beneficial in case of the ideal shipment.

Yet, the time wherein money is accumulated is important too. Therefore, centers other than start and close must add relatively little to the distance travelled: They have to lie aside the path, simplest: on the path.

The 1.153 trader therefore acts irrationally and always in the same manner. It is a detriment to the game world.

I desire, in short, an AI that acts sensible (but not optimal) within the confines of its world.
What do you find desirable?

It does lower the gameplay possibilities at night, so it's not all good. Some map parts may become empty and unpopulated by regular parties.

It is the desired effect, I must confess:
The night be there to rest, read books, to heal. There is a time compression feature in the game and a night is shorter than the turn of some 4X games (Space Empires 5 comes to mind). Accelerated time also makes the player susceptible to ambush - at least I have successfully evaded everything nasty the game would throw at me for literal years. This creates an unhealthy imbalance between player character and its supposed peers.
Scarcely populated spaces, then, are already reality - say everything east of Tulga. They are not, however, perceptible for anything but the player. A simple count of visitors would denote a center node as more or less economically important, the AI could be made aware of and gain a need to secure important trade routes. By dynamically weighting edges with a risk factor, then, an important trade route may actually become deserted through ongoing warfare. Which the AI may then notice and shift its effort, follow the flow of wealth.
Natural. Beautiful. Captivating.

Maybe it means we won't be able to fight lords or caravans in woods or other "unnatural" terrain.

This would not be WAD, I concur. It would have to be spotted and corrected.

It also adds a strain on the CPU, as your party dispatcher simple trigger must frequently oversee all the parties, except maybe some bandits.

This is a worry of mine. In a multi-threaded environment I would employ interrupts to rid myself of a constant-interval based system in favour of something that balances itself (by virtue of the thread implementation which were of no concern to me). This is obviously not possible here.
Why, oh why did they not simply embed Python! "Vampires: The Masquerade" used Java as a scripting language...
I dare write that there be no good solution to this problem. One has to implement and see whether the performance at hand suffices or not.

Now, I have a question about this whole "OSP" ordeal. It has so far been my understanding that if I wished for some not to use my code, I would not post it where they can reach. The idea to show it around without an implicit understanding that it may be employed frankly appears ridiculous, the act uncourtly in a most scurrilous way.
But apparently things are seen differently here. I should then transfer everything that another one be allowed to touch and use into this "OSP" section, yes? Would that mean that people be not actually allowed to play with code such as that posted here, which is in no working condition but a draft in need of completion and revision? Would it further mean that, if another one had posted code which works not, as it desired help to make it so, I may have only helped if I saw the fault but not if it required to test it on my system (which would mean to employ it which in turn were forbidden)?
A quaint thought that.

 

[xenoargh]

Basically, if it's posted here, it's not legally fair game, but if it's useful, expect it to show up elsewhere.  OSP is our version of Open Source; for code, it's usually construed as MIT license or as Creative Commons Credit Required, depending on the modder's statements of intent.  Releasing source as OSP without clear instructions otherwise is construed as MIT; we give away a lot of code here.

I desire, in short, an AI that acts sensible (but not optimal) within the confines of its world.

I think that you're going to hit a lot of walls on this, starting with the fact that the underlying economy doesn't work well and really doesn't make much sense, and ending with the sheer complexity of the existing strategic AI code, which is a sprawling, complex mess.

TBH, my frank advice on this (as one of the few who've touched this area much, and all my public code is OSP) is that you've got two real choices if you want to keep your scope in "this year" category, even if you're a fairly fast coder and have a solid gameplan:

1.  Start from ground zero and write a new strategic AI.  Really messy, largely because so many other things wander in and out of it or depend upon it in some way, like conversation states.  I've thought about doing it several times, but it keeps looking out-of-scope to me.  Would love to see a much-simplified approach to Lord behavior and a cleaner, easier-to-deal-with state machine with less real complexity under the hood and a streamlined approach to conversation trees (seriously, go look into that mess and you'll see why it's out of scope for me, lol).

2.  Ditch the over-complex "economy" that is neither a good economic simulation nor is it a good base to build a better one upon.  I did that quite some time ago, but my core interests aren't in this area of game design so while a model exists, it's the bare minimum and it cheats to keep Lords intact.

I really honestly think that trying to regulate movement behavior of Parties in general past some very basic things is going to cause you more trouble than it may be worth.  There are issues that you'll hit with hard-coded AI behaviors (for example, wandering off to fight people in range) that will often prevent it from discharging its current missions in a timely-enough manner to result in really fundamental changes.  Moreover, there are important game-design considerations; if the Lords tend to head into town at night, the player's going to take full advantage of that and burn the villages then, amongst other things; you'll have to counter that and pretty soon you're in a huge messy battle between realism and AI responsiveness and the engine's quirks. 

Anyhow, have fun. 

One last note:  the graph behavior isn't really necessary for a lot of this; a simple state-machine that merely checks distance to nearest town / village each hour and will set it as the destination for the Party (with the main goal being kept in a Party slot if needbe, based on Template checks) if hour is between some values should be sufficient to generate the behavior desired. 

Lords are a wee bit tricky, however; if they're currently just roaming about, they will be fine, but they are very frequently not really roaming about, but have a mission that they're just not getting to atm because they're too busy chasing bandit parties they'll never catch    Touching their goals can screw up their strategic state machines, as they'll never arrive at the destination earlier specified, etc.  I would be extremely cautious about touching them without reading the relevant code in its entirety.

 

[Zsar]

• A simple state-machine that merely checks distance to nearest town / village each hour and will set it as the destination for the Party (with the main goal being kept in a Party slot if needbe, based on Template checks) if hour is between some values should be sufficient to generate the behavior desired.

  So...
  • Select target.
  • While not there:
    • Enumerate valid centers within <range threshold>.
    • Compare vector angles between enumerated centers and target.
      • If target in valid centers, travel to target.
      • Else, travel to valid center with least angle deviation to target.
  
  The check for a valid center would have to loop through range increments, similar to my "script_calculate_center_adjacencies". However, the only way to fetch parties within an increment seems to be "store_random_party_in_range" - how would one ensure completeness? If it is a generic pseudorandom sequence, the same party may be chosen arbitrarily often in succession.
  ... Approximating would suffice in this case, but how to factor in the terrain?
  How to detect, that
  • Ismirala Castle is on the path from Sargoth to Wercheg (divergence by more than 90°),
  • Senuzgda Castle is not on the path from Dhirim to Uxkhal (divergence by ~20°),
  • Malayurg Castle not between Ichamur and Dhirim,
  • Derchios Castle between Uxkhal and Dhirim,
  • etc... ?
  I can see, though, how it actually might be more performant to build subgraphs ad hoc using this approach, to solve the strategic calculations and provide dynamic edge weighting.
  
  

  Start from ground zero and write a new strategic AI.

  Even ripping out the thing from an otherwisely vanilla MS is a huge task. It has not been mapped out by anyone, I assume?

  wandering off to fight people in range

  Personalities are defined in party_templates... It is possible to add templates to an existing party, but not to remove them.
  If a party had one template with a given personality and then got another one with a different personality, how would these interact? Overwrite? Binary or? Binary and? Integral addition? Nothing?
  If now, the party received a template it already has, would this act like receiving a new template in terms of personality interaction or be ignored after the first time (so "add peaceful template"-"add aggressive template"-"add peaceful template" would equal "add_peaceful-template"-"add aggressive template")?

 

[Mad Vader]

Have you taken a peek at the strategic AI code? You should. It is rather grand. See also motomataru's thread with his fixes and tweaks: http://forums.taleworlds.com/index.php/topic,248544.0.html

The personalities are lord personalities (martial, upstanding...) and are used frequently to guide the lord AI - you are talking about party "personalities" (courage, aggression, helpfulness), those are overridden in the AI code, depending on the lord's role in a campaign, or his personality.

If I were to take on the strategic AI, I would first take the time to read the code and understand it, especially on a conceptual level. Then think about how would it get better, and only then rip it out (if necessary) and change it.

 

[Zsar]

Have you taken a peek at the strategic AI code? You should. It is rather grand.

Lax coding conventions and the "too-many-cooks"-syndrome had a child and it is ugly!
First I will have to reformat it: proper indentations and sensible paragraphs.
Then I will have to map it: static call graph.
Then I will have to interpret it: semantic modules.
... Somewhere along the line I would probably lose my faith and throw the whole thing out by virtue of simple recursive removal. Then I were in need to replace the whole functionality before I can play my game.

Not quite sure whether I want to do this or not. But it is not as if I could hope for someone else to do the work for me, is it?

... Anyway, before I am not sure what to replace it with how, I will not touch it. Regarding that, I have found an elegant solution to the bridge problem:

  ("Bridge_1","{!}1",icon_bridge_snow_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(39.37, 65.10),[], -44.8),
  ("Bridge_2","{!}2",icon_bridge_snow_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(56.44, 77.88),[], 4.28),
  ("Bridge_3","{!}3",icon_bridge_snow_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(70.87, 87.95),[], 64.5),
  ("Bridge_4","{!}4",icon_bridge_snow_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(93.71, 62.13),[], -2.13),
  ("Bridge_5","{!}5",icon_bridge_snow_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(11.02, 72.61),[], 21.5),
  ("Bridge_6","{!}6",icon_bridge_b|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-8.83, 52.24),[], -73.5),
  ("Bridge_7","{!}7",icon_bridge_b|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-29.79, 76.84),[], -64),
  ("Bridge_8","{!}8",icon_bridge_b|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-64.05, -6),[], 1.72),
  ("Bridge_9","{!}9",icon_bridge_b|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-64.95, -9.60),[], -33.76),
  ("Bridge_10","{!}10",icon_bridge_b|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-75.32, -75.27),[], -44.07),
  ("Bridge_11","{!}11",icon_bridge_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-24.39, 67.82),[], 81.3),
  ("Bridge_12","{!}12",icon_bridge_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-114.33, -1.94),[], -35.5),
  ("Bridge_13","{!}13",icon_bridge_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-84.02, -7),[], -17.7),
  ("Bridge_14","{!}14",icon_bridge_a|pf_is_static|pf_always_visible|pf_no_label, no_menu, pt_none, fac_neutral,0,ai_bhvr_hold,0,(-23.36, 75.8),[], 66.6),

You see it too, do you not? I need not spell it out.

This leaves the angle problem. An additional condition must be found, I guess.

The personalities are lord personalities [...] - you are talking about party "personalities" [...], those are overridden in the AI code [...]

I refer to

#personality modifiers:

[...]

soldier_personality = aggressiveness_8 | courage_9
merchant_personality = aggressiveness_0 | courage_7
escorted_merchant_personality = aggressiveness_0 | courage_11
bandit_personality   = aggressiveness_3 | courage_8 | banditness

So, "personality modifiers" would have been the appropriate term. I apologise.
... Helpfulness is the only one that can explicitely be set.

See also motomataru's thread [...]

Yes, I had a look when it was bumped two days ago. Contains little information. But I may use the source to compare to vanilla code; if I am in luck, it might even be nicely commented.

--

... Look what I dug up when reviving my posts for the OSP Forum!
Ha, this really haunts me! Had totally forgotten...

 

[xenoargh]

I think that the angle problem's going to be irrelevant most of the time, and it won't help with edge cases, where the shortest linear distance will result in a longer pathfinding distance.  Angle won't really help you there- something may be at a perfect angle and be closest, for example, but have mountains or a river in the way. 

Theoretically, these cases could be tested for (by moving a Party to a point along the line and checking the terrain types) but it's too expensive for a check that's supposed to get performed a lot.  I think that none of it's worth bothering with; in most cases, if you simply check the Party every hour, it's night-time, they aren't camped yet and there is something close by to go to, eventually it will find a valid resting-place even if its first target is in a silly place, pathfinding-wise.

Lax coding conventions and the "too-many-cooks"-syndrome had a child and it is ugly!
First I will have to reformat it: proper indentations and sensible paragraphs.
Then I will have to map it: static call graph.
Then I will have to interpret it: semantic modules.
... Somewhere along the line I would probably lose my faith and throw the whole thing out by virtue of simple recursive removal. Then I were in need to replace the whole functionality before I can play my game.

Yeah, that's pretty much been my problem, lol.  I know it could be written more simply and clearly; most of what it's doing, on the grand scale, is actually pretty simple.

That said, it's what really runs most of the show, in terms of Lord behaviors.  In order to make them do anything new, it must be messed with.

 

[Zsar]

As there seems to be no proper way to solve the angles problem, which is exactly that angle alone does not suffice as an indicator of whether a center is a useable intermediate step on the way to glory; and as I felt a bit frisky, I have completed a proper prototype (updated draft post) of this whole graph ordeal.
My design is no longer thread-safe, but I do not think that matters.

Once I have recovered a bit, I may test it... or start mapping the strategic AI... or do whatever strikes my fancy by then, unless it escaladed the next woody plant with escape speed.

 

[cmpxchg8b]

My design is no longer thread-safe, but I do not think that matters.

It doesn't. Warband game logic (including scripting) is single-threaded.