生成与邻居有关的对象坐标

Question

我正在制作一个游戏，其中我有随机生成的物体。我还有一个表格，其中包含哪些对象彼此接近的数据，比如在200px的范围内 - 让我们称它们为邻居。我想要的是生成并分配所有可用对象的坐标，以便反映这种关系。我想查看它们的结构。 我做了一个贪婪的算法。这工作非常缓慢。并有时会卡住。有没有人有更好的方法呢？ - 坐标可以通过试验和错误动态分配没有问题。 下面是当前的代码类。

/** 
    * biggest problem 
    * */ 
    public void assignInitialCoords(MyObject[] objects) 
    { 
     objects[0].setxCoor(rand.nextInt(1000)); 
     objects[0].setyCoor(rand.nextInt(1000)); 

     for(int i=0; i<objects.length; i++) 
     { 
      ArrayList<MyObject> neighs = objects[i].getNeighbours(); 
      System.out.println("Assigning " + objects[i].getId() + "'s coors"); 
      setNonNeighborCoords(objects, i); 
      setNeighborCoordinates(objects, i, neighs); 
      System.out.println(objects[i].getId() + "(" + objects[i].getxCoor() + ", " + objects[i].getyCoor() + ")\n"); 
     } 
    } 

的类

import java.util.ArrayList; 
import java.util.HashMap; 

public class MyObject 
{ 
    public ArrayList<MyObject> neighbours; 
    public ArrayList<MyObject> nonNeighbours; 
    public double fov = 360; 
    public double sRange = 100, xCoor, yCoor; 
    boolean isClustered = false; 
    public String id; 
    //Cluster[] clusters; 


    public MyObject() 
    { 
     neighbours = new ArrayList<MyObject>(); 
     nonNeighbours = new ArrayList<MyObject>(); 
    } 

    /** 
    * Find neighbours for this Object given a relations table 
    * example: if a MyObject has id A, and neighbor is B, then the key can be either: A_B or B_A 
    * Both represent the same relation, so we only need to check it once 
    * */ 
    public void findNeighbours(HashMap<String, Integer> table, MyObject[] objects) 
    { 
     for (int i = 0; i < objects.length; i++) 
     { 
      String key1 = getId() + "_" + objects[i].getId(), key2 = objects[i].getId() +"_" + getId(), key=""; 
      if(table.get(key1) != null) 
      { 
       key = key1; 
       if(table.get(key) <= getsRange()) 
        getNeighbours().add(objects[i]); 
      } 
      if(table.get(key2) != null) 
      { 
       key = key2; 
       if(table.get(key) <= getsRange()) 
        getNeighbours().add(objects[i]); 
      } 
     } 
    } 

    /** 
    * Check whether a given Object is the neighbour ArrayList of this object 
    * */ 
    public boolean isInNeighbours(MyObject n) 
    { 
     if(neighbours.equals(null)) { return false; } 
     for(int i=0; i<getNeighbours().size(); i++) 
      if(getNeighbours().get(i).getId().equals(n.getId())) { return true; } 
     return false; 
    } 

    /** 
    * Check whether a given Object is the noneighbour ArrayList of this object 
    * */ 
    public boolean isInNonNeighbours(MyObject n) 
    { 
     if(nonNeighbours.equals(null)) { return false; } 
     for(int i=0; i<getNonNeighbours().size(); i++) 
      if(getNonNeighbours().get(i).getId().equals(n.getId())) { return true; } 
     return false; 
    } 


    /** 
    * Check if given MyObject Can be a neighbour to this Object - for rand coord generation 
    * */ 
    public boolean canBeANeighbour(MyObject n) 
    { 
     return distanceTo(n) <= sRange; 
    } 

    // return Euclidean distance between this and p 
    public double distanceTo(MyObject p) { 
     double dx = this.xCoor - p.xCoor; 
     double dy = this.yCoor - p.yCoor; 
     return Math.sqrt(dx*dx + dy*dy); 
    } 

    //Setters And Getters 
    public ArrayList<MyObject> getNeighbours(){ return neighbours; } 

    public void setNeighbours(ArrayList<MyObject> neighbours) 
    { 
     this.neighbours = neighbours; 
    } 
    public double getFov() 
    { 
     return fov; 
    } 
    public void setFov(double fov) 
    { 
     this.fov = fov; 
    } 
    public double getsRange() 
    { 
     return sRange; 
    } 
    public void setsRange(double sRange) 
    { 
     this.sRange = sRange; 
    } 
    public double getxCoor() 
    { 
     return xCoor; 
    } 
    public void setxCoor(double xCoor) 
    { 
     this.xCoor = xCoor; 
    } 
    public double getyCoor() 
    { 
     return yCoor; 
    } 
    public void setyCoor(double yCoor) 
    { 
     this.yCoor = yCoor; 
    } 
    public boolean isClustered() 
    { 
     return isClustered; 
    } 
    public void setClustered(boolean isClustered) 
    { 
     this.isClustered = isClustered; 
    } 
    public String getId() 
    { 
     return id; 
    } 
    public void setId(String id) 
    { 
     this.id = id; 
    } 

    public ArrayList<MyObject> getNonNeighbours() 
    { 
     return nonNeighbours; 
    } 

    public void setNonNeighbours(ArrayList<MyObject> nonNeighbours) 
    { 
     this.nonNeighbours = nonNeighbours; 
    } 
} 

//样品测试：

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.Random; 

public class SampleField 
{ 
    Random rand = new Random(); 
    public int range = 100; 
    HashMap<String, Integer> table = new HashMap<String, Integer>(); 
    String[] nodeIds = {"A", "B", "C", "D", "E", "F"}; 
    public MyObject[] objects = new MyObject[nodeIds.length]; 

    public static void main(String[] args) 
    { 
     SampleField test = new SampleField(); 
     for(MyObject n: test.objects) 
     { 
      n.findNeighbours(test.table, test.objects); 
     } 
     test.populateNonNeighbours(test.objects); 
     System.out.println(test.table); 
     test.printRelationsTable( test.objects); 
     test.assignInitialCoords(test.objects); 
     System.out.println(test.table); 
     test.printRelationsTable( test.objects); 
    } 

    public SampleField() 
    { 
     initialiseNodes(); 
     generateTestTable(objects); 
    } 

    /** 
    * biggest problem 
    * */ 
    public void assignInitialCoords(MyObject[] objects) 
    { 
     objects[0].setxCoor(rand.nextInt(1000)); 
     objects[0].setyCoor(rand.nextInt(1000)); 

     for(int i=0; i<objects.length; i++) 
     { 
      ArrayList<MyObject> neighs = objects[i].getNeighbours(); 
      System.out.println("Assigning " + objects[i].getId() + "'s coors"); 
      setNonNeighborCoords(objects, i); 
      setNeighborCoordinates(objects, i, neighs); 
      System.out.println(objects[i].getId() + "(" + objects[i].getxCoor() + ", " + objects[i].getyCoor() + ")\n"); 
     } 
    } 

    /** 
    * if this object has neighbours, try to set their coordinates so that they do not conflict 
    * 
    * @param objects 
    * @param i 
    * @param neighs 
    */ 
    private void setNeighborCoordinates(MyObject[] objects, int i, ArrayList<MyObject> neighs) 
    { 
     //it should have at least one neighbour 
     if(neighs != null) 
      for(int j=0; j<neighs.size(); j++) 
      { 
       //Initial assignment to the first neighbor 
       neighs.get(j).setxCoor(rand.nextInt() + objects[i].getsRange()); 
       neighs.get(j).setyCoor(rand.nextInt() + objects[i].getsRange()); 
       //If not a neighbor keep generating coordinates until it keeps being a neighbor. 
       while(!objects[i].canBeANeighbour(neighs.get(j)) ) 
       { 
        //go deeper? - later 
        neighs.get(j).setxCoor(rand.nextInt(1000) - shootRange() - 5); 
        neighs.get(j).setyCoor(rand.nextInt(1000) - shootRange() - 5); 
       }        
      } 
    } 

    /** 
    * try to set the coordinates of each object here 
    * @param objects 
    * @param i 
    */ 
    private void setNonNeighborCoords(MyObject[] objects, int i) 
    { 
     for(MyObject n : objects[i].getNonNeighbours()) 
     { 
      n.setxCoor(rand.nextInt() + shootRange() - 5); 
      n.setyCoor(rand.nextInt() + shootRange() - 5); 
       //Make sure non neighbors remain non neighbors 
       while(objects[i].canBeANeighbour(n)) 
       { 
        n.setxCoor(rand.nextInt() + shootRange() - 5); 
        n.setyCoor(rand.nextInt() + shootRange() - 5); 
       } 

     } 
    } 

    /* populate nonNeighbours */ 
    public void populateNonNeighbours(MyObject[] objects) 
    { 
     for(int i=0; i<objects.length; i++) 
     { 
      for(int j=0; j<objects.length; j++) 
      { 
       if((objects[i].getId() != objects[j].getId()) && !objects[i].isInNeighbours(objects[j])) 
       { 
        objects[i].getNonNeighbours().add(objects[j]); 
       } 
      } 
     } 
    } 
    /* Show each object and its neighbors/nonneighbors - just for output */ 
    public void printRelationsTable(MyObject[] objects) 
    { 
     for(int i=0; i<objects.length; i++) 
     { 
      System.out.print("MyObject " + objects[i].getId() + "'s neighbours: "); 
      for(int j=0; j<objects[i].getNeighbours().size(); j++) 
      { 
       System.out.print(objects[i].getNeighbours().get(j).getId() + " "); 
      } 
      System.out.println(); 

      System.out.print("\t\t" +objects[i].getId()+ "' : "); 
      for(int j=0; j<objects[i].getNonNeighbours().size(); j++) 
      { 
       System.out.print(objects[i].getNonNeighbours().get(j).getId() + " "); 
      } 
      System.out.println(); 
     } 
    } 
    /* Initialise Objects here - give basic information */ 
    public void initialiseNodes() 
    { 
     for(int i=0; i<nodeIds.length; i++) 
     { 
      MyObject n = new MyObject(); 
      n.setId(nodeIds[i]); 
      n.setsRange(shootRange()); 
      objects[i] = n; 
     } 
    } 

    /* Generate a list of neighbors for testing */ 
    public void generateTestTable(MyObject[] objects) 
    { 
     for(int i=0; i<objects.length; i++) 
     { 
      /* Get two objects' ids and make them neighbors - ids must be unique */ 
      String firstId = objects[rand.nextInt(objects.length)].getId(); 
      String secondId = objects[rand.nextInt(objects.length)].getId(); 
      while(firstId.equals(secondId) || table.containsKey(firstId + "_" + secondId) || table.containsKey(secondId + "_" + firstId)) 
      { 
       firstId = objects[rand.nextInt(objects.length)].getId(); 
       secondId = objects[rand.nextInt(objects.length)].getId(); 
      } 
      table.put(firstId + "_" + secondId, shootRange()); 
     } 
    } 

    /* Range within which they are neighbors */ 
    public int shootRange() 
    { 
     return range; 
    } 

    public void setRange(int range) 
    { 
     this.range = range; 
    } 
} 

Answer 1

如果你想比较的距离（如果你正在谈论的邻居，似乎这样），那么你根本不需要数数。取而代之的

range = sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)) 
if (range >d)... 

使用

sqrange(a,b) = sqr(a.x-b.x)+sqr(a.y-b.y) 
if (range> d_sqr) ... 

这意味着，你不使用的范围，但它们的平方。这加快了比较约50倍（双倍）。所以，你可以使用更简单的结构。