アルゴリズム

JavaでのA *（スター）パス検索の実装、最短パス検索アルゴリズム



Path Finding Implementation Java



私の知る限り、現在、A *とダイクストラ（SPアルゴリズム）という2つの一般的な経路探索方法があります。
ダイクストラアルゴリズム：
[img] http://www.java2000.net/redirectImage.jsp?id=669 [/ img]
氏によって発明されました。エドガー・ダイクストラ（故人）
ダイクストラアルゴリズムは、1つのノードから他のすべてのノードへの最短経路を計算するための典型的な最短経路アルゴリズムです。主な特徴は、始点が終点まで伸びるまで、外層の中心にあることです。ダイクストラアルゴリズムは最短経路の最適解を導き出すことができますが、計算の多くのノードを通過するため非効率的です。ダイクストラアルゴリズムは、各頂点nについて、これまでに見つかったmからnへの最短経路を保持することによって機能する段階的な検索アルゴリズムです。

検索プロセス：
m番目のステップで最短パスが見つかり、パス上のソースノードに最も近いノードがn個ある場合、それらはm + 1番目のステップでノードセットNと見なされ、距離ソースノードはNに属していません。検索されます。最も近いノードであり、検索されたノードがNに参加すると、宛先ノードに到達するまで検索が続行されます。Nのノードのセットは、送信元ノードから宛先ノードへの最短パスです。

アルゴリズムの説明：

ダイクストラアルゴリズムは、頂点vごとにこれまでに見つかったsからvまでの最短経路を維持することによって機能します。最初に、ソースポイントsの経路長値に0（d [s] = 0）が割り当てられ、すべての経路長が他の頂点は無限大に設定されます。これは、これらの頂点へのパスがわからないことを意味します（Vの場合、sを除くすべての頂点vはd [v] =∞です）。アルゴリズムが終了すると、d [v]はsからvまでの最短パス、またはパスが存在しない場合は無限大を格納します。ダイクストラアルゴリズムの基本的な操作は、エッジの拡張です。uからvへのエッジがある場合、sからuへの最短パスは、エッジ（u、v）をに追加することにより、sからvへのパスを拡張できます。尾。このパスの長さはd + w（u、v）です。この値が現在知られているd [v]の値よりも小さい場合は、現在のd [v]の値を新しい値に置き換えることができます。拡張エッジの操作は、すべてのd [v]がsからvへの最短パスのコストを表すまで実行されます。このアルゴリズムは、dが最終値に達したときに、エッジ（u、v）が1回だけ拡張されないように構成されています。 。アルゴリズムは頂点SとQの2つのセットを維持します。セットSは、最短経路の値の頂点であることがわかっているすべてのd [v]値を保持しますが、セットQは他のすべての頂点を保持します。セットSの初期状態は空であり、各ステップにはQからSに移動する頂点があります。この選択された頂点は、最小のd値を持つQの頂点です。頂点uがQからSに転送されると、アルゴリズムは各外接エッジ（u、v）を拡張します。

A *（スター）アルゴリズム：
[img] http://www.java2000.net/redirectImage.jsp?id=670 [/ img]
A *（A-Star）アルゴリズムは、静的な道路網の最短経路を解決するための最も効果的な方法です。
式は次のように表されます。f（n）= g（n）+ h（n）、ここでf（n）は、初期点から目標点までのノードnの評価関数であり、g（n）は初期ノードからターゲットノードまでの状態空間nノードの実際のコストh（n）は、nからターゲットノードまでの最適なパスの推定コストです。

検索プロセス：

2つのテーブルを作成します。OPENテーブルには生成されたが検査されていないすべてのノードが保持され、CLOSEDテーブルにはアクセスされたノードが記録されます。現在のノードのノードをトラバースし、nノードをCLOSEに配置し、nノードの子ノードXを取得して、Xの評価値を計算します。

While（OPEN！= NULL）
{{
評価値fが最小のノードnをOPENテーブルから取得します。
If（n node == target node）break
そうしないと
{{
If（X in OPEN）2つのXの評価値を比較しますf //同じノードの2つの異なるパスの評価に注意してください
If（Xの評価がOPENテーブルの評価よりも小さい）
OPENテーブルの評価値を更新します//最小パスの評価値を取得します
If（X in CLOSE）は2つのXの評価値を比較します//同じノードの2つの異なるパスの評価値に注意してください
If（Xの評価がCLOSEテーブルの評価よりも小さい）
CLOSEテーブルの評価値を更新してXノードをOPENにします//最小パスの評価値を取得します
if（Xは両方にない）
Xの評価を見つける
そしてXをOPENテーブルに挿入します//まだソートされていません
}
nノードをCLOSEテーブルに挿入します
OPENテーブルのノードは推定値に従ってソートされます//実際にはOPENテーブルのノードfのサイズを比較し、最小パスのノードから下に進みます。
}


実際のアプリケーションに関する限り、A *アルゴリズムとDijistraアルゴリズムの最大の違いは、評価値があるかどうかです。本質的に、Dijistraアルゴリズムは、A *アルゴリズムの評価値が0の場合と同等です。そこで今回は、Javaの実装にA *アルゴリズムを選択しました。

理論的な数学的概念は別として、通常のA *アルゴリズムには2つのステップしかありません。 1つは、移動の次の位置がターゲットに最も近いことを確認するためのパス評価です。評価の結果が正確であるほど、経路探索の効率が高くなります。 。 2つ目はパスクエリです。これも評価結果に反応し、新しい位置から再評価して、実行可能なパスを通過するように道路を行き場のない場所に誘導します。

A *アルゴリズムのプログラム実装では、基本的に、開始点、終了点、およびマップ情報の3つの点だけを気にする必要があります。これらの3つの基本データを使用して、どのような場合でもA *実装を構築できます。

以下に、A * Java静的ルーティングアルゴリズムの実装を示します。ロジックは、コードコメントを参照してください。

効果は次のとおりです（1、1から10、13）。
[img] http://www.java2000.net/redirectImage.jsp?id=671 [/ img]
（小さな家のドアの真ん中にある1,1から7,9）
[img] http://www.java2000.net/redirectImage.jsp?id=672 [/ img]
（小さな家の中の1,1から6,7）
[img] http://www.java2000.net/redirectImage.jsp?id=673 [/ img]

Node.java

package test.star
import java.awt.Point
import java.util.LinkedList
/** */
/**
*


* Title: LoonFramework
*


*


* Description: describes the path node class
*




*


* Copyright: Copyright (c) 2008
*


*


* Company: LoonFramework
*




*


* License: http://www.apache.org/licenses/LICENSE-2.0
*


*
* @author chenpeng
* @email：root@xxxxx
* @version 0.1
*/
public class Node implements Comparable {
// coordinates
public Point _pos
// starting point value
public int _costFromStart
// target location value
public int _costToObject
// parent node
public Node _parentNode
private Node() {
}
/** */
/**
* Initialize Node by injecting coordinate points
*
* @param _pos
*/
public Node(Point _pos) {
this._pos = _pos
}
/** */
/**
* Return path cost
*
* @param node
* @return
*/
public int getCost(Node node) {
// Get the difference between the coordinate points. Formula: (x1, y1)-(x2, y2)
int m = node._pos.x - _pos.x
int n = node._pos.y - _pos.y
// Take the Euclidean distance (straight line distance) between the two nodes as the estimated value to obtain the cost
return (int) Math.sqrt(m * m + n * n)
}
/** */
/**
* Check if the node object is consistent with the verification object
*/
public boolean equals(Object node) {
/ / Verify the coordinates as the basis for judgment
if (_pos.x == ((Node) node)._pos.x && _pos.y == ((Node) node)._pos.y) {
return true
}
return false
}
/** */
/**
* Compare two points to get the lowest cost object
*/
public int compareTo(Object node) {
int a1 = _costFromStart + _costToObject
int a2 = ((Node) node)._costFromStart + ((Node) node)._costToObject
if (a1 return -1
} else if (a1 == a2) {
return 0
} else {
return 1
}
}
/** */
/**
* Get the movement limit area between the top, bottom, left and right points
*
* @return
*/
public LinkedList getLimit() {
LinkedList limit = new LinkedList()
int x = _pos.x
int y = _pos.y
// Move the area between the top, bottom, left and right points (for squint maps, you can turn on the offset of the annotation, and 8 orientations will be evaluated at this time)
// on
limit.add(new Node(new Point(x, y - 1)))
// upper right
// limit.add(new Node(new Point(x+1, y-1)))
// right
limit.add(new Node(new Point(x + 1, y)))
// lower right
// limit.add(new Node(new Point(x+1, y+1)))
// under
limit.add(new Node(new Point(x, y + 1)))
// lower left
// limit.add(new Node(new Point(x-1, y+1)))
// left
limit.add(new Node(new Point(x - 1, y)))
// top left
// limit.add(new Node(new Point(x-1, y-1)))
return limit
}
}PathFinder.java

package test.star
import java.awt.Point
import java.util.LinkedList
import java.util.List
/** */
/**
*


* Title: LoonFramework
*


*


* Description: A* path-finding class (this class is for demonstration purposes, does not mean that the algorithm is the best implementation)
*




*


* Copyright: Copyright (c) 2008
*


*


* Company: LoonFramework
*


*


* License: http://www.apache.org/licenses/LICENSE-2.0
*


*
* @author chenpeng
* @email：root@xxxxx
* @version 0.1
*/
public class PathFinder {
// path priority list (internal method in this example)
private LevelList _levelList
// List of completed paths
private LinkedList _closedList
// map description
private int[][] _map
// walking area restrictions
private int[] _limit
/** */
/**
* Initialize this class with a 2-dimensional array of injected maps and a restriction point description
*
* @param _map
*/
public PathFinder(int[][] map, int[] limit) {
_map = map
_limit = limit
_levelList = new LevelList()
_closedList = new LinkedList()
}
/** */
/**
* A* way path finding, injecting start coordinates and target coordinates, returning a list of feasible paths
*
* @param startPos
* @param objectPos
* @return
*/
public List searchPath(Point startPos, Point objectPos) {
/ / Initialize the starting node and the target node
Node startNode = new Node(startPos)
Node objectNode = new Node(objectPos)
/ / Set the starting node parameters
startNode._costFromStart = 0
startNode._costToObject = startNode.getCost(objectNode)
startNode._parentNode = null
/ / Add the operation level sequence
_levelList.add(startNode)
// When there is data in the operation level sequence, the loop is routed until the levelList is empty.
while (!_levelList.isEmpty()) {
// remove and delete the original element
Node firstNode = (Node) _levelList.removeFirst()
/ / Determine whether the coordinates of the target node are equal
if (firstNode.equals(objectNode)) {
// Yes, you can build the entire walking route map, and the calculation is completed.
return makePath(firstNode)
} else {
// Otherwise
// Join the verified list
_closedList.add(firstNode)
/ / Get the mobile area of ​​firstNode
LinkedList _limit = firstNode.getLimit()
// traverse
for (int i = 0 i <_limit.size() i++) {
// Get neighbors
Node neighborNode = (Node) _limit.get(i)
// Get a rating condition
boolean isOpen = _levelList.contains(neighborNode)
// get if you have walked
boolean isClosed = _closedList.contains(neighborNode)
/ / Determine whether it is impossible to pass
boolean isHit = isHit(neighborNode._pos.x, neighborNode._pos.y)
// When three are judged to be non-
if (!isOpen && !isClosed && !isHit) {
/ / Set costFromStart
neighborNode._costFromStart = firstNode._costFromStart + 1
/ / Set costToObject
neighborNode._costToObject = neighborNode.getCost(objectNode)
/ / Change the neighborNode parent node
neighborNode._parentNode = firstNode
// join level
_levelList.add(neighborNode)
}
}
}
}
// clear the data
_levelList.clear()
_closedList.clear()
// will return null when while cannot run
return null
}
/** */
/**
* Determine if it is a passable area
*
* @param x
* @param y
* @return
*/
private boolean isHit(int x, int y) {
for (int i = 0 i <_limit.length i++) {
if (_map[y][x] == _limit[i]) {
return true
}
}
return false
}
/** */
/**
* Make walking path through Node
*
* @param node
* @return
*/
private LinkedList makePath(Node node) {
LinkedList path = new LinkedList()
// When the superior node exists
while (node._parentNode != null) {
// add at the first element
path.addFirst(node)
// Assign node to parent node
node = node._parentNode
}
// add at the first element
path.addFirst(node)
return path
}
private class LevelList extends LinkedList {
/** */
/**
*
*/
private static final long serialVersionUID = 1L
/** */
/**
* Add a node
*
* @param node
*/
public void add(Node node) {
for (int i = 0 i if (node.compareTo(get(i)) <= 0) {
add(i, node)
return
}
}
addLast(node)
}
}
}TestMap.java

package test.star
import java.awt.Graphics
import java.awt.Image
import java.io.File
import java.io.IOException
/** */
/**
*


* Title: LoonFramework
*


*


* Description: A simple map implementation
*


*


* Copyright: Copyright (c) 2008
*


*


* Company: LoonFramework
*


*


* License: http://www.apache.org/licenses/LICENSE-2.0
*


*
* @author chenpeng
* @email：root@xxxxx
* @version 0.1
*/
public class TestMap {
final static private int CS = 32
// map description
final static public int[][] MAP = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }
// Unable to move area
final static public int[] HIT = { 1 }
/ / Set the default number of background squares
final static private int ROW = 15
/ / Set the default number of background squares
final static private int COL = 15
private Image floorImage
private Image wallImage
public TestMap() {
try {
floorImage = javax.imageio.ImageIO.read(new File('floor.gif'))
wallImage = javax.imageio.ImageIO.read(new File('wall.gif'))
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace()
}
}
public void draw(Graphics g) {
for (int i = 0 i for (int j = 0 j switch (MAP[i][j]) {
case 0:
g.drawImage(floorImage, j * CS, i * CS, null)
break
case 1:
g.drawImage(wallImage, j * CS, i * CS, null)
break
}
}
}
}
}Main.java

package test.star
import java.awt.Color
import java.awt.Frame
import java.awt.Graphics
import java.awt.Image
import java.awt.Panel
import java.awt.Point
import java.awt.event.WindowAdapter
import java.awt.event.WindowEvent
import java.awt.image.BufferedImage
import java.util.List
/** */
/**
*


* Title: LoonFramework
*


*


* Description: Java's A* pathfinding implementation
*


*


* Copyright: Copyright (c) 2008
*


*


* Company: LoonFramework
*


*


* License: http://www.apache.org/licenses/LICENSE-2.0
*


*
* @author chenpeng
* @email：root@xxxxx
* @version 0.1
*/
public class Main extends Panel {
/** */
/**
*
*/
final static private long serialVersionUID = 1L
final static private int WIDTH = 480
final static private int HEIGHT = 480
final static private int CS = 32
private TestMap map
private PathFinder astar
// starting coordinates 1,1
private static Point START_POS = new Point(1, 1)
// destination coordinates 10, 13
private static Point OBJECT_POS = new Point(8, 6)
private Image screen
private Graphics graphics
private List path
public Main() {
setSize(WIDTH, HEIGHT)
setFocusable(true)
screen = new BufferedImage(WIDTH, HEIGHT, BufferedImage.TYPE_INT_RGB)
graphics = screen.getGraphics()
map = new TestMap()
// Inject map description and obstacle description
astar = new PathFinder(TestMap.MAP, TestMap.HIT)
// searchPath will get the List collection of the coordinates of the moving path between two points
/ / In the actual application, use Thread to step through the coordinates of the List to achieve automatic walking
path = astar.searchPath(START_POS, OBJECT_POS)
}
public void update(Graphics g) {
paint(g)
}
public void paint(Graphics g) {
// draw a map
map.draw(graphics)
graphics.setColor(Color.RED)
graphics.fillRect(START_POS.x * CS, START_POS.y * CS, CS, CS)
graphics.setColor(Color.BLUE)
graphics.fillRect(OBJECT_POS.x * CS, OBJECT_POS.y * CS, CS, CS)
// draw the path
if (path != null) {
graphics.setColor(Color.YELLOW)
// traverse the coordinates and paint one by one
for (int i = 0 i Node node = (Node) path.get(i)
Point pos = node._pos
// draw the border
graphics.fillRect(pos.x * CS + 7, pos.y * CS + 7, CS - 14, CS - 14)
}
}
g.drawImage(screen, 0, 0, this)
}
public static void main(String[] args) {
Frame frame = new Frame()
frame.setTitle('Java's A* Pathfinding Implementation')
frame.setSize(WIDTH, HEIGHT + 20)
frame.setResizable(false)
frame.setLocationRelativeTo(null)
frame.add(new Main())
frame.setVisible(true)
frame.addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0)
}
})
}
}