生成与邻居有关的对象坐标
我正在制作一个游戏，其中我有随机生成的物体。我还有一个表格，其中包含哪些对象彼此接近的数据，比如在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;
}
}
回答：
如果你想比较的距离（如果你正在谈论的邻居，似乎这样），那么你根本不需要数数。取而代之的
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倍（双倍）。所以，你可以使用更简单的结构。
以上是 生成与邻居有关的对象坐标 的全部内容， 来源链接： utcz.com/qa/263350.html
