0
我正在製作一個遊戲，其中我有隨機生成的物體。我還有一個表格，其中包含哪些對象彼此接近的數據，比如在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;
}
}
如果您希望我們給您一個改進算法的建議，請在這裏將您的課程與解釋放在一起。剛纔的代碼是不可讀的。 – Gangnus
@Gangnus我也添加了類。 – gordon