我使用算法 a start 来寻找带有数组节点的路径。我有这样的图像映射和节点:
红色节点是障碍物，黑色用于寻找路径。我不知道为什么这条路是弯的。我使用了这个库 https://code.google.com/p/a-star-java/source/browse/AStar/src/aStar/?r=7我被更改为函数 registerEdges.:
private void registerEdges(ArrayList<Node> nodes)
{
float currentDistX = 0;
float currentDistY = 0;
float distance = 0;
for(int l = 0 ; l < nodes.size(); l++)
{
MINDISTN = Integer.MIN_VALUE;
MINDISTS = Integer.MAX_VALUE;
MINDISTE = Integer.MIN_VALUE;
MINDISTW = Integer.MAX_VALUE;
MINDISTNE = Integer.MAX_VALUE;
MINDISTNW = Integer.MAX_VALUE;
MINDISTSE = Integer.MAX_VALUE;
MINDISTSW = Integer.MAX_VALUE;
Node node = null;
currentDistX = 0;
currentDistY = 0;
//System.out.println("current " + node.x + " " + node.y);
for(int j = 0 ; j < map.size() ; j++)
{
if(l != j)
{
node = map.get(l);
currentDistX = map.get(j).x - node.x;
currentDistY = map.get(j).y - node.y;
if(currentDistX == 0)
{
if(currentDistY < 0)
{
if(currentDistY > MINDISTN)
{
MINDISTN = currentDistY;
node.setNorth(map.get(j));
//System.out.println(currentDist + " n " + map.get(j).x + " " + map.get(j).y);
}
}
else if(currentDistY > 0)
{
if(currentDistY < MINDISTS)
{
//System.out.println(currentDist + " south " + map.get(j).x + " " + map.get(j).y);
MINDISTS = currentDistY;
node.setSouth(map.get(j));
}
}
}
if(currentDistY == 0)
{
if(currentDistX < 0)
{
if(currentDistX > MINDISTE)
{
MINDISTE = currentDistX;
node.setEast(map.get(j));
//System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
}
}
else if(currentDistX > 0)
{
//System.out.print("m " + MINDISTRIGHT);
if(currentDistX < MINDISTW)
{
MINDISTW = currentDistX;
node.setWest(map.get(j));
//System.out.println(currentDist + " w " + map.get(j).x + " " + map.get(j).y);
}
}
}
if(currentDistY != 0 && currentDistX != 0)
{
if(currentDistX > 0 && currentDistY > 0)
{
distance = node.calculateDistanceBetweenNods(map.get(j));
if(distance < MINDISTNE)
{
MINDISTNE = distance;
node.setNorthEast(map.get(j));
//System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
}
}
else if(currentDistX < 0 && currentDistY > 0)
{
distance = node.calculateDistanceBetweenNods(map.get(j));
if(distance < MINDISTNW)
{
MINDISTNW = distance;
node.setNorthWest(map.get(j));
//System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
}
}
else if(currentDistX <= 0 && currentDistY <= 0)
{
distance = node.calculateDistanceBetweenNods(map.get(j));
if(distance < MINDISTSW)
{
MINDISTSW = distance;
node.setSouthWest(map.get(j));
//System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
}
}
else if(currentDistX > 0 && currentDistY < 0)
{
distance = node.calculateDistanceBetweenNods(map.get(j));
if(distance < MINDISTSE)
{
MINDISTSE = distance;
node.setSouthEast(map.get(j));
//System.out.println(currentDist + " e " + map.get(j).x + " " + map.get(j).y);
}
}
}
}
}
}
此函数查找 North,South,West,East,N-East... 邻居节点。
估计路径:
public float getEstimatedDistanceToGoal(float startX, float startY, float goalX, float goalY) {
float dx = goalX - startX;
float dy = goalY - startY;
//float result = (float) (Math.sqrt((dx*dx)+(dy*dy)));
//Optimization! Changed to distance^2 distance: (but looks more "ugly")
float result = (float) (dx*dx)+(dy*dy);
return (float) Math.sqrt(result);
}
当前节点与邻居节点的连接不良。
示例:
一些节点具有单向连接(上图)。
节点2有邻居节点1，节点1没有邻居节点2。
最佳答案
您在答案中粘贴的代码对于二维路径搜索来说似乎有点复杂。
如果我理解你的话，你打算在一个8连通的网格中搜索图像中的最短路径，并且你正在尝试使用A*来解决这个问题。我建议您使用搜索库，它可以更清楚地组织搜索算法的不同组件。
在基础上，如果您有 A* 的实现，您只需定义:
- 成本函数(根据您的问题描述，可能是点之间的欧氏距离)。
- 一个转换函数(给定一个
Point检索 8 个邻居，过滤那些由于 map 图像中的障碍物而无法访问的邻居)。 - 您已在
getEstimatedDistanceToGoal中实现的启发式函数。
您可以查看 Hipster library ，除了具有更清晰的结构外，还具有以动态方式生成图形节点的好处。这允许您节省大量内存，因为您先验生成的大多数节点不会用于搜索过程。
Here您可以找到使用迷宫进行二维搜索的代码示例。您唯一需要根据您的情况调整示例的是实现 TransitionFunction 以使用您的 map 图像。该示例使用以下代码生成给定当前节点的邻居节点(函数 Maze2D.validLocationsFrom(Point)):
public Collection<Point> validLocationsFrom(Point loc) {
Collection<Point> validMoves = new HashSet<Point>();
// Check for all valid movements
for (int row = -1; row <= 1; row++) {
for (int column = -1; column <= 1; column++) {
try {
//
//TODO: Implement isFree(Point) to check in your map image
//if a node is occupied or not.
//
if (isFree(new Point(loc.x + column, loc.y + row))) {
validMoves.add(new Point(loc.x + column, loc.y + row));
}
} catch (ArrayIndexOutOfBoundsException ex) {
// Invalid move!
}
}
}
validMoves.remove(loc);
return validMoves;
}
在示例中，函数 isFree(Point) 查询迷宫以了解节点是否被占用。您只需要填写此功能即可查询您的 map 图像而不是迷宫，仅此而已!
希望我的回答对您有所帮助，
关于java - 带图像映射的星算法(android)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25120786/