Skocz do zawartości

[Java] AStar.


Toster

Polecane posty

Jakoś tak wyszło że musiałem sobie sportować Szukacza drogi z RuneSingera na Jave. Jakby ktoś szukał gotowej implementacji to nie krępować się:

 

/*
* AStar.java
* Date: 2011-09-21 10:10:45
* Author: Bartłomiej Żarnowski
*
*/
package pl.thetosters.generalzorg.pathfinder.astar;
import java.awt.Point;
import java.util.ArrayList;
/**
* @author Bartłomiej Żarnowski
* @version 1.0.0
*/
public class AStar {
WayNode oList, cList, fList;
SearchableMap theMap;

public AStar(SearchableMap map){
 theMap = map;
 WayNode tt;
 //tyle nodow do szukania drogi na maxa
 fList = new WayNode();
 tt = fList;
 for(int t = 1; t < 1000; t++){
  tt.next = new WayNode();
  tt = tt.next;
 }
}

public ArrayList<Point> findWay(int sx, int sy, int ex, int ey){
 cleanUp(oList);
 cleanUp(cList);
 WayNode temp, t, t2, tt;
 int cy;
 oList.uid = -1;
 cList.uid = -1;
 temp = fList;
 fList = fList.next;
 temp.x = sx;
 temp.y = sy;
 temp.uid = (sx << 16) | sy;
 temp.next = null;
 oList.next = temp;
 do{
  //bierzemy pierwszy z gory
  if (oList.next == null) {
break;
  }
  cy = 1000000;
  t = oList.next;
  tt = oList;
  t2 = tt;
  do{
if (t.cost < cy) {
cy = t.cost;
temp = t;
t2 = tt;
}
tt = t;
t = t.next;
  } while (t != null);
  t2.next = temp.next;
  temp.next = cList.next;
  cList.next = temp;
  //dokonujemy analizy elementow przyleglych
  AnalyzePosition(temp,-1,-1,ex,ey);
  AnalyzePosition(temp, 0,-1,ex,ey);
  AnalyzePosition(temp, 1,-1,ex,ey);
  AnalyzePosition(temp, 1, 0,ex,ey);
  AnalyzePosition(temp, 1, 1,ex,ey);
  AnalyzePosition(temp, 0, 1,ex,ey);
  AnalyzePosition(temp,-1, 1,ex,ey);
  AnalyzePosition(temp,-1, 0,ex,ey);
 } while (((temp.x == ex) && (temp.y == ey)) == false);
 //szukanie od tylca
 ArrayList<Point> arr = new ArrayList<Point>();
 cy = 0;
 arr.add( new Point(temp.x, temp.y) );
 do{
  temp = temp.parent;
  arr.add( new Point(temp.x, temp.y) );
 }while ( ( (temp.x == sx) && (temp.y == sy) ) == false);

 return arr;
}

/**
* @param temp
* @param i
* @param j
* @param ex
* @param ey
*/
private void AnalyzePosition(WayNode node, int dx, int dy, int endx, int endy) {
 WayNode temp;
 int cx, cy, t;
 cx = node.x + dx;
 cy = node.y + dy;
 if ( (cx <0) || (cy < 0) || (cx >= theMap.Width()) ||
 	(cy >= theMap.Height()) ) {
  return;
 }
 if ( theMap.isObstacle(cx,cy) == true) {
  return;
 }
 //sprawdzamy czy nie mamy takiego noda w ktorejs z list ?
 t = (cx << 16) | cy;
 // <>false jest szybsze niz =true
 if ((onList(oList,t) != false) || (onList(cList,t) != false)) {
  return;
 }
 //   temp := TWayNode.Create(cx, cy);
 //pobieramy z freeList zamiast tworzyc
 temp = fList;
 fList = fList.next;
 temp.x = cx;
 temp.y = cy;
 temp.uid = t;
 temp.parent = node;
 cx -= endx;
 if (cx < 0) {
  cx = -cx;
 }
 cy -= endy;
 if (cy < 0) {
  cy = -cy;
 }
 temp.cost = (cx+cy) << 4;	//heuristic
 temp.next = oList.next;
 oList.next = temp;    
}
/**
* @param oList2
* @param t
* @return
*/
private boolean onList(WayNode list, int i) {
WayNode t;
t = list;
do {
 	if (t.uid == i) {
  	return true;
 	}
 	t = t.next;
} while ( t != null);
return false;
}
private void cleanUp(WayNode list){
 WayNode t, t2;
 if (list.next == null){
  return;
 }
 t = list.next;
 do {
  t2 = t.next;
  t.next = fList.next;
  fList.next = t;

  t = t2;
 } while (t != null);
}

}

 

/*
* SearchableMap.java
* Date: 2011-09-21 10:19:12
* Author: Bartłomiej Żarnowski
*
*/
package pl.thetosters.generalzorg.pathfinder.astar;
/**
* TODO: Opis
* @author Bartłomiej Żarnowski
* @version 1.0.0
*/
public interface SearchableMap {
/**
* @return
*/
int Height();
/**
* @return
*/
int Width();
/**
* @param cx
* @param cy
* @return
*/
boolean isObstacle(int cx, int cy);
}

/*
* Node.java
* Date: 2011-09-21 10:17:28
* Author: Bartłomiej Żarnowski
*
*/
package pl.thetosters.generalzorg.pathfinder.astar;
/**
* @author Bartłomiej Żarnowski
* @version 1.0.0
*/
public class WayNode {
public WayNode parent;
public WayNode next;
public int cost;
public int x, y;
public int uid;
}

Always Dark<br />u1_tt_logo.png banner-1.pngexFabula-banner.pngson_banner_ubersmall.jpg

Link do komentarza
Udostępnij na innych stronach

Zarchiwizowany

Ten temat jest archiwizowany i nie można dodawać nowych odpowiedzi.

×
×
  • Utwórz nowe...