之前的AStar算法學習筆記部落格提到了大神的基于AStar算法的RCP布線算法但是大神給的開源碼還有存在可以優化的部分這個部落客要是記錄自己優化的過程

大神源碼連結：RCP：gef智能尋路算法（A star）

我的AStar的算法學習：AStar算法學習筆記

改進與優化

1. 關于終點出現斜線問題

分析：由于坐标是以起始點作為坐标原點的，是以終點極大可能不在有整數坐标的點位上，找不到路徑就會出現斜線直連

解決：大神已經給出了解決的代碼：算法：Astar尋路算法改進

我補充下這段代碼添加的位置：route() 方法最後擷取到路徑并放到最終存儲路徑資訊的points過程中，将最後的幾個點進行處理即：添加points.addPoint(endPoint)之前。當然我更建議将對通過算法獲得的路徑進行額外的處理的部分封裝到獨立的函數中，因為處理終點斜線問題隻是很多中的一個。

private void pathExtraControl(PointList points, Point endPoint)
    {
        // 對于終點沒有在方格上 出現斜線的處理
        int size = points.size();
        if (size < 3)
            return;
        points.removePoint(size - 1);
        Point pointN1 = points.getLastPoint();
        Point pointN2 = points.getPoint(size - 3);

        if (pointN2.x == pointN1.x)
        {
            points.setPoint(new Point(pointN1.x, endPoint.y), size - 2);
        } else if (pointN2.y == pointN1.y)
        {
            points.setPoint(new Point(endPoint.x, pointN1.y), size - 2);
        }
    }

2.部分線可以經過一些圖源

分析：在預讀取為每個點設定難易度時存在問題

源碼自帶了标記openList 和 closeList的方法:test() 我也仿寫方法标記預讀難度的pool池的方法。

PoolHandler類：

public class PoolHandler extends SquareHandle
{
    public ANodeLevel level = ANodeLevel.EASY;

    public void setOwner(GraphicalEditPart editpart)
    {
        super.setOwner(editpart);
    }

    @Override
    protected DragTracker createDragTracker()
    {
        // TODO Auto-generated method stub
        return null;
    }

    public void validate()
    {
        if (isValid())
            return;
        // getLocator().relocate(this);
        // super.validate();
    }

    protected Color getFillColor()
    {
        ANodeLevel localLevel = getLevel();
        Color color = null;
        if (localLevel.equals(ANodeLevel.EASY))
        {
            color = ColorConstants.lightBlue;
        } else if (localLevel.equals(ANodeLevel.NORMAL))
        {
            color = ColorConstants.yellow;
        } else if (localLevel.equals(ANodeLevel.HARD))
        {
            color = ColorConstants.darkBlue;
        } else if (localLevel.equals(ANodeLevel.DEAD))
        {
            color = ColorConstants.black;
        }
        return color;
    }

    public void paintFigure(Graphics g)
    {
        Rectangle r = getBounds();
        r.shrink(1, 1);
        try
        {
            g.setAlpha(130);
            g.setBackgroundColor(getFillColor());
            g.fillRectangle(r.x, r.y, r.width, r.height);
            g.setForegroundColor(getBorderColor());
            g.drawRectangle(r.x, r.y, r.width, r.height);
        } finally
        {
            // We don't really own rect 'r', so fix it.
            r.expand(1, 1);
        }
    }

    public ANodeLevel getLevel()
    {
        return level;
    }
}

調用這個類的方法：調用這個方法的位置于test相同

private void showPool()
    {
        if ((this.style & SHOWPOOL) != SHOWPOOL)
            return;
        Map<Integer, Map<Integer, ANodeLevel>> pool = preReader.getPool();
        LayerManager manager = (LayerManager) editPart.getViewer()
                .getEditPartRegistry().get(LayerManager.ID);
        FreeformLayer layer = (FreeformLayer) manager
                .getLayer(org.eclipse.gef.LayerConstants.HANDLE_LAYER);
        // 移除之前的oldHandlers
        <strong>removeOldHandles(layer, PoolHandler.class);</strong>
        List<ANode> poolList = new ArrayList<ANode>();
        for (Map.Entry<Integer, Map<Integer, ANodeLevel>> entrySet : pool
                .entrySet())
        {
            int x = entrySet.getKey();
            Map<Integer, ANodeLevel> valueMap = entrySet.getValue();
            for (Map.Entry<Integer, ANodeLevel> valueEntry : valueMap
                    .entrySet())
            {
                int y = valueEntry.getKey();
                ANodeLevel level = valueEntry.getValue();
                ANode node = new ANode(x, y);
                node.setLevel(level);
                poolList.add(node);
            }
        }
        for (ANode poolNode : poolList)
        {
            Point p = poolNode.getPoint(preReader.getStartPoint(), D);
            PoolHandler h = new PoolHandler();
            h.level = poolNode.getLevel();
            h.setBounds(<strong>new Rectangle(p.x, p.y, 5, 5)</strong>);
            h.setOwner((GraphicalEditPart) this.editPart);
            layer.add(h);
        }

    }

這個方法裡有兩個改變: 為了更加方面直覺

1.removeOldHandles()方法: 移除特定類型的handle

@SuppressWarnings("unchecked")
    private void removeOldHandles(FreeformLayer layer, Class<?> clazz)
    {
        List<Figure> removeFigures = new ArrayList<Figure>();
        List<Object> layerFigure = layer.getChildren();
        for (Iterator<Object> iterator = layerFigure.iterator(); iterator.hasNext();)
        {
            Object object = (Object) iterator.next();
            if (clazz == TestHandler.class)
            {
                if (object instanceof TestHandler)
                {
                    TestHandler testHandler = (TestHandler) object;
                    removeFigures.add(testHandler);
                }
            } else if (clazz == PoolHandler.class)
            {
                if (object instanceof PoolHandler)
                {
                    PoolHandler poolHandler = (PoolHandler) object;
                    removeFigures.add(poolHandler);
                }
            } else
            {
                // do nothing
            }
        }
        for (Iterator<Figure> iterator = removeFigures.iterator(); iterator.hasNext();)
        {
            Figure object = (Figure) iterator.next();
            layer.remove(object);
        }
    }

2.将handler的大小改為5,5 很小感覺這個更直覺的看到難度設定到了哪些點上黑色的點預讀的pool設定了難度的部分細心的你一定發現了問題

基于AStar算法的RCP布線優化改進與優化

問題的明确描述應該修改為：預讀難度标記錯誤問題

分析：如上圖所示，圖源外面的點應該是可通路的難度：normal 而内部的點應該都是不可通路的難度：hard

代碼分析：這是計算

public static int calculateIndex(int v1, int v2, int distance)
    {
        int offset = (v1 - v2) % distance;
        return offset > 0 ? (v1 - v2) / distance + 1 : offset == 0 ? (v1 - v2)
                / distance : (v1 - v2) / distance - 1;
    }

v1是rectangle的位置 v2是starPoint的位置

當offset>0 時，開始節點在左側（上側）由于/ 會保留結果的整數部分是以+1就可以找到同源中的點

當offset<0 時，開始節點在右側（下側）由于/ 會保留結果的整數部分計算位置時無需進行平移而已有代碼為-1 則會出現上述情況

處理方法：offset

public static int calculateIndex(int v1, int v2, int distance)
    {
        int offset = (v1 - v2) % distance;
        return offset > 0 ? (v1 - v2) / distance + 1 : (v1 - v2) / distance ;
    }

3.删除共線點

原有算法：

判斷條件：通過全等三角形判斷位置：在floyd()中

if (fatherNode.xIndex - currentNode.xIndex == grandNode.xIndex
                    - fatherNode.xIndex
                    && fatherNode.yIndex - currentNode.yIndex == grandNode.yIndex
                            - fatherNode.yIndex)

但由于坐标系的原因都是同間距的點簡單跟一些就知道隻能去除一條直線上的一半的點

更改為：相似判斷則可以删除一條線段兩端之間所有的點

// 删除共線終點 根據相似三角形 x1/y1=x2/y2 根據： x1y2=x2y1 判斷
			// 	     /|
			// 	    / |
			//         /  |
			//        /   |y2
			//       /|   |
			//      / |y1 |
			//     /  |   |
			//    /___|___|
			//     x1
			//    |--x2---|
			if ((fatherNode.xIndex - currentNode.xIndex) * (grandNode.yIndex - currentNode.yIndex) == (grandNode.xIndex - currentNode.xIndex)
					* (fatherNode.yIndex - currentNode.yIndex)) {
				currentNode.setParent(grandNode);
			} else
				currentNode = fatherNode;
		}

基于AStar算法的RCP布線優化改進與優化

改進與優化

1. 關于終點出現斜線問題

2.部分線可以經過一些圖源

3.删除共線點

繼續閱讀

多關鍵字排序筆記

大和整數，大整數加法大整數加法與乘法（高精度算法）

最好、最壞、平均情況時間複雜度

算法題解：整數中1出現的次數（從1到n整數中1出現的次數）題目描述代碼實作解題思路

維納濾波在圖像複原中的應用

吸血鬼數字問題

堆排序（最小堆）C++

Top N 算法

全智通A+常見問題彙總解答—A+内部領料編輯頁面，選擇全部倉庫查詢配件不顯示結果

全智通A+常見問題彙總解答—A+某個銷售單号與其他銷售單号編号規則不一緻

全智通A+常見問題彙總解答—A+經營情況報表頁面的客戶賬收銀情況中的金額有誤

連通分量 | Connected Components | C/C++實作問題描述輸入示例輸出示例講解AC代碼如下

生成格雷碼生成格雷碼

Android查缺補漏之SpannableString

線性規劃網絡流之最短增廣路算法

解壓縮字元串