이웃과 관련하여 객체 좌표 생성

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 배 (두 배)의 비교가 빠릅니다. 따라서 훨씬 쉬운 구조를 사용할 수 있습니다.