Welcome to Keen Software House Forums! Log in or Sign up to interact with the KSH community.
  1. You are currently browsing our forum as a guest. Create your own forum account to access all forum functionality.

Code to get localgrid (and remote grids) Added: Blocks

Discussion in 'Programming Released Codes' started by Wicorel, Jan 28, 2017.

Thread Status:
This last post in this thread was made more than 31 days old.
  1. Wicorel Senior Engineer

    Messages:
    1,242
    Now that we have piston and rotor connected grid info, I'e finished my code to walk the grids and make lists of what's local and what's not.

    This allows a PB to find out which grids are 'local' grids and which grids are only connected via connector.

    It works by:
    1. Get list of all blocks
    2. Walk the list and make list of all (unique) grids
    3. Assume grid that contains active PB itself is 'local'
    4. When adding a grid to local list:
      • Walk the grid and search for rotors and pistons and add to local any grid connected FROM this grid
      • Walk all grids that are have a rotor or piston connected TO that grid
    Then walk all connectors on local grids and add grids connected to dockedgrids list.


    Edit Mar 19 2017: Update code for fix in piston walking. Also added calcGridSystemChanged() function to say when # of blocks on grid system has changed.
     
    Last edited: Mar 19, 2017
  2. Wicorel Senior Engineer

    Messages:
    1,242
    Here is my code for getting (lists of) blocks.

    It has three main functions that it provides:

    1. List<IMyTerminalBlock> GetTargetBlocks<T>(string Keyword = null)
    2. List<IMyTerminalBlock> GetBlocksContains<T>(string Keyword = null)
    3. List<IMyTerminalBlock> GetBlocksNamed<T>(string Keyword = null)
    The first returns blocks that Start with the specified name. The second returns blocks that contain the specified string (for example "[LCD]"). The last one returns a list that matches the name exactly.


    Edit Mar 29,2017: Init grids on get if needed. use cached block list from grids
     
    Last edited: Mar 19, 2017
  3. Burillo Junior Engineer

    Messages:
    648
    I think your code is a bit arcane for the problem it tries to solve. It's basically a simple graph problem. In BARABAS v1.5, i've rewritten my grid detection code to be graph-based, and it solves the problem of finding local/remote grids quite nicely, while avoiding many pitfalls inherent to loop-based solutions such as yours. It's a bit of work to rip it out of BARABAS, but here it is:

    Code:
    List < IMyCubeGrid > local_grids = null;
    List < IMyCubeGrid > remote_grids = null;
    
    // grid graph edge class, represents a connection point between two grids.
    public class Edge < T > {
    public T src {get; set;}
    public T dst {get; set;}
    }
    
    // comparer for graph edges - the way the comparison is done means the edges are
    // bidirectional - meaning, it doesn't matter which grid is source and which
    // grid is destination, they will be equal as far as comparison is concerned.
    public class EdgeComparer < T > : IEqualityComparer < Edge < T > > {
    public int GetHashCode(Edge < T > e) {
      // multiply src hashcode by dst hashcode - multiplication is commutative, so
      // result will be the same no matter which grid was source or destination
      return e.src.GetHashCode() * e.dst.GetHashCode();
    }
    public bool Equals(Edge < T > e1, Edge < T > e2) {
      if (e1.src.Equals(e2.src) && e1.dst.Equals(e2.dst)) {
      return true;
      }
      if (e1.src.Equals(e2.dst) && e1.dst.Equals(e2.src)) {
      return true;
      }
      return false;
    }
    }
    
    // our grid graph
    public class Graph < T > {
    public Graph() {
      cmp = new EdgeComparer < T >();
      v_edges = new Dictionary < T, HashSet < Edge < T > > >();
      r_edges = new HashSet < Edge < T > >(cmp);
    }
    
    // add an edge to the graph
    public void addEdge(T src, T dst, bool is_remote) {
      var t = new Edge<T>();
      t.src = src;
      t.dst = dst;
    
      // remote edges don't need to be added to list of edges
      if (is_remote) {
      r_edges.Add(t);
      return;
      }
    
      // add edge to list of per-vertex edges
      HashSet < Edge < T > > hs_src, hs_dst;
      if (!v_edges.TryGetValue(src, out hs_src)) {
      hs_src = new HashSet < Edge < T > >(cmp);
      v_edges.Add(src, hs_src);
      }
      if (!v_edges.TryGetValue(dst, out hs_dst)) {
      hs_dst = new HashSet < Edge < T > >(cmp);
      v_edges.Add(dst, hs_dst);
      }
      hs_src.Add(t);
      hs_dst.Add(t);
    }
    
    // get all grids that are local to source grid (i.e. all grids connected by
    // rotors or pistons)
    public List < T > getGridRegion(T src) {
      // if there never was a local edge from/to this grid, it's by definition
      // the only grid in this region
      if (!v_edges.ContainsKey(src)) {
      return new List < T >() {src};
      }
      // otherwise, gather all vertices in this region
      var region = new List<T>();
      var seen = new HashSet<T>();
      var next = new Queue<T>();
      next.Enqueue(src);
      while (next.Count != 0) {
      var g = next.Dequeue();
      if (!seen.Contains(g)) {
        var edges = v_edges[g];
        foreach (var edge in edges) {
        next.Enqueue(edge.src);
        next.Enqueue(edge.dst);
        }
        seen.Add(g);
        region.Add(g);
      }
      }
      return region;
    }
    
    // this must be called after adding all edges. what this does is, it removes
    // edges that aren't supposed to be there. For example, if you have grids
    // A, B, C, local edges A->B and B->C, and a remote edge C->A, there is a path
    // from C to A through local edges, so the remote edge should not count as an
    // actual "remote" edge, and therefore should be removed.
    public void validateGraph() {
      var to_remove = new HashSet < Edge <T> >(cmp);
      var seen = new HashSet<T>();
      foreach (var edge in r_edges) {
      var next = new Queue<T>();
      next.Enqueue(edge.src);
      next.Enqueue(edge.dst);
      while (next.Count != 0) {
        var g = next.Dequeue();
        if (!seen.Contains(g)) {
        var region = new HashSet<T>(getGridRegion(g));
        seen.UnionWith(region);
        // find any edges that are completely inside this region, and remove them
        foreach (var e in r_edges) {
          if (region.Contains(e.src) && region.Contains(e.dst)) {
          to_remove.Add(e);
          }
        }
        }
      }
      }
      foreach (var e in to_remove) {
      r_edges.Remove(e);
      }
    }
    
    // get all neighboring (connected by connectors) grid entry points
    public List < Edge < T > > getGridConnections() {
      return new List < Edge < T > >(r_edges);
    }
    
    // our comparer to use with all sets
    EdgeComparer < T > cmp;
    // list of all edges
    HashSet < Edge < T > > r_edges;
    // dictionaries of edges for each vertex
    Dictionary < T, HashSet < Edge < T > > > v_edges;
    }
    
    IMyCubeGrid getConnectedGrid(IMyShipConnector c) {
    if (c.Status != MyShipConnectorStatus.Connected) {
      return null;
    }
    // skip connectors connecting to the same grid
    var o = c.OtherConnector;
    if (o.CubeGrid == c.CubeGrid) {
      return null;
    }
    return o.CubeGrid;
    }
    
    IMyCubeGrid getConnectedGrid(IMyMotorBase r) {
    if (!r.IsAttached) {
      return null;
    }
    return r.TopGrid;
    }
    
    IMyCubeGrid getConnectedGrid(IMyPistonBase p) {
    if (!p.IsAttached) {
      return null;
    }
    return p.TopGrid;
    }
    
    // getting local grids is not trivial, we're basically building a graph of all
    // grids and figure out which ones are local to us.
    void findGrids() {
    // list of local blocks
    var local_blocks = new List < IMyTerminalBlock > ();
    // all possible connection points
    var pistons = new List < IMyTerminalBlock > ();
    var rotors = new List < IMyTerminalBlock > ();
    var connectors = new List < IMyTerminalBlock > ();
    
    // get all blocks that are accessible to GTS
    GridTerminalSystem.GetBlocks(local_blocks);
    
    // for each block, populate respective object list if it's one of the objects
    // we're interested in
    foreach (var b in local_blocks) {
      if (b is IMyShipConnector) {
      connectors.Add(b);
      } else if (b is IMyPistonBase) {
      pistons.Add(b);
      } else if (b is IMyMotorBase) {
      rotors.Add(b);
      }
    }
    
    // now, build a graph of all grids
    var gr = new Graph<IMyCubeGrid>();
    
    // first, go through all pistons
    foreach (IMyPistonBase p in pistons) {
      var connected_grid = getConnectedGrid(p);
    
      if (connected_grid != null) {
      // grids connected to pistons are local to their source
      gr.addEdge(p.CubeGrid, connected_grid, false);
      }
    }
    
    // do the same for rotors
    foreach (IMyMotorBase rotor in rotors) {
      var connected_grid = getConnectedGrid(rotor);
    
      if (connected_grid != null) {
      // grids connected to rotors are local to their source
      gr.addEdge(rotor.CubeGrid, connected_grid, false);
      }
    }
    
    // do the same for connectors
    foreach (IMyShipConnector c in local_connectors) {
      var connected_grid = getConnectedGrid(c);
    
      if (connected_grid != null) {
      // grids connected to connectors belong to a different entity
      gr.addEdge(c.CubeGrid, connected_grid, true);
      }
    }
    
    // make sure we remove all unnecessary edges from the graph
    gr.validateGraph();
    
    // this list will contain all local grids
    local_grids = gr.getGridRegion(Me.CubeGrid);
    
    // this list will contain all remote grids
    remote_grids = new List<IMyCubeGrid>();
    
    // now, go through all connector-to-connector grid connections
    var connections = gr.getGridConnections();
    // we don't want to count known local grids as remote, so mark all local grids
    // as ones we've seen already
    var seen = new HashSet < IMyCubeGrid > (local_grids);
    
    foreach (var e in connections) {
      // we may end up with two unknown grids
      var edge_grids = new List<IMyCubeGrid>(){e.src, e.dst};
    
      foreach (var e_g in edge_grids) {
      // if we found a new grid
      if (!seen.Contains(e_g)) {
        // get all grids that are local to it
        var r_grids = gr.getGridRegion(e_g);
        seen.UnionWith(r_grids);
        remote_grids.AddRange(r_grids);
      }
      }
    }
    }
    
    you can also easily extend it to store information about remote grids (for example, it's easy to store information about how many ships you have, as getGridConnection() will return all connections to remote grids).

    also, your second snippet misses a definition of localGridFilter :)
     
    Last edited: Feb 15, 2017
  4. Whiplash141 Junior Engineer

    Messages:
    958
    What pitfalls does this (incredibly confusing) graphical method solve?
     
  5. Burillo Junior Engineer

    Messages:
    648
    mostly having to do with scenarios like attaching a connector to a piston (i.e. grids that may appear remote but are actually local). and it's only "incredibly confusing" if you've never done graph theory :p
     
    Last edited: Feb 12, 2018
Thread Status:
This last post in this thread was made more than 31 days old.